Author: Yuxuan Zhang
This paper explores the theoretical foundations and practical implementation of random peaked circuits (RPCs). These are quantum circuits that appear globally random but concentrate a significant portion of their output probability on a single "peaked" bitstring. Zhang proves that these circuits are classically hard to simulate and "incompressible," providing a robust framework for demonstrating verifiable quantum advantage on near-term hardware.
The Problem: The Verification Gap in Quantum Advantage
To prove "quantum advantage," a protocol must satisfy three criteria: near-term feasibility on noisy (NISQ) hardware, provable classical hardness, and efficient verifiability. While current methods like Random Circuit Sampling (RCS) demonstrate quantum advantage, they fail at verifiability. As the number of qubits grows beyond ~70, verifying the results requires exponential classical computation.
Peaked circuits solve this verification problem—a user simply checks if the output matches the expected "peak." However, critics have questioned whether these circuits are "too simple" or merely trivial variations of the identity matrix. Zhang addresses this by proving their complexity and providing a scalable path for their construction.
Theoretical Framework and Complexity
The paper models a peaked circuit as $P = C'^{\dagger} C$. In this construction, $C$ is a random circuit (a $k$-design), and $C'$ is another random circuit chosen via postselection to have a high overlap with $C$ in exactly one row.
Using unitary design theory and block decomposition, Zhang proves that these circuits are "incompressible," meaning they cannot be simplified into a significantly smaller number of gates. Furthermore, the paper establishes that estimating the peak's weight is average-case #P-hard—the same complexity class as counting the number of satisfying assignments for a logic formula. This confirms that RPCs are not "simple" circuits but are as random as possible while maintaining a verifiable peak.
Methods: Optimization and Circuit Stitching
Since theoretical postselection does not scale to large qubit counts, the paper introduces two practical methods for implementation:
- Variational Search: The author uses the Adam optimizer to numerically find parameters for $C'$ that create a peak.
- Circuit Stitching: To reach sizes beyond the limits of classical simulation, Zhang proposes "stitching" smaller peaked blocks together. This maintains the global peak while making the overall circuit structure appear as a scrambling "black box" to classical simulators.
Key Results
- Incompressibility: Proved that RPCs require a linear number of gates relative to the design order $k$, confirming they possess high circuit complexity.
- Simulation Hardness: Established that estimating the peak weight to within $2^{-poly(n)}$ error is average-case #P-hard. Even with a relaxed $1/poly(n)$ error, the problem remains PromiseBQP-complete.
- Noise Robustness: Analytical results show that the peak remains detectable under sparse bit-flip noise and global depolarizing noise, making the protocol viable for noisy NISQ devices.
- Numerical Success: Exact tensor-network contractions verified that numerically optimized circuits (for $n = 8$ to $12$ qubits) match the statistical properties predicted by the theoretical model.
Limitations and Future Outlook
While "stitching" provides a path to scalability, the initial numerical search for base peaked blocks is currently limited to classically simulable sizes (approximately 36 qubits). Future work will focus on establishing a formal complexity-theoretic proof for the hardness of "stitched" circuits and implementing the protocol on large-scale quantum hardware, such as superconducting or trapped-ion processors, to establish new benchmarks for quantum advantage.
Summary updated