Improving quantum computation by optimized qubit routing
From MaRDI portal
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 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. (arXiv:2106.06446), we formulate the allocation subproblem as a binary 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. We present numerical results for the 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 gates and output circuit depth when compared to 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.
Recommendations
- On the qubit routing problem
- scientific article; zbMATH DE number 7496272
- A doubly stochastic matrices-based approach to optimal qubit routing
- Optimized quantum circuit partitioning
- Quantum circuit optimization by Hadamard gate reduction
- Quantum optimization
- Efficient scheme for optimizing quantum Fourier circuits
- Improving gate-level simulation of quantum circuits
- Optimal Quantum Circuits for Nearest-Neighbor Architectures
Cites work
- Approximation and hardness of token swapping
- Complexity Theory
- scientific article; zbMATH DE number 5899272 (Why is no real title available?)
- scientific article; zbMATH DE number 1222894 (Why is no real title available?)
- scientific article; zbMATH DE number 7559364 (Why is no real title available?)
- On the qubit routing problem
- Optimality Study of Existing Quantum Computing Layout Synthesis Tools
- Quantum computation and quantum information. 10th anniversary edition
- Sorting on graphs by adjacent swaps using permutation groups
- Swapping labeled tokens on graphs
Cited in
(12)- Optimized quantum circuit partitioning
- Trajectory optimization using quantum computing
- An exact qubit allocation approach for NISQ architectures
- Qubits' mapping and routing for NISQ on variability of quantum gates
- scientific article; zbMATH DE number 7496272 (Why is no real title available?)
- Analyzing heuristic-based randomized search strategies for the quantum circuit compilation problem
- Efficient routing quantum information in one-dimensional tight-binding array
- A doubly stochastic matrices-based approach to optimal qubit routing
- Universal graph theory operations for graph state preparation
- Parallel token swapping for qubit routing
- Fidelity decay and error accumulation in random quantum circuits
- Improved hardness-of-approximation for token-swapping
This page was built for publication: Improving quantum computation by optimized qubit routing
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6167090)
