Technical Summary: Unconditional Quantum Advantage for Sampling with Shallow Circuits

Problem Statement

The paper addresses the question of whether constant-depth quantum circuits ($QNC_0$) can perform sampling tasks that are impossible for constant-depth classical circuits with bounded fan-in ($NC_0$), specifically in an input-independent setting.

While previous work by Bravyi, Gosset, and Koenig established an unconditional separation between $QNC_0$ and $NC_0$ for search problems (mapping inputs to valid outputs), the question remained open for sampling problems where the goal is to generate samples from a fixed distribution $D_n$ without a specific computational input. In the input-dependent setting, classical hardness often relies on complexity-theoretic conjectures (e.g., $P \neq NP$). In the input-independent setting, the challenge is to prove that a classical circuit, given only a fixed number of random bits, cannot reproduce the output distribution of a shallow quantum circuit, even up to additive error (total variation distance).

Methodology

The authors construct a specific family of distributions $\{D_n\}$ and demonstrate a separation through a three-part methodology:

1. Quantum Construction with GHZ Advice

The authors first design a constant-depth quantum circuit that samples from a distribution close to $(X, \text{majmod}_p(X) \oplus \text{parity}(X))$, where $X$ is a uniformly random bitstring and $\text{majmod}_p$ is a "Majority mod $p$" function.

• Initial Approach: They utilize a "self-controlled" non-unitary rotation gate $A_\theta$ acting on a GHZ state ($|GHZ_n\rangle = \frac{1}{\sqrt{2}}(|0^n\rangle + |1^n\rangle)$). This allows the circuit to correlate the final output bit with the Hamming weight of the input bits modulo $p$.
• Unitary Compilation: To make the circuit physical, they replace the non-unitary gates with multi-qubit unitary gates $U_{m,\theta}$. They prove that these unitaries can approximate the non-unitary operations with high fidelity on the GHZ state while maintaining constant depth.
• Result: A constant-depth quantum circuit with access to a GHZ state (treated as "advice") can sample from the target distribution with low total variation distance.

2. Removing the GHZ Advice (Poor Man's GHZ)

To achieve a separation without external advice, the authors replace the input GHZ state with a "Poor Man's GHZ" state.

• Construction: This state is generated by a constant-depth circuit acting on $2n-1$ qubits (based on a binary tree structure) followed by measurements of $n-1$ auxiliary qubits.
• Adaptation: The measurement outcomes of the auxiliary qubits introduce Pauli errors (sign flips) on the remaining state. Instead of correcting these errors (which would require logarithmic depth), the authors absorb the errors into the definition of the target distribution.
• New Distribution: The resulting circuit samples from a modified distribution $(Z, \text{pmmajmod}_p(Z))$. The function $\text{pmmajmod}_p$ is a weighted sum of bits where the weights depend on the structure of the binary tree used to generate the state.

3. Classical Lower Bounds

The authors prove that any constant-depth classical circuit with bounded fan-in cannot sample from these distributions if the number of random input bits is bounded.

• Technique: They adapt techniques from Viola's work on sampling hardness. The proof relies on the concept of locality. A constant-depth circuit with bounded fan-in has limited locality; its output bits depend on only a small subset of input bits.
• Statistical Test: They construct a statistical test (a set of "bad" strings) that the target distribution passes with very low probability, but any local function (classical circuit) passes with high probability.
• Key Insight: For the distribution $(X, \text{majmod}_p(X) \oplus \text{parity}(X))$, fixing a large portion of the input bits leaves the Hamming weight of the remaining bits as a sum of independent random variables. The authors show that a local function cannot simultaneously satisfy the parity and majority-mod-$p$ constraints on these sums.
• Extension to $\text{pmmajmod}_p$: For the distribution without GHZ advice, the dependence structure is more complex due to the tree-based weights. The authors partition the output variables into "forest" blocks based on the binary tree structure. They show that even with this complex dependence, fixing enough input bits isolates independent blocks, allowing the same lower bound logic to apply.

Key Contributions and Results

1. Unconditional Separation for Sampling: The paper provides the first unconditional proof that constant-depth quantum circuits can sample from distributions that constant-depth classical circuits with bounded fan-in cannot, even up to additive error.

   • Theorem 3: For any $\delta < 1$, there exists a distribution $D_n$ such that a constant-depth quantum circuit samples from it with distance $\le 1/6 + O(n^{-c})$, while any classical circuit with $n + n^\delta$ random input bits and bounded fan-in requires depth $\Omega(\log \log n)$ to achieve distance $\le 1/2 - \omega(1/\log n)$.

2. Handling Randomness Constraints: The separation holds specifically when the classical circuit's access to randomness is bounded (specifically $n + n^\delta$ bits). The authors note that if the classical circuit has access to an unbounded number of random bits, it can trivially simulate the distribution. However, they also show a separation for classical circuits with unbounded inputs but bounded fan-out, provided they have access to quantum advice.

3. Robustness to Biased Inputs: The authors extend their lower bounds to classical circuits that receive biased random inputs (Bernoulli variables with entropy $1/k$), provided the total entropy is bounded. This addresses potential concerns that the separation relies on the classical circuit having access to perfectly uniform randomness.

4. Explicit Circuit Constructions: The paper details the construction of the quantum circuits using standard gate sets (single-qubit gates and CNOTs), proving they form a uniform family. It also provides the specific mathematical definitions for the "Poor Man's GHZ" state and the resulting sampling distribution.

Significance

The paper claims significance in the following areas:

• Input-Independent Quantum Advantage: It answers a specific question posed by Bravyi, Gosset, and Koenig regarding input-independent sampling, demonstrating that quantum advantage is not limited to search problems or input-dependent tasks.
• Unconditional Hardness: Unlike many sampling hardness results (e.g., Random Circuit Sampling) which rely on unproven complexity conjectures (like the non-collapse of the polynomial hierarchy), this result is unconditional. It relies only on the structural limitations of constant-depth classical circuits.
• State Preparation Complexity: The results have implications for the complexity of state preparation. Since sampling from a distribution $(X, f(X))$ is classically analogous to preparing a specific quantum state, the separation suggests that certain quantum states (and their associated distributions) are inherently difficult for shallow classical circuits to prepare or simulate, even with randomness.
• Refining the Boundary: The work refines the understanding of the power of shallow quantum circuits by showing they can generate correlations (specifically involving parity and majority-mod-$p$) that shallow classical circuits cannot replicate, even when the classical circuits are allowed a small amount of extra randomness.

The authors remain modest, noting that their classical lower bound applies only when the number of random bits is bounded (specifically $n + n^\delta$). They acknowledge that extending these bounds to classical circuits with unbounded randomness remains an open problem, though they make progress in the bounded fan-out setting.