Optimization of lattice surgery is NP-hard

Daniel Herr*, Franco Nori, Simon J. Devitt

*Corresponding author for this work

Research output: Contribution to journalArticlepeer-review

17 Citations (Scopus)
55 Downloads (Pure)


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.

Original languageEnglish
Article number35
Pages (from-to)1-5
Number of pages5
Journalnpj quantum information
Publication statusPublished - 11 Sept 2017

Bibliographical note

Copyright the Author(s) 2017. Version archived for private and non-commercial use with the permission of the author/s and according to publisher conditions. For further rights please contact the publisher.


Dive into the research topics of 'Optimization of lattice surgery is NP-hard'. Together they form a unique fingerprint.

Cite this