Complexity and hardness of random peaked circuits

Yuxuan ZhangarXiv 2025 · DOI · arXiv

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.

Overview of Random Peaked Circuits (RPCs) illustrating their circuit structure, the resulting peaked probability distribution, and their core computational properties.

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:

  1. Variational Search: The author uses the Adam optimizer to numerically find parameters for $C'$ that create a peak.
  2. 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.
The circuit stitching strategy (left) and numerical validation (right) showing that optimized circuits follow the same scaling behavior as the theoretical postselection model.

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

Abstract

Near-term feasibility, classical hardness, and verifiability are the three requirements for demonstrating quantum advantage; most existing quantum advantage proposals achieve at most two. A promising candidate recently proposed is through randomly generated peaked circuits. In this work, we study an explicit construction for random peaked circuits: first selecting a random circuit $C$ of polynomial size, which forms a $k$-design. Subsequently, a second random circuit $C'$ is chosen from the same architecture, subject to a postselection criterion: $C'$ must exhibit a high overlap with $C$ in one of their rows. Utilizing unitary design properties, we demonstrate that the circuits generated by this method are non-trivial; specifically, $C'$ is provably far from $C^\dagger$. Indeed, with overwhelmingly high probability, a random peaked circuit generated this way is non-compressible and is of circuit complexity $\tilde Ω(nk)$. This resolves an open problem posed by Aaronson in 2022. Secondly, we analytically establish that estimating the peakedness of a random peaked circuit to within a $2^{-\text{poly}(n)}$ additive error, is average-case \#P-hard. When the additive error is relaxed to $1/\text{poly}(n)$, we note that the worst-case scenario for this problem is BQP-complete. Under widely accepted assumptions on random quantum circuits, we identify a regime where no classical polynomial-time sequential simulator attains inverse-polynomial additive accuracy on the peak on a non-negligible fraction of instances. Thirdly, we study using peaked circuits as a practical attempt for a verifiable quantum advantage protocol. While the postselection method for generating peaked circuits could be costly, we demonstrate that numerical search for $C'$ with randomized initialization successfully returns a random peaked circuit, achieving the properties as theoretically predicted.
BibTeX
@misc{zhang2025complexity,
  author = {Yuxuan Zhang},
  title = {{Complexity and hardness of random peaked circuits}},
  year = {2025},
  eprint = {2510.00132},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2510.00132},
}
Figure