pith. sign in

arxiv: 1906.08890 · v1 · pith:WRYZRPV6new · submitted 2019-06-20 · 🪐 quant-ph · cs.CC

Exponential separation between shallow quantum circuits and unbounded fan-in shallow classical circuits

Adam Bene Watts , Robin Kothari , Luke Schaeffer , Avishay Tal This is my paper

Pith reviewed 2026-05-25 19:13 UTC · model grok-4.3

classification 🪐 quant-ph cs.CC
keywords quantum circuitsAC0 lower boundsshallow circuitshidden linear functioncircuit complexityquantum advantageparity halving
0
0 comments X

The pith

The 2D hidden linear function problem lies in QNC^0 but not in AC^0, with average-case exponential hardness against nearly exponential AC^0 circuits.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The paper proves that the 2D Hidden Linear Function problem, solvable exactly by constant-depth bounded-fan-in quantum circuits, cannot be solved by any constant-depth classical circuit using unbounded-fan-in AND, OR, and NOT gates. It introduces the Relaxed Parity Halving Problem as an intermediate that is also in QNC^0, proves AC^0 lower bounds for it using switching lemmas and related techniques, and reduces it to the 2D HLF problem while preserving the separation. The work adds an average-case result showing that under a simple distribution any AC^0 circuit of size 2 to the n to the o(1) has only exponentially small correlation with the function. A sympathetic reader cares because the result strengthens the known quantum-classical separation for shallow circuits beyond the earlier bounded-fan-in case.

Core claim

The 2D Hidden Linear Function problem is in QNC^0 but not in AC^0. Moreover, there exists a simple distribution under which any AC^0 circuit of nearly exponential size has exponentially small correlation with the problem. These bounds are obtained by first establishing them for the Relaxed Parity Halving Problem and then reducing that problem to 2D HLF while preserving both the quantum upper bound and the classical lower bound.

What carries the argument

The reduction from the Relaxed Parity Halving Problem to the 2D Hidden Linear Function problem, which preserves QNC^0 membership while transferring AC^0 hardness.

If this is right

  • The 2D HLF problem requires superpolynomial size for any AC^0 circuit.
  • Under a simple input distribution, every AC^0 circuit of size 2^{n^{o(1)}} has correlation at most 2^{-n^{\Omega(1)}} with the 2D HLF function.
  • The Parity Bending Problem lies in QNC^0 with polynomial quantum advice but lies outside AC^0[2].

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

  • The same reduction strategy may extend to show that 2D HLF is hard for other constant-depth classical classes such as TC^0.
  • The average-case hardness result could be used to rule out classical shallow-circuit heuristics for related quantum search problems.
  • Techniques from the switching-lemma refinement might apply directly to other multi-output quantum search problems to obtain AC^0 lower bounds.

Load-bearing premise

The reduction from instances of the Relaxed Parity Halving Problem to the 2D Hidden Linear Function problem preserves both the existence of a constant-depth bounded-fan-in quantum solution and the hardness against constant-depth unbounded-fan-in classical circuits.

What would settle it

An explicit AC^0 circuit of polynomial size that correctly solves the 2D Hidden Linear Function problem on every input would falsify the worst-case claim.

Figures

Figures reproduced from arXiv: 1906.08890 by Adam Bene Watts, Avishay Tal, Luke Schaeffer, Robin Kothari.

Figure 1
Figure 1. Figure 1: Quantum circuit for the Parity Halving Problem on 3 [PITH_FULL_IMAGE:figures/full_fig_p005_1.png] view at source ↗
Figure 2
Figure 2. Figure 2: Grid Implementation of a Poor Man’s Cat State. Blac [PITH_FULL_IMAGE:figures/full_fig_p021_2.png] view at source ↗
read the original abstract

Recently, Bravyi, Gosset, and K\"{o}nig (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 Relaxed 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. As a step towards even stronger lower bounds, we present a search problem that we call the Parity Bending Problem, which is in QNC^0/qpoly (QNC^0 circuits that are allowed to start with a quantum state of their choice that is independent of the input), but is not even in AC^0[2] (the class AC^0 with unbounded fan-in XOR gates). All the quantum circuits in our paper are simple, and the main difficulty lies in proving the classical lower bounds. For this we employ a host of techniques, including a refinement of H{\aa}stad's switching lemmas for multi-output circuits that may be of independent interest, the Razborov-Smolensky AC^0[2] lower bound, Vazirani's XOR lemma, and lower bounds for non-local games.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Referee Report

0 major / 2 minor

Summary. The paper strengthens the Bravyi-Gosset-König separation by proving that the 2D Hidden Linear Function (2D HLF) problem lies in QNC^0 but not in AC^0. It introduces the Relaxed Parity Halving (RPH) problem, shows RPH is in QNC^0, establishes both worst-case and average-case AC^0 lower bounds for RPH via a refined multi-output switching lemma, Razborov-Smolensky, and Vazirani's XOR lemma, and reduces RPH to 2D HLF while preserving the quantum upper bound. A secondary construction, the Parity Bending Problem, is shown to be in QNC^0/qpoly but not in AC^0[2].

Significance. If the proofs hold, the result gives a strictly stronger classical lower bound (AC^0 rather than NC^0) together with an average-case guarantee under a simple distribution, using only standard circuit-complexity tools plus one refinement of the switching lemma. The explicit reduction and the multi-output switching lemma are reusable contributions.

minor comments (2)
  1. The abstract states that the reduction from RPH to 2D HLF 'maps instances so that membership in QNC^0 is preserved'; a short paragraph in §4 clarifying how the quantum circuit for RPH is transformed into one for 2D HLF would help readers verify the inheritance of the upper bound.
  2. Notation for the multi-output switching lemma (Lemma 3.4 or equivalent) is introduced without an explicit statement of the failure probability as a function of the number of outputs; adding this parameter list would make the subsequent applications easier to check.

Simulated Author's Rebuttal

0 responses · 0 unresolved

We thank the referee for their positive summary, significance assessment, and recommendation to accept the paper. We are pleased that the contributions, including the refined multi-output switching lemma and the explicit reduction, were viewed as reusable.

Circularity Check

0 steps flagged

No significant circularity detected

full rationale

The derivation introduces the Relaxed Parity Halving Problem (RPH) as an auxiliary problem shown to lie in QNC^0 via an explicit circuit construction, then applies external combinatorial tools (refined multi-output switching lemma, Razborov-Smolensky AC^0[2] bound, Vazirani XOR lemma) to obtain both worst-case and average-case AC^0 lower bounds for RPH, and finally reduces RPH to 2D HLF while transferring the classical hardness and inheriting the quantum upper bound from the independent prior work of Bravyi-Gosset-König. None of these steps is self-definitional, none renames a fitted parameter as a prediction, and the load-bearing lemmas are external rather than self-citations. The Parity Bending Problem is presented separately as a further extension and does not close any loop in the main argument.

Axiom & Free-Parameter Ledger

0 free parameters · 2 axioms · 0 invented entities

The proof relies on standard, previously published circuit-complexity tools rather than new axioms or fitted parameters.

axioms (2)
  • standard math Håstad's switching lemma (refined version for multi-output circuits)
    Invoked to obtain AC^0 lower bounds on the auxiliary problem.
  • standard math Razborov-Smolensky AC^0[2] lower bound
    Used for the Parity Bending Problem hardness.

pith-pipeline@v0.9.0 · 5951 in / 1338 out tokens · 25007 ms · 2026-05-25T19:13:37.712773+00:00 · methodology

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Reference graph

Works this paper leans on

38 extracted references · 38 canonical work pages · 2 internal anchors

  1. [1]

    A theorem on probabilistic constant depth computations

    Miklos Ajtai and Michael Ben-Or. A theorem on probabilistic constant depth computations. In Proceedings of the 16th Annual ACM Symposium on Theory of Computing , STOC '84, pages 471--474, 1984. http://dx.doi.org/10.1145/800057.808715 doi:10.1145/800057.808715

    work page doi:10.1145/800057.808715 1984

  2. [2]

    _1^1 -formulae on finite structures

    Miklos Ajtai. _1^1 -formulae on finite structures. Annals of Pure and Applied Logic , 24:1--48, 1983. http://dx.doi.org/10.1016/0168-0072(83)90038-6 doi:10.1016/0168-0072(83)90038-6

    work page doi:10.1016/0168-0072(83)90038-6 1983

  3. [3]

    Recasting Mermin's multi-player game into the framework of pseudo-telepathy

    Gilles Brassard, Anne Broadbent, and Alain Tapp. Recasting Mermin's multi-player game into the framework of pseudo-telepathy. Quantum Information & Computation , 5(7):538--550, November 2005. URL: http://dl.acm.org/citation.cfm?id=2011656.2011658

    work page arXiv 2005

  4. [4]

    Complexity measures and decision tree complexity: a survey

    Harry Buhrman and Ronald de Wolf. Complexity measures and decision tree complexity: a survey. Theor. Comput. Sci. , 288(1):21--43, 2002. http://dx.doi.org/10.1016/S0304-3975(01)00144-X doi:10.1016/S0304-3975(01)00144-X

    work page doi:10.1016/s0304-3975(01)00144-x 2002

  5. [5]

    Small depth quantum circuits

    Debajyoti Bera, Frederic Green, and Steven Homer. Small depth quantum circuits. ACM SIGACT News , 38(2):35--50, June 2007. http://dx.doi.org/10.1145/1272729.1272739 doi:10.1145/1272729.1272739

    work page doi:10.1145/1272729.1272739 2007

  6. [6]

    Quantum advantage with shallow circuits

    Sergey Bravyi, David Gosset, and Robert K \"o nig. Quantum advantage with shallow circuits. Science , 362(6412):308--311, 2018. http://dx.doi.org/10.1126/science.aar3106 doi:10.1126/science.aar3106

    work page doi:10.1126/science.aar3106 2018

  7. [7]

    Architectures for quantum simulation showing a quantum speedup

    Juan Bermejo-Vega, Dominik Hangleiter, Martin Schwarz, Robert Raussendorf, and Jens Eisert. Architectures for quantum simulation showing a quantum speedup. Physical Review X , 8:021010, Apr 2018. http://dx.doi.org/10.1103/PhysRevX.8.021010 doi:10.1103/PhysRevX.8.021010

    work page doi:10.1103/physrevx.8.021010 2018

  8. [8]

    Harrow, Gurtej Kanwar, and Anand Natarajan

    Adam Bene Watts, Aram W. Harrow, Gurtej Kanwar, and Anand Natarajan. Algorithms, Bounds, and Strategies for Entangled XOR Games . In 10th Innovations in Theoretical Computer Science Conference (ITCS 2019) , volume 124 of Leibniz International Proceedings in Informatics (LIPIcs) , pages 10:1--10:18. Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik, 2018. ...

    work page doi:10.4230/lipics.itcs.2019.10 2019

  9. [9]

    Trading locality for time: certifiable randomness from low-depth circuits

    Matthew Coudron, Jalex Stark, and Thomas Vidick. Trading locality for time: certifiable randomness from low-depth circuits. arXiv preprint arXiv:1810.04233 , 2018. http://arxiv.org/abs/1810.04233 arXiv:1810.04233

    work page internal anchor Pith review Pith/arXiv arXiv 2018

  10. [10]

    Quantum lower bounds for fanout

    Maosen Fang, Stephen Fenner, Frederic Green, Steven Homer, and Yong Zhang. Quantum lower bounds for fanout. Quantum Information & Computation , 6(1):46--57, January 2006. URL: http://dl.acm.org/citation.cfm?id=2011679.2011682

    work page arXiv 2006

  11. [11]

    Bounds on the power of constant-depth quantum circuits

    Stephen Fenner, Frederic Green, Steven Homer, and Yong Zhang. Bounds on the power of constant-depth quantum circuits. In Fundamentals of Computation Theory , pages 44--55, 2005. http://dx.doi.org/10.1007/11537311_5 doi:10.1007/11537311_5

    work page doi:10.1007/11537311_5 2005

  12. [12]

    Saxe, and Michael Sipser

    Merrick Furst, James B. Saxe, and Michael Sipser. Parity, circuits, and the polynomial-time hierarchy. Mathematical systems theory , 17(1):13--27, Dec 1984. http://dx.doi.org/10.1007/BF01744431 doi:10.1007/BF01744431

    work page doi:10.1007/bf01744431 1984

  13. [13]

    Counting, fanout and the complexity of quantum ACC

    Frederic Green, Steven Homer, Cristopher Moore, and Christopher Pollett. Counting, fanout and the complexity of quantum ACC . Quantum Information & Computation , 2(1):35--65, December 2002. URL: http://dl.acm.org/citation.cfm?id=2011417.2011420

    work page arXiv 2002

  14. [14]

    Greenberger, Michael A

    Daniel M. Greenberger, Michael A. Horne, and Anton Zeilinger. Going beyond B ell’s theorem. In Bell’s theorem, quantum theory and conceptions of the universe , pages 69--72. Springer, 1989. http://dx.doi.org/10.1007/978-94-017-0849-4_10 doi:10.1007/978-94-017-0849-4_10

    work page doi:10.1007/978-94-017-0849-4_10 1989

  15. [15]

    Computational limitations of small-depth circuits

    Johan H stad. Computational limitations of small-depth circuits . PhD thesis, Massachusetts Institute of Technology, 1986. URL: https://www.nada.kth.se/ johanh/thesis.pdf

    work page 1986

  16. [16]

    On the correlation of parity and small-depth circuits

    Johan H stad. On the correlation of parity and small-depth circuits. SIAM Journal on Computing , 43(5):1699--1708, 2014. http://dx.doi.org/10.1137/120897432 doi:10.1137/120897432

    work page doi:10.1137/120897432 2014

  17. [17]

    Quantum Fan -out is Powerful

    Peter H yer and Robert S palek. Quantum Fan -out is Powerful . Theory of Computing , 1:23, 2005. http://dx.doi.org/10.4086/toc.2005.v001a005 doi:10.4086/toc.2005.v001a005

    work page doi:10.4086/toc.2005.v001a005 2005

  18. [18]

    Average-case quantum advantage with shallow circuits

    Fran c ois Le Gall. Average-case quantum advantage with shallow circuits. arXiv preprint arXiv:1810.12792 , 2018. http://arxiv.org/abs/1810.12792 arXiv:1810.12792

    work page arXiv 2018

  19. [19]

    David Mermin

    N. David Mermin. Extreme quantum entanglement in a superposition of macroscopically distinct states. Physical Review Letters , 65:1838--1840, Oct 1990. http://dx.doi.org/10.1103/PhysRevLett.65.1838 doi:10.1103/PhysRevLett.65.1838

    work page doi:10.1103/physrevlett.65.1838 1990

  20. [20]

    Parallel quantum computation and quantum codes

    Cristopher Moore and Martin Nilsson. Parallel quantum computation and quantum codes. SIAM Journal on Computing , 31(3):799--815, March 2002. http://dx.doi.org/10.1137/S0097539799355053 doi:10.1137/S0097539799355053

    work page doi:10.1137/s0097539799355053 2002

  21. [21]

    Quantum Circuits: Fanout, Parity, and Counting

    Cristopher Moore. Quantum Circuits : Fanout , Parity , and Counting . arXiv:quant-ph/9903046 , March 1999. http://arxiv.org/abs/quant-ph/9903046 arXiv:quant-ph/9903046

    work page internal anchor Pith review Pith/arXiv arXiv 1999

  22. [22]

    Circuit lower bounds for nondeterministic quasi-polytime: An easy witness lemma for NP and NQP

    Cody Murray and Ryan Williams. 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, pages 890--901, 2018. http://dx.doi.org/10.1145/3188745.3188910 doi:10.1145/3188745.3188910

    work page doi:10.1145/3188745.3188910 2018

  23. [23]

    An exposition of B ourgain’s 2-source extractor

    Anup Rao. An exposition of B ourgain’s 2-source extractor. In Electronic Colloquium on Computational Complexity (ECCC) , volume 07-34, 2007. URL: https://eccc.weizmann.ac.il/report/2007/034/

    work page 2007

  24. [24]

    Razborov

    Alexander A. Razborov. Lower bounds on the size of bounded depth circuits over a complete basis with logical addition. Mathematical notes of the Academy of Sciences of the USSR , 41(4):333--338, Apr 1987. http://dx.doi.org/10.1007/BF01137685 doi:10.1007/BF01137685

    work page doi:10.1007/bf01137685 1987

  25. [25]

    A parallel repetition theorem

    Ran Raz. A parallel repetition theorem. SIAM Journal on Computing , 27(3):763--803, 1998. http://dx.doi.org/10.1137/S0097539795280895 doi:10.1137/S0097539795280895

    work page doi:10.1137/s0097539795280895 1998

  26. [26]

    An entropy proof of the switching lemma and tight bounds on the decision-tree size of AC ^0

    Benjamin Rossman. An entropy proof of the switching lemma and tight bounds on the decision-tree size of AC ^0 . Manuscript, 2017. URL: http://www.math.toronto.edu/rossman/logsize.pdf

    work page 2017

  27. [27]

    Oracle separation of BQP and PH

    Ran Raz and Avishay Tal. Oracle separation of BQP and PH . In Proceedings of the 51st Annual Symposium on Theory of Computing , STOC 2019, pages 13--23, 2019. http://dx.doi.org/10.1145/3313276.3316315 doi:10.1145/3313276.3316315

    work page doi:10.1145/3313276.3316315 2019

  28. [28]

    Towards proving strong direct product theorems

    Ronen Shaltiel. Towards proving strong direct product theorems. Computational Complexity , 12(1/2):1--22, July 2004. http://dx.doi.org/10.1007/s00037-003-0175-x doi:10.1007/s00037-003-0175-x

    work page doi:10.1007/s00037-003-0175-x 2004

  29. [29]

    Peter W. Shor. Polynomial-time algorithms for prime factorization and discrete logarithms on a quantum computer. SIAM Journal on Computing , 26(5):1484--1509, 1997. http://dx.doi.org/10.1137/S0036144598347011 doi:10.1137/S0036144598347011

    work page doi:10.1137/s0036144598347011 1997

  30. [30]

    Algebraic methods in the theory of lower bounds for Boolean circuit complexity

    Roman Smolensky. Algebraic methods in the theory of lower bounds for Boolean circuit complexity. In Proceedings of the Nineteenth Annual ACM Symposium on Theory of Computing , STOC '87, pages 77--82, 1987. http://dx.doi.org/10.1145/28395.28404 doi:10.1145/28395.28404

    work page doi:10.1145/28395.28404 1987

  31. [31]

    Tight bounds on the fourier spectrum of AC0

    Avishay Tal. Tight bounds on the fourier spectrum of AC0 . In Computational Complexity Conference , volume 79 of LIPIcs , pages 15:1--15:31. Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik, 2017. http://dx.doi.org/10.4230/LIPIcs.CCC.2017.15 doi:10.4230/LIPIcs.CCC.2017.15

    work page doi:10.4230/lipics.ccc.2017.15 2017

  32. [32]

    Terhal and David P

    Barbara M. Terhal and David P. DiVincenzo. Adaptive quantum computation, constant depth quantum circuits and Arthur-Merlin games. Quantum Information & Computation , 4(2):134--145, March 2004. URL: http://dl.acm.org/citation.cfm?id=2011577.2011582

    work page arXiv 2004

  33. [33]

    Collapse of the hierarchy of constant-depth exact quantum circuits

    Yasuhiro Takahashi and Seiichiro Tani. Collapse of the hierarchy of constant-depth exact quantum circuits. Computational Complexity , 25(4):849--881, Dec 2016. http://dx.doi.org/10.1007/s00037-016-0140-0 doi:10.1007/s00037-016-0140-0

    work page doi:10.1007/s00037-016-0140-0 2016

  34. [34]

    Power of Uninitialized Qubits in Shallow Quantum Circuits

    Yasuhiro Takahashi and Seiichiro Tani. Power of Uninitialized Qubits in Shallow Quantum Circuits . In 35th Symposium on Theoretical Aspects of Computer Science (STACS 2018) , volume 96 of Leibniz International Proceedings in Informatics (LIPIcs) , pages 57:1--57:13, 2018. http://dx.doi.org/10.4230/LIPIcs.STACS.2018.57 doi:10.4230/LIPIcs.STACS.2018.57

    work page doi:10.4230/lipics.stacs.2018.57 2018

  35. [35]

    Randomness, Adversaries and Computation

    Umesh Vazirani. Randomness, Adversaries and Computation . PhD thesis, UC Berkeley, 1986

    work page 1986

  36. [36]

    Extractors for circuit sources

    Emanuele Viola. Extractors for circuit sources. SIAM Journal on Computing , 43(2):655--672, 2014. http://dx.doi.org/10.1137/11085983X doi:10.1137/11085983X

    work page doi:10.1137/11085983x 2014

  37. [37]

    Nonuniform ACC circuit lower bounds

    Ryan Williams. Nonuniform ACC circuit lower bounds. Journal of the ACM , 61(1):2:1--2:32, January 2014. http://dx.doi.org/10.1145/2559903 doi:10.1145/2559903

    work page doi:10.1145/2559903 2014

  38. [38]

    Andrew C-C. Yao. Separating the polynomial-time hierarchy by oracles. In Proc. 26th Annual Symposium on Foundations of Computer Science , pages 1--10, 1985. URL: http://dl.acm.org/citation.cfm?id=4479.4487

    work page arXiv 1985