Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

arXiv:2106.06446 · ACM Transactions on Quantum Computing

Optimal Qubit Assignment and Routing via Integer Programming

Giacomo Nannicini, Lev S. Bishop, Oktay Günlük, Petar Jurcevic

Published Jun 22, 2022• 54 citations
arXivHTMLPDF

Abstract

We consider the problem of mapping a logical quantum circuit onto a given hardware with limited 2-qubit connectivity. We model this problem as an integer linear program, using a network flow formulation with binary variables that includes the initial allocation of qubits and their routing. We consider several cost functions: an approximation of the fidelity of the circuit, its total depth, and a measure of cross-talk, all of which can be incorporated in the model. Numerical experiments on synthetic data and different hardware topologies indicate that the error rate and depth can be optimized simultaneously without significant loss. We test our algorithm on a large number of quantum volume circuits, optimizing for error rate and depth; our algorithm significantly reduces the number of CNOTs compared to Qiskit’s default transpiler SABRE [ 19 ] and produces circuits that, when executed on hardware, exhibit higher fidelity.

DOI
10.1145/3544563

Related papers

Constraint programming models for depth-optimal qubit assignment and SWAP-based routing

Kyle E. C. Booth

Due to the limited connectivity of gate model quantum devices, logical quantum circuits must be compiled to target hardware before they can be executed. Often, this process involves the insertion of SWAP gates into the logical circuit, usually increasing the depth of the circuit, achieved by solving a so-called qubit assignment and routing problem. Recently, a number of integer linear programming (ILP) models have been proposed for solving the qubit assignment and routing problem to proven optimality. These models encode the objective function and constraints of the problem, and leverage the use of automated solver technology to find hardware-compliant quantum circuits. In this work, we propose constraint programming (CP) models for this problem and compare their performance against ILP for circuit depth minimization for both linear and two-dimensional grid lattice device topologies on a set of randomly generated instances. Our empirical analysis indicates that the proposed CP approaches outperform the ILP models both in terms of solution quality and runtime.

arXiv:2306.08629•Jun 14, 2023•2 citations

Improving Quantum Computation by Optimized Qubit Routing

Friedrich Wagner, Andreas Bärmann, Frauke Liers +1 more

Abstract In this work we propose a high-quality decomposition approach for qubit routing by swap insertion. This optimization problem arises in the context of compiling quantum algorithms formulated in the circuit model of computation onto specific quantum hardware. Our approach decomposes the routing problem into an allocation subproblem and a set of token swapping problems. This allows us to tackle the allocation part and the token swapping part separately. Extracting the allocation part from the qubit routing model of Nannicini et al. (Optimal qubit assignment and routing via integer programming, 2021, http://arxiv.org/abs/2106.06446 ), we formulate the allocation subproblem as a binary linear program. Herein, we employ a cost function that is a lower bound on the overall routing problem objective. We strengthen the linear relaxation by novel valid inequalities. For the token swapping part we develop an exact branch-and-bound algorithm. In this context, we improve upon known lower bounds on the token swapping problem. Furthermore, we enhance an existing approximation algorithm which runs much faster than the exact approach and typically is able to determine solutions close to the optimum. We present numerical results for the fully integrated allocation and token swapping problem. Obtained solutions may not be globally optimal due to the decomposition and the usage of an approximation algorithm. However, the solutions are obtained fast and are typically close to optimal. In addition, there is a significant reduction in the number of artificial gates and output circuit depth when compared to various state-of-the-art heuristics. Reducing these figures is crucial for minimizing noise when running quantum algorithms on near-term hardware. As a consequence, using the novel decomposition approach leads to compiled algorithms with improved quality. Indeed, when compiled with the novel routing procedure and executed on real hardware, our experimental results for quantum approximate optimization algorithms show an significant increase in solution quality in comparison to standard routing methods.

arXiv:2206.01294•Journal of Optimization Theory and Applications•May 4, 2023•24 citations

Quantum Circuit Mapping Using Binary Integer Nonlinear Programming

Aaron Orenstein, Vipin Chaudhary

As Quantum Computers continue to increase in size, throughput has not increased proportionally [1]. Errors in qubit measurement and gate operations continue to increase with circuit width and depth. In order to maximize machine throughput, researchers have begun exploring ways of parallelizing circuit execution [2]–[9]. Due to the noisyness of quantum computers, this requires new algorithms for efficient resource allocation, qubit mapping, and scheduling. We improve on existing greedy algorithms by formulating the mapping search as a Binary Integer Non-Linear Programming (BINLP) problem. We model practical constraints and propose new heuristics for determining the goodness of a mapping. We evaluate our mappings on several sets of benchmark circuits and investigate the usefulness of parallel execution for circuit cutting, QAOAs, and deep circuits. We observe similar fidelity compared to Qiskit's transpiler for circuit cutting and throughput benchmarks. We observe greater fidelity over Qiskit's transpiler for dense QAOA ansatzes. Finally, we find that parallel circuit cutting provides greater fidelity than full-circuit execution.

IEEE International Symposium on Parallel & Distributed Processing, Workshops and Phd Forum•May 27, 2024•0 citations

An Integer Programming Model for the Optimal Qubit Allocation

Hyeonseok Choi, In-Chan Choi

A qubit allocation problem is to find an assignment of logical qubits in a quantum algorithm to the physical qubits of a quantum computing device. The physical qubits are often configured in a coupling map, which is a directed graph that represents communication relationship between adjacent physical qubits. A proper qubit allocation satisfies all logical qubit communication relationship in a quantum circuit by conforming to the coupling map restriction. To find the proper qubit allocation, we often need to change the quantum circuit by using a set of circuit transformations, which include reversal, bridge, and swap. Such a transformation results in the quantum circuit with newly added quantum gates and subsequenlty causes extra quantum errors. In this study, we propose an integer programming model that minimizes the sum of the quantum costs of the circuit transformation. In our model, all three circuit transformations are considered. Moreover, we present the results of the computational experiment in which our model is compared with heuristic procedures from previous studies.

Journal of Korean Institute of Industrial Engineers•Apr 15, 2021•1 citation

Improving and benchmarking NISQ qubit routers

Vicente Pina-Canelles, Adrian Auer, Inés de Vega

Quantum computers with a limited qubit connectivity require inserting SWAP gates for qubit routing, which increases gate execution errors and the impact of environmental noise due to an overhead in circuit depth. In this work, we benchmark various routing techniques considering random quantum circuits on one-dimensional and square lattice connectivities, employing both analytical and numerical methods. We introduce circuit fidelity as a comprehensive metric that captures the effects of SWAP and circuit depth overheads. Leveraging a novel approach based on the SABRE algorithm, we achieve up to $84\%$ higher average circuit fidelity for large devices within the NISQ range, compared to previously existing methods. Additionally, our results highlight that the optimal routing choice critically depends on the qubit count and the hardware characteristics, including gate fidelities and coherence times.

arXiv:2502.03908•Feb 6, 2025•0 citations

A QUBO Formulation for Qubit Allocation

Bryan Dury, Olivia Di Matteo

To run an algorithm on a quantum computer, one must choose an assignment from logical qubits in a circuit to physical qubits on quantum hardware. This task of initial qubit placement, or qubit allocation, is especially important on present-day quantum computers which have a limited number of qubits, connectivity constraints, and varying gate fidelities. In this work we formulate and implement the qubit placement problem as a quadratic, unconstrained binary optimization (QUBO) problem and solve it using simulated annealing to obtain a spectrum of initial placements. Compared to contemporary allocation methods available in t|ket$\rangle $ and Qiskit, the QUBO method yields allocations with improved circuit depth for $>$50% of a large set of benchmark circuits, with many also requiring fewer CX gates.

arXiv:2009.00140•Aug 31, 2020•10 citations
We consider the problem of mapping a logical quantum circuit onto a given hardware with limited 2-qubit connectivity. We model this problem as an integer linear program, using a network flow formulation with binary variables that includes the initial allocation of qubits and their routing. We consider several cost functions: an approximation of the fidelity of the circuit, its total depth, and a measure of cross-talk, all of which can be incorporated in the model. Numerical experiments on synthetic data and different hardware topologies indicate that the error rate and depth can be optimized simultaneously without significant loss. We test our algorithm on a large number of quantum volume circuits, optimizing for error rate and depth; our algorithm significantly reduces the number of CNOTs compared to Qiskit’s default transpiler SABRE [ 19 ] and produces circuits that, when executed on hardware, exhibit higher fidelity.
Due to the limited connectivity of gate model quantum devices, logical quantum circuits must be compiled to target hardware before they can be executed. Often, this process involves the insertion of SWAP gates into the logical circuit, usually increasing the depth of the circuit, achieved by solving a so-called qubit assignment and routing problem. Recently, a number of integer linear programming (ILP) models have been proposed for solving the qubit assignment and routing problem to proven optimality. These models encode the objective function and constraints of the problem, and leverage the use of automated solver technology to find hardware-compliant quantum circuits. In this work, we propose constraint programming (CP) models for this problem and compare their performance against ILP for circuit depth minimization for both linear and two-dimensional grid lattice device topologies on a set of randomly generated instances. Our empirical analysis indicates that the proposed CP approaches outperform the ILP models both in terms of solution quality and runtime.
Abstract In this work we propose a high-quality decomposition approach for qubit routing by swap insertion. This optimization problem arises in the context of compiling quantum algorithms formulated in the circuit model of computation onto specific quantum hardware. Our approach decomposes the routing problem into an allocation subproblem and a set of token swapping problems. This allows us to tackle the allocation part and the token swapping part separately. Extracting the allocation part from the qubit routing model of Nannicini et al. (Optimal qubit assignment and routing via integer programming, 2021, http://arxiv.org/abs/2106.06446 ), we formulate the allocation subproblem as a binary linear program. Herein, we employ a cost function that is a lower bound on the overall routing problem objective. We strengthen the linear relaxation by novel valid inequalities. For the token swapping part we develop an exact branch-and-bound algorithm. In this context, we improve upon known lower bounds on the token swapping problem. Furthermore, we enhance an existing approximation algorithm which runs much faster than the exact approach and typically is able to determine solutions close to the optimum. We present numerical results for the fully integrated allocation and token swapping problem. Obtained solutions may not be globally optimal due to the decomposition and the usage of an approximation algorithm. However, the solutions are obtained fast and are typically close to optimal. In addition, there is a significant reduction in the number of artificial gates and output circuit depth when compared to various state-of-the-art heuristics. Reducing these figures is crucial for minimizing noise when running quantum algorithms on near-term hardware. As a consequence, using the novel decomposition approach leads to compiled algorithms with improved quality. Indeed, when compiled with the novel routing procedure and executed on real hardware, our experimental results for quantum approximate optimization algorithms show an significant increase in solution quality in comparison to standard routing methods.
As Quantum Computers continue to increase in size, throughput has not increased proportionally [1]. Errors in qubit measurement and gate operations continue to increase with circuit width and depth. In order to maximize machine throughput, researchers have begun exploring ways of parallelizing circuit execution [2]–[9]. Due to the noisyness of quantum computers, this requires new algorithms for efficient resource allocation, qubit mapping, and scheduling. We improve on existing greedy algorithms by formulating the mapping search as a Binary Integer Non-Linear Programming (BINLP) problem. We model practical constraints and propose new heuristics for determining the goodness of a mapping. We evaluate our mappings on several sets of benchmark circuits and investigate the usefulness of parallel execution for circuit cutting, QAOAs, and deep circuits. We observe similar fidelity compared to Qiskit's transpiler for circuit cutting and throughput benchmarks. We observe greater fidelity over Qiskit's transpiler for dense QAOA ansatzes. Finally, we find that parallel circuit cutting provides greater fidelity than full-circuit execution.
A qubit allocation problem is to find an assignment of logical qubits in a quantum algorithm to the physical qubits of a quantum computing device. The physical qubits are often configured in a coupling map, which is a directed graph that represents communication relationship between adjacent physical qubits. A proper qubit allocation satisfies all logical qubit communication relationship in a quantum circuit by conforming to the coupling map restriction. To find the proper qubit allocation, we often need to change the quantum circuit by using a set of circuit transformations, which include reversal, bridge, and swap. Such a transformation results in the quantum circuit with newly added quantum gates and subsequenlty causes extra quantum errors. In this study, we propose an integer programming model that minimizes the sum of the quantum costs of the circuit transformation. In our model, all three circuit transformations are considered. Moreover, we present the results of the computational experiment in which our model is compared with heuristic procedures from previous studies.
Quantum computers with a limited qubit connectivity require inserting SWAP gates for qubit routing, which increases gate execution errors and the impact of environmental noise due to an overhead in circuit depth. In this work, we benchmark various routing techniques considering random quantum circuits on one-dimensional and square lattice connectivities, employing both analytical and numerical methods. We introduce circuit fidelity as a comprehensive metric that captures the effects of SWAP and circuit depth overheads. Leveraging a novel approach based on the SABRE algorithm, we achieve up to 84%84\%84% higher average circuit fidelity for large devices within the NISQ range, compared to previously existing methods. Additionally, our results highlight that the optimal routing choice critically depends on the qubit count and the hardware characteristics, including gate fidelities and coherence times.
To run an algorithm on a quantum computer, one must choose an assignment from logical qubits in a circuit to physical qubits on quantum hardware. This task of initial qubit placement, or qubit allocation, is especially important on present-day quantum computers which have a limited number of qubits, connectivity constraints, and varying gate fidelities. In this work we formulate and implement the qubit placement problem as a quadratic, unconstrained binary optimization (QUBO) problem and solve it using simulated annealing to obtain a spectrum of initial placements. Compared to contemporary allocation methods available in t|ket$\rangle $ and Qiskit, the QUBO method yields allocations with improved circuit depth for $>$50% of a large set of benchmark circuits, with many also requiring fewer CX gates.