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
- 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) - Digitized Counterdiabatic Quantum Algorithms for Logistics Scheduling [33.04597339860113]
We study a job shop scheduling problem for an automatized robot and a travelling salesperson problem.
In DCQO, we find the solution of an optimization problem via an adiabatic quantum dynamics.
We experimentally implement our algorithms on superconducting and trapped-ion quantum processors.
arXiv Detail & Related papers (2024-05-24T16:53:30Z) - Qubit efficient quantum algorithms for the vehicle routing problem on
NISQ processors [48.68474702382697]
Vehicle routing problem with time windows (VRPTW) is a common optimization problem faced within the logistics industry.
In this work, we explore the use of a previously-introduced qubit encoding scheme to reduce the number of binary variables.
arXiv Detail & Related papers (2023-06-14T13:44:35Z) - Qubit Mapping and Routing via MaxSAT [6.711547274386115]
A critical problem for near-term quantum computing is laying out a logical circuit onto a physical device with limited connectivity between qubits.
It is important to solve QMR as optimally as possible to reduce the amount of added noise, which may render a quantum useless.
We present a novel approach for optimally solving the QMR problem via a reduction to maximum satisfiability (MAXSAT)
arXiv Detail & Related papers (2022-08-29T15:39:04Z) - Quantum Goemans-Williamson Algorithm with the Hadamard Test and
Approximate Amplitude Constraints [62.72309460291971]
We introduce a variational quantum algorithm for Goemans-Williamson algorithm that uses only $n+1$ qubits.
Efficient optimization is achieved by encoding the objective matrix as a properly parameterized unitary conditioned on an auxilary qubit.
We demonstrate the effectiveness of our protocol by devising an efficient quantum implementation of the Goemans-Williamson algorithm for various NP-hard problems.
arXiv Detail & Related papers (2022-06-30T03:15:23Z) - Near-Optimal Fidelity in Quantum Circuits through Incorporating
Efficient Real-time Error Based Heuristics in Compiler Mappings [0.0]
This paper focuses on finding efficient techniques to incorporate real-time error feedback and device connectivity information.
We show that our best approach performs better than one baseline and textbf1.934x ( on average ) better than the other baseline on random benchmarks.
arXiv Detail & Related papers (2022-04-18T20:06:44Z) - 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) - OMPQ: Orthogonal Mixed Precision Quantization [64.59700856607017]
Mixed precision quantization takes advantage of hardware's multiple bit-width arithmetic operations to unleash the full potential of network quantization.
We propose to optimize a proxy metric, the concept of networkity, which is highly correlated with the loss of the integer programming.
This approach reduces the search time and required data amount by orders of magnitude, with little compromise on quantization accuracy.
arXiv Detail & Related papers (2021-09-16T10:59:33Z) - Optimal qubit assignment and routing via integer programming [0.22940141855172028]
We consider the problem of mapping a logical quantum circuit onto a given hardware with limited two-qubit connectivity.
We model this problem as an integer linear program, using a network flow formulation with binary variables.
We consider several cost functions: an approximation of the fidelity of the circuit, its total depth, and a measure of cross-talk.
arXiv Detail & Related papers (2021-06-11T15:02:26Z) - Towards Optimally Efficient Tree Search with Deep Learning [76.64632985696237]
This paper investigates the classical integer least-squares problem which estimates signals integer from linear models.
The problem is NP-hard and often arises in diverse applications such as signal processing, bioinformatics, communications and machine learning.
We propose a general hyper-accelerated tree search (HATS) algorithm by employing a deep neural network to estimate the optimal estimation for the underlying simplified memory-bounded A* algorithm.
arXiv Detail & Related papers (2021-01-07T08:00: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)
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.