Quantum Formulas: a Lower Bound and Simulation

2001/04/10 by Vwani P. Roychowdhury, Roychowdhury, Vwani P., Farrokh Vatan +1
Computer Science · Physics and Astronomy · #Computational Complexity (cs.CC) #FOS: Computer and information sciences #FOS: Physical sciences #Quantum Physics (quant-ph) #cs.CC #quant-ph

paper · pdf · doi:10.48550/arxiv.quant-ph/0104053

22 pages, LaTeX, 6 figures. Final and extended version of quant-ph/9903042. To appear in SIAM Journal on Computing

arxiv created 2001/04/10 · arxiv updated 2009/11/30

Abstract

We show that Nechiporuk's method for proving lower bounds for Boolean formulas can be extended to the quantum case. This leads to an Ω(n² / log² n) lower bound for quantum formulas computing an explicit function. The only known previous explicit lower bound for quantum formulas states that the majority function does not have a linear-size quantum formula. We also show that quantum formulas can be simulated by Boolean circuits of almost the same size.

Related

• An Almost-Quadratic Lower Bound for Quantum Formula Size
• Quantum Analog of Shannon's Lower Bound Theorem
• Quantum Lower Bounds by Polynomials
• One-way communication complexity and the Neciporuk lower bound on formula size
• Quantum Meets the Minimum Circuit Size Problem