The quantum query complexity of read-many formulas

DOI10.1007/978-3-642-33090-2_30MaRDI QIDQ2912853zbMATH OpenOpenAlexFDO

Authors Andrew M. Childs, Shelby Kimmel, Robin Kothari

Publication date 25 September 2012

Published in Algorithms – ESA 2012 (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1112.0548

Mathematics Subject Classification ID

Quantum algorithms and complexity in the theory of computing (68Q12)

Abstract: The quantum query complexity of evaluating any read-once formula with n black-box input bits is Theta(sqrt(n)). However, the corresponding problem for read-many formulas (i.e., formulas in which the inputs have fanout) is not well understood. Although the optimal read-once formula evaluation algorithm can be applied to any formula, it can be suboptimal if the inputs have large fanout. We give an algorithm for evaluating any formula with n inputs, size S, and G gates using O(min{n, sqrt{S}, n^{1/2} G^{1/4}}) quantum queries. Furthermore, we show that this algorithm is optimal, since for any n,S,G there exists a formula with n inputs, size at most S, and at most G gates that requires Omega(min{n, sqrt{S}, n^{1/2} G^{1/4}}) queries. We also show that the algorithm remains nearly optimal for circuits of any particular depth k >= 3, and we give a linear-size circuit of depth 2 that requires Omega (n^{5/9}) queries. Applications of these results include a Omega (n^{19/18}) lower bound for Boolean matrix product verification, a nearly tight characterization of the quantum query complexity of evaluating constant-depth circuits with bounded fanout, new formula gate count lower bounds for several functions including PARITY, and a construction of an AC^0 circuit of linear size that can only be evaluated by a formula with Omega(n^{2-epsilon}) gates.

Recommendations

• A lower bound on the quantum query complexity of read-once functions
• Formula lower bounds via the quantum method
• Any AND-OR formula of size \(N\) can be evaluated in time \(N^{1/2+o(1)}\) on a quantum computer
• Reflections for quantum query algorithms
• Dequantizing read-once quantum formulas

Cited in

(21)

• The average sensitivity of bounded-depth formulas
• A lower bound on the quantum query complexity of read-once functions
• Quantum branch-and-bound algorithm and its application to the travelling salesman problem
• Quantum formulas: A lower bound and simulation
• Super-polynomial quantum speed-ups for Boolean evaluation trees with hidden structure
• Span-program-based quantum algorithm for evaluating formulas
• Quantum complexity of Boolean matrix multiplication and related problems
• Dequantizing read-once quantum formulas
• Any AND-OR formula of size \(N\) can be evaluated in time \(N^{1/2+o(1)}\) on a quantum computer
• The quantum query complexity of certification
• Span-program-based quantum algorithm for evaluating unbalanced formulas
• scientific article; zbMATH DE number 2021815 (Why is no real title available?)
• Formula lower bounds via the quantum method
• A nearly optimal lower bound on the approximate degree of \(\mathrm{AC}^0\)
• Quantum algorithms and approximating polynomials for composed functions with shared inputs
• Reflections for quantum query algorithms
• Quantum algorithm for dynamic programming approach for DAGs and applications
• Shrinkage under random projections, and cubic formula lower bounds for AC^0 (extended abstract)
• Quantum algorithms for Hopcroft's problem
• The quantum query complexity of elliptic PDE
• The quantum query complexity of the determinant

This page was built for publication: The quantum query complexity of read-many formulas

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