On Finding Sensitivity of Quantum and Classical Gates


Show simple item record Bera, Debajyoti en_US Homer, Steve en_US 2011-10-20T04:56:37Z 2011-10-20T04:56:37Z 2009-06-05 en_US
dc.identifier.citation Bera, Debajyoti; Homer, Steve. "On Finding Sensitivity of Quantum and Classical Gates", Technical Report BUCS-TR-2009-019, Computer Science Department, Boston University, June 5, 2009. [Available from:] en_US
dc.description.abstract We consider a fault model of Boolean gates, both classical and quantum, where some of the inputs may not be connected to the actual gate hardware. This model is somewhat similar to the stuck-at model which is a very popular model in testing Boolean circuits. We consider the problem of detecting such faults; the detection algorithm can query the faulty gate and its complexity is the number of such queries. This problem is related to determining the sensitivity of Boolean functions. We show how quantum parallelism can be used to detect such faults. Specifically, we show that a quantum algorithm can detect such faults more efficiently than a classical algorithm for a Parity gate and an AND gate. We give explicit constructions of quantum detector algorithms and show lower bounds for classical algorithms. We show that the model for detecting such faults is similar to algebraic decision trees and extend some known results from quantum query complexity to prove some of our results. en_US
dc.language.iso en_US en_US
dc.publisher Boston University Computer Science Department en_US
dc.relation.ispartofseries BUCS Technical Reports;BUCS-TR-2009-019 en_US
dc.title On Finding Sensitivity of Quantum and Classical Gates en_US
dc.type Technical Report en_US

Files in this item

This item appears in the following Collection(s)

Show simple item record

Search OpenBU


Deposit Materials