Adam Bene Watts
ABSTRACT
Recently, Bravyi, Gosset, and Konig (Science, 2018) exhibited a search problem called the 2D Hidden Linear Function (2D HLF) problem that can be solved exactly by a constant-depth quantum circuit using bounded fan-in gates (or QNC^0 circuits), but cannot be solved by any constant-depth classical circuit using bounded fan-in AND, OR, and NOT gates (or NC^0 circuits). In other words, they exhibited a search problem in QNC^0 that is not in NC^0.
We strengthen their result by proving that the 2D HLF problem is not contained in AC^0, the class of classical, polynomial-size, constant-depth circuits over the gate set of unbounded fan-in AND and OR gates, and NOT gates. We also supplement this worst-case lower bound with an average-case result: There exists a simple distribution under which any AC^0 circuit (even of nearly exponential size) has exponentially small correlation with the 2D HLF problem.
Our results are shown by constructing a new problem in QNC^0, which we call the Parity Halving Problem, which is easier to work with. We prove our AC^0 lower bounds for this problem, and then show that it reduces to the 2D HLF problem.
- Miklos Ajtai. 1983.Google Scholar
- Σ 1 1 -formulae on finite structures. Annals of Pure and Applied Logic 24 (1983), 1–48. 0072(83)90038- 6Google Scholar
- Debajyoti Bera, Frederic Green, and Steven Homer. 2007. Small Depth Quantum Circuits. ACM SIGACT News 38, 2 (June 2007), 35–50. 1272729.1272739 Google ScholarDigital Library
- Juan Bermejo-Vega, Dominik Hangleiter, Martin Schwarz, Robert Raussendorf, and Jens Eisert. 2018. Architectures for Quantum Simulation Showing a Quantum Speedup. Physical Review X 8 (Apr 2018), 021010. Issue 2. 1103/PhysRevX.8.021010Google Scholar
- Gilles Brassard, Anne Broadbent, and Alain Tapp. 2005. Recasting Mermin’s Multiplayer Game into the Framework of Pseudo-telepathy. Quantum Information & Computation 5, 7 (Nov. 2005), 538–550. http://dl.acm.org/citation.cfm?id= 2011656.2011658 Google ScholarDigital Library
- Sergey Bravyi, David Gosset, and Robert König. 2018. Quantum advantage with shallow circuits. Science 362, 6412 (2018), 308–311. science.aar3106Google Scholar
- Harry Buhrman and Ronald de Wolf. 2002. Complexity measures and decision tree complexity: a survey. Theor. Comput. Sci. 288, 1 (2002), 21–43. 3975(01)00144-X Google ScholarDigital Library
- Matthew Coudron, Jalex Stark, and Thomas Vidick. 2018. Trading locality for time: certifiable randomness from low-depth circuits. arXiv preprint arXiv:1810.04233 (2018). arXiv: 1810.04233Google Scholar
- M. Fang, S. Fenner, F. Green, S. Homer, and Y. Zhang. 2006.Google Scholar
- Quantum Lower Bounds for Fanout. Quantum Information & Computation 6, 1 (Jan. 2006), 46–57. http://dl.acm.org/citation.cfm?id=2011679.2011682 Google ScholarDigital Library
- Stephen Fenner, Frederic Green, Steven Homer, and Yong Zhang. 2005. Bounds on the Power of Constant-Depth Quantum Circuits. In Fundamentals of Computation Theory. 44–55. Google ScholarDigital Library
- Merrick Furst, James B. Saxe, and Michael Sipser. 1984. Parity, circuits, and the polynomial-time hierarchy. Mathematical systems theory 17, 1 (Dec 1984), 13–27.Google Scholar
- Frederic Green, Steven Homer, Cristopher Moore, and Christopher Pollett. 2002.Google Scholar
- Counting, Fanout and the Complexity of Quantum ACC. Quantum Information & Computation 2, 1 (Dec. 2002), 35–65. http://dl.acm.org/citation.cfm?id=2011417. Google ScholarDigital Library
- 2011420Google Scholar
- Daniel M. Greenberger, Michael A. Horne, and Anton Zeilinger. 1989.Google Scholar
- Going beyond Bell’s theorem. In Bell’s theorem, quantum theory and conceptions of the universe. Springer, 69–72. 94- 017- 0849- 4_10Google Scholar
- Johan Håstad. 1986.Google Scholar
- Computational limitations of small-depth circuits. Ph.D. Dissertation. Massachusetts Institute of Technology. https://www.nada.kth.se/ ~johanh/thesis.pdfGoogle Scholar
- Johan Håstad. 2014. On the Correlation of Parity and Small-Depth Circuits. SIAM J. Comput. 43, 5 (2014), 1699–1708.Google ScholarCross Ref
- Peter Høyer and Robert Špalek. 2005. Quantum Fan-out is Powerful. Theory of Computing 1 (2005), 23.Google ScholarCross Ref
- François Le Gall. 2018. Average-Case Quantum Advantage with Shallow Circuits. arXiv preprint arXiv:1810.12792 (2018). arXiv: 1810.12792Google Scholar
- N. David Mermin. 1990. Extreme quantum entanglement in a superposition of macroscopically distinct states. Physical Review Letters 65 (Oct 1990), 1838–1840.Google Scholar
- Cristopher Moore. 1999.Google Scholar
- Quantum Circuits: Fanout, Parity, and Counting. arXiv:quant-ph/9903046 (March 1999). arXiv: quant-ph/9903046Google Scholar
- Cristopher Moore and Martin Nilsson. 2002.Google Scholar
- Parallel Quantum Computation and Quantum Codes. SIAM J. Comput. 31, 3 (March 2002), 799–815. arXiv: quant-ph/9808027 Google ScholarDigital Library
- Cody Murray and Ryan Williams. 2018. Circuit Lower Bounds for Nondeterministic Quasi-polytime: An Easy Witness Lemma for NP and NQP. In Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing (STOC 2018). 890–901. Google ScholarDigital Library
- Ran Raz and Avishay Tal. 2018. Oracle Separation of BQP and PH. In Electronic Colloquium on Computational Complexity (ECCC), Vol. 18-107. https://eccc. weizmann.ac.il/report/2018/107/Google Scholar
- Benjamin Rossman. 2017. An entropy proof of the switching lemma and tight bounds on the decision-tree size of AC 0. (2017). http://www.math.toronto.edu/ rossman/logsize.pdf Manuscript.Google Scholar
- Peter W. Shor. 1997.Google Scholar
- Polynomial-time algorithms for prime factorization and discrete logarithms on a quantum computer. SIAM J. Comput. 26, 5 (1997), 1484– 1509. Google ScholarDigital Library
- Yasuhiro Takahashi and Seiichiro Tani. 2016.Google Scholar
- Collapse of the Hierarchy of Constant-Depth Exact Quantum Circuits. Computational Complexity 25, 4 (01 Dec 2016), 849–881. 016- 0140- 0 Google ScholarDigital Library
- Yasuhiro Takahashi and Seiichiro Tani. 2018. Power of Uninitialized Qubits in Shallow Quantum Circuits. In 35th Symposium on Theoretical Aspects of Computer Science (STACS 2018) (Leibniz International Proceedings in Informatics (LIPIcs)), Vol. 96. 57:1–57:13.Google Scholar
- Barbara M. Terhal and David P. DiVincenzo. 2004. Adaptive Quantum Computation, Constant Depth Quantum Circuits and Arthur-Merlin Games. Quantum Information & Computation 4, 2 (March 2004), 134–145. http://dl.acm.org/citation. cfm?id=2011577.2011582 Google ScholarDigital Library
- Emanuele Viola. 2014.Google Scholar
- Extractors for Circuit Sources. SIAM J. Comput. 43, 2 (2014), 655–672.Google Scholar
- Ryan Williams. 2014.Google Scholar
- Nonuniform ACC Circuit Lower Bounds. J. ACM 61, 1, Article 2 (Jan. 2014), 32 pages. Google ScholarDigital Library
Index Terms
- Exponential separation between shallow quantum circuits and unbounded fan-in shallow classical circuits
Recommendations
Interactive shallow Clifford circuits: Quantum advantage against NC¹ and beyond
STOC 2020: Proceedings of the 52nd Annual ACM SIGACT Symposium on Theory of ComputingRecent work of Bravyi et al. and follow-up work by Bene Watts et al. demonstrates a quantum advantage for shallow circuits: constant-depth quantum circuits can perform a task which constant-depth classical (i.e., 0) circuits cannot. Their results have ...
Quantum addition circuits and unbounded fan-out
We first show how to construct an O(n)-depth O(n)-size quantum circuit for additionof two n-bit binary numbers with no ancillary qubits. The exact size is 7n-6, whichis smaller than that of any other quantum circuit ever constructed for addition withno ...
Hardness of classically simulating quantum circuits with unbounded Toffoli and fan-out gates
We study the classical simulatability of constant-depth polynomial-size quantum circuits followed by only one single-qubit measurement, where the circuits consist of universal gates on at most two qubits and additional gates on an unbounded number of ...
Comments