Qubit Mapping and Routing via MaxSAT
- URL: http://arxiv.org/abs/2208.13679v1
- Date: Mon, 29 Aug 2022 15:39:04 GMT
- Title: Qubit Mapping and Routing via MaxSAT
- Authors: Abtin Molavi, Amanda Xu, Martin Diges, Lauren Pick, Swamit Tannu, Aws
Albarghouthi
- Abstract summary: 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)
- Score: 6.711547274386115
- License: http://creativecommons.org/licenses/by-nc-sa/4.0/
- Abstract: Near-term quantum computers will operate in a noisy environment, without
error correction. A critical problem for near-term quantum computing is laying
out a logical circuit onto a physical device with limited connectivity between
qubits. This is known as the qubit mapping and routing (QMR) problem, an
intractable combinatorial problem. It is important to solve QMR as optimally as
possible to reduce the amount of added noise, which may render a quantum
computation useless. In this paper, we present a novel approach for optimally
solving the QMR problem via a reduction to maximum satisfiability (MAXSAT).
Additionally, we present two novel relaxation ideas that shrink the size of the
MAXSAT constraints by exploiting the structure of a quantum circuit. Our
thorough empirical evaluation demonstrates (1) the scalability of our approach
compared to state-of-the-art optimal QMR techniques (solves more than 3x
benchmarks with 40x speedup), (2) the significant cost reduction compared to
state-of-the-art heuristic approaches (an average of ~5x swap reduction), and
(3) the power of our proposed constraint relaxations.
Related papers
- Scaling Up the Quantum Divide and Conquer Algorithm for Combinatorial Optimization [0.8121127831316319]
We propose a method for constructing quantum circuits which greatly reduces inter-device communication costs.
We show that we can construct tractable circuits nearly three times the size of previous QDCA methods while retaining a similar or greater level of quality.
arXiv Detail & Related papers (2024-05-01T20:49:50Z) - Improving Quantum and Classical Decomposition Methods for Vehicle Routing [2.4646794072984477]
We propose an elaborate combination of two decomposition methods, namely graph shrinking and circuit cutting.
Our results offer insights into the performance of algorithms for optimization problems within the constraints of current quantum technology.
arXiv Detail & Related papers (2024-04-08T14:19:25Z) - Compilation for Surface Code Quantum Computers [8.093450284837559]
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.
arXiv Detail & Related papers (2023-11-29T19:36:19Z) - Toward Consistent High-fidelity Quantum Learning on Unstable Devices via
Efficient In-situ Calibration [5.0854551390284]
In the near-term noisy intermediate-scale quantum (NISQ) era, high noise will significantly reduce the fidelity of quantum computing.
In this paper, we propose a novel quantum pulse-based noise adaptation framework, namely QuPAD.
Experiments show that the runtime on quantum devices of QuPAD with 8-10 qubits is less than 15 minutes, which is up to 270x faster than the parameter-shift approach.
arXiv Detail & Related papers (2023-09-12T15:39:06Z) - 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) - Efficient MILP Decomposition in Quantum Computing for ReLU Network
Robustness [2.854196251981274]
In this study, we examine two decomposition methods for Mixed-Integer Linear Programming (MILP)
We concentrate on breaking down the original problem into smaller subproblems, which are then solved iteratively using a combined quantum-classical hardware approach.
Our experimental results demonstrate that this approach can save up to 90% of qubits compared to existing methods on quantum annealing and gate-based quantum computers.
arXiv Detail & Related papers (2023-04-30T13:10:56Z) - QAOA-in-QAOA: solving large-scale MaxCut problems on small quantum
machines [81.4597482536073]
Quantum approximate optimization algorithms (QAOAs) utilize the power of quantum machines and inherit the spirit of adiabatic evolution.
We propose QAOA-in-QAOA ($textQAOA2$) to solve arbitrary large-scale MaxCut problems using quantum machines.
Our method can be seamlessly embedded into other advanced strategies to enhance the capability of QAOAs in large-scale optimization problems.
arXiv Detail & Related papers (2022-05-24T03:49:10Z) - Adiabatic Quantum Computing for Multi Object Tracking [170.8716555363907]
Multi-Object Tracking (MOT) is most often approached in the tracking-by-detection paradigm, where object detections are associated through time.
As these optimization problems are often NP-hard, they can only be solved exactly for small instances on current hardware.
We show that our approach is competitive compared with state-of-the-art optimization-based approaches, even when using of-the-shelf integer programming solvers.
arXiv Detail & Related papers (2022-02-17T18:59:20Z) - 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) - Error mitigation and quantum-assisted simulation in the error corrected
regime [77.34726150561087]
A standard approach to quantum computing is based on the idea of promoting a classically simulable and fault-tolerant set of operations.
We show how the addition of noisy magic resources allows one to boost classical quasiprobability simulations of a quantum circuit.
arXiv Detail & Related papers (2021-03-12T20:58:41Z) - 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.