Quantum formulas: A lower bound and simulation

DOI10.1137/S0097539700370965MaRDI QIDQ2784465zbMATH OpenOpenAlexFDO

Authors Farrokh Vatan, Vwani Roychowdhury

Publication date 23 April 2002

Published in SIAM Journal on Computing (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1137/s0097539700370965

zbMATH Keywords

Boolean circuitsdensity matrixlower boundmixed stateNechiporuk's methodquantum algorithmquantum formula

Mathematics Subject Classification ID

Turing machines and related notions (03D10) Modes of computation (nondeterministic, parallel, interactive, probabilistic, etc.) (68Q10) Quantum computation (81P68)

Recommendations

• Formula lower bounds via the quantum method
• One-Way Communication Complexity and the Nečiporuk Lower Bound on Formula Size
• Quantum lower bounds by polynomials
• The quantum query complexity of read-many formulas
• Dequantizing read-once quantum formulas

Cited in

(6)

• A lower bound method for quantum circuits
• Dequantizing read-once quantum formulas
• Formula lower bounds via the quantum method
• One-Way Communication Complexity and the Nečiporuk Lower Bound on Formula Size
• Deriving Grover's lower bound from simple physical principles
• Lower bounds for QCDCL via formula gauge

This page was built for publication: Quantum formulas: A lower bound and simulation

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