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

Quantum circuit optimization by topological compaction in the surface code

Adam Paetznick, Austin G. Fowler

Published Apr 9, 2013• 19 citations
arXivHTMLPDF

Abstract

The fragile nature of quantum information limits our ability to construct large quantities of quantum bits suitable for quantum computing. An important goal, therefore, is to minimize the amount of resources required to implement quantum algorithms, many of which are serial in nature and leave large numbers of qubits idle much of the time unless compression techniques are used. Furthermore, quantum error-correcting codes, which are required to reduce the effects of noise, introduce additional resource overhead. We consider a strategy for quantum circuit optimization based on topological deformation in the surface code, one of the best performing and most practical quantum error-correcting codes. Specifically, we examine the problem of minimizing computation time on a two-dimensional qubit lattice of arbitrary, but fixed dimension, and propose two algorithms for doing so.

DOI
10.48550/arxiv.1304.2807

Related papers

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

Quantum Error Correction Codes: Topological Optimization

Jincheng Zhang

This paper investigates the application of topological optimization techniques to quantum error correction codes. The core claim is that optimizing the topological structure of quantum error correction codes can significantly reduce error correction resource consumption and enhance the resilience of quantum computations. This is achieved through the utilization of topological optimization algorithms to identify optimal sub-graph structures within the topological network of a quantum error correction code, minimizing resource usage while maintaining sufficient error correction capability. We present a novel approach to quantum error correction design, moving beyond traditional code selection and offering a framework for dynamic code adaptation. The theoretical framework incorporates concepts from graph theory, linear algebra, and quantum information theory. The primary objective is to demonstrate a method for systematically reducing the overhead associated with quantum error correction, a critical step towards building fault-tolerant quantum computers. Our approach focuses on minimizing the number of physical qubits required to encode a logical qubit, a key metric for evaluating the efficiency of any quantum error correction scheme. The results indicate a substantial potential for optimization, suggesting a path toward more practical and scalable quantum computation.

•Sep 5, 2026•0 citations

Fault-tolerance thresholds for the surface code with fabrication errors

James M. Auger, Hussain Anwar, Mercedes Gimeno-Segovia +2 more

The construction of topological error correction codes requires the ability to fabricate a lattice of physical qubits embedded on a manifold with a nontrivial topology such that the quantum information is encoded in the global degrees of freedom (i.e., the topology) of the manifold. However, the manufacturing of large-scale topological devices will undoubtedly suffer from fabrication errors---permanent faulty components such as missing physical qubits or failed entangling gates---introducing permanent defects into the topology of the lattice and hence significantly reducing the distance of the code and the quality of the encoded logical qubits. In this work we investigate how fabrication errors affect the performance of topological codes, using the surface code as the test bed. A known approach to mitigate defective lattices involves the use of primitive swap gates in a long sequence of syndrome extraction circuits. Instead, we show that in the presence of fabrication errors the syndrome can be determined using the supercheck operator approach and the outcome of the defective gauge stabilizer generators without any additional computational overhead or use of swap gates. We report numerical fault-tolerance thresholds in the presence of both qubit fabrication and gate fabrication errors using a circuit-based noise model and the minimum-weight perfect-matching decoder. Our numerical analysis is most applicable to two-dimensional chip-based technologies, but the techniques presented here can be readily extended to other topological architectures. We find that in the presence of $8%$ qubit fabrication errors, the surface code can still tolerate a computational error rate of up to $0.1%$.

arXiv:1706.04912•Physical Review A•Oct 12, 2017•39 citations

Comparative study of quantum error correction strategies for the heavy-hexagonal lattice

César Benito, Esperanza López, Borja Peropadre +1 more

Topological quantum error correction is a milestone in the scaling roadmap of quantum computers, which targets circuits with trillions of gates that would allow running quantum algorithms for real-world problems. The square-lattice surface code has become the workhorse to address this challenge, as it poses milder requirements on current devices both in terms of required error rates and small local connectivities. In some platforms, however, the connectivities are kept even lower in order to minimise gate errors at the hardware level, which limits the error correcting codes that can be directly implemented on them. In this work, we make a comparative study of possible strategies to overcome this limitation for the heavy-hexagonal lattice, the architecture of current IBM superconducting quantum computers. We explore two complementary strategies: the search for an efficient embedding of the surface code into the heavy-hexagonal lattice, as well as the use of codes whose connectivity requirements are naturally tailored to this architecture, such as subsystem-type and Floquet codes. Using noise models of increased complexity, we assess the performance of these strategies for IBM devices in terms of their error thresholds and qubit footprints. An optimized SWAP-based embedding of the surface code is found to be the most promising strategy towards a near-term demonstration of quantum error correction advantage.

arXiv:2402.02185•Quantum•Feb 6, 2025•14 citations

A Bridge-based Compression Algorithm for Topological Quantum Circuits

Chen-Hao Hsu, Wan-Hsuan Lin, Wei-Hsiang Tseng +1 more

The topological quantum error correction (TQEC) scheme is promising for scalable and reliable quantum computing. A TQEC circuit can be modeled by a three-dimensional diagram, and the implementation resource of a TQEC circuit is abstracted to its space-time volume. Implementing a quantum algorithm with a reasonable physical qubit number and reasonable computation time is challenging for large-scale practical problems. Therefore, minimizing the space-time volume of a TQEC circuit becomes a crucial issue. Previous work shows that bridge compression can greatly compress TQEC circuits, but it was performed only manually. It is desirable to develop automated compression techniques for TQEC circuits to achieve low-overhead, large-scale quantum computations. In this paper, we present the first work that can automatically perform bridge compression on TQEC circuits. Compared with the state-of-the-art method, experimental results show that our proposed algorithm can averagely reduce space-time volumes by 83%.

ACM/IEEE Design Automation Conference (DAC)•Nov 8, 2021•5 citations
The fragile nature of quantum information limits our ability to construct large quantities of quantum bits suitable for quantum computing. An important goal, therefore, is to minimize the amount of resources required to implement quantum algorithms, many of which are serial in nature and leave large numbers of qubits idle much of the time unless compression techniques are used. Furthermore, quantum error-correcting codes, which are required to reduce the effects of noise, introduce additional resource overhead. We consider a strategy for quantum circuit optimization based on topological deformation in the surface code, one of the best performing and most practical quantum error-correcting codes. Specifically, we examine the problem of minimizing computation time on a two-dimensional qubit lattice of arbitrary, but fixed dimension, and propose two algorithms for doing so.
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.
This paper investigates the application of topological optimization techniques to quantum error correction codes. The core claim is that optimizing the topological structure of quantum error correction codes can significantly reduce error correction resource consumption and enhance the resilience of quantum computations. This is achieved through the utilization of topological optimization algorithms to identify optimal sub-graph structures within the topological network of a quantum error correction code, minimizing resource usage while maintaining sufficient error correction capability. We present a novel approach to quantum error correction design, moving beyond traditional code selection and offering a framework for dynamic code adaptation. The theoretical framework incorporates concepts from graph theory, linear algebra, and quantum information theory. The primary objective is to demonstrate a method for systematically reducing the overhead associated with quantum error correction, a critical step towards building fault-tolerant quantum computers. Our approach focuses on minimizing the number of physical qubits required to encode a logical qubit, a key metric for evaluating the efficiency of any quantum error correction scheme. The results indicate a substantial potential for optimization, suggesting a path toward more practical and scalable quantum computation.
The construction of topological error correction codes requires the ability to fabricate a lattice of physical qubits embedded on a manifold with a nontrivial topology such that the quantum information is encoded in the global degrees of freedom (i.e., the topology) of the manifold. However, the manufacturing of large-scale topological devices will undoubtedly suffer from fabrication errors---permanent faulty components such as missing physical qubits or failed entangling gates---introducing permanent defects into the topology of the lattice and hence significantly reducing the distance of the code and the quality of the encoded logical qubits. In this work we investigate how fabrication errors affect the performance of topological codes, using the surface code as the test bed. A known approach to mitigate defective lattices involves the use of primitive swap gates in a long sequence of syndrome extraction circuits. Instead, we show that in the presence of fabrication errors the syndrome can be determined using the supercheck operator approach and the outcome of the defective gauge stabilizer generators without any additional computational overhead or use of swap gates. We report numerical fault-tolerance thresholds in the presence of both qubit fabrication and gate fabrication errors using a circuit-based noise model and the minimum-weight perfect-matching decoder. Our numerical analysis is most applicable to two-dimensional chip-based technologies, but the techniques presented here can be readily extended to other topological architectures. We find that in the presence of 88%8 qubit fabrication errors, the surface code can still tolerate a computational error rate of up to 0.10.1%0.1.
Topological quantum error correction is a milestone in the scaling roadmap of quantum computers, which targets circuits with trillions of gates that would allow running quantum algorithms for real-world problems. The square-lattice surface code has become the workhorse to address this challenge, as it poses milder requirements on current devices both in terms of required error rates and small local connectivities. In some platforms, however, the connectivities are kept even lower in order to minimise gate errors at the hardware level, which limits the error correcting codes that can be directly implemented on them. In this work, we make a comparative study of possible strategies to overcome this limitation for the heavy-hexagonal lattice, the architecture of current IBM superconducting quantum computers. We explore two complementary strategies: the search for an efficient embedding of the surface code into the heavy-hexagonal lattice, as well as the use of codes whose connectivity requirements are naturally tailored to this architecture, such as subsystem-type and Floquet codes. Using noise models of increased complexity, we assess the performance of these strategies for IBM devices in terms of their error thresholds and qubit footprints. An optimized SWAP-based embedding of the surface code is found to be the most promising strategy towards a near-term demonstration of quantum error correction advantage.
The topological quantum error correction (TQEC) scheme is promising for scalable and reliable quantum computing. A TQEC circuit can be modeled by a three-dimensional diagram, and the implementation resource of a TQEC circuit is abstracted to its space-time volume. Implementing a quantum algorithm with a reasonable physical qubit number and reasonable computation time is challenging for large-scale practical problems. Therefore, minimizing the space-time volume of a TQEC circuit becomes a crucial issue. Previous work shows that bridge compression can greatly compress TQEC circuits, but it was performed only manually. It is desirable to develop automated compression techniques for TQEC circuits to achieve low-overhead, large-scale quantum computations. In this paper, we present the first work that can automatically perform bridge compression on TQEC circuits. Compared with the state-of-the-art method, experimental results show that our proposed algorithm can averagely reduce space-time volumes by 83%.