Quantum computing theorems

In quantum computing, intuition can be misleading. And if we don't pay enough attention, we may end up saying something wrong. Superposition does not mean that a quantum computer evaluates all solutions in parallel. Measuring one qubit of an entangled state does not mean messages can be sent faster than light. If something exists, it does not mean it can be duplicated. We don't rely only on probabilities, phases are also important.

Not being able to rely on intuition does not mean that it should be discarded altogether but we have to create educated intuition. This can be done by relying as much as possible on intuition-proof results, results that have been proven to be true, that we can use and from which we can build safely.

When studying quantum computing it's important to look for these results. Some of them are constructive, showing that quantum information can be controlled and manipulated with only modest resources. Others impose fundamental restrictions, reminding us that quantum mechanics is not simply “classical computation with complex numbers,” but a profoundly different regime with its own boundaries.

Here is a list of such intuition-proof results that work as structural insights. Rather than being tied to a specific algorithm or hardware implementation, they reveal what quantum information, quantum gates, and quantum error correction (QEC) can and cannot do in principle.

• Certain impossibility results, such as the no-cloning theorem and the Eastin-Knill theorem, set hard limits on what operations are compatible with the laws of quantum mechanics and fault-tolerant design.
• Others like the Solovay-Kitaev theorem and the threshold theorem establish that universal quantum computation is feasible in practice, provided errors are controlled and resources are managed wisely.
• Theorems such as the Knill-Laflamme condition, Gottesman-Knill theorem, and the discretization of error channels lay out core principles of quantum error correction and efficient simulation, which underpin the theoretical and practical work of building scalable devices.

My goal in assembling these theorems is not only to have their statements and implication for QEC all in one place, but also to highlight the way they complement one another: some closing doors, others opening new ones. With these limitative principles and constructive tools in mind, we can build educated intuition and comply with the unforgiving structure of quantum mechanics.

1. No-cloning theorem (1982):
   • There is no unitary operator $U$ on $H\otimes H$ such that for all normalised states $|\varphi {⟩}_A$ and $|e{⟩}_B$ in $H$, $U(|\varphi {⟩}_A|e{⟩}_B)=e^{i\alpha (\varphi ,e)}|\varphi {⟩}_A|\varphi {⟩}_B$ for some real number $\alpha$ depending on $\varphi$ and $e$.
   • For QEC, it implies that the design of a QECC to protect quantum information against decoherence cannot rely on some part of the quantum information being duplicated
   • W. K. Wootters, W. H. Zurek, A single quantum cannot be cloned , 1982
2. Solovay–Kitaev theorem (1995):
   • A finite set of quantum gates can efficiently approximate an arbitrary unitary operator on one qubit
   • A. Yu Kitaev, Quantum computations: algorithms and error correction , 1997
3. Knill-Laflamme condition (1997):
   • Two different errors should result in two different measurement outcome patterns
   • Emanuel Knill, Raymond Laflamme, Theory of quantum error-correcting codes , 1997
4. Threshold theorem for quantum computation (1997):
   • Arbitrarily accurate quantum computations are possible provided that the error per operation is below a threshold value
   • Emanuel Knill, Raymond Laflamme, Wojciech H. Zurek, Resilient quantum computation: error models and thresholds , 1998
5. Gottesman-Knill theorem (1998):
   • Stabilizer circuits can be perfectly simulated in polynomial time on a probabilistic classical computer
   • Daniel Gottesman, The Heisenberg Representation of Quantum Computers , 1998
6. Discretization of error channels (2000):
   • Designing a quantum error-correcting code and its recovery operation is equivalent to constructing a code capable of correcting all Pauli basis errors.
   • M.A. Nielsen, I. L. Chuang, Quantum Computation and Quantum Information 10th Anniversary Edition Cambridge University Press, 2000
   • Emanuel Knill, Raymond Laflamme, Theory of quantum error-correcting codes , 1997
7. Eastin-Knill theorem (2009):
   • No quantum error correcting code can have a continuous symmetry which acts transversely on physical qubits.
   • For many QECC, Clifford group gates can be implemented transversally on the code, hence this rules out the possibility of realizing non-Clifford gates transversally.
   • Bryan Eastin, Emanuel Knill, Restrictions on Transversal Encoded Quantum Gate Sets , 2009

For reference, check out this wikipedia category about theorems in quantum mechanics.