Hardness of braided quantum circuit optimization in the surface code
arXiv:2302.00273 · doi:10.1109/TQE.2023.3251358
Abstract
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 two-dimensional 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 Planar Rectilinear 3SAT.
arXiv comment9 pages, 9 figures
References in corpus (19)
- Elementary gates for quantum computation
- Quantum cryptography: Public key distribution and coin tossing
- Surface codes: Towards practical large-scale quantum computation
- Two-Bit Gates are Universal for Quantum Computation
- Fault-tolerant quantum computation with high threshold in two dimensions
- Stabilizer Codes and Quantum Error Correction
- How to factor 2048 bit RSA integers in 8 hours using 20 million noisy qubits
- Surface code quantum computing by lattice surgery
- Universality in Quantum Computation
- A Universal Two--Bit Gate for Quantum Computation
- Layered architecture for quantum computing
- Tradeoffs for reliable quantum information storage in 2D systems
- Fault-tolerant thresholds for quantum error correction with the surface code
- Fault-Tolerant High Level Quantum Circuits: Form, Compilation and Description
- Requirements for fault-tolerant factoring on an atom-optics quantum computer
- A bridge to lower overhead quantum computation
- Optimization of Lattice Surgery is NP-Hard
- Quantum circuit optimization by topological compaction in the surface code
- Effective Compression of Quantum Braided Circuits Aided by ZX-Calculus