Peaked circuits are random quantum circuits whose measurement returns one bitstring far more often than chance. They are a candidate route to verifiable quantum advantage, and the bottleneck is classical generation. Aaronson and Zhang fix a random circuit, append a trainable brickwall of half that depth, and optimize it by gradient descent to raise the probability of one chosen output string. Their method plateaus at a size-dependent ceiling, which they attribute to a barren plateau. A dichotomy remains open: either the optimizer stops short, so a better algorithm would reach higher, or no efficient method exists. We map the landscape on which the answer depends. Across 18 instances per size at n = 8-16, at fixed and converged budgets, no fixed-base exponential, the law they fit, matches the optimizer's reach: at convergence the decay steepens from 1.16 to 1.295 per qubit through n = 16 (p = 0.011 frozen and 0.025 converged, on n = 8-14 alone), leaving their n = 50 estimate unsupported; at n = 16 they report more than we reach at any budget measured. One optimizer beats ours: L-BFGS-B ends 3.9 +/- 1.6% above converged Adam at n = 16, on three instances. That margin retires our hardness conjecture under its registered rule and leaves the rate untouched: every optimizer measured loses a factor 1.3 per qubit. The barren plateau is present and cannot explain that rate: the reach sits far above the Haar floor 2^-n, and the exact second-order amplitude data are depth-independent while the reach is not. Nor do solutions cluster at that floor: they are decorrelated yet path-connected by paths 10^2-10^3 above 2^-n whose floor falls from 0.73 to 0.23 of the endpoints. Path search is one-sided, so near-optimal clustering stays open. In the deep limit we prove no poly(n)-parameter family beats poly(n) 2^-n on average. What survives: a connected landscape and a shrinking reach.
Comments
33 pages, 6 figures, 2 tables. Analysis code, logs and data archived on Zenodo (doi:10.5281/zenodo.21893815, doi:10.5281/zenodo.21893670); see the Data and code availability section
Peaked circuits are random quantum circuits whose measurement returns one bitstring far more often than chance. They are a candidate route to verifiable quantum advantage, and the bottleneck is classical generation. Aaronson and Zhang fix a random circuit, append a trainable brickwall of half that depth, and optimize it by gradient descent to raise the probability of one chosen output string. Their method plateaus at a size-dependent ceiling, which they attribute to a barren plateau. A dichotomy remains open: either the optimizer stops short, so a better algorithm would reach higher, or no efficient method exists. We map the landscape on which the answer depends. Across 18 instances per size at n = 8-16, at fixed and converged budgets, no fixed-base exponential, the law they fit, matches the optimizer's reach: at convergence the decay steepens from 1.16 to 1.295 per qubit through n = 16 (p = 0.011 frozen and 0.025 converged, on n = 8-14 alone), leaving their n = 50 estimate unsupported; at n = 16 they report more than we reach at any budget measured. One optimizer beats ours: L-BFGS-B ends 3.9 +/- 1.6% above converged Adam at n = 16, on three instances. That margin retires our hardness conjecture under its registered rule and leaves the rate untouched: every optimizer measured loses a factor 1.3 per qubit. The barren plateau is present and cannot explain that rate: the reach sits far above the Haar floor 2^-n, and the exact second-order amplitude data are depth-independent while the reach is not. Nor do solutions cluster at that floor: they are decorrelated yet path-connected by paths 10^2-10^3 above 2^-n whose floor falls from 0.73 to 0.23 of the endpoints. Path search is one-sided, so near-optimal clustering stays open. In the deep limit we prove no poly(n)-parameter family beats poly(n) 2^-n on average. What survives: a connected landscape and a shrinking reach.
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†. Indeed, with overwhelmingly high probability, a random peaked circuit generated this way is non-compressible and is of circuit complexity Ω~(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−poly(n) additive error, is average-case \#P-hard. When the additive error is relaxed to 1/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.
Over a decade after its proposal, the idea of using quantum computers to sample hard distributions has remained a key path to demonstrating quantum advantage. Yet a severe drawback remains: verification seems to require classical computation exponential in the system size, n. As an attempt to overcome this difficulty, we propose a new candidate for quantum advantage experiments with otherwise random "peaked circuits", i.e., quantum circuits whose outputs have high concentrations on a computational basis state. Naturally, the heavy output string can be used for classical verification. In this work, we analytically and numerically study an explicit model of peaked circuits, in which τr layers of uniformly random gates are augmented by τp layers of gates that are optimized to maximize peakedness. We show that getting 1/poly(n) peakedness from such circuits requires τp=Ω((τr/n)0.19) with overwhelming probability. However, we also give numerical evidence that nontrivial peakedness is possible in this model -- decaying exponentially with the number of qubits, but more than can be explained by any approximation where the output of a random quantum circuit is treated as a Haar-random state. This suggests that these peaked circuits have the potential for future verifiable quantum advantage experiments. Our work raises numerous open questions about random peaked circuits, including how to generate them efficiently, and whether they can be distinguished from fully random circuits in classical polynomial time.
Variational quantum algorithms are viewed as promising candidates for demonstrating quantum advantage on near-term devices. These approaches typically involve the training of parameterized quantum circuits through a classical optimization loop. However, they often encounter challenges attributed to the exponentially diminishing gradient components, known as the barren plateau (BP) problem. This work introduces a novel optimization approach designed to alleviate the adverse effects of BPs during circuit training. In contrast to conventional gradient descent methods with a small learning parameter, our approach relies on making a finite hops along the search direction determined on a randomly chosen subsets of the free parameters. The optimization search direction, together with the range of the search, is determined by the distant features of the cost-function landscape. This enables the optimization path to navigate around barren plateaus without the need for external control mechanisms. We have successfully applied our optimization strategy to quantum circuits comprising 21 qubits and 15000 entangling gates, demonstrating robust resistance against BPs. Additionally, we have extended our optimization strategy by incorporating an evolutionary selection framework, enhancing its ability to avoid local minima in the landscape. The modified algorithm has been successfully utilized in quantum gate synthesis applications, showcasing a significantly improved efficiency in generating highly compressed quantum circuits compared to traditional gradient-based optimization approaches.
Variational Quantum Algorithms are a vital part of quantum computing. It is a blend of quantum and classical methods for tackling tough problems in machine learning, chemistry, and combinatorial optimization. Yet as these algorithms scale up, they cannot escape the barren-plateau phenomenon. As systems grow, gradients can vanish so quickly that training deep or randomly initialized circuits becomes nearly impossible. To overcome the barren plateau problem, we introduce a two-stage optimization framework. First comes the convex initialization stage. Here, we shape the quantum energy landscape, the Hilmaton landscape, into a smooth, low-energy basin. This step makes gradients easier to spot and keeps noise from derailing the process. Once we have gotten a stable gradient flow, we move to the second stage: nonconvex refinement. In this phase, we let the algorithm wander through different energy minima, making the model more expressive. We show that our proposed algorithm theoretically reduces the dependence on the condition number of the underlying quantum least squares approximate matrix via Riemannian manifold optimization. Finally, we used our two-stage solution to perform quantum cryptanalysis of quantum key distribution protocol (i.e., BB84) to determine the optimal cloning strategies. The simulation results showed that our proposed two-stage solution outperforms its random initialization counterpart.
Many experimental proposals for noisy intermediate scale quantum devices involve training a parameterized quantum circuit with a classical optimization loop. Such hybrid quantum-classical algorithms are popular for applications in quantum simulation, optimization, and machine learning. Due to its simplicity and hardware efficiency, random circuits are often proposed as initial guesses for exploring the space of quantum states. We show that the exponential dimension of Hilbert space and the gradient estimation complexity make this choice unsuitable for hybrid quantum-classical algorithms run on more than a few qubits. Specifically, we show that for a wide class of reasonable parameterized quantum circuits, the probability that the gradient along any reasonable direction is non-zero to some fixed precision is exponentially small as a function of the number of qubits. We argue that this is related to the 2-design characteristic of random circuits, and that solutions to this problem must be studied.
Hybrid quantum-classical variational algorithms are one of the most propitious implementations of quantum computing on near-term devices, offering classical machine-learning support to quantum scale solution spaces. However, numerous studies have demonstrated that the rate at which this space grows in qubit number could preclude learning in deep quantum circuits, a phenomenon known as barren plateaus. In this work, we implicate random entanglement, i.e., entanglement that is formed due to state evolution with random unitaries, as a source of barren plateaus and characterize them in terms of many-body entanglement dynamics, detailing their formation as a function of system size, circuit depth, and circuit connectivity. Using this comprehension of entanglement, we propose and demonstrate a number of barren plateau ameliorating techniques, including initial partitioning of cost function and non-cost function registers, meta-learning of low-entanglement circuit initializations, selective inter-register interaction, entanglement regularization, the addition of Langevin noise, and rotation into preferred cost function eigenbases. We find that entanglement limiting, both automatic and engineered, is a hallmark of high-accuracy training and emphasize that, because learning is an iterative organization process whereas barren plateaus are a consequence of randomization, they are not necessarily unavoidable or inescapable. Our work forms both a theoretical characterization and a practical toolbox; first defining barren plateaus in terms of random entanglement and then employing this expertise to strategically combat them.