A New Lower Bound Technique for Quantum Circuits without Ancillae
Date
2008-07-22
DOI
Authors
Bera, Debajyoti
Version
OA Version
Citation
Bera, Debajyoti. "A New Lower Bound Technique for Quantum Circuits without Ancillae", Technical Report BUCS-TR-2008-015, Computer Science Department, Boston University, July 22, 2008. [Available from: http://hdl.handle.net/2144/1708]
Abstract
We present a technique to derive depth lower bounds for quantum circuits. The technique is based on the observation that in circuits without ancillae, only a few input states can set all the control qubits of a Toffoli gate to 1. This can be used to selectively remove large Toffoli gates from a quantum circuit while keeping the cumulative error low. We use the technique to give another proof that parity cannot be computed by constant depth quantum circuits without ancillæ.