Peaked quantum circuits, whose output distribution is sharply concentrated on a single bitstring, have emerged as a promising candidate for verifiable quantum advantage, as the correctness of the quantum output can be checked by simply comparing against the known peak. Recent work by Gharibyan et al. arXiv:2510.25838 claimed heuristic quantum advantage using peaked circuits executed on Quantinuum's 56-qubit H2 processor. These peaked circuits concentrate their output on a single hidden bitstring by training a shallow simulable circuit variationally and inserting an obfuscated permutation to increase the depth to a level that makes classical simulation intractable, with estimated runtimes of years for the largest instances. We show that these circuits can be efficiently simulated classically. We describe a method that efficiently performs a full tensor network contraction, allowing near-exact sampling and extraction of the peaked bitstring. The method exploits the mirrored structure of the circuit and iteratively cancels both halves into a Matrix Product Operator (MPO), and avoids the obfuscated permutation by greedily reducing the MPO bond dimension through a process we call unswapping. The method can fully contract and extract the peak of the largest circuit in approximately one hour on a single GPU, around half the time it took to run on the quantum hardware.
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.
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.
The matrix product state (MPS) belongs to the most important models in, for example, quantum information sciences and condensed-matter physics. However, realizing an
N-qubit MPS with large
N and large entanglement on a quantum platform is extremely challenging, since it requires high-level qudits or
n-qubit gates with $n\ensuremath{\gg}2$ to carry or produce the entanglement. In this work, an efficient method that accurately encodes a given MPS into a quantum circuit with only one- and two-qubit gates is proposed. Essentially different from the existing compiling methods, our idea is to construct the unitary matrix product operators that optimally disentangle the MPS to a product state. These matrix product operators form the quantum circuit that evolves a product state to the targeted MPS with a high fidelity. Our benchmark on the ground-state MPSs of the strongly correlated spin models show that the constructed quantum circuits can simulate the MPSs with much fewer qubits than the sizes of the MPSs themselves. This method paves a feasible and efficient path to realizing useful and/or exotic quantum states and MPS-based models as quantum circuits on near-term quantum platforms.
Peaked circuits are random quantum circuits whose measurement returns one bitstring far more often than chance. The probability of that string is the peakedness, and a verifier who knows the string checks the device in a few shots. Peaked circuits are a candidate route to verifiable quantum advantage, and classical generation is the bottleneck. Aaronson and Zhang train a variational circuit by gradient descent, and the peakedness they reach decays exponentially with the number of qubits. They state that either their optimizer stalls or no efficient generation method exists. Here we show that no bare fixed base fits the decay we measure and that neither the barren plateau nor fragmentation of the solution set explains it. We measure the optimization landscape on eighteen instances per size, from eight to sixteen qubits, under a protocol whose falsifiers were fixed in advance. The decay steepens as the qubit number grows, leaving extrapolations to larger devices unsupported. A better optimizer exists, but it gains a few percent and the peakedness it reaches decays at nearly the same rate. Aaronson and Zhang attribute the difficulty to a barren plateau. The plateau is present, but the second-order amplitude data are depth-independent while the attained peakedness is not. Independent runs land on uncorrelated solutions, yet paths connecting them stay well above the scale of a random state, so fragmentation fails at that scale. In the deep limit we take the scrambled state Haar-random. There we prove that no search over a polynomial-parameter Lipschitz family, exhaustive search included, beats the scale of a random state by more than a poly(n) factor on average. Both branches of the Aaronson-Zhang alternative therefore stay open. A generation method must beat a preregistered baseline, and a hardness argument must accommodate a solution set connected at the scale of a random state.
Matrix product state (MPS) belongs to the most important mathematical models in, for example, condensed matter physics and quantum information sciences. However, to realize an
N-qubit MPS with large
N and large entanglement on a quantum platform is extremely challenging, since it requires high-level qudits or multi-body gates of two-level qubits to carry the entanglement. In this work, an efficient method that accurately encodes a given MPS into a quantum circuit with only one- and two-qubit gates is proposed. The idea is to construct the unitary matrix product operators that optimally disentangle the MPS to a product state. These matrix product operators form the quantum circuit that evolves a product state to the targeted MPS with a high fidelity. Our benchmark on the ground-state MPS's of the strongly-correlated spin models show that the constructed quantum circuits can encode the MPS's with much fewer qubits than the sizes of the MPS's themselves. This method paves a feasible and efficient path to realizing quantum many-body states and other MPS-based models as quantum circuits on the near-term quantum platforms.