A lower bound method for quantum circuits

DOI10.1016/J.IPL.2011.05.002MaRDI QIDQ1944121zbMATH OpenOpenAlexFDO

Authors Debajyoti Bera

Publication date 4 April 2013

Published in Information Processing Letters (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.ipl.2011.05.002

zbMATH Keywords

circuit complexity theorycomputational complexitylower boundparity functionquantum circuit

Mathematics Subject Classification ID

Quantum algorithms and complexity in the theory of computing (68Q12) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Quantum computation (81P68)

Recommendations

• Quantum lower bounds for fanout
• Quantum lower bounds by polynomials
• Quantum lower bounds by quantum arguments
• Quantum lower bounds by quantum arguments
• Quantum formulas: A lower bound and simulation

Cites work

• scientific article; zbMATH DE number 1579275 (Why is no real title available?)
• Quantum fan-out is powerful
• Quantum lower bounds for fanout

Cited in

(11)

• Power of uninitialized qubits in shallow quantum circuits
• scientific article; zbMATH DE number 1583875 (Why is no real title available?)
• Reducing the Depth of Quantum Circuits Using Additional Circuit Lines
• scientific article; zbMATH DE number 7228448 (Why is no real title available?)
• Quantum lower bounds for fanout
• Computation at a distance
• Bounds on Threshold Gate Realizability
• Deriving Grover's lower bound from simple physical principles
• Quantum lower bounds by quantum arguments
• Lower bounds for QCDCL via formula gauge
• Bounds on the QAC^0 complexity of approximating parity

This page was built for publication: A lower bound method for quantum circuits

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1944121)