Title: On Finding Sensitivity of Quantum and Classical Gates
Authors: Debajyoti Bera and Steve Homer
Date: June 5, 2009
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.