Sampling hard circuits with verifiably high fidelity

Problem Statement

Demonstrating quantum advantage via sampling-based proposals (e.g., Random Circuit Sampling) faces two critical bottlenecks in the near-term era:

1. Error Suppression: Increasing circuit size to achieve classical hardness typically amplifies hardware noise, causing the output distribution to become trivial and classically simulable. Existing hardware-friendly proposals lack low-overhead error protection, while structured proposals are difficult to map to near-term hardware in classically hard regimes.
2. Verification: Verifying that a complex quantum computation was performed with high fidelity is difficult. Resolving fidelity in broadly distributed outputs requires a prohibitive number of samples. Existing benchmarks (like Cross-Entropy Benchmarking, XEB) rely on strong assumptions about noise (e.g., spatial homogeneity, temporal independence) or require expensive classical simulation to serve as a proxy.

The authors aim to develop a protocol that simultaneously achieves provable classical hardness, high-fidelity execution via error detection, and device-dependent verification with weaker noise assumptions than current benchmarks.

Methodology: Doped Clifford Sampling (DCS)

The authors propose a protocol called Doped Clifford Sampling (DCS) which combines structured Clifford circuits with non-Clifford "magic" resources, all encoded within a spacetime code.

1. Circuit Construction:

• Clifford Backbone: The experiment begins with a random, highly entangling Clifford circuit (specifically a brickwork pattern of depth $n$ on $n$ qubits). This structure is chosen because it can be efficiently encoded and its output fidelity can be measured directly.
• Spacetime Encoding: The Clifford circuit is encoded using spacetime codes. This involves adding ancilla qubits to perform Pauli checks (syndrome measurements) distributed across both space and time. These checks detect errors by measuring syndromes; shots with non-zero syndromes are post-selected (discarded). This effectively projects the state into a low-error subspace.
• T-Gate Doping: To introduce classical hardness, the circuit is "doped" with non-Clifford $T$ gates. Crucially, these $T$ gates are placed only on spacetime wires that commute with the code stabilizers (specifically, they commute with the back-cumulants of the Pauli checks).
  • Because the $T$ gates commute with the checks, they do not alter the syndrome distribution.
  • On superconducting hardware, $Z$-rotations (including $T$ gates) are implemented virtually via frame tracking, meaning they introduce negligible additional noise.

2. Fidelity Certification Logic:
The core innovation is a method to lower-bound the fidelity of the hard, doped state ($F_2$) using the measurable fidelity of the undoped Clifford state ($F_1$).

• Invariance: Since $T$ gates commute with the checks, the set of accepted faults (syndromes) remains identical for both the doped and undoped circuits.
• Harmless vs. Harmful: In the undoped Clifford circuit, some faults are "harmless" (they stabilize the state) and some are "harmful." Doping can potentially convert a previously harmless fault into a harmful one, reducing fidelity.
• The Bound: The authors prove that the probability of a harmless fault converting to a harmful one is asymptotically small (inverse polynomial in $n$) for random Clifford circuits.
• Result: The fidelity of the doped state is lower-bounded by:
  $$F_2 \ge F_1 - \text{Pr}(\text{harmless} \mid \text{accepted})$$
  This allows the authors to estimate $F_2$ without needing to simulate the hard doped circuit, relying only on the measurable $F_1$ and a theoretical bound on fault conversion.

Experimental Results

The protocol was demonstrated on a 70-qubit, depth-70 Clifford circuit doped with 468 $T$ gates, executed on an IBM superconducting processor (IBM Boston) using 97 physical qubits (70 data + 27 ancilla).

• Error Suppression: Syndrome post-selection suppressed gate error rates by a factor of 10$\times$ compared to the physical error rate. The encoded Clifford reference state achieved a fidelity of 0.32(1) (0.57(2) with readout mitigation).
• Fidelity Lower Bound: Based on the measured Clifford fidelity and the estimated probability of harmless fault conversion (0.013), the authors established a 95% confidence lower bound of 0.284 for the fidelity of the classically hard, doped state.
• Classical Hardness: The experiment generated ~2,000 samples in 16 minutes. The authors estimate this instance is infeasible for current tensor-network and stabilizer-based algorithms.
  • Tensor Networks: The circuit exhibits high entanglement (minimum bipartite rank of 30), requiring bond dimensions ($2^{30}$) that exceed the memory of current frontier supercomputers.
  • Stabilizer Decomposition: With 468 $T$ gates, the stabilizer rank is too high for efficient simulation ($\Omega(2^{0.228 \times 468})$).
• Validation: The fidelity bound was validated in intermediate regimes (low and medium $T$ counts) using Direct Fidelity Estimation (DFE) and Cross-Entropy Benchmarking (XEB), confirming the theoretical bound holds.

Key Contributions

1. Structured Hardness with Error Detection: The paper introduces a systematic method to promote a stabilizer state to a magic state (via $T$-doping) while preserving the error-detection capabilities of a spacetime code. This allows for high-fidelity execution of classically hard circuits.
2. Device-Dependent Fidelity Certificate: The authors provide a certificate for the fidelity of a hard quantum state that requires substantially weaker noise assumptions than existing proxies (like XEB). It does not assume spatially homogeneous or temporally independent noise, only a general Pauli noise model (attainable via twirling).
3. Experimental Demonstration: The work demonstrates the first sampling experiment that combines algorithm-agnostic hardness guarantees with trusted execution of deep, error-detected circuits on current hardware.

Significance and Claims

The paper claims to address the "scaling problem" in quantum advantage demonstrations: the difficulty of simultaneously scaling circuit size, suppressing noise, and verifying the result.

• Coexistence of Hardness and Trust: The primary significance is demonstrating that provable classical hardness and trusted execution (via error detection and fidelity certification) can coexist.
• Scalability Path: While the current approach relies on post-selection (which has overhead), the authors argue that the same spacetime codes can be adapted for fault-tolerant quantum advantage as hardware improves.
• Verification Robustness: The method relaxes the stringent noise assumptions required by XEB, making verification more robust against realistic, correlated hardware noise.

The authors remain modest regarding the absolute scale of the advantage, noting that simulation times may change with better algorithms or hardware, but emphasizing that the structural guarantee of hardness combined with verified fidelity is the key achievement. They leave open the possibility of faster simulations with improved algorithms but assert that their specific instance is currently intractable for state-of-the-art methods.