Unconditional quantum magic advantage in shallow circuit computation Authors: Xingjian Zhang, Zhaokai Pan, Guoding Liu Published: 2024 ABSTRACT AbstractQuantum 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.Subject terms: Quantum information, Computer science, Information theory and computation, Applied mathematics Introduction Starting from Richard Feynman’s proposal of simulating physics with quantum means1, it has been an appealing quest to exploit phenomena unique to quantum theory to accelerate computation. A series of results, such as Shor’s factoring algorithm2 and Grover’s search3, strengthen the belief in the power of quantum computation. Notwithstanding the prosperity in the zoo of quantum algorithms, it is still intriguing to answer the basic questions: does quantum theory really bring a computational advantage over classical means, and if yes, what is the origin of such power? A well-known statement that seems to respond to both questions is quantum “magic”4. The so-called quantum magic states are beyond the reach of stabilizer circuits, the ones initialized in the computational basis state and composed of only Clifford gates and Pauli measurements. The Gottesman-Knill Theorem shows that stabilizer circuits can be perfectly simulated by classical computers in a polynomial time of the input size, deemed as efficient5–7. On the other hand, attempts from the simulation field suggest a strong relevance between the quantity of magic and the extent of quantum advantage8–16. Quantum algorithms richer in magic are often more difficult for a classical computer to simulate. Indeed, considering the structure of quantum state space, magic states, or equivalently non-Clifford operations, is indispensable for a complete picture4,17. In contrast, whether they bring a super-polynomial or even an exponential quantum computational advantage as promised remains to be proved. Despite numerous good reasons to believe in its validity18,19, unfortunately, explorations to date have not got rid of assumptions of unproven hardness for classical algorithms, such as factoring a large number in Shor’s algorithm2, or reliance on queries to a black-box oracle as in Grover’s search3, where the oracle construction may be hard work. To firmly establish the quantum advantage, one may alternatively start from a more restrictive regime in complexity. Instead of defining “efficient” as a polynomially growing time, a notable regime is the set of shallow circuits20,21, where the circuit depth, or equivalently the computing time, is restricted to a constant irrelevant to the problem size. The consideration of quantum shallow circuits was partly attributed to an experimental perspective, as it is relatively simpler to deal with system decoherence within a fixed time22. More importantly, theorists have rich toolkits from quantum information theory to aid the investigations. A particular instrument is a quantum nonlocality, a most distinguishing property of quantum theory23,24. As shown by the renowned Bell theorem25, entanglement leads to purely quantum correlations between nonlocal observers beyond the scope of classical physics26. One can translate quantum nonlocality into a computational task to generate nonlocal statistics among distant computing sites27–30. While classical circuits require a growing time with respect to the input size to scramble the information for computation, quantum shallow circuits are competent to the task, bringing an unconditional advantage. Despite the recent progress in shallow circuits, a vague question arises: Is magic indispensable for the full power of quantum computation in the low-complexity regime? Indeed, among all the existing explorations of quantum shallow circuits, the essential ingredient for the quantum advantage—long-range entanglement, can be generated with Clifford circuits without using the magic resource31. On the other hand, though not rigorous, with our experiences in the complexity theory such as the padding argument32, we may be inclined to think of a collapse of the power of universal quantum computation if magic makes no difference in the low-complexity regime. Following the logic of relating nonlocality with shallow circuit computation, a relevant question is the role of quantum magic in nonlocality, which is much unexplored compared to the more prevalent quantum features like entanglement. In this work, we unconditionally confirm that quantum magic brings an advantage, at least in a shallow circuit. For this purpose, we consider the strongest form of nonlocality, where nonlocal observers generate perfectly synchronous statistics, namely quantum “pseudo-telepathy”23. For the first time, we explicitly construct a quantum pseudo-telepathy correlation requiring magic resources and prove strict upper bounds on the correlation strength of solely magic-free operations. Then, we design a computational task that requires the output and the input to satisfy the constructed magic-necessary pseudo-telepathy correlations. This task separates the capabilities of generic quantum shallow circuits and their magic-free counterparts. We summarize our approach in Fig. 1. Summary of the results and methods. a A general BCS nonlocal game. Given a BCS, the question to Alice is a constraint indexed by α, and the question to Bob is a variable indexed by β, with β∈Sα, where Sα corresponds to the set of variables in constraint α. The players win the game if and only if Alice outputs an assignment to the variables {vγ}γ satisfying the constraint ∏γ∈Sαvγ=cα, and Alice and Bob give an identical assignment to vβ. b Different game strategies. (1) Classical strategy: players share randomness and apply local classical operations. (2) Clifford strategy: players share entanglement prepared by stabilizer circuits and apply local Clifford operations and local Pauli measurements. The set of stabilizer states forms a convex polytope7,8. (3) General strategy: players share a general entangled state and apply general local quantum operations. The set of all quantum states is a convex set. There is a hierarchy among the maximum winning probabilities in each level: pC ≤ pClif ≤ pQ. We present a family of nonlocal games via Eq. (8), which manifest leveled quantum pseudo-telepathy, namely pC < pClif = 1 and pClif < pQ = 1 under different game parameters. c Solving a relation problem via a shallow circuit with bounded fan-in gates. The circuit depth D and the maximum gate fan-in K are both fixed constants. The BCS nonlocal game can be translated to a relation problem on 2N sites. See Methods for the detailed construction. The bounded fan-in and constant-depth conditions restrict each output site to be affected only by a constant number of input sites, as shown by the lightcone shaded in green. d Categories of shallow circuits. (1) NC0: classical shallow circuits with bounded fan-in gates, comprising classical gates like AND,OR,NOT,NAND. (2) ClifNC0: magic-free shallow circuits with bounded fan-in gates, comprising a magic-free initial quantum state, Clifford gates like H,S,CNOT, and Pauli measurements. (3) QNC0: general quantum shallow circuits with bounded fan-in gates, allowing a generic initial state and non-Clifford gates like the T gate and the Toffoli gate. Previous results have established the strict separation of NC0≠ClifNC027,28. In this work, we prove the strict separation of ClifNC0≠QNC0. Results Basic notions and main result The concept of quantum magic originates from the study of the classical simulation of quantum computation, closely related to the stabilizer formalism5. Consider an n-qubit quantum system on which the Pauli group is defined as the set of operators together with operator multiplication. Here, I is the two-dimensional identity operator, and σx, σy, σz are the qubit Pauli matrices. The Clifford group is defined as the normalizer group of the Pauli group Pn: where Un is the set of all n-qubit unitary operators. Elements in the Clifford group are called Clifford operators or gates. A quantum circuit initialized in the computational-basis state and containing only Clifford gates and Pauli measurements is called a stabilizer circuit. Note that the Pauli measurements are equivalent to applying some Clifford gates, followed by computational-basis measurements. The Gottesman-Knill theorem states that the measurement results can be well-simulated by a classical circuit running in a time that is polynomial in the number of qubits5,6. Clearly, there are unitary operators that do not belong to the Clifford group. Well-known non-Clifford operations include the T-gate, which adds a non-trivial relative phase to basis state superposition: and the Toffoli gate, the quantum generalization of the NAND gate: where c1, c2, t ∈ {0, 1} represent the values in the two control qubits and the target qubit, respectively. Correspondingly, there are quantum states that cannot be prepared by any stabilizer circuit, even allowing post-selecting a subsystem upon Pauli measurement results. We call such states “magic” states. As an example, the state is a qubit magic state. To realize universal quantum computation and achieve quantum advantage, some sort of “magic” must be involved, which can be either some magic states or non-Clifford gates4,6,9,33,34. In later discussions, we consider a model where all the magic comes from the gates. That is, the quantum state is initialized in 0⊗n, and the quantum measurement is performed on a computational basis. Depending on the type of computational resources, we categorize the circuits into three types. In a generic quantum circuit, the state undergoes operations in a universal gate set. Without strictly quantum gates, namely, all the quantum gates are restricted to a change of computational basis states, the circuit degenerates into a classical one. In between, we define the Clifford or magic-free circuit, in which the quantum gates must be Clifford. Besides the accessible computational resources, the power of a circuit is also influenced by the circuit depth and the gate fan-in. The circuit depth is defined as the number of steps to perform all the gates and measurements. Note that in one step, multiple gates acting on different subsystems can be implemented in parallel. The gate fan-in is defined as the number of input (quantum) bits a gate can act on. For instance, the T gate has fan-in 1, and the Toffoli gate has fan-in 3. In our definition, the fan-in includes both classical bits and qubits, as depicted and explained in Fig. 2, e.g., a T gate controlled by a classical bit has fan-in 2. In this way, we unify the discussions for classical logical gates, quantum gates, classically controlled quantum gates, and measurements. A K-bounded fan-in gate. In general, it acts on nc bits and nq qubits, with nc + nq ≤ K. When nc = 0, it becomes a normal quantum gate characterized by a unitary operation. When nq = 0, it becomes a normal classical gate. In this work, we are interested in the computational power of shallow circuits with bounded fan-in gates. That is, the circuit depth is constant, and the fan-in of all the operations in the circuit has a constant upper bound. Within this restriction, we denote the classes of classical circuits20,35, Clifford circuits, and generic quantum circuits36 as NC0, ClifNC0, and QNC0, respectively. We depict examples of these circuits in Fig. 1d. As a remark, we overuse the complexity class notations for the associated circuits, like previous works in the field. Finally, we model the general description of a computational task, where a user of the circuit aims to compute a specific problem. For this purpose, the user interacts with the circuit by sending an input and asking it to return a desired output. Before reaching the final result, the user may interact with the circuit for multiple rounds, and the input in each round may depend on previous interactions. We can ask what the minimal circuit computational power is required to solve the problem. Previously, a strict separation between NC0 and ClifNC0 was proved27,28. Here, we show magic further makes a fine structure among shallow circuits. Theorem 1 (Informal). There is a separation between the circuit power: Binary-constraint-system-based nonlocal games To prove the main result in Eq. (6), essentially, we manifest nonlocal correlations where magic states or non-Clifford operations play a non-trivial role. Our starting point is a special nonlocal game originating from the linear binary-constraint system (BCS)37. A BCS comprises a set of Boolean functions, namely constraints, over binary variables vγ. We take the variable values over {+1, −1} for later convenience. For a linear BCS, the constraints are given by functions in the form of ∏γ∈Sαvγ=cα∈{+1,−1}, where Sα defines a subset of the variables. Given a linear BCS, consider a corresponding nonlocal game with two parties, Alice and Bob, as shown in Fig. 1a. In each round of the game, a referee picks a constraint from the BCS labeled by α and a variable labeled by β∈Sα. The referee asks Alice to assign values to the variables satisfying the constraint and Bob to output a value for vβ. The nonlocal players win the game if and only if Alice gives a satisfying assignment for the constraint cα, and Alice gives a satisfying assignment for the constraint cα, and Alice’s assignment to vβ coincides with Bob’s. Alice’s assignment to vβ coincides with Bob’s. Alice and Bob cannot communicate with each other once the game starts. Nevertheless, they can agree on a game strategy in advance. Naturally, the existence of a perfect winning strategy is related to the properties of the underlying linear BCS. If and only if the linear BCS has a solution where a fixed value assignment to the variables satisfies all the constraints, Alice and Bob can win the associated nonlocal game with certainty by classical means37. Otherwise, the winning probability by any classical strategy, where the players are restricted to shared randomness and local classical operations, is strictly upper-bounded from 1. Notwithstanding, even if a fixed satisfying assignment does not exist, the nonlocal players may still win the game perfectly by exploiting quantum strategies. For a systematic study, we first generalize the BCS to a set of operator-valued functions. The scalar variables are replaced with Hermitian operators Aγ of a finite dimension with eigenvalues {+1, −1}, and the constraints become ∏γ∈SαAγ=cαI with I an identity operator. In addition, the observables corresponding to the variables in each constraint are required to be compatible, namely jointly measurable. The existence of a quantum perfect-winning strategy is equivalent to the operator-valued BCS having a solution37. Suppose the solution to the operator-valued BCS is given by a set of d-dimensional operators, {Aγ}γ, then the perfect-winning strategy in the corresponding nonlocal game goes as follows: Alice and Bob first share a maximally entangled state, Φ+=∑i=0d−1ii/d; Alice and Bob first share a maximally entangled state, Φ+=∑i=0d−1ii/d; After the game starts, Alice measures the observables {Aγ}γ, and Bob measures the observables {AγT}γ to assign values to the variables, where T denotes the operator transpose. After the game starts, Alice measures the observables {Aγ}γ, and Bob measures the observables {AγT}γ to assign values to the variables, where T denotes the operator transpose. By construction, Alice’s measurement results satisfy the constraint. Also, as the maximally entangled state has the property the assignments of Alice and Bob to the same variable thus coincide. Due to the intrinsic randomness in quantum measurements, an observable may take different outcomes in each constraint, hence assigning a different value to the same variable. Such flexibility brings an advantage over classical means, where quantum resources bring Alice and Bob “pseudo-telepathy” as if they knew what was going on the other side via a “spooky action”23. We shall further discuss this issue and review relevant existing results in the Supplementary Information (SI) Sec. IB, such as the famous Mermin-Peres nonlocal game38,39. Among quantum strategies for the nonlocal game, there are also different levels of capabilities, as shown in Fig. 1b. Instead of having access to all quantum states and operations, we consider constraining the players to apply only Clifford strategies. Specifically, Alice and Bob can apply Clifford operations to a state initialized 0 before the nonlocal game to create entanglement. Afterward, they each take a share of the state and apply only Pauli-string measurements to the state for the game. If the nonlocal game has a Clifford strategy that wins perfectly, then the underlying BCS has a Pauli-string solution, and vice versa. Notably, we derive the following results for general linear BCS. We prove Theorem 2 in SI Sec. VB and Theorem 3 in SI Sec. III. Theorem 2 Given a linear BCS with l variables and m constraints, there exists a classical algorithm that finishes in poly(l, m) steps to determine whether the BCS has a Pauli-string operator-valued solution. If the answer is affirmative, the algorithm returns one such solution. Theorem 3 Suppose a linear BCS does not have a Pauli-string solution. Then, for its associated nonlocal game, if Alice and Bob are restricted to Clifford strategies, either Alice fails to give satisfying assignments for all the constraints, or there exists one pair of questions (α, β), where the probability that Alice and Bob’s assignments to vβ coincide does not exceed 1/2. We outline the algorithm in Theorem 2 in Methods. This result improves previous attempts of searching for a Pauli-string solution to a linear BCS40,41, which pose additional requirements on the appeared times of each variable. Besides, Theorem 2 sharply contrasts the common undecidability in the field of constraint systems, such as determining the existence of an operator-valued solution to a general BCS, which may not be Pauli strings42. Magic-necessary quantum pseudo-telepathy Previously, it was conjectured that whenever a linear BCS nonlocal game has a perfect-winning strategy, it is either a Clifford or a classical one40. Recent group embedding results evidence the falseness of this conjecture42,43. Here, we take a relevant yet different approach and directly present a linear BCS nonlocal game to disprove it. To make it illustrative, we state the underlying BCS in the language of graph theory. Consider an undirected complete graph G = (V, E) with n vertices in the vertex set V. An undirected graph indicates that for any two connected vertices, u and v, the tuples (u, v) and (v, u) represent the same edge in the edge set E. The BCS contains the following variables: Each vertex v ∈ V corresponds to one variable av. Each vertex v ∈ V corresponds to one variable av. Each undirected edge, denoted by e = (u, v) ∈ E, corresponds to three variables xuv, yuv, and zuv. Each undirected edge, denoted by e = (u, v) ∈ E, corresponds to three variables xuv, yuv, and zuv. Every two disjoint edges, denoted by e1 = (u, v) ∈ E and e2 = (s, t) ∈ E, where s, t, u, and v are different vertices, correspond to one variable be1e2≡buv∣st, where be1e2=be2e1;two variables ce1e2≡cuv∣st and ce2e1≡cst∣uv, where ce1e2≠ce2e1 in general. Every two disjoint edges, denoted by e1 = (u, v) ∈ E and e2 = (s, t) ∈ E, where s, t, u, and v are different vertices, correspond to one variable be1e2≡buv∣st, where be1e2=be2e1;two variables ce1e2≡cuv∣st and ce2e1≡cst∣uv, where ce1e2≠ce2e1 in general. one variable be1e2≡buv∣st, where be1e2=be2e1; one variable be1e2≡buv∣st, where be1e2=be2e1; two variables ce1e2≡cuv∣st and ce2e1≡cst∣uv, where ce1e2≠ce2e1 in general. two variables ce1e2≡cuv∣st and ce2e1≡cst∣uv, where ce1e2≠ce2e1 in general. For clarity, we express the variables with respect to the underlying vertices and denote the BCS (nonlocal game) size with the number of vertices. Based on these variables, the BCS contains the following constraints: The smallest non-trivial BCS that contains all types of variables is defined on a graph with four vertices, as shown in Fig. 3. BCS with a larger size can be defined similarly. Depending on the graph size, this family of BCS’s exhibits a hierarchy among classical, Clifford, and general quantum resources, as shown by the following theorem. The undirected complete graph with four vertices. This graph defines the smallest non-trivial BCS variables in Eq. (8). Each vertex v corresponds to one variable av, and there are four such variables in the subgraph. Each undirected edge e = (u, v) corresponds to three variables xuv, yuv, zuv. With six edges in the subgraph, there are six variables for each kind. Every two disjoint edges e1 = (u, v), e2 = (s, t) correspond to two kinds of variable buv∣st = bst∣uv and cuv∣st, cst∣uv. The subgraph has three sets of disjoint edges, denoted by black solid lines, blue dashed lines, and orange dotted lines, respectively. Consequently, there are three variables of the kind buv∣st and six variables of the kind cuv∣st. Theorem 4 For the nonlocal game defined through the BCS in Eq. (8), when n = 4, it has a perfect-winning Clifford strategy, but it does not have a perfect-winning classical strategy; when n = 4, it has a perfect-winning Clifford strategy, but it does not have a perfect-winning classical strategy; when n∈2N+5={5,7,9,⋯}, it has a perfect-winning classical strategy; when n∈2N+5={5,7,9,⋯}, it has a perfect-winning classical strategy; when n∈2N+6={6,8,10,⋯}, it has strategies that exploit quantum magic to win perfectly, but it does not have a perfect-winning Clifford strategy or classical strategy. when n∈2N+6={6,8,10,⋯}, it has strategies that exploit quantum magic to win perfectly, but it does not have a perfect-winning Clifford strategy or classical strategy. In SI Sec. II, we construct perfect-winning strategies in each level (Theorem 1 for n∈2N+5, Theorem 2 for n = 4, and Theorems 5 and 6 for n∈2N+6 in SI). The general algorithm in Theorem 2 can aid the proof for the non-existence of Clifford strategies when n∈2N+6. Nevertheless, we provide a simpler proof tailored to this specific BCS nonlocal game (Theorem 4 in SI). As a corollary of Theorem 3, for the nonlocal game with n∈2N+6, with uniformly distributed random questions, the winning probabilities of all Clifford and classical strategies can be upper-bounded by where Q denotes the set of questions in the nonlocal game. We present the calculation of ∣Q∣ in Methods. In the construction of perfect-winning strategies for BCS games with size n∈2N+6, we apply a group-theoretic method44,45. A notable property is that there are non-unique solutions to the BCS and, thus, non-equivalent perfect-winning quantum strategies in this case. The measurements in different strategies cannot be transformed into each other via a local isometry or the complex conjugate operation, hence the BCS game does not manifest a self-testing property46. Moreover, as the strategies take different dimensions, the associated maximally entangled states are thus non-equivalent47. This property even distinguishes our BCS game from nonlocal games with the “weak-form” self-testing property48, where while the measurements can be non-unique in the optimal quantum strategies, they require the same entangled state with a fixed dimension up to a local isometry for the optimal quantum strategy. Here, we present one operator-valued solution to the BCS when n = 8. Labeling the vertices from 1 to 8, a realization of av and xuv in the above BCS is where I8 is an eight-dimensional identity operator, and eij denotes an elementary matrix, of which the element in the i’th row and j’th column is one, and all the other elements are zero. The other operators can be determined via av’s and xuv’s. The perfect-winning strategy of the nonlocal game thus takes three pairs of the Einstein-Podolsky-Rosen (EPR) state, (00+11)/2. In this strategy, the measurements corresponding to xuv require non-Clifford operations, which can be realized by applying a Toffoli gate up to a local unitary operation followed by the computational-basis measurement. We further explain their implementation in Methods. Magic computational advantage in shallow circuits As shown in Theorem 4, the nonlocal game defined through the BCS in Eq. (8) separates the capabilities between a generic quantum world and the magic-free world to generate correlations. Now, we translate correlation generation into a computational task of a relation problem and show the magic advantage. As a reminder, the computational task is a single-user one. “Alice” and “Bob” in the nonlocal game now refer to parts of the circuit, which is merely for intuitive thinking. In particular, one should not consider the task as a distributed computation. Briefly speaking, a relation problem randomly selects an input bit string zin from a set and asks the computation to output a bit string zout, such that zout always satisfies a certain relation with respect to zin. Given a nonlocal game with size n, we can define a relation problem labeled by n, RNn. As shown in Fig. 1c, one can imagine that two experimentalists, Alice and Bob, each holds N computing sites and collaborate to solve RNn. We use the capital letter N for the number of computing sites to distinguish it from the underlying nonlocal game size n. The problem of RNn randomly specifies two sites of Alice and Bob, denoted as 2j−1 and 2k, respectively, and inputs questions in the nonlocal game, which we encode as bit strings α∈QA,β∈QB. Other sites are input with a fixed value, ⊥. The sites 2j−1 and 2k are required to output fA(α, β) and fB(α, β), respectively. In a circuit comprising K-bounded fan-in gates, where each gate can act on at most K inputs, the value K mimics the light speed for information scrambling49. Furthermore, if the circuit is shallow, where the circuit depth is a constant independent of the problem size, it restricts the “time” for information scrambling; hence, many sites in the circuit are “space-like” separated from each other. When applying a shallow circuit with bounded fan-in gates to solve the relation problem defined by a nonlocal game, Alice and Bob must be capable of winning the game between space-like separated sites without communication. Suppose the underlying nonlocal game cannot be won perfectly without a particular resource, which is quantum magic in our discussion. In that case, the players must communicate to exchange information and generate the desired correlation, which takes time. Therefore, the shallow circuit should fail in the task. On the contrary, suppose this particular resource exists such that the nonlocal game can be won perfectly. Entanglement can be created and distributed between two arbitrary sites via entanglement swapping with bounded fan-in quantum gates in constant steps28,30, and quantum pseudo-telepathy completes the remaining task. A caveat is that although the distributed state after entanglement swapping ψ is still maximally entangled, conditioned on the quantum measurement result in this procedure, the state might undergo a random local Pauli error, deviating from the EPR state Φ+ necessary for perfect-winning the BCS nonlocal game. Due to the non-Clifford nature, the measurements of Alice and Bob are not perfectly correlated, namely ψA⊗ATψ≠1. They are neither perfectly anti-correlated, namely ψA⊗ATψ≠−1, such that we can embed the correlation flip to the defining relation28. Without communication to correct the Pauli error based on the error syndrome, these cases render in random statistics that violate the relation. To solve this issue, we consider a two-round interaction. In the first round, the user simply picks two computational sites at random, and the shallow circuit carries out entanglement swapping to distribute the EPR state to them. In the second round, besides asking nonlocal game questions to these sites, the user also sends an error syndrome to one of them, giving it the necessary information to correct the Pauli error. By construction, a generic quantum shallow circuit that embeds the nonlocal game strategy as a sub-routine is competent for the task. Building on the nonlocal games defined through Eq. (8), the following theorem illustrates the separation between QNC0 and ClifNC0 circuits in solving the BCS relation computational problem. We present the formal task description in Methods and provide the analysis details in SI Sec. IV. Theorem 5 Given the nonlocal game defined by the BCS in Eq. (8) with size n∈2N+6, there is a relation problem RNn carried out in two rounds and a constant Kth independent of N, such that for any integer K > Kth, RNn can be perfectly solved by a fixed QNC0 circuit with K-bounded fan-in one-dimensional geometrically local gates, where some gates are non-Clifford operations. RNn can be perfectly solved by a fixed QNC0 circuit with K-bounded fan-in one-dimensional geometrically local gates, where some gates are non-Clifford operations. Any probabilistic Clifford circuit with K-bounded fan-in gates that solves RNn with probability larger than (1 1+ pClif)/2, where pClif is given in Eq. (9), must have a circuit depth at least increasing logarithmically with respect to the problem size N, where the gates can be non-geometrically local. Any probabilistic Clifford circuit with K-bounded fan-in gates that solves RNn with probability larger than (1 1+ pClif)/2, where pClif is given in Eq. (9), must have a circuit depth at least increasing logarithmically with respect to the problem size N, where the gates can be non-geometrically local. By this, we prove the main result in Eq. (6). In the second part of the theorem, the logarithmic separation is tight. That is, a magic-free circuit with bounded fan-in gates can solve the problem, of which the depth grows logarithmically. For a straightforward solution, all the computing sites send their input to a fixed ancilla, which performs the nonlocal game calculation and sends back the result to the specified sites. In addition, we also construct a one-round sampling problem that is defined similarly in SI Sec. IVB. We prove this problem separates a fixed QNC0 circuit from all fixed ClifNC0 circuits, where no additional randomness is allowed. Discussion In summary, we discover a family of nonlocal games that require quantum magic to win perfectly and translate it into an unconditional proof of magic computational advantage. While not being the purpose of this work, by applying the “game gluing” technique45,50, one can combine games with different sizes in the family and construct a nonlocal game with a strict separation between the winning probabilities of classical, Clifford, and general quantum strategies. We consider this to be of independent interest to some research. In addition, we believe other nonlocal games exist that can demonstrate magic advantage. For instance, following the method of embedding a general group into a BCS in ref. 42, one can obtain candidate BCS nonlocal games. In SI Sec. VA, we review the procedure. Combined with Theorem 2, one can efficiently check whether they have perfect-winning Clifford strategies. To compute the relation problem in a realistic experiment, one shall further consider the noise. For this purpose, noise-tolerant methods, such as error correction and mitigation in a shallow circuit, need to be developed. With recent experimental progress, preparing magic states and implementing a few layers of non-Clifford gates are becoming easy51,52. We expect that the computational task in this work can be faithfully realized on an upcoming early fault-tolerant quantum computing platform53–55. This work takes the first step in proving the computation necessity of quantum magic unconditioned on any complexity assumption. We hope our results can inspire further explorations in this direction, eventually going beyond the regime of shallow circuits and solidifying the “magic” of universal quantum computation. Methods BCS nonlocal game size For the BCS given in Eq. (8), we denote the set of questions for Alice as Q~A, namely the BCS constraints, and the set of questions for Bob as Q~B, namely the BCS variables. In Tables 1 and 2, we give the expressions to calculate the set sizes. We also provide the concrete numbers for the case of n = 8. Note that the constraint ∏v∈Vav = −1 comprises n variables, while every other constraint consists of three variables. Table 1Number of constraints in the BCS gameconstraint formatexpressionnumber (n = 8)aa′y=1n228xyz = 1n228xx′b=1n4⋅3210xzc = 1n4⋅3⋅2420bb′b″=1n470cc′c″=1n4⋅4280∏a = −111Total∣Q~A∣1037 Number of constraints in the BCS game Table 2Number of variables in the BCS gamevariable typeexpressionnumber (n = 8)an8xn228yn228zn228bn4⋅3210cn4⋅3⋅2420total∣Q~B∣722 Number of variables in the BCS game For the convenience of the shallow circuit computational task, we slightly modify the BCS in Eq. (8). For the n-variable constraint ∏v∈Vav = −1, we can introduce (n−3) new variables and turn it into an equivalent set of (n−2) constraints with three variables each. That is, we introduce new variables a12, a123,⋯, a1⋯n−2 and convert the constraint as Note that the commutation requirement between variables au and av in the original constraint is preserved since they also need to satisfy the constraint of auavyuv = 1. Denote the set of constraints in the modified BCS as QA. Suppose the original BCS with size n consists of ∣Q~A∣ constraints. In correspondence with Eq. (9) in the main text, there are ∣Q∣=3∣QA∣ sets of questions in the modified BCS nonlocal game, with By applying Theorem 3, we obtain a direct upper bound on the average winning probability of Clifford strategies as 1−1/6∣QA∣. Non-Clifford operations in the BCS nonlocal game To illustrate the circuit operations for the nonlocal game, in Fig. 4, we depict the observables of x78, y78, z78 and the implementation for the constraint x78y78z78 = 1. The observable x78 is the same as the Toffoli gate. To measure this observable, one can use the Hadamard test, in which the required non-Clifford gate is the controlled-controlled-controlled-X (CCCX) gate. Similarly, the non-Clifford gates required to measure y78 and z78 are the controlled-controlled-Z (CCZ) and controlled-controlled-controlled-(-X) gates, respectively. The circuit with non-Clifford gates to realize the simultaneous measurement of x78, y78, and z78 by using the Hadamard test. The Hadamard test uses an ancilla initialized in 0, followed by a Hadamard gate, applying controlled-O and again a Hadamard gate, and measuring in the computational basis to get measurement results of O. Here, the non-Clifford gates are CCCX, CCZ, and CCC(-X) for x78, y78, and z78, respectively. Translating the nonlocal game into a relation problem Based on the BCS nonlocal game, we define the shallow circuit computational task. In the following discussions, we focus on the relation problem RN8, namely the problem that embeds the BCS nonlocal game with size n = 8. Other values of n can be studied similarly. We describe the task by giving the quantum circuit that perfectly solves the computational problem. As shown in Fig. 5b, consider a quantum circuit containing 2N computing sites labeling from 1 to 2N. Imagine the circuit is divided into two parts, Alice and Bob, where Alice holds the odd-valued sites, and Bob holds the even-valued sites. Each site consists of a set of classical wires to receive the input of RN8 and quantum wires initialized in 0 for three qubits. Throughout this work, we denote the classical systems by double wires and quantum systems by single wires. Description of the interactive relation problem. Schematic diagram (a) of the interactions in the relation problem RNn and a shallow circuit construction (b) to solve it. In the first round, the user randomly picks computation sites j, k, on which the nonlocal game shall be taken in the second round. The user informs the circuit of this choice with the character ⊤ on the positions Alicej and Bobk in a 2N-bit string. The other positions in the bit string take the character ⊥. In the quantum shallow circuit for this round [the left dashed box in (b)], EPR states are initially prepared in each pair of sites between Alice and Bob (shown by the blue boxes). Upon receiving the input in this round, the circuit performs BSMs between adjacent EPR states (shown by the white boxes) except for the positions receiving ⊤ (shown by the orange dots). The measurement outcomes r(1) are taken as the outputs of the first round, which is sent back to the user. Computation sites Alicej and Bobk shall share EPR states up to a local Pauli flip related to the measurement outcomes. In the second round, the user calculates the Pauli error syndrome pA, pB from r(1) by Eq. (16) and randomly picks questions α∈QA,β∈QB in the BCS nonlocal game defined by Eq. (8). Afterwards, the user sends the syndrome pA, pB and the question α to Alicej and sends the question β to Bobk. In the quantum shallow circuit for this round [dashed box on the right of (b)], Alicej first corrects the Pauli error according to pA, pB (shown by the white box) and then performs the perfect-winning strategy for question α (shown by the orange box denoted as “Alice”); Bobk performs the perfect-winning strategy for question β (shown by the orange box denoted as “Bob”). The final computation output is the measurement results rjA,rkB in the nonlocal game. In the computation, the user randomly picks up two computational sites (j, k), as depicted by the orange dots, on which they require the shallow circuit to generate nonlocal correlations with respect to randomly chosen questions (α, β) in the BCS nonlocal game. To share entanglement and get ready for the nonlocal game, Alice and Bob first prepare three pairs of the EPR state, (00+11)/2, between their adjacent sites (2i−1,2i),i∈N+, as shown by the blue boxes. Next, Alice and Bob perform three Bell-state measurements (BSMs) between the three pairs of qubits on their adjacent sites (2j, 2j + 1), ⋯ , (2k − 2, 2k − 1) in a concatenated manner, as shown by the white boxes. A BSM projects two qubits into one of the four orthogonal Bell states, and the measurement can be realized by a CNOT gate with Pauli measurements. When the BSM is performed jointly on one qubit of two Bell states each, the remaining two qubits become one of the Bell states with equal probability conditioned on the measurement outcome, a phenomenon called entanglement swapping56. After establishing a maximally entangled state, Alice and Bob perform the perfect-winning strategy for the nonlocal game at sites 2j − 1 and 2k with respect to the questions α and β, respectively, as shown by the orange boxes. To win the BCS nonlocal game, we hope the post-measurement state after entanglement swapping is ∣Φ+⟩⊗3, three pairs of the EPR state, such that ⟨Φ+∣⊗3Aγ⊗AγT∣Φ+⟩⊗3=1. However, a subtle issue is the so-called bit and phase flips in entanglement swapping. Due to the randomness in BSM, the post-measurement state may differ from the EPR state ∣Φ+⟩, experiencing a rotation of a local Pauli operator. Note that different from the case of Pauli measurements, where for any ∣ψ⟩∈{∣Φ+⟩,∣Φ−⟩,∣Ψ+⟩,∣Ψ−⟩} and any Pauli operator P, ⟨ψ∣P⊗PT∣ψ⟩=±1, such a Pauli error totally ruins the non-Pauli measurement statistics of Alice and Bob in the nonlocal game and results in random outcomes. To solve this issue, we relax the computational task to take two rounds of interactions. In the first round, the user simply selects sites (j, k) to distribute EPR states. The circuit distributes entanglement to the two sites up to a Pauli error. The user reads the BSM results and calculates the error syndrome of the distributed entangled state. In the second round, besides sending the randomly chosen nonlocal game questions to the sites, the user also sends the error syndrome to one of the sites, say j, letting the circuit first correct the Pauli error before playing the nonlocal game. We depict the interactions between the user and the shallow circuit in Fig. 5a and a circuit competent to the task in (b). Note that each site performs either the BSM or the nonlocal game operations conditioned on the input information, and we omit the quantum gates that do not take actions in the figure. The rigorous description of the task is given as follows. Relation problem RNn: Given a BCS game defined by Eq. (8) of size n, a problem instance of (j, k, α, β) where 1≤j