Optimization of Lattice Surgery is NP-Hard
arXiv:1702.00591 · doi:10.1038/s41534-017-0035-1
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 (20)
- Polynomial-Time Algorithms for Prime Factorization and Discrete Logarithms on a Quantum Computer
- Surface codes: Towards practical large-scale quantum computation
- Logic gates at the surface code threshold: Superconducting qubits poised for fault-tolerant quantum computing
- Topological quantum memory
- Measurement-based quantum computation with cluster states
- Quantum Error Correction for Quantum Memories
- Multiple Particle Interference and Quantum Error Correction
- An addressable quantum dot qubit with fault-tolerant control fidelity
- High-fidelity two-qubit quantum logic gates using trapped calcium-43 ions
- High-fidelity quantum logic gates using trapped-ion hyperfine qubits
- Surface code quantum computing by lattice surgery
- High threshold universal quantum computation on the surface code
- Blueprint for a microwave trapped-ion quantum computer
- A fault-tolerant addressable spin qubit in a natural silicon quantum dot
- Efficient Distributed Quantum Computing
- Photonic architecture for scalable quantum information processing in NV-diamond
- Fault-tolerant error correction with the gauge color code
- Fault-Tolerant High Level Quantum Circuits: Form, Compilation and Description
- Classical Processing Requirements for a Topological Quantum Computing System
- 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