Show simple item record

dc.contributor.authorBera, Debajyotien_US
dc.contributor.authorHomer, Steveen_US
dc.date.accessioned2011-10-20T04:56:37Z
dc.date.available2011-10-20T04:56:37Z
dc.date.issued2009-06-05en_US
dc.identifier.citationBera, 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: http://hdl.handle.net/2144/1743]en_US
dc.identifier.urihttp://hdl.handle.net/2144/1743
dc.description.abstractWe 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.isoen_USen_US
dc.publisherBoston University Computer Science Departmenten_US
dc.relation.ispartofseriesBUCS Technical Reports;BUCS-TR-2009-019en_US
dc.titleOn Finding Sensitivity of Quantum and Classical Gatesen_US
dc.typeTechnical Reporten_US


Files in this item

This item appears in the following Collection(s)

Show simple item record