Source-linked AI summary
Quantum advantage with shallow circuits
Sergey Bravyi, David Gosset, Robert Koenig
TL;DR
The paper asks whether constant-depth quantum circuits can outperform constant-depth classical circuits on a concrete computational problem. It introduces the 2D Hidden Linear Function problem and proves that local constant-depth quantum circuits solve it with certainty, whereas bounded-fan-in classical probabilistic circuits require logarithmic depth. The result establishes a provable separation and motivates further questions about stronger classical circuit families and quantum-sampled distributions.
Problem
The paper investigates whether constant-depth quantum circuits can solve a computational problem that constant-depth classical circuits cannot.
Method
The paper introduces the 2D Hidden Linear Function problem, whose input is a grid-local quadratic form over binary variables, and analyzes quantum and bounded-fan-in classical circuits for solving it.
Results
Bounded-fan-in classical probabilistic circuits solving the problem with success probability greater than 7/8 require depth Ω(log n), while local constant-depth quantum circuits solve it with certainty.
Takeaways & Limitations
The result proves that shallow quantum circuits are more powerful than their classical counterparts for this search problem, even with nearest-neighbor gates on a 2D grid.
Takeaways & Limitations
The paper leaves open whether the problem also resists more powerful classical families such as AC0 and whether the success threshold 7/8 can be improved.
Abstract
from arXiv · showhide
We prove that constant-depth quantum circuits are more powerful than their classical counterparts. To this end we introduce a non-oracular version of the Bernstein-Vazirani problem which we call the 2D Hidden Linear Function problem. An instance of the problem is specified by a quadratic form q that maps n-bit strings to integers modulo four. The goal is to identify a linear boolean function which describes the action of q on a certain subset of n-bit strings. We prove that any classical probabilistic circuit composed of bounded fan-in gates that solves the 2D Hidden Linear Function problem with high probability must have depth logarithmic in n. In contrast, we show that this problem can be solved with certainty by a constant-depth quantum circuit composed of one- and two-qubit gates acting locally on a two-dimensional grid.
1 Introduction
The paper asks whether constant-depth quantum circuits can outperform constant-depth classical circuits and answers yes with a provable separation. It introduces the 2D Hidden Linear Function problem, solved exactly by local quantum circuits but requiring logarithmic depth for bounded-fan-in classical circuits.
- Motivation and main result: Constant-depth quantum circuits can solve a computational problem that constant-depth classical circuits cannot.The separation remains provable even when quantum gates are nearest-neighbor on a 2D grid, while classical gates may be long-range and unbounded-fan-out.
- Problem definition: The 2D Hidden Linear Function problem gives a non-oracular analogue of Bernstein–Vazirani learning for quadratic forms over binary variables.The quadratic form is explicitly specified by coefficients A and b rather than through oracle access.
- Main result: Any bounded-fan-in classical probabilistic circuit solving the problem with success probability greater than 7/8 has depth Ω(log n).The result establishes a lower bound for classical circuits rather than relying on complexity-class conjectures.
- Main result: A constant-depth quantum circuit of one- and two-qubit gates solves the problem with certainty while acting locally on a two-dimensional grid.The construction uses shallow quantum computation and an operator U_q determined by the coefficients specifying q.
- Technical contribution: The classical lower bound exploits strong nonlocality in cluster states, whose input-output correlations also appear in the Hidden Linear Function problem.The quantum algorithm consists of two layers of single-qubit gates and a constant-depth implementation of U_q.
2 Preliminaries
The preliminaries define the circuit models used for the separation and introduce graph states as stabilizer states. Classical circuits are represented as directed acyclic graphs with bounded fan-in and analyzed through correlations and light cones.
- Quantum circuits: A quantum circuit is a sequence of layers of one- and two-qubit gates, with disjoint gate supports within each layer.The circuit unitary is expressed as a product of layer unitaries.
- Classical circuits: Classical circuits are directed acyclic graphs whose gates compute Boolean functions of their incoming bits and copy outputs along outgoing edges.The number of incoming edges is the gate's fan-in, while outgoing edges determine fan-out.
- Classical circuits: Probabilistic classical circuits may append random input bits drawn from an arbitrary distribution to the fixed input.The input is decomposed as x = x′r, where r is the random string.
- Classical circuits: Two variables are correlated when flipping an input bit can flip an output bit for some input assignment, and this requires a path through the circuit.Light cones collect the correlated outputs of an input or correlated inputs of an output.
- Classical circuits: An NC0 circuit has constant depth and bounded fan-in K = O(1), so each output bit can depend on only a constant number of input bits.This locality of dependence is captured by the circuit's light-cone structure.
- Graph states: A graph state is a stabilizer state uniquely characterized by the simultaneous +1 eigenvalue conditions of its graph-derived stabilizer generators.The construction associates a state to a finite simple graph G = (V, E).
3 Hidden linear function problems
The paper defines Hidden Linear Function problems by encoding a linear Boolean function inside a Z4-valued quadratic form, then specializes to 2D grid instances. These instances separate constant-depth quantum and classical circuits: quantum circuits solve them deterministically, while bounded-fan-in classical circuits require logarithmic depth.
- Hidden linear structure: The restriction of q to Lq is linear modulo two, so q(x) = 2z^T x for some binary vector z.Lq is a linear subspace and q(x) takes values in {0, 2} on it.
- Problem definition: The Hidden Linear Function problem asks for a binary vector z satisfying q(x) = 2z^T x for every x in the subspace Lq.The vector z may be non-unique because the hidden function is defined only on Lq.
- Quantum algorithm: A quantum circuit applies the quadratic-form unitary and Hadamards, producing an output z uniformly from the set of valid solutions.The output distribution has support exactly on valid solutions, so the circuit succeeds with probability 1.
- 2D specialization: For 2D instances, the matrix A specifies only nearest-neighbor edges of an N × N grid, with n = N^2 output bits.The input consists of the quadratic form parameters A and b, and the solution remains a binary vector satisfying the same restriction on Lq.
- 2D specialization: The 2D quantum algorithm has constant depth and uses one- and two-qubit gates that are geometrically local on the grid.The circuit can be embedded with O(1) qubits per vertex, while its controlled gates are decomposed over the Clifford+T gate set.
4 Nonlocality thwarts shallow classical circuits
The section uses quantum nonlocality in graph-state measurements to show that shallow bounded-fan-in classical circuits cannot reproduce the 2D Hidden Linear Function correlations. A lightcone argument then yields the logarithmic classical-depth lower bound.
- 4.1 Geometric nonlocality in a 1D graph state: Graph-state measurement statistics exhibit correlations that cannot be reproduced by local hidden-variable models, even with limited communication.The construction uses an even cycle and measurements in X or Y bases determined by input bits.
- 4.1 Geometric nonlocality in a 1D graph state: Any classical circuit satisfying the cycle correlations with success probability above 7/8 must have an input lightcone reaching an output at distance at least D/2.If all relevant lightcones remained local, fixing the random string would produce an output outside the valid outcome set for some measurement setting.
- 4.1 Geometric nonlocality in a 1D graph state: For an even cycle, valid measurement outcomes satisfy product constraints involving outputs on the three sides and selected measurement settings.The outcome set T(b) is defined by measuring u, v, and w in bases chosen by b, while the remaining qubits are measured in the X basis.
- 4.2 Proof of Theorem 2: A required Ω(N)-distance lightcone contradicts the box-locality bounds, proving that the assumed shallow classical circuit cannot solve the problem.The contradiction follows because the lightcone must lie inside the corresponding box, whose cycle distance is at most N^1/2.
5 Conclusions and open problems
The paper concludes that shallow quantum circuits are more powerful than their classical counterparts and identifies unresolved questions about stronger classical circuit models and quantum sampling.
- Conclusions: The paper concludes that shallow quantum circuits are more powerful than their classical counterparts.
- Open problems: It remains open whether the 2D Hidden Linear Function problem resists simulation by AC0 circuits with unbounded fan-in.The authors also question whether the 7/8 success threshold can be reduced as a function of N.
- Open problems: It remains open whether constant-depth quantum circuits can sample distributions that constant-depth classical circuits cannot.The paper notes that a characterization of distributions generated by shallow classical circuits does not establish whether shallow quantum distributions share that property.
A Proof of Claim 2
The proof establishes that the interaction function J associated with the quadratic form is a symmetric bilinear form over the binary field, then uses this structure to prove the claim about Γ(K, z).
- A Proof of Claim 2: J is shown to be a symmetric bilinear form, J(x, y) = 2x^TBy modulo four for a symmetric binary matrix B.The proof derives bilinearity from a vanishing third discrete derivative of the quadratic form.
- A Proof of Claim 2: Every vector z is decomposed as z = B(w ⊕ w′) ⊕ v with w ∈ K, w′ ∈ Lq, and v ∈ K⊥.This decomposition uses the image and kernel relationships established in the proof.
- A Proof of Claim 2: The phase relation reduces (−1)^zT x · i^q(x) to i^{J(w,x)+q(x)} = i^{q(w⊕x)−q(w)} for all x ∈ K.The resulting expression shows that the absolute value of Γ(K, z) is independent of z.
- A Proof of Claim 2: The proof combines the Γ identities with the preceding claim to obtain the stated result.The final algebraic combination yields the claim directly.
B Proof of Claim 4
The proof analyzes affine Boolean expressions on the even-parity inputs and shows that their required sign pattern is inconsistent, preventing the relevant sum from reaching four.
- B Proof of Claim 4: For even-parity inputs, x1x3 and x2x3 can be rewritten using x1x2, x1, and x2.These identities simplify the quadratic expression on the restricted input set.
- B Proof of Claim 4: The resulting exponent is an affine Boolean function, as is e(x), so equality would require a corresponding affine sign pattern.The proof reduces the target equality to conditions on four even-parity assignments.
- B Proof of Claim 4: The four equations w0 = 0, w1 ⊕ w2 = 1, w1 ⊕ w3 = 1, and w2 ⊕ w3 = 1 have no solution over F2.Therefore the sum is strictly less than 4.