Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

arXiv:quant-ph/0403025 · Physical Review A

Universal quantum computation with ideal Clifford gates and noisy ancillas

Sergey B. Bravyi, Alexei Kitaev

Published Feb 22, 2005• 1,818 citations
arXivHTMLPDF

Abstract

We consider a model of quantum computation in which the set of elementary operations is limited to Clifford unitaries, the creation of the state $\ensuremath{\mid}0⟩$, and qubit measurement in the computational basis. In addition, we allow the creation of a one-qubit ancilla in a mixed state $\ensuremath{\rho}$, which should be regarded as a parameter of the model. Our goal is to determine for which $\ensuremath{\rho}$ universal quantum computation (UQC) can be efficiently simulated. To answer this question, we construct purification protocols that consume several copies of $\ensuremath{\rho}$ and produce a single output qubit with higher polarization. The protocols allow one to increase the polarization only along certain ``magic'' directions. If the polarization of $\ensuremath{\rho}$ along a magic direction exceeds a threshold value (about 65%), the purification asymptotically yields a pure state, which we call a magic state. We show that the Clifford group operations combined with magic states preparation are sufficient for UQC. The connection of our results with the Gottesman-Knill theorem is discussed.

DOI
10.1103/physreva.71.022316

Related papers

Universal Quantum Computation Based on a Magic States Distillation

Sergey B. Bravyi, Alexei Kitaev

We consider a model of quantum computation in which the set of elementary operations is limited to Clifford unitaries, the creation of the state $|0>$, and qubit measurement in the computational basis. In addition, we allow the creation of a one-qubit ancilla in a mixed state $\\rho$, which should be regarded as a parameter of the model. Our goal is to determine for which $\\rho$ universal quantum computation (UQC) can be efficiently simulated. To answer this question, we construct purification protocols that consume several copies of $\\rho$ and produce a single output qubit with higher polarization. The protocols allow one to increase the polarization only along certain ``magic'' directions. If the polarization of $\\rho$ along a magic direction exceeds a threshold value (about 65%), the purification asymptotically yields a pure state, which we call a magic state. We show that the Clifford group operations combined with magic states preparation are sufficient for UQC. The connection of our results with the Gottesman-Knill theorem is discussed.

•Mar 3, 2004•6 citations

The robustness of magic state distillation against errors in Clifford gates

Tomas Jochym-O’Connor, Ya-Fei Yu, Bassam Helou +1 more

Quantum error correction and fault-tolerance have provided the possibility for large scale quantum computations without a detrimental loss of quantum information. A very natural class of gates for fault-tolerant quantum computation is the Clifford gate set and as such their usefulness for universal quantum computation is of great interest. Clifford group gates augmented by magic state preparation give the possibility of simulating universal quantum computation. However, experimentally one cannot expect to perfectly prepare magic states. Nonetheless, it has been shown that by repeatedly applying operations from the Clifford group and measurements in the Pauli basis, the fidelity of noisy prepared magic states can be increased arbitrarily close to a pure magic state~\cite{Bravyi}. We investigate the robustness of magic state distillation to perturbations of the initial states to arbitrary locations in the Bloch sphere due to noise. Additionally, we consider a depolarizing noise model on the quantum gates in the decoding section of the distillation protocol and demonstrate its effect on the convergence rate and threshold value. Finally, we establish that faulty magic state distillation is more efficient than fault-tolerance-assisted magic state distillation at low error rates due to the large overhead in the number of quantum gates and qubits required in a fault-tolerance architecture. The ability to perform magic state distillation with noisy gates leads us to conclude that this could be a realistic scheme for future small-scale quantum computing devices as fault-tolerance need only be used in the final steps of the protocol.

arXiv:1205.6715•Quantum Information and Computation•May 1, 2013•25 citations

Classical simulation complexity of extended Clifford circuits

Richard Jozsa, M. Van den Nest

Clifford gates are a winsome class of quantum operations combining mathematical elegance with physical significance. The Gottesman-Knill theorem asserts that Clifford computations can be classically efficiently simulated but this is true only in a suitably restricted setting. Here we consider Clifford computations with a variety of additional ingredients: (a) strong vs. weak simulation, (b) inputs being computational basis states vs. general product states, (c) adaptive vs. non-adaptive choices of gates for circuits involving intermediate measurements, (d) single line outputs vs. multi-line outputs. We consider the classical simulation complexity of all combinations of these ingredients and show that many are not classically efficiently simulatable (subject to common complexity assumptions such as P not equal to NP). Our results reveal a surprising proximity of classical to quantum computing power viz. a class of classically simulatable quantum circuits which yields universal quantum computation if extended by a purely classical additional ingredient that does not extend the class of quantum processes occurring.

arXiv:1305.6190•Quantum Information and Computation•May 1, 2014•97 citations

The power of restricted quantum computational models

Mithuna Yoganathan

Restricted models of quantum computation are ones that have less power than a universal quantum computer. We studied the consequences of removing particular properties from a universal quantum computer to discover whether those resources were important.In the first part of the thesis we studied universal quantum computers which are implemented using Clifford gates, adaptive measurements, and magic states. The Gottesman–Knill theorem shows that circuits in this form which do not use magic states can be simulated by a classical computer. We extended this result to show that all circuits in this form can be partially simulated; the same computation can be implemented using a smaller quantum computer with the assistance of some polynomial time classical computation. We also identified a subclass of these computations that can be shown to not be entirely classically simulated by any method, given certain complexity theoretic assumptions are true.In the next part of the thesis we examine the role of entanglement in noisy quantum computations. Entanglement is necessary for noiseless quantum computers to have any quantum advantage, but it is not known whether the same is true for mixed state quantum computers. We show that entanglement, unexpectedly, does play a crucial role in the most well known mixed state computer: the one clean qubit model.Finally, we investigate how closely classical simulation is related to another idea of classicality.This notion captures how easily the final state of a computation can be learnt, given samples of measurements from it. We find an extra condition under which a circuit that is classically simulable is also efficiently learnable.

•Jan 5, 2021•1 citation

Universal magic state concentration

Jacopo Rizzo, Lorenzo Leone

Magic plays a dual role in quantum computation: it promotes stabilizer dynamics from efficient classical simulability to computational universality, but also challenges fault-tolerant architectures, since non-stabilizer operations are harder to protect against noise. Magic state distillation addresses this issue, yet existing protocols remain largely tailored to specific assumptions about the input or noise model and, more fundamentally, no general information-theoretic theory of optimal magic-state conversion currently exists. Here we develop such a characterization for pure qubit states through universal magic state concentration: a fixed stabilizer protocol that converts a few copies of an unknown pure non-stabilizer qubit state into an exact target magic state. Motivated by the impossibility of exact $T$-state concentration, we build six- and eight-copy protocols producing an exact $\mathrm{CCZ}$ state, with six copies being minimal. Their success probabilities are governed by the linearized order-three stabilizer Rényi entropy $M^{\mathrm{lin}}_3$. We show that this connection is structural: for up to nine input copies, $M^{\mathrm{lin}}_3$ fully determines the success probability of every universal Clifford-invariant stabilizer protocol. Remarkably, this characterization persists asymptotically: our constructions achieve optimal rates among universal single-output protocols and remain optimal up to logarithmic factors among arbitrary stabilizer protocols. As a corollary, we show that any unknown pure non-stabilizer state suffices for universal quantum computation via probabilistic $\mathrm{CCZ}$-state injection. Together, these results identify the stabilizer Rényi entropy as a fundamental operational quantity in magic state distillation.

quant-pharXiv:2608.13376•Aug 14, 2026•2 citations

Generalized Clifford groups and simulation of associated quantum circuits

Stephen R. L. Clark, Richard Jozsa, Noah Linden

Quantum computations starting with computational basis states and involving only Clifford operations, are classically simulable despite the fact that they generate highly entangled states; this is the content of the Gottesman-Knill theorem. Here we isolate the ingredients of the theorem and provide generalisations of some of them with the aim of identifying new classes of simulable quantum computations. In the usual construction, Clifford operations arise as projective normalisers of the first and second tensor powers of the Pauli group. We consider replacing the Pauli group by an arbitrary finite subgroup $G$ of $U(d)$. In particular we seek $G$ such that $G\otimes G$ has an entangling normaliser. Via a generalisation of the Gottesman-Knill theorem the resulting normalisers lead to classes of quantum circuits that can be classically efficiently simulated. For the qubit case $d = 2$ we exhaustively treat all finite irreducible subgroups of $U(2)$ and find that the only ones (up to unitary equivalence and trivial phase extensions) with entangling normalisers are the groups generated by X and the $n^{\rm th}$ root of $Z$ for $n \in \N$.

arXiv:quant-ph/0701103•Quantum Information and Computation•Jan 1, 2008•29 citations
We consider a model of quantum computation in which the set of elementary operations is limited to Clifford unitaries, the creation of the state \ensuremath∣0⟩\ensuremath{\mid}0⟩\ensuremath∣0⟩, and qubit measurement in the computational basis. In addition, we allow the creation of a one-qubit ancilla in a mixed state \ensuremathρ\ensuremath{\rho}\ensuremathρ, which should be regarded as a parameter of the model. Our goal is to determine for which \ensuremathρ\ensuremath{\rho}\ensuremathρ universal quantum computation (UQC) can be efficiently simulated. To answer this question, we construct purification protocols that consume several copies of \ensuremathρ\ensuremath{\rho}\ensuremathρ and produce a single output qubit with higher polarization. The protocols allow one to increase the polarization only along certain ``magic'' directions. If the polarization of \ensuremathρ\ensuremath{\rho}\ensuremathρ along a magic direction exceeds a threshold value (about 65%), the purification asymptotically yields a pure state, which we call a magic state. We show that the Clifford group operations combined with magic states preparation are sufficient for UQC. The connection of our results with the Gottesman-Knill theorem is discussed.
We consider a model of quantum computation in which the set of elementary operations is limited to Clifford unitaries, the creation of the state ∣0>|0>∣0>, and qubit measurement in the computational basis. In addition, we allow the creation of a one-qubit ancilla in a mixed state rho\\rhorho, which should be regarded as a parameter of the model. Our goal is to determine for which rho\\rhorho universal quantum computation (UQC) can be efficiently simulated. To answer this question, we construct purification protocols that consume several copies of rho\\rhorho and produce a single output qubit with higher polarization. The protocols allow one to increase the polarization only along certain ``magic'' directions. If the polarization of rho\\rhorho along a magic direction exceeds a threshold value (about 65%), the purification asymptotically yields a pure state, which we call a magic state. We show that the Clifford group operations combined with magic states preparation are sufficient for UQC. The connection of our results with the Gottesman-Knill theorem is discussed.
Quantum error correction and fault-tolerance have provided the possibility for large scale quantum computations without a detrimental loss of quantum information. A very natural class of gates for fault-tolerant quantum computation is the Clifford gate set and as such their usefulness for universal quantum computation is of great interest. Clifford group gates augmented by magic state preparation give the possibility of simulating universal quantum computation. However, experimentally one cannot expect to perfectly prepare magic states. Nonetheless, it has been shown that by repeatedly applying operations from the Clifford group and measurements in the Pauli basis, the fidelity of noisy prepared magic states can be increased arbitrarily close to a pure magic state~\cite{Bravyi}. We investigate the robustness of magic state distillation to perturbations of the initial states to arbitrary locations in the Bloch sphere due to noise. Additionally, we consider a depolarizing noise model on the quantum gates in the decoding section of the distillation protocol and demonstrate its effect on the convergence rate and threshold value. Finally, we establish that faulty magic state distillation is more efficient than fault-tolerance-assisted magic state distillation at low error rates due to the large overhead in the number of quantum gates and qubits required in a fault-tolerance architecture. The ability to perform magic state distillation with noisy gates leads us to conclude that this could be a realistic scheme for future small-scale quantum computing devices as fault-tolerance need only be used in the final steps of the protocol.
Clifford gates are a winsome class of quantum operations combining mathematical elegance with physical significance. The Gottesman-Knill theorem asserts that Clifford computations can be classically efficiently simulated but this is true only in a suitably restricted setting. Here we consider Clifford computations with a variety of additional ingredients: (a) strong vs. weak simulation, (b) inputs being computational basis states vs. general product states, (c) adaptive vs. non-adaptive choices of gates for circuits involving intermediate measurements, (d) single line outputs vs. multi-line outputs. We consider the classical simulation complexity of all combinations of these ingredients and show that many are not classically efficiently simulatable (subject to common complexity assumptions such as P not equal to NP). Our results reveal a surprising proximity of classical to quantum computing power viz. a class of classically simulatable quantum circuits which yields universal quantum computation if extended by a purely classical additional ingredient that does not extend the class of quantum processes occurring.
Restricted models of quantum computation are ones that have less power than a universal quantum computer. We studied the consequences of removing particular properties from a universal quantum computer to discover whether those resources were important.In the first part of the thesis we studied universal quantum computers which are implemented using Clifford gates, adaptive measurements, and magic states. The Gottesman–Knill theorem shows that circuits in this form which do not use magic states can be simulated by a classical computer. We extended this result to show that all circuits in this form can be partially simulated; the same computation can be implemented using a smaller quantum computer with the assistance of some polynomial time classical computation. We also identified a subclass of these computations that can be shown to not be entirely classically simulated by any method, given certain complexity theoretic assumptions are true.In the next part of the thesis we examine the role of entanglement in noisy quantum computations. Entanglement is necessary for noiseless quantum computers to have any quantum advantage, but it is not known whether the same is true for mixed state quantum computers. We show that entanglement, unexpectedly, does play a crucial role in the most well known mixed state computer: the one clean qubit model.Finally, we investigate how closely classical simulation is related to another idea of classicality.This notion captures how easily the final state of a computation can be learnt, given samples of measurements from it. We find an extra condition under which a circuit that is classically simulable is also efficiently learnable.
Magic plays a dual role in quantum computation: it promotes stabilizer dynamics from efficient classical simulability to computational universality, but also challenges fault-tolerant architectures, since non-stabilizer operations are harder to protect against noise. Magic state distillation addresses this issue, yet existing protocols remain largely tailored to specific assumptions about the input or noise model and, more fundamentally, no general information-theoretic theory of optimal magic-state conversion currently exists. Here we develop such a characterization for pure qubit states through universal magic state concentration: a fixed stabilizer protocol that converts a few copies of an unknown pure non-stabilizer qubit state into an exact target magic state. Motivated by the impossibility of exact TTT-state concentration, we build six- and eight-copy protocols producing an exact CCZ\mathrm{CCZ}CCZ state, with six copies being minimal. Their success probabilities are governed by the linearized order-three stabilizer Rényi entropy M3linM^{\mathrm{lin}}_3M3lin​. We show that this connection is structural: for up to nine input copies, M3linM^{\mathrm{lin}}_3M3lin​ fully determines the success probability of every universal Clifford-invariant stabilizer protocol. Remarkably, this characterization persists asymptotically: our constructions achieve optimal rates among universal single-output protocols and remain optimal up to logarithmic factors among arbitrary stabilizer protocols. As a corollary, we show that any unknown pure non-stabilizer state suffices for universal quantum computation via probabilistic CCZ\mathrm{CCZ}CCZ-state injection. Together, these results identify the stabilizer Rényi entropy as a fundamental operational quantity in magic state distillation.
Quantum computations starting with computational basis states and involving only Clifford operations, are classically simulable despite the fact that they generate highly entangled states; this is the content of the Gottesman-Knill theorem. Here we isolate the ingredients of the theorem and provide generalisations of some of them with the aim of identifying new classes of simulable quantum computations. In the usual construction, Clifford operations arise as projective normalisers of the first and second tensor powers of the Pauli group. We consider replacing the Pauli group by an arbitrary finite subgroup GGG of U(d)U(d)U(d). In particular we seek GGG such that G⊗GG\otimes GG⊗G has an entangling normaliser. Via a generalisation of the Gottesman-Knill theorem the resulting normalisers lead to classes of quantum circuits that can be classically efficiently simulated. For the qubit case d=2d = 2d=2 we exhaustively treat all finite irreducible subgroups of U(2)U(2)U(2) and find that the only ones (up to unitary equivalence and trivial phase extensions) with entangling normalisers are the groups generated by X and the nthn^{\rm th}nth root of ZZZ for n∈Nn \in \Nn∈N.