Abstract Constant‐depth quantum circuits that prepare and measure graph states on 2D grids are proved to possess a computational quantum advantage over their classical counterparts due to quantum nonlocality and are also well suited for demonstrations on current superconducting quantum processor architectures. To simulate the partial or full sampling of 2D graph states, a practical two‐stage classical strategy that can exactly generate any number of samples (bit strings) from such circuits is proposed. The strategy is inspired by exploiting specific properties of a hidden linear function problem solved by the target quantum circuit, which in particular combines traditional classical parallel algorithms and an explicit gate‐based constant‐depth classical circuit together. A theoretical analysis reveals that on average each sample can be obtained in nearly constant time for sampling specific circuit instances of large size. Moreover, the feasibility of the theoretical model is demonstrated by implementing typical instances up to 25 qubits on a moderate field programmable gate array platform. Therefore, the strategy can be used as a practical tool for verifying experimental results obtained from shallow quantum circuits of this type.
Abstract Constant‐depth quantum circuits that prepare and measure graph states on 2D grids are proved to possess a computational quantum advantage over their classical counterparts due to quantum nonlocality and are also well suited for demonstrations on current superconducting quantum processor architectures. To simulate the partial or full sampling of 2D graph states, a practical two‐stage classical strategy that can exactly generate any number of samples (bit strings) from such circuits is proposed. The strategy is inspired by exploiting specific properties of a hidden linear function problem solved by the target quantum circuit, which in particular combines traditional classical parallel algorithms and an explicit gate‐based constant‐depth classical circuit together. A theoretical analysis reveals that on average each sample can be obtained in nearly constant time for sampling specific circuit instances of large size. Moreover, the feasibility of the theoretical model is demonstrated by implementing typical instances up to 25 qubits on a moderate field programmable gate array platform. Therefore, the strategy can be used as a practical tool for verifying experimental results obtained from shallow quantum circuits of this type.
Recently, constant-depth quantum circuits are proved more powerful than their classical counterparts at solving certain problems, e.g., the two-dimensional (2D) hidden linear function (HLF) problem regarding a symmetric binary matrix. To further investigate the boundary between classical and quantum computing models, in this work we propose a high-performance two-stage classical scheme to solve a full-sampling variant of the 2D HLF problem, which combines traditional classical parallel algorithms and a gate-based classical circuit model together for exactly simulating the target shallow quantum circuits. Under reasonable parameter assumptions, a theoretical analysis reveals our classical simulator consumes less runtime than that of near-term quantum processors for most problem instances. Furthermore, we demonstrate the typical all-connected 2D grid instances by moderate FPGA circuits, and show our designed parallel scheme is a practically scalable, high-efficient and operationally convenient tool for simulating and verifying graph-state circuits performed by current quantum hardware.
We consider quantum circuits consisting of d layers of nearest-neighbor two-qubit gates acting on n qubits arranged on a line, where every qubit is independently depolarized with a constant probability before each layer. We describe a randomized parallel algorithm which samples from the output distribution of any such circuit to within total variation error δ, with parallel runtime 2O(d)loglog(n/δ) and n2O(d) elementary real-arithmetic operations. Without noise, the same approach gives an exact sampler with parallel runtime O(logn). For constant depth, we further show that the input/output behavior of the noisy quantum circuit is reproduced up to a constant error by a randomized AC0-circuit, that is, a Boolean circuit of polynomial size and constant depth with unbounded fan-in AND and OR gates and NOT gates. Consequently, every relation problem solved by a noisy constant-depth quantum circuit in one dimension is also solved, with essentially the same success probability, by a randomized AC0-circuit. This rules out, for noisy circuits in one dimension, the unconditional quantum advantage established for noisy shallow circuits in two and three dimensions, where polynomial-size classical circuits over the same gate set require depth Ω(logn/loglogn). Our algorithm exploits the fact that depolarizing noise cuts a one-dimensional circuit into independent pieces of logarithmic width, each of which can be sampled exactly in parallel.
We give a sampling problem that is solvable by shallow quantum circuits, hard for polynomial-time classical algorithms under lattice-based assumptions, and efficiently verifiable by a classical computer. The quantum sampler admits two implementations: one uses log-logarithmic-depth quantum circuits with one- and two-qubit gates, i.e., QNC0[loglog] circuits, while the other uses constant-depth quantum circuits with unbounded fan-in gates, i.e., QAC0 circuits. Our construction can be seen as compiling the Learning with Errors (LWE)-based single-round proof of quantumness of Arabadjieva et al. (2025) to very low depth. The price paid for this compilation is the reliance on less standard, though well-motivated, assumptions: in addition to the lattice knowledge assumption used by Arabadjieva et al. (2025), we require a strengthened variant of the adaptive-hardcore-bit property of LWE, for which we provide supporting evidence. Unlike previous low-depth proofs of quantumness, the quantum computation here requires no mid-circuit measurements or feed-forward: it consists only of running a shallow circuit and sampling from its output distribution. This shows that shallow quantum circuits have sufficient structure to solve certain classically hard tasks whose solutions can be verified efficiently.
A central question of quantum computing is determining the source of the advantage of quantum computation over classical computation.Even though simulating quantum dynamics on a classical computer is thought to require exponential overhead in the worst case, efficient simulations are known to exist in several special cases.It was widely assumed that these easy-to-simulate cases as well as any yetundiscovered ones could be avoided by choosing a quantum circuit at random.We prove that this intuition is false by showing that certain families of constant-depth, 2D random circuits can be approximately simulated on a classical computer in time only linear in the number of qubits and gates, even though the same families are capable of universal quantum computation and are hard to exactly simulate in the worst case (under standard hardness assumptions).While our proof applies to specific random circuit families, we demonstrate numerically that typical instances of more general families of sufficiently shallow constantdepth 2D random circuits are also efficiently simulable.We propose two classical simulation algorithms.One is based on first simulating spatially local regions which are then "stitched" together via recovery maps.The other reduces the 2D simulation problem to a problem of simulating a form of 1D dynamics consisting of alternating rounds of random local unitaries and weak measurements.Similar processes have recently been the subject of an intensive research focus, which has observed that the dynamics generally undergo a phase transition from a low-entanglement (and efficient-to-simulate) regime to a highentanglement (and inefficient-to-simulate) regime as measurement strength is varied.Via a mapping from random quantum circuits to classical statistical mechanical models, we give analytical evidence that a similar computational phase transition occurs for both of our algorithms as parameters of the circuit architecture like the local Hilbert space dimension and circuit depth are varied and, additionally, that the effective 1D dynamics corresponding to sufficiently shallow random quantum circuits falls within the efficient-to-simulate regime.Implementing the latter algorithm for the depth-3 "brickwork" architecture, for which exact simulation is hard, we find that a laptop could simulate typical instances on a 409 × 409 grid with a total variation distance error less than 0.01 in approximately one minute per sample, a task intractable for previously known circuit simulation algorithms.Numerical results support our analytic evidence that the algorithm is asymptotically efficient.
Experimental tests of shallow-circuit quantum advantage require explicit classical bounds at finite circuit sizes. We refine the finite-size classical soundness bound of Aasnaess's graph-distributed construction to depend linearly on the number of players. Combined with standard disjoint-player repetition, this gives a two-round test on a single processor for any finite nonlocal game with a finite-dimensional perfect quantum strategy and classical winning probability γ<1, with arbitrarily small classical success. The method is based on playing m copies with disjoint players and teleporting each player's register to a uniformly random one of N sites before the questions are revealed. Each answer bit of a depth-D, fan-in-K classical response with fixed wiring depends on at most KD question wires, making cross-player dependencies unlikely when N is large. The quantum implementation has constant depth per round and wins with certainty. A classical device wins with probability at most γm+O(mKD/N), which vanishes as O(logN/N) for m=⌈log1/γN⌉ at fixed D and K. We present an explicit proposal for an experimentally testable quantum advantage with 99 qubits.
We study random constant-depth quantum circuits in a two-dimensional (2D) architecture. While these circuits only produce entanglement between nearby qubits on the lattice, long-range entanglement can be generated by measuring a subset of the qubits of the output state. It is conjectured that this (MIE) proliferates when the circuit depth is at least a constant critical value d ∗ . For circuits composed of Haar-random two-qubit gates, it is also believed that this coincides with a in the classical hardness of sampling from the output distribution. Here, we provide evidence for a quantum advantage phase transition in the setting of random circuits. Our work extends the scope of recent separations between the computational power of constant-depth quantum and classical circuits, demonstrating that this kind of advantage is present in canonical random circuit sampling tasks. In particular, we show that in any architecture of random shallow Clifford circuits, the presence of long-range MIE gives rise to an unconditional quantum advantage. In contrast, any depth- d 2D quantum circuit that satisfies a short-range MIE property can be classically simulated efficiently and with depth O ( d ) . Finally, we introduce a 2D depth- 2 “coarse-grained” circuit architecture, composed of random Clifford gates acting on O ( log ( n ) ) qubits, for which we prove the existence of long-range MIE and establish an unconditional quantum advantage.