An official website of the United States government
Despite fundamental interests in learning quantum circuits, the existence of a computationally efficient algorithm for learning shallow quantum circuits remains an open question. Because shallow quantum circuits can generate distributions that are classically hard to sample from, existing learning algorithms do not apply. In this work, we present a polynomial-time classical algorithm for learning the description of any unknown π-qubit shallow quantum circuit π (with arbitrary unknown architecture) within a small diamond distance using single-qubit measurement data on the output states of π. We also provide a polynomial-time classical algorithm for learning the description of any unknown π-qubit state |πβ© = π|0^πβ© prepared by a shallow quantum circuit π (on a 2D lattice) within a small trace distance using single-qubit measurements on copies of |πβ©. Our approach uses a quantum circuit representation based on local inversions and a technique to combine these inversions. This circuit representation yields an optimization landscape that can be efficiently navigated and enables efficient learning of quantum circuits that are classically hard to simulate.
more »
« less
This content will become publicly available on June 15, 2026
On the Computational Power of QAC0 with Barely Superlinear Ancillae
QAC0 is the family of constant-depth polynomial-size quantum circuits consisting of arbitrary single qubit unitaries and multi-qubit Toffoli gates. It was introduced by Moore as a quantum counterpart of AC0, along with the conjecture that QAC0 circuits cannot compute PARITY. In this work, we make progress on this long-standing conjecture: we show that any depth-π QAC0 circuit requires π^{1+3^{βπ}} ancillae to compute a function with approximate degree Ξ(π), which includes PARITY, MAJORITY and MOD_π. We further establish superlinear lower bounds on quantum state synthesis and quantum channel synthesis. This is the first lower bound on the super-linear sized QAC0. Regarding PARITY, we show that any further improvement on the size of ancillae to π^{1+exp(βπ(π))} would imply that PARITY β QAC0. These lower bounds are derived by giving low-degree approximations to QAC0 circuits. We show that a depth-π QAC0 circuit with π ancillae, when applied to low-degree operators, has a degree (π + π)^{1β3^{βπ}} polynomial approximation in the spectral norm. This implies that the class QLC0, corresponding to linear size QAC0 circuits, has an approximate degree π(π). This is a quantum generalization of the result that LC0 circuits have an approximate degree π(π) by Bun, Kothari, and Thaler. Our result also implies that QLC0 β NC1.
more »
« less
- Award ID(s):
- 2013303
- PAR ID:
- 10658491
- Editor(s):
- Bansal, Nikhil
- Publisher / Repository:
- ACM
- Date Published:
- Page Range / eLocation ID:
- 1476 to 1487
- Subject(s) / Keyword(s):
- QAC0 analysis of Boolean functions quantum circuit complexity
- Format(s):
- Medium: X
- Sponsoring Org:
- National Science Foundation
More Like this
-
-
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.more » « less
-
Fawzi, Omar; Walter, Michael (Ed.)The approximate degree of a Boolean function is the minimum degree of real polynomial that approximates it pointwise. For any Boolean function, its approximate degree serves as a lower bound on its quantum query complexity, and generically lifts to a quantum communication lower bound for a related function. We introduce a framework for proving approximate degree lower bounds for certain oracle identification problems, where the goal is to recover a hidden binary string x β {0, 1}βΏ given possibly non-standard oracle access to it. Our lower bounds apply to decision versions of these problems, where the goal is to compute the parity of x. We apply our framework to the ordered search and hidden string problems, proving nearly tight approximate degree lower bounds of Ξ©(n/logΒ² n) for each. These lower bounds generalize to the weakly unbounded error setting, giving a new quantum query lower bound for the hidden string problem in this regime. Our lower bounds are driven by randomized communication upper bounds for the greater-than and equality functions.more » « less
-
We show that there is an equation of degree at most poly( n ) for the (Zariski closure of the) set of the non-rigid matrices: That is, we show that for every large enough field π½, there is a non-zero n 2 -variate polynomial P Ξ΅ π½[ x 1, 1 , ..., x n, n ] of degree at most poly( n ) such that every matrix M that can be written as a sum of a matrix of rank at most n /100 and a matrix of sparsity at most n 2 /100 satisfies P(M) = 0. This confirms a conjecture of Gesmundo, Hauenstein, Ikenmeyer, and Landsberg [ 9 ] and improves the best upper bound known for this problem down from exp ( n 2 ) [ 9 , 12 ] to poly( n ). We also show a similar polynomial degree bound for the (Zariski closure of the) set of all matrices M such that the linear transformation represented by M can be computed by an algebraic circuit with at most n 2 /200 edges (without any restriction on the depth). As far as we are aware, no such bound was known prior to this work when the depth of the circuits is unbounded. Our methods are elementary and short and rely on a polynomial map of Shpilka and Volkovich [ 21 ] to construct low-degree βuniversalβ maps for non-rigid matrices and small linear circuits. Combining this construction with a simple dimension counting argument to show that any such polynomial map has a low-degree annihilating polynomial completes the proof. As a corollary, we show that any derandomization of the polynomial identity testing problem will imply new circuit lower bounds. A similar (but incomparable) theorem was proved by Kabanets and Impagliazzo [ 11 ].more » « less
-
null (Ed.)The approximate degree of a Boolean function f is the least degree of a real polynomial that approximates f pointwise to error at most 1/3. The approximate degree of f is known to be a lower bound on the quantum query complexity of f (Beals et al., FOCS 1998 and J. ACM 2001). We find tight or nearly tight bounds on the approximate degree and quantum query complexities of several basic functions. Specifically, we show the following. k-Distinctness: For any constant k, the approximate degree and quantum query complexity of the k-distinctness function is Ξ©(n3/4β1/(2k)). This is nearly tight for large k, as Belovs (FOCS 2012) has shown that for any constant k, the approximate degree and quantum query complexity of k-distinctness is O(n3/4β1/(2k+2β4)). Image size testing: The approximate degree and quantum query complexity of testing the size of the image of a function [n]β[n] is Ξ©~(n1/2). This proves a conjecture of Ambainis et al. (SODA 2016), and it implies tight lower bounds on the approximate degree and quantum query complexity of the following natural problems. k-Junta testing: A tight Ξ©~(k1/2) lower bound for k-junta testing, answering the main open question of Ambainis et al. (SODA 2016). Statistical distance from uniform: A tight Ξ©~(n1/2) lower bound for approximating the statistical distance of a distribution from uniform, answering the main question left open by Bravyi et al. (STACS 2010 and IEEE Trans. Inf. Theory 2011). Shannon entropy: A tight Ξ©~(n1/2) lower bound for approximating Shannon entropy up to a certain additive constant, answering a question of Li and Wu (2017). Surjectivity: The approximate degree of the surjectivity function is Ξ©~(n3/4). The best prior lower bound was Ξ©(n2/3). Our result matches an upper bound of O~(n3/4) due to Sherstov (STOC 2018), which we reprove using different techniques. The quantum query complexity of this function is known to be Ξ(n) (Beame and Machmouchi, Quantum Inf. Comput. 2012 and Sherstov, FOCS 2015). Our upper bound for surjectivity introduces new techniques for approximating Boolean functions by low-degree polynomials. Our lower bounds are proved by significantly refining techniques recently introduced by Bun and Thaler (FOCS 2017).more » « less
