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:1310.0863

Optimal complexity correction of correlated errors in the surface code

Austin G. Fowler

Published Oct 2, 2013• 36 citations
arXivHTMLPDF

Abstract

The surface code is designed to suppress errors in quantum computing hardware and currently offers the most believable pathway to large-scale quantum computation. The surface code requires a 2-D array of nearest-neighbor coupled qubits that are capable of implementing a universal set of gates with error rates below approximately 1%, requirements compatible with experimental reality. Consequently, a number of authors are attempting to squeeze additional performance out of the surface code. We describe an optimal complexity error suppression algorithm, parallelizable to O(1) given constant computing resources per unit area, and provide evidence that this algorithm exploits correlations in the error models of each gate in an asymptotically optimal manner.

DOI
10.48550/arxiv.1310.0863

Related papers

Towards Practical Classical Processing for the Surface Code

Austin G. Fowler, Adam C. Whiteside, Lloyd C. L. Hollenberg

The surface code is unarguably the leading quantum error correction code for 2D nearest neighbor architectures, featuring a high threshold error rate of approximately 1%, low overhead implementations of the entire Clifford group, and flexible, arbitrarily long-range logical gates. These highly desirable features come at the cost of significant classical processing complexity. We show how to perform the processing associated with an n×n lattice of qubits, each being manipulated in a realistic, fault-tolerant manner, in O(n2) average time per round of error correction. We also describe how to parallelize the algorithm to achieve O(1) average processing per round, using only constant computing resources per unit area and local communication. Both of these complexities are optimal.

arXiv:1110.5133•Physical Review Letters•May 1, 2012•208 citations

Surface code quantum computing with error rates over 1%

David S. Wang, Austin G. Fowler, Lloyd C. L. Hollenberg

Large-scale quantum computation will only be achieved if experimentally implementable quantum error correction procedures are devised that can tolerate experimentally achievable error rates. We describe an improved decoding algorithm for the Kitaev surface code, which requires only a two-dimensional square lattice of qubits that can interact with their nearest neighbors, that raises the tolerable quantum gate error rate to over 1%. The precise maximum tolerable error rate depends on the error model, and we calculate values in the range 1.1--1.4% for various physically reasonable models. These values represent a very high threshold error rate calculated in a constrained setting.

arXiv:1009.3686•Physical Review A•Feb 18, 2011•345 citations

Hardness of Braided Quantum Circuit Optimization in the Surface Code

Wasa Kunihiro, Nishio Shin, Koki Suetsugu +4 more

Large-scale quantum information processing requires the use of quantum error-correcting codes to mitigate the effects of noise in quantum devices. Topological error-correcting codes, such as surface codes, are promising candidates, as they can be implemented using only local interactions in a 2-D array of physical qubits. Procedures, such as defect braiding and lattice surgery, can then be used to realize a fault-tolerant universal set of gates on the logical space of such topological codes. However, error correction also introduces a significant overhead in computation time, the number of physical qubits, and the number of physical gates. While optimizing fault-tolerant circuits to minimize this overhead is critical, the computational complexity of such optimization problems remains unknown. This ambiguity leaves room for doubt surrounding the most effective methods for compiling fault-tolerant circuits for a large-scale quantum computer. In this article, we show that the optimization of a special subset of braided quantum circuits is NP-hard by a polynomial-time reduction of the optimization problem into a specific problem called PlanarRectilinear3SAT.

•Mar 2, 2023•0 citations

Hardness of Braided Quantum Circuit Optimization in the Surface Code

Kunihiro Wasa, S. Nishio, Koki Suetsugu +4 more

Large-scale quantum information processing requires the use of quantum error correcting codes to mitigate the effects of noise in quantum devices. Topological error-correcting codes, such as surface codes, are promising candidates as they can be implemented using only local interactions in a twodimensional array of physical qubits. Procedures such as defect braiding and lattice surgery can then be used to realize a fault-tolerant universal set of gates on the logical space of such topological codes. However, error correction also introduces a significant overhead in computation time, the number of physical qubits, and the number of physical gates. While optimizing fault-tolerant circuits to minimize this overhead is critical, the computational complexity of such optimization problems remains unknown. This ambiguity leaves room for doubt surrounding the most effective methods for compiling fault-tolerant circuits for a large-scale quantum computer. In this paper, we show that the optimization of a special subset of braided quantum circuits is NP-hard by a polynomial-time reduction of the optimization problem into a specific problem called PlanarRectilinear3SAT.

arXiv:2302.00273•IEEE Transactions on Quantum Engineering•Jan 1, 2023•6 citations

Quantifying the effects of local many-qubit errors and nonlocal two-qubit errors on the surface code

Austin G. Fowler, John M. Martinis

Topological quantum error correction codes are known to be able to tolerate arbitrary local errors given sufficient qubits. This includes correlated errors involving many local qubits. In this work, we quantify this level of tolerance, numerically studying the effects of many-qubit errors on the performance of the surface code. We find that if increasingly large-area errors are at least moderately exponentially suppressed, arbitrarily reliable quantum computation can still be achieved with practical overhead. We furthermore quantify the effect of nonlocal two-qubit correlated errors, which would be expected in arrays of qubits coupled by a polynomially decaying interaction, and when using many-qubit coupling devices. We surprisingly find that the surface code is very robust to this class of errors, despite a provable lack of a threshold error rate when such errors are present.

arXiv:1401.2466•Physical Review A•Mar 12, 2014•49 citations

A bridge to lower overhead quantum computation

Austin G. Fowler, Simon J. Devitt

Two primary challenges stand in the way of practical large-scale quantum computation, namely achieving sufficiently low error rate quantum gates and implementing interesting quantum algorithms with a physically reasonable number of qubits. In this work we address the second challenge, presenting a new technique, bridge compression, which enables remarkably low volume structures to be found that implement complex computations in the surface code. The surface code has a number of highly desirable properties, including the ability to achieve arbitrarily reliable computation given sufficient qubits and quantum gate error rates below approximately 1%, and the use of only a 2-D array of qubits with nearest neighbor interactions. As such, our compression technique is of great practical relevance.

arXiv:1209.0510•Sep 4, 2012•58 citations
The surface code is designed to suppress errors in quantum computing hardware and currently offers the most believable pathway to large-scale quantum computation. The surface code requires a 2-D array of nearest-neighbor coupled qubits that are capable of implementing a universal set of gates with error rates below approximately 1%, requirements compatible with experimental reality. Consequently, a number of authors are attempting to squeeze additional performance out of the surface code. We describe an optimal complexity error suppression algorithm, parallelizable to O(1) given constant computing resources per unit area, and provide evidence that this algorithm exploits correlations in the error models of each gate in an asymptotically optimal manner.
The surface code is unarguably the leading quantum error correction code for 2D nearest neighbor architectures, featuring a high threshold error rate of approximately 1%, low overhead implementations of the entire Clifford group, and flexible, arbitrarily long-range logical gates. These highly desirable features come at the cost of significant classical processing complexity. We show how to perform the processing associated with an n×n lattice of qubits, each being manipulated in a realistic, fault-tolerant manner, in O(n2) average time per round of error correction. We also describe how to parallelize the algorithm to achieve O(1) average processing per round, using only constant computing resources per unit area and local communication. Both of these complexities are optimal.
Large-scale quantum computation will only be achieved if experimentally implementable quantum error correction procedures are devised that can tolerate experimentally achievable error rates. We describe an improved decoding algorithm for the Kitaev surface code, which requires only a two-dimensional square lattice of qubits that can interact with their nearest neighbors, that raises the tolerable quantum gate error rate to over 1%. The precise maximum tolerable error rate depends on the error model, and we calculate values in the range 1.1--1.4% for various physically reasonable models. These values represent a very high threshold error rate calculated in a constrained setting.
Large-scale quantum information processing requires the use of quantum error-correcting codes to mitigate the effects of noise in quantum devices. Topological error-correcting codes, such as surface codes, are promising candidates, as they can be implemented using only local interactions in a 2-D array of physical qubits. Procedures, such as defect braiding and lattice surgery, can then be used to realize a fault-tolerant universal set of gates on the logical space of such topological codes. However, error correction also introduces a significant overhead in computation time, the number of physical qubits, and the number of physical gates. While optimizing fault-tolerant circuits to minimize this overhead is critical, the computational complexity of such optimization problems remains unknown. This ambiguity leaves room for doubt surrounding the most effective methods for compiling fault-tolerant circuits for a large-scale quantum computer. In this article, we show that the optimization of a special subset of braided quantum circuits is NP-hard by a polynomial-time reduction of the optimization problem into a specific problem called PlanarRectilinear3SAT.
Large-scale quantum information processing requires the use of quantum error correcting codes to mitigate the effects of noise in quantum devices. Topological error-correcting codes, such as surface codes, are promising candidates as they can be implemented using only local interactions in a twodimensional array of physical qubits. Procedures such as defect braiding and lattice surgery can then be used to realize a fault-tolerant universal set of gates on the logical space of such topological codes. However, error correction also introduces a significant overhead in computation time, the number of physical qubits, and the number of physical gates. While optimizing fault-tolerant circuits to minimize this overhead is critical, the computational complexity of such optimization problems remains unknown. This ambiguity leaves room for doubt surrounding the most effective methods for compiling fault-tolerant circuits for a large-scale quantum computer. In this paper, we show that the optimization of a special subset of braided quantum circuits is NP-hard by a polynomial-time reduction of the optimization problem into a specific problem called PlanarRectilinear3SAT.
Topological quantum error correction codes are known to be able to tolerate arbitrary local errors given sufficient qubits. This includes correlated errors involving many local qubits. In this work, we quantify this level of tolerance, numerically studying the effects of many-qubit errors on the performance of the surface code. We find that if increasingly large-area errors are at least moderately exponentially suppressed, arbitrarily reliable quantum computation can still be achieved with practical overhead. We furthermore quantify the effect of nonlocal two-qubit correlated errors, which would be expected in arrays of qubits coupled by a polynomially decaying interaction, and when using many-qubit coupling devices. We surprisingly find that the surface code is very robust to this class of errors, despite a provable lack of a threshold error rate when such errors are present.
Two primary challenges stand in the way of practical large-scale quantum computation, namely achieving sufficiently low error rate quantum gates and implementing interesting quantum algorithms with a physically reasonable number of qubits. In this work we address the second challenge, presenting a new technique, bridge compression, which enables remarkably low volume structures to be found that implement complex computations in the surface code. The surface code has a number of highly desirable properties, including the ability to achieve arbitrarily reliable computation given sufficient qubits and quantum gate error rates below approximately 1%, and the use of only a 2-D array of qubits with nearest neighbor interactions. As such, our compression technique is of great practical relevance.