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.
Practical applications of quantum computing depend on fault-tolerant devices with error correction. Today, the most promising approach is a class of error-correcting codes called surface codes. We study the problem of compiling quantum circuits for quantum computers implementing surface codes. Optimal or near-optimal compilation is critical for both efficiency and correctness. The compilation problem requires (1) mapping circuit qubits to the device qubits and (2) routing execution paths between interacting qubits. We solve this problem efficiently and near-optimally with a novel algorithm that exploits the dependency structure of circuit operations to formulate discrete optimization problems that can be approximated via simulated annealing, a classic and simple algorithm. Our extensive evaluation shows that our approach is powerful and flexible for compiling realistic workloads.
Efficient decoding is essential for the practical realization of fault-tolerant quantum computers. We study the computational complexity of minimum-weight decoding for topological quantum codes. For surface codes under the depolarizing channel, we consider Minimum-Weight decoding, which seeks a minimum-weight Pauli error consistent with both the
X- and
Z-syndromes. For color codes under independent
X- and
Z-error models, we consider Separate Minimum-Weight decoding.
Assuming
P=NP, we establish polynomial additive inapproximability gaps for these problems. Specifically, for the toric code and the
4.8.8 color code on the torus, there exists a constant
c>0 such that no polynomial-time algorithm can always produce a solution whose weight is within
cN1/14 of the optimum, where
N is the number of qubits, unless
P=NP. For the planar surface code, we obtain an
Ω(N1/18) gap. Our inapproximability results use Håstad's hardness of approximation for MAX-3SAT.
Our reduction develops a general, modular framework for embedding logical constraints into coupled primal--dual join problems on a lattice. A key ingredient is a localization argument that controls unintended interactions between different parts of the construction.
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.
Quantum technologies have the potential to solve certain computationally hard problems with polynomial or super-polynomial speedups when compared to classical methods. Unfortunately, the unstable nature of quantum information makes it prone to errors. For this reason, quantum error correction is an invaluable tool to make quantum information reliable and enable the ultimate goal of fault-tolerant quantum computing. Surface codes currently stand as the most promising candidates to build near term error corrected qubits given their two-dimensional architecture, the requirement of only local operations, and high tolerance to quantum noise. Decoding algorithms are an integral component of any error correction scheme, as they are tasked with producing accurate estimates of the errors that affect quantum information, so that they can subsequently be corrected. A critical aspect of decoding algorithms is their speed, since the quantum state will suffer additional errors with the passage of time. This poses a connundrum, where decoding performance is improved at the expense of complexity and viceversa. In this review, a thorough discussion of state-of-the-art decoding algorithms for surface codes is provided. The target audience of this work are both readers with an introductory understanding of the field as well as those seeking to further their knowledge of the decoding paradigm of surface codes. We describe the core principles of these decoding methods as well as existing variants that show promise for improved results. In addition, both the decoding performance, in terms of error correction capability, and decoding complexity, are compared. A review of the existing software tools regarding surface codes decoding is also provided.
Quantum Error Correction (QEC) is required in quantum computers to mitigate the effect of errors on physical qubits. When adopting a QEC scheme based on surface codes, error decoding is the most computationally expensive task in the classical electronic back-end. Decoders employing neural networks (NN) are well-suited for this task but their hardware implementation has not been presented yet. This work presents a space exploration of fully-connected feed-forward NN decoders for small distance surface codes. The goal is to optimize the neural network for high decoding performance, while keeping a minimalistic hardware implementation. This is needed to meet the tight delay constraints of real-time surface code decoding. We demonstrate that hardware based NN-decoders can achieve high decoding performance comparable to other state-of-the-art decoding algorithms whilst being well below the tight delay requirements (440 ns) of current solid-state qubit technologies for both ASIC designs (<30 ns) and FPGA implementations (<90 ns). These results indicate that NN-decoders are viable candidates for further exploration of an integrated hardware implementation in future large-scale quantum computers.