A lower bound method for quantum circuits

作者：Bera Debajyoti^*

来源：Information Processing Letters, 2011, 111(15): 723-726.

DOI：10.1016/j.ipl.2011.05.002

• Computational complexity
• Quantum circuit
• Circuit complexity theory
• Lower bound
• Parity function

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.

• 出版日期2011-8-15