Eastin–Knill theorem

The Eastin–Knill theorem is a no-go theorem that states: "No quantum error correcting code can have a continuous symmetry which acts transversely on physical qubits".^[1] In other words, no quantum error correcting code can transversely implement a universal gate set, where a transversal logical gate is one that can be implemented on a logical qubit by the independent action of separate physical gates on corresponding physical qubits.^{[citation needed]}

In addition to investigating fault tolerant quantum computation, the Eastin–Knill theorem is also useful for studying quantum gravity via the AdS/CFT correspondence and in condensed matter physics via quantum reference frame^[2] or many-body theory.^[3]

The theorem is named after Bryan Eastin and Emanuel Knill, who published it in 2009.^[1]

Description

Since quantum computers are inherently noisy, quantum error correcting codes are used to correct errors that affect information due to decoherence and dissipation. Decoding error corrected data in order to perform gates on the qubits makes it prone to errors. Fault tolerant quantum computation avoids this by performing gates on encoded data. Transversal gates, which perform a gate between two logical qubits each of which is encoded in N physical qubits by pairing up the physical qubits of each encoded qubit ("code block"), and performing independent gates on each pair, can be used to perform fault tolerant but not universal quantum computation because they guarantee that errors don't spread uncontrollably through the computation. This is because transversal gates ensure that each qubit in a code block is acted on by at most a single physical gate and each code block is corrected independently when an error occurs.

The Eastin–Knill theorem implies that a universal set like {H, S, CNOT, T } gates can't be implemented transversally. For example, the T gate can't be implemented transversely in the Steane code.^[4] This calls for ways of circumventing Eastin–Knill in order to perform fault tolerant quantum computation.

Approximate Eastin–Knill theorem

The approximate version of the Eastin–Knill theorem states: "If a code admits a continuous symmetry pertaining to a Lie group and corrects erasure with fixed accuracy, then for each logical qubit, a number of physical qubits per subsystem that is inversely proportional to the error parameter is needed".^[2][3][5] The approximate version of the Eastin–Knill theorem is more robust than the original because it explains why it's impossible to have continuous symmetries for transversal gates on the microscopic scale while also explaining how it's possible to have continuous symmetries for transversal gates on the macroscopic scale.

Circumventing the theorem

The Eastin–Knill theorem does not prohibit protocols that provide fault tolerant quantum computation. Some methods of getting around Eastin–Knill are:

• Code switching^[6]
• Code drift^[7]
• Using continuous variables^[2][3][5]
• Shor's fault tolerant toffoli gate^[8]
• Teleportation of gates^[9]
• Magic state distillation^[10]
• Multiple partitions ^[11]
• Pieceable fault tolerance ^[12]
• Universal braiding^[13]

References

1. Eastin, Bryan; Knill, Emanuel (2009). "Restrictions on Transversal Encoded Quantum Gate Sets". Physical Review Letters. 102 (11): 110502. arXiv:0811.4262. Bibcode:2009PhRvL.102k0502E. doi:10.1103/PhysRevLett.102.110502. PMID 19392181. S2CID 44457708.
2. Woods, Mischa; Alhambra, Alvaro M. (2020). "Continuous groups of transversal gates for quantum error correcting codes from finite clock reference frames". Quantum. 4: 245. arXiv:1902.07725. Bibcode:2020Quant...4..245W. doi:10.22331/q-2020-03-23-245. S2CID 119302752.
3. Faist, Philippe; Nezami, Sepehr; V. Albert, Victor; Salton, Grant; Pastawski, Fernando; Hayden, Patrick; Preskill, John (2020). "Continuous Symmetries and Approximate Quantum Error Correction". Physical Review X. 10 (4): 041018. arXiv:1902.07714. Bibcode:2020PhRvX..10d1018F. doi:10.1103/PhysRevX.10.041018. S2CID 119207861.
4. Campbell, Earl T.; Terhal, Barbara M.; Vuillot, Christophe (2016). "Roads towards fault-tolerant universal quantum computation". Nature. 549 (7671): 172–179. arXiv:1612.07330. Bibcode:2017Natur.549..172C. doi:10.1038/nature23460. PMID 28905902. S2CID 4446310.
5. Yang, Yuxiang; Mo, Yin; Renes, Joseph M.; Chiribella, Giulio; Woods, Mischa (2022). "Optimal universal quantum error correction via bounded reference frames". Physical Review Research. 4 (2): 023107. arXiv:2007.09154. Bibcode:2022PhRvR...4b3107Y. doi:10.1103/PhysRevResearch.4.023107. S2CID 244488748.
6. Duclos-Cianci, Guillaume; Poulin, David (2014). "Reducing the quantum computing overhead with complex gate distillation". Physical Review A. 91 (4): 042315. arXiv:1309.3310. doi:10.1103/PhysRevA.91.042315. S2CID 73589915.
7. Paetznick, Adam; Reichardt, Ben W. (2014). "Universal fault-tolerant quantum computation with only transversal gates and error correction". Physical Review Letters. 111 (9): 090505. arXiv:1309.3310. doi:10.1103/PhysRevLett.111.090505. PMID 24033013. S2CID 20659050.
8. Shor, Peter (1996). "Fault-tolerant quantum computation". Proceedings of 37th Conference on Foundations of Computer Science. Vol. 102. pp. 56–65. doi:10.1109/SFCS.1996.548464. ISBN 978-0-8186-7594-2. S2CID 7508572.
9. Gottesman, Daniel; Chuang, Isaac L. (1999). "Quantum Teleportation is a Universal Computational Primitive". Nature. 402 (6760): 390–393. arXiv:quant-ph/9908010. Bibcode:1999Natur.402..390G. doi:10.1038/46503. S2CID 4411647.
10. Bravyi, Sergey; Kitaev, Alexei (2005). "Universal quantum computation with ideal Clifford gates and noisy ancillas". Physical Review A. 71 (2): 022316. arXiv:quant-ph/0403025. Bibcode:2005PhRvA..71b2316B. doi:10.1103/PhysRevA.71.022316. S2CID 17504370.
11. Jochym-O’Connor, Tomas; Laflamme, Raymond (2013). "Using Concatenated Quantum Codes for Universal Fault-Tolerant Quantum Gates". Physical Review Letters. 112 (1): 010505. arXiv:quant-ph/0403025. doi:10.1103/PhysRevLett.112.010505. PMID 24483879. S2CID 23069274.
12. Yoder, Theodore J.; Takagi, Ryuji (2016). "Universal fault-tolerant gates on concatenated stabilizer codes". Physical Review X. 6 (3): 090505. arXiv:1603.03948. Bibcode:2016PhRvX...6c1039Y. doi:10.1103/PhysRevX.6.031039. S2CID 39022969.
13. Levin, Michael A.; Wen, Xiao-Gang (2004). "String-net condensation: A physical mechanism for topological phases". Physical Review B. 71 (4): 045110. arXiv:cond-mat/0404617. doi:10.1103/PhysRevB.71.045110. S2CID 51962817.