Compilation for Surface Code Quantum Computers

• URL: http://arxiv.org/abs/2311.18042v1
• Date: Wed, 29 Nov 2023 19:36:19 GMT
• Title: Compilation for Surface Code Quantum Computers
• Authors: Abtin Molavi, Amanda Xu, Swamit Tannu, Aws Albarghouthi
• Abstract summary: We study the problem of compiling quantum circuits for quantum computers implementing surface codes. The problem involves (1) mapping circuit qubits to the device qubits and (2) routing execution paths between pairs of interacting qubits. We present a spectrum of efficient relaxations of SCMR, for example, by exploiting greedy algorithms for solving the problem of node-disjoint paths.
• Score: 8.093450284837559
• License: http://creativecommons.org/licenses/by-nc-sa/4.0/
• Abstract: 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. In this paper, we study the problem of compiling quantum circuits for quantum computers implementing surface codes. The problem involves (1) mapping circuit qubits to the device qubits and (2) routing execution paths between pairs of interacting qubits. We call this the surface code mapping and routing problem (SCMR). Solving SCMR near-optimally is critical for both efficiency and correctness. An optimal solution limits the cost of a computation in terms of precious quantum resources and also minimizes the probability of incurring an undetected logical error, which increases with each additional time step. We study SCMR from a theoretical and practical perspective. First, we prove that SCMR, as well as a constrained version of the problem, is NP-complete. Second, we present a optimal algorithm for solving SCMR that is based on a SAT encoding. Third, we present a spectrum of efficient relaxations of SCMR, for example, by exploiting greedy algorithms for solving the problem of node-disjoint paths. Finally, we implement and evaluate our algorithms on a large suite of real and synthetic circuits. Our results suggest that our relaxations are a powerful tool for compiling realistic workloads. The relaxation-based algorithms are orders of magnitude faster than the optimal algorithm (solving instances with tens of thousands of gates in minutes), while still finding high-quality solutions, achieving the theoretical lower bound on up to 55 out of 168 circuits from a diverse benchmark suite.

Related papers

• Optimized Qubit Routing for Commuting Gates via Integer Programming [0.0]
  We propose a two-step decomposition approach based on integer programming, which is guaranteed to return an optimal solution.<n>We develop several integer programming models and derive linear descriptions of related polytopes, which generalize to applications beyond this work.
  arXiv  Detail & Related papers  (2025-07-16T12:55:09Z)
• Fast correlated decoding of transversal logical algorithms [67.01652927671279]
  Quantum error correction (QEC) is required for large-scale computation, but incurs a significant resource overhead.<n>Recent advances have shown that by jointly decoding logical qubits in algorithms composed of logical gates, the number of syndrome extraction rounds can be reduced.<n>Here, we reform the problem of decoding circuits by directly decoding relevant logical operator products as they propagate through the circuit.
  arXiv  Detail & Related papers  (2025-05-19T18:00:00Z)
• Constant-time hybrid compilation of Shor's algorithm with quantum just-in-time compilation [0.0]
  This work provides an implementation of Shor's factoring algorithm, compiled to elementary quantum gates using PennyLane and Catalyst. We demonstrate that with QJIT compilation, the algorithm is compiled once per bit width of $N$, even when $N$-specific optimizations are applied to circuit generation. The implementation is benchmarked up to 32-bit $N$, and both the size of the compiled program and the pure compilation time are found to be constant.
  arXiv  Detail & Related papers  (2025-04-16T19:30:10Z)
• Snakes and Ladders: Adapting the surface code to defects [36.136619420474766]
  We develop a suite of novel and highly performant methods for adapting surface code patches in the presence of defective qubits and gates. Compared to prior works, our methods significantly improve the code distance of the adapted surface code patches for realistic defect rates.
  arXiv  Detail & Related papers  (2024-12-16T07:27:24Z)
• Quantum Compiling with Reinforcement Learning on a Superconducting Processor [55.135709564322624]
  We develop a reinforcement learning-based quantum compiler for a superconducting processor. We demonstrate its capability of discovering novel and hardware-amenable circuits with short lengths. Our study exemplifies the codesign of the software with hardware for efficient quantum compilation.
  arXiv  Detail & Related papers  (2024-06-18T01:49:48Z)
• A Fast and Adaptable Algorithm for Optimal Multi-Qubit Pathfinding in Quantum Circuit Compilation [0.0]
  This work focuses on multi-qubit pathfinding as a critical subroutine within the quantum circuit compilation mapping problem. We introduce an algorithm, modelled using binary integer linear programming, that navigates qubits on quantum hardware optimally with respect to circuit SWAP-gate depth. We have benchmarked the algorithm across a variety of quantum hardware layouts, assessing properties such as computational runtimes, solution SWAP depths, and accumulated SWAP-gate error rates.
  arXiv  Detail & Related papers  (2024-05-29T05:59:15Z)
• Optimizing quantum gates towards the scale of logical qubits [78.55133994211627]
  A foundational assumption of quantum gates theory is that quantum gates can be scaled to large processors without exceeding the error-threshold for fault tolerance. Here we report on a strategy that can overcome such problems. We demonstrate it by choreographing the frequency trajectories of 68 frequency-tunablebits to execute single qubit while superconducting errors.
  arXiv  Detail & Related papers  (2023-08-04T13:39:46Z)
• Mapping quantum circuits to modular architectures with QUBO [3.0148208709026005]
  In multi-core architectures, it is crucial to minimize the amount of communication between cores when executing an algorithm. We propose for the first time a Quadratic Unconstrained Binary Optimization technique to encode the problem and the solution. Our method showed promising results and performed exceptionally well with very dense and highly-parallelized circuits.
  arXiv  Detail & Related papers  (2023-05-11T09:45:47Z)
• Hardness of braided quantum circuit optimization in the surface code [0.1759008116536278]
  Large-scale quantum information processing requires the use of quantum error 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. However, error correction also introduces a significant overhead in time, the number of physical qubits, and the number of physical gates.
  arXiv  Detail & Related papers  (2023-02-01T06:35:50Z)
• Error Mitigation for Quantum Approximate Optimization [0.0]
  We show how a redundant encoding of logical variables can be exploited to mitigate errors in quantum optimization algorithms. In the specific context of the quantum approximate optimization algorithm (QAOA), we show that errors can be significantly mitigated by appropriately modifying the objective cost function.
  arXiv  Detail & Related papers  (2023-01-12T14:13:06Z)
• A Hybrid Quantum-Classical Algorithm for Robust Fitting [47.42391857319388]
  We propose a hybrid quantum-classical algorithm for robust fitting. Our core contribution is a novel robust fitting formulation that solves a sequence of integer programs. We present results obtained using an actual quantum computer.
  arXiv  Detail & Related papers  (2022-01-25T05:59:24Z)
• Scaling Quantum Approximate Optimization on Near-term Hardware [49.94954584453379]
  We quantify scaling of the expected resource requirements by optimized circuits for hardware architectures with varying levels of connectivity. We show the number of measurements, and hence total time to synthesizing solution, grows exponentially in problem size and problem graph degree. These problems may be alleviated by increasing hardware connectivity or by recently proposed modifications to the QAOA that achieve higher performance with fewer circuit layers.
  arXiv  Detail & Related papers  (2022-01-06T21:02:30Z)
• Variational Quantum Optimization with Multi-Basis Encodings [62.72309460291971]
  We introduce a new variational quantum algorithm that benefits from two innovations: multi-basis graph complexity and nonlinear activation functions. Our results in increased optimization performance, two increase in effective landscapes and a reduction in measurement progress.
  arXiv  Detail & Related papers  (2021-06-24T20:16:02Z)
• Space-efficient binary optimization for variational computing [68.8204255655161]
  We show that it is possible to greatly reduce the number of qubits needed for the Traveling Salesman Problem. We also propose encoding schemes which smoothly interpolate between the qubit-efficient and the circuit depth-efficient models.
  arXiv  Detail & Related papers  (2020-09-15T18:17:27Z)
• Compilation of Fault-Tolerant Quantum Heuristics for Combinatorial Optimization [0.14755786263360526]
  We explore which quantum algorithms for optimization might be most practical to try out on a small fault-tolerant quantum computer. Our results discourage the notion that any quantum optimization realizing only a quadratic speedup will achieve an advantage over classical algorithms.
  arXiv  Detail & Related papers  (2020-07-14T22:54:04Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.