OpenBU

On Finding Sensitivity of Quantum and Classical Gates

OpenBU

Show simple item record

dc.contributor.author Bera, Debajyoti en_US
dc.contributor.author Homer, Steve en_US
dc.date.accessioned 2011-10-20T04:56:37Z
dc.date.available 2011-10-20T04:56:37Z
dc.date.issued 2009-06-05 en_US
dc.identifier.uri http://hdl.handle.net/2144/1743
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


Browse

Deposit Materials

Statistics