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:1912.11503 · Physical Review X

Effective Compression of Quantum Braided Circuits Aided by ZX-Calculus

Michael Hanks, Marta P. Estarellas, William J. Munro, Kae Nemoto

Published Nov 11, 2020• 28 citations
arXivHTMLPDF

Abstract

Mapping a quantum algorithm to any practical large-scale quantum computer will require a sequence of compilations and optimizations.At the level of fault-tolerant encoding, one likely requirement of this process is the translation into a topological circuit, for which braided circuits represent one candidate model.Given the large overhead associated with encoded circuits, it is paramount to reduce their size in terms of computation time and qubit number through circuit compression.While these optimizations have typically been performed in the language of three-dimensional diagrams, such a representation does not allow an efficient, general, and scalable approach to reduction or verification.We propose the use of the ZX-calculus as an intermediate language for braided circuit compression, demonstrating advantage by comparing results using this approach with those previously obtained for the compression of jAi and jYi state distillation circuits.We then provide a benchmark of our method against a small set of Clifford þ T circuits, yielding compression percentages of ∼77%.Our results suggest that the overheads of braided, defect-based circuits are comparable to those of their lattice-surgery counterparts, restoring the potential of this model for surface-code quantum computation.

DOI
10.1103/physrevx.10.041030

Related papers

Untangling Surface Codes: Bridging Braids and Lattice Surgery

Alexandru Paler

We present a systematic method for translating fault-tolerant quantum circuits between their braiding and lattice surgery (LS) representations within the surface code. Our approach employs the ZX calculus to establish an equivalence between these two paradigms, enabling verified, bidirectional conversion of arbitrary surface-code-level circuits. We show that both braiding and LS operations can be uniformly expressed as compositions of multibody measurements and demonstrate that the Raussendorf compression rule encompasses all known braid and bridge optimizations. We also introduce a novel CNOT circuit with LS. Our framework provides a foundation for the automated verification, compilation, and benchmarking of large-scale surface code computations, advancing toward a unified formal language for topological quantum computation.

quant-pharXiv:2511.22290•Nov 28, 2025•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

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

String Diagrams for Defect-Based Surface Code Computing

Mateusz Kupper, Dominic C. Horsman, Chris Heunen +1 more

Surface codes are a popular choice for implementing fault-tolerant quantum computing.Two-qubit gates may be realised in these codes using only nearest-neighbour interactions, either by lattice surgery [27] or by braiding defects around each other [43].The effect of lattice surgery operations may be simply described [3] using the ZX-calculus: a graphical language that has proven effective for program design and optimisation (see e.g.[23]).In this work, we formalise a similar description via the ZX-calculus of defect braiding, as it is conventionally described.We define a graphical calculus KNOT, denoting the logical effects (in the absence of byproduct operations) of defect braiding in surface codes: we show how these effects may be described via a fragment of ZX-calculus which we call the (0, π)-fragment.We then use a 'doubling' construction to define a subtheory of KNOT, more specialised to standard encoding techniques in the defect braiding literature.Within this subtheory, we encompass standard braiding techniques by families of 'ribbon-like' and 'tangle-like' diagrams, each with semantics distinct from KNOT, in terms of the (0, π)-fragment of ZX diagrams (again in the absence of byproducts).These subtheories may be used interoperably, and are each sound and complete for the (0, π)-fragment of ZX diagrams.This provides a starting point to use the formal diagrammatics to analyse the operational effects of defect braiding procedures.* Corresponding author; author order is reverse-alphabetical, with the purpose of sowing confusion.

arXiv:2508.14672•Electronic Proceedings in Theoretical Computer Science•Aug 19, 2025•1 citation

Optimization of lattice surgery is NP-hard

Daniel Herr, Franco Nori, Simon J. Devitt

The traditional method for computation in either the surface code or in the Raussendorf model is the creation of holes or “defects” within the encoded lattice of qubits that are manipulated via topological braiding to enact logic gates. However, this is not the only way to achieve universal, fault-tolerant computation. In this work, we focus on the lattice surgery representation, which realizes transversal logic operations without destroying the intrinsic 2D nearest-neighbor properties of the braid-based surface code and achieves universality without defects and braid-based logic. For both techniques there are open questions regarding the compilation and resource optimization of quantum circuits. Optimization in braid-based logic is proving to be difficult and the classical complexity associated with this problem has yet to be determined. In the context of lattice-surgery-based logic, we can introduce an optimality condition, which corresponds to a circuit with the lowest resource requirements in terms of physical qubits and computational time, and prove that the complexity of optimizing a quantum circuit in the lattice surgery model is NP-hard.

•Jan 1, 2017•22 citations

Optimization of lattice surgery is NP-hard

Daniel Herr, Franco Nori, Simon J. Devitt

Abstract The traditional method for computation in either the surface code or in the Raussendorf model is the creation of holes or “defects” within the encoded lattice of qubits that are manipulated via topological braiding to enact logic gates. However, this is not the only way to achieve universal, fault-tolerant computation. In this work, we focus on the lattice surgery representation, which realizes transversal logic operations without destroying the intrinsic 2D nearest-neighbor properties of the braid-based surface code and achieves universality without defects and braid-based logic. For both techniques there are open questions regarding the compilation and resource optimization of quantum circuits. Optimization in braid-based logic is proving to be difficult and the classical complexity associated with this problem has yet to be determined. In the context of lattice-surgery-based logic, we can introduce an optimality condition, which corresponds to a circuit with the lowest resource requirements in terms of physical qubits and computational time, and prove that the complexity of optimizing a quantum circuit in the lattice surgery model is NP-hard.

arXiv:1702.00591•npj Quantum Information•Aug 22, 2017•31 citations
Mapping a quantum algorithm to any practical large-scale quantum computer will require a sequence of compilations and optimizations.At the level of fault-tolerant encoding, one likely requirement of this process is the translation into a topological circuit, for which braided circuits represent one candidate model.Given the large overhead associated with encoded circuits, it is paramount to reduce their size in terms of computation time and qubit number through circuit compression.While these optimizations have typically been performed in the language of three-dimensional diagrams, such a representation does not allow an efficient, general, and scalable approach to reduction or verification.We propose the use of the ZX-calculus as an intermediate language for braided circuit compression, demonstrating advantage by comparing results using this approach with those previously obtained for the compression of jAi and jYi state distillation circuits.We then provide a benchmark of our method against a small set of Clifford þ T circuits, yielding compression percentages of ∼77%.Our results suggest that the overheads of braided, defect-based circuits are comparable to those of their lattice-surgery counterparts, restoring the potential of this model for surface-code quantum computation.
We present a systematic method for translating fault-tolerant quantum circuits between their braiding and lattice surgery (LS) representations within the surface code. Our approach employs the ZX calculus to establish an equivalence between these two paradigms, enabling verified, bidirectional conversion of arbitrary surface-code-level circuits. We show that both braiding and LS operations can be uniformly expressed as compositions of multibody measurements and demonstrate that the Raussendorf compression rule encompasses all known braid and bridge optimizations. We also introduce a novel CNOT circuit with LS. Our framework provides a foundation for the automated verification, compilation, and benchmarking of large-scale surface code computations, advancing toward a unified formal language for topological quantum computation.
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.
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.
Surface codes are a popular choice for implementing fault-tolerant quantum computing.Two-qubit gates may be realised in these codes using only nearest-neighbour interactions, either by lattice surgery [27] or by braiding defects around each other [43].The effect of lattice surgery operations may be simply described [3] using the ZX-calculus: a graphical language that has proven effective for program design and optimisation (see e.g.[23]).In this work, we formalise a similar description via the ZX-calculus of defect braiding, as it is conventionally described.We define a graphical calculus KNOT, denoting the logical effects (in the absence of byproduct operations) of defect braiding in surface codes: we show how these effects may be described via a fragment of ZX-calculus which we call the (0, π)-fragment.We then use a 'doubling' construction to define a subtheory of KNOT, more specialised to standard encoding techniques in the defect braiding literature.Within this subtheory, we encompass standard braiding techniques by families of 'ribbon-like' and 'tangle-like' diagrams, each with semantics distinct from KNOT, in terms of the (0, π)-fragment of ZX diagrams (again in the absence of byproducts).These subtheories may be used interoperably, and are each sound and complete for the (0, π)-fragment of ZX diagrams.This provides a starting point to use the formal diagrammatics to analyse the operational effects of defect braiding procedures.* Corresponding author; author order is reverse-alphabetical, with the purpose of sowing confusion.
The traditional method for computation in either the surface code or in the Raussendorf model is the creation of holes or “defects” within the encoded lattice of qubits that are manipulated via topological braiding to enact logic gates. However, this is not the only way to achieve universal, fault-tolerant computation. In this work, we focus on the lattice surgery representation, which realizes transversal logic operations without destroying the intrinsic 2D nearest-neighbor properties of the braid-based surface code and achieves universality without defects and braid-based logic. For both techniques there are open questions regarding the compilation and resource optimization of quantum circuits. Optimization in braid-based logic is proving to be difficult and the classical complexity associated with this problem has yet to be determined. In the context of lattice-surgery-based logic, we can introduce an optimality condition, which corresponds to a circuit with the lowest resource requirements in terms of physical qubits and computational time, and prove that the complexity of optimizing a quantum circuit in the lattice surgery model is NP-hard.
Abstract The traditional method for computation in either the surface code or in the Raussendorf model is the creation of holes or “defects” within the encoded lattice of qubits that are manipulated via topological braiding to enact logic gates. However, this is not the only way to achieve universal, fault-tolerant computation. In this work, we focus on the lattice surgery representation, which realizes transversal logic operations without destroying the intrinsic 2D nearest-neighbor properties of the braid-based surface code and achieves universality without defects and braid-based logic. For both techniques there are open questions regarding the compilation and resource optimization of quantum circuits. Optimization in braid-based logic is proving to be difficult and the classical complexity associated with this problem has yet to be determined. In the context of lattice-surgery-based logic, we can introduce an optimality condition, which corresponds to a circuit with the lowest resource requirements in terms of physical qubits and computational time, and prove that the complexity of optimizing a quantum circuit in the lattice surgery model is NP-hard.