Quantum theory promises computational speed-ups over classical approaches. The celebrated Gottesman-Knill Theorem implies that the full power of quantum computation resides in the specific resource of “magic” states—the secret sauce to establish universal quantum computation. However, it is still questionable whether magic indeed brings the believed quantum advantage, ridding unproven complexity assumptions or black-box oracles. In this work, we demonstrate the first unconditional magic advantage: a separation between the power of generic constant-depth or shallow quantum circuits and magic-free counterparts. For this purpose, we link the shallow circuit computation with the strongest form of quantum nonlocality—quantum pseudo-telepathy, where distant non-communicating observers generate perfectly synchronous statistics. We prove quantum magic is indispensable for such correlated statistics in a specific nonlocal game inspired by the linear binary constraint system. Then, we translate generating quantum pseudo-telepathy into computational tasks, where magic is necessary for a shallow circuit to meet the target. As a by-product, we provide an efficient algorithm to solve a general linear binary constraint system over the Pauli group, in contrast to the broad undecidability in constraint systems. We anticipate our results will enlighten the final establishment of the unconditional advantage of universal quantum computation. "Magic” is a resource in quantum computation that is believed to be important for quantum speedup, but the proofs of this have involved complexity assumptions or invoking a black-box oracle. Here, by constructing magic-required quantum pseudo-telepathy and converting it into a relation problem, the authors show an unconditional separation between constant-depth quantum circuits and magic-free ones.
Quantum theory promises computational speed-ups over classical approaches. The celebrated Gottesman-Knill Theorem implies that the full power of quantum computation resides in the specific resource of “magic” states—the secret sauce to establish universal quantum computation. However, it is still questionable whether magic indeed brings the believed quantum advantage, ridding unproven complexity assumptions or black-box oracles. In this work, we demonstrate the first unconditional magic advantage: a separation between the power of generic constant-depth or shallow quantum circuits and magic-free counterparts. For this purpose, we link the shallow circuit computation with the strongest form of quantum nonlocality—quantum pseudo-telepathy, where distant non-communicating observers generate perfectly synchronous statistics. We prove quantum magic is indispensable for such correlated statistics in a specific nonlocal game inspired by the linear binary constraint system. Then, we translate generating quantum pseudo-telepathy into computational tasks, where magic is necessary for a shallow circuit to meet the target. As a by-product, we provide an efficient algorithm to solve a general linear binary constraint system over the Pauli group, in contrast to the broad undecidability in constraint systems. We anticipate our results will enlighten the final establishment of the unconditional advantage of universal quantum computation. "Magic” is a resource in quantum computation that is believed to be important for quantum speedup, but the proofs of this have involved complexity assumptions or invoking a black-box oracle. Here, by constructing magic-required quantum pseudo-telepathy and converting it into a relation problem, the authors show an unconditional separation between constant-depth quantum circuits and magic-free ones.
Quantum effects can enhance information-processing capabilities and speed up the solution of certain computational problems. Whether a quantum advantage can be rigorously proven in some setting or demonstrated experimentally using near-term devices is the subject of active debate. We show that parallel quantum algorithms running in a constant time period are strictly more powerful than their classical counterparts; they are provably better at solving certain linear algebra problems associated with binary quadratic forms. Our work gives an unconditional proof of a computational quantum advantage and simultaneously pinpoints its origin: It is a consequence of quantum nonlocality. The proposed quantum algorithm is a suitable candidate for near-future experimental realizations, as it requires only constant-depth quantum circuits with nearest-neighbor gates on a two-dimensional grid of qubits (quantum bits).
Quantum computers were initially proposed to surpass the limitations of classical computers in simulating physical systems. Soon after, the field of quantum computing advanced through landmark discoveries of quantum algorithms, with some conjectured to provide exponential advantages over classical counterparts. These include Shor’s factoring algorithm, which has profound implications in cryptography. Additionally, moderate yet significant polynomial separations have further increased interest in the field. However, despite this progress, unconditional proofs confirming quantum superiority on the theoretical side remain elusive. At the same time, large, noise-resilient quantum computations on the experimental side, which could challenge the extended Church-Turing thesis by potentially breaking classical computational barriers, have yet to be achieved. Meanwhile, our understanding of the differences between classical and quantum mechanics has deepened. We now possess rigorous theoretical tools, such as Bell inequalities and nonlocal games, to describe behaviors unique to these theories. Moreover, the main loopholes for observing non-classical correlations have been closed experimentally, showing that correlations in the physical world exceed those predicted by classical mechanics. This thesis investigates computational complexity differences between quantum and classical models by studying shallow-depth circuits. The primary focus lies in identifying, elucidating, and proving computational quantum advantages. Additionally, the analysis delves into the bijection between these circuits and foundational non-local game constructions, exploring how quantum-classical deviations in multi-party correlation settings translate to computational advantages. A key question addressed is how to synthesize constant-depth quantum circuits for various problems to leverage quantum advantages. To this end, circuit synthesis techniques tailored to measurement-based quantum computation are developed, enabling simultaneously optimal quantum strategies for certain nonlocal games based on a particular bijection between this model and XOR non-local games. Building on this work, we confront a pivotal challenge: If a candidate quantum circuit potentially provides a computational advantage, how can we prove that no classical circuit surpasses it? This work presents new unconditional quantum-classical separations within shallow-depth settings, distinguishing for the first time constant-depth quantum circuits with one- and two-qubit gates from biased polynomial threshold circuits, which incorporate neural-network-type functionalities. These separations extend to prime-dimensional quantum systems, and we conjecture to have identified Razborov-Smolensky-type problems uniquely solvable by specific prime dimensions. The thesis also differentiates constant-depth quantum circuits with multi-qubit Toffoli gates from their classical counterparts, emphasizing the power of parallel quantum computation. Finally, verifying shallow-depth quantum computations is challenging due to conjectured exponential separations from classical computations, limiting correctness verification through simulation. While specific quantum algorithms within BQP have been addressed, we explore whether a quantum computer can reliably execute any instance from a fixed class of quantum circuits. Moving beyond heuristic-based solutions, we propose a benchmarking protocol that certifies, with exponentially high confidence, the execution of arbitrary circuits of specified dimensions, widths, and depths.
Quantum systems are known to offer advantages over their classical counterpart in communication complexity protocols, where the aim is to minimize the amount of information exchange between distant parties to compute global functions of their distributed inputs. In this work, we establish that any one-way communication protocol implemented using a prime-dimensional quantum system -- restricted to stabilizer-state encodings and Clifford-operation decodings -- can be exactly simulated by transmitting a classical system of the same dimension, given access to shared randomness between the sender and receiver. In direct analogy with the Gottesman-Knill theorem, which attributes quantum computational speedup to non-stabilizer resources, commonly known as the magic resources, our result identifies the same non-stabilizer resources as the essential ingredient for the quantum advantage in one-way communication complexity. Furthermore, we present explicit tasks where even a 'minimal magic resource' suffices to achieve a provable quantum advantage, highlighting its efficient use in communication protocols.
Circuit depth is a central resource in complexity theory. While bounded-depth classical circuits admit well-understood hierarchy theorems, the internal structure of constant-depth quantum computation remains comparatively unexplored.
We prove an explicit depth hierarchy theorem for QNC0. For each d≥12, we construct a family of two-round interactive problems on which no depth-(d−1) quantum circuit can achieve near-perfect success, regardless of gate set, circuit size, or ancillary qubits. In contrast, we prove that our construction admits realizations by simple bounded fan-in quantum circuits of depth larger than d by a small constant factor. Moreover, all bounded fan-in classical circuits of sublogarithmic depth (in the input size) fail to achieve perfect success on these tasks for every d, yielding a hierarchy of problems that show unconditional quantum advantage of QNC0 over NC0.
A key obstacle is the scarcity of lower bound techniques for quantum circuits. To address this, we develop methods to analyze how depth affects a circuit's ability to realize nonlocal correlations amongst its output qubits in a fine-grained manner. Our approach exploits the correspondence between constraint systems and nonlocal games, translating group-theoretic constructions into rigid operator-valued constraint systems and then into non-local games. In particular, we construct constraint systems whose unique faithful operator-valued solutions require every perfect strategy, and every near-perfect strategy to a fixed precision, to implement multi-controlled phase operations. This reduces to a nonlocal unitary-synthesis problem, yielding depth lower bounds for both shallow quantum and classical circuits.
These results show that increasing depth strictly increases computational power within QNC0, establishing a genuinely quantum hierarchy.
Quantum magic is a necessary resource for quantum computers to be not efficiently simulable by classical computers. Previous results have linked the of quantum magic, characterized by the number of T gates or the stabilizer rank, to classical simulability. However, the effect of the of quantum magic on the hardness of simulating a quantum circuit remains open. In this work, we investigate the classical simulability of quantum circuits with alternating Clifford and T layers across three tasks: amplitude estimation, sampling, and evaluating Pauli observables. In the case in which all T gates are distributed in a single layer, performing amplitude estimation and sampling to multiplicative error are already classically intractable under reasonable assumptions, but Pauli observables are easy to evaluate. Surprisingly, with the addition of just one T -gate layer or merely replacing all T gates with T 1 / 2 , the Pauli evaluation task reveals a sharp complexity transition from being in P to being GapP-complete. Nevertheless, when the precision requirement is relaxed to 1 / poly ( n ) additive error, we are able to give a polynomial-time classical algorithm to compute amplitudes, Pauli observables, and sampling from log ( n ) -sized marginal distributions for any magic-depth-1 circuit that is decomposable into a product of diagonal gates. This rules out certain forms of quantum advantage in these circuits. Our research provides new techniques to simulate highly magical circuits while shedding light on their complexity and their significant dependence on the magic depth.
Nonstabilizerness, or magic, is an archetypal \emph{quantum} resource that is necessary for quantum computational advantage. Here we uncover a phenomenon seemingly at odds with the quantum nature of magic: entirely nonlocal magic (ENM)---magic present only in correlations and absent from each party's marginal---can live without entanglement. We systematically study this separation and show it is universal and operationally reversible: every magical state or channel can be encoded into and recovered from a separable ENM realization using only local stabilizer processing and classical communication. We leverage this mechanism to devise an activation key protocol in which a classical key controls access to non-Clifford operations. We further formulate magic secret sharing, in which computational power inaccessible to any party alone becomes accessible through cooperation. On a superconducting quantum processor, we experimentally demonstrate activation key and network computing primitives, together with separable ENM state preparation and extraction protocols. Together, our results establish that magic can be classically activated, localized, and secret-shared without entanglement, providing new resource-control primitives for distributed quantum computation.