Optimization of Lattice Surgery 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.

References in corpus (5)

• Surface codes: Towards practical large-scale quantum computation
• An addressable quantum dot qubit with fault-tolerant control fidelity
• A fault-tolerant addressable spin qubit in a natural silicon quantum dot
• Efficient Distributed Quantum Computing
• Lattice Surgery Translation for Quantum Computation

Cited by in corpus (18)

• A Game of Surface Codes: Large-Scale Quantum Computing with Lattice Surgery
• Blueprint for a Scalable Photonic Fault-Tolerant Quantum Computer
• Entangling logical qubits with lattice surgery
• Quantum circuit optimizations for NISQ architectures
• On the CNOT-complexity of CNOT-PHASE circuits
• Mapping of Lattice Surgery-based Quantum Circuits on Surface Code Architectures
• Algebraic Compression of Quantum Circuits for Hamiltonian Evolution
• Constant-Depth Circuits for Dynamic Simulations of Materials on Quantum Computers
• A High Performance Compiler for Very Large Scale Surface Code Computations
• Phase polynomials synthesis algorithms for NISQ architectures and beyond
• Lattice Surgery on the Raussendorf Lattice
• Realistic Cost to Execute Practical Quantum Circuits using Direct Clifford+T Lattice Surgery Compilation
• Domain-Specific Compilers for Dynamic Simulations of Quantum Materials on Quantum Computers
• Hardness of braided quantum circuit optimization in the surface code
• Methods for Classically Simulating Noisy Networked Quantum Architectures
• Quantum Software Ecosystem Design
• Lattice Surgery Compilation Beyond the Surface Code
• Lattice Surgery for Dummies