A lower bound method for quantum circuits

Quantum circuits, which are shallow, limited in the number of gates and additional workspace qubits, are popular for quantum computation because they form the simplest possible model similar to the classical model of a network of Boolean gates and capable of performing non-trivial computation. We give a new lower bound technique for such circuits and use it to give another proof that deterministic computation of the parity function cannot be performed by such circuits.

► Constant depth quantum circuits with no ancillæ using unbounded Toffoli gates and bounded fanin gates. ► Lower bound on the computational limit of such circuits. ► Explicit lower bound for computation of parity.