Optimized Qubit Routing for Commuting Gates via Integer Programming

• URL: http://arxiv.org/abs/2507.12199v1
• Date: Wed, 16 Jul 2025 12:55:09 GMT
• Title: Optimized Qubit Routing for Commuting Gates via Integer Programming
• Authors: Moritz Stargalla, Friedrich Wagner,
• Abstract summary: 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.
• Score: 0.0
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Quantum computers promise to outperform their classical counterparts at certain tasks. However, existing quantum devices are error-prone and restricted in size. Thus, effective compilation methods are crucial to exploit limited quantum resources. In this work, we address the problem of qubit routing for commuting gates, which arises, for example, during the compilation of the well-known Quantum Approximate Optimization Algorithm. We propose a two-step decomposition approach based on integer programming, which is guaranteed to return an optimal solution. To justify the use of integer programming, we prove NP-hardness of the underlying optimization problem. Furthermore, we derive asymptotic upper and lower bounds on the quality of a solution. We develop several integer programming models and derive linear descriptions of related polytopes, which generalize to applications beyond this work. Finally, we conduct a computational study showing that our approach outperforms existing heuristics in terms of quality and exact methods in terms of runtime.

Related papers

• Solving quadratic binary optimization problems using quantum SDP methods: Non-asymptotic running time analysis [1.9081120388919084]
  Quantum computers can solve semidefinite programs (SDPs) using resources that scale better than state-of-the-art classical methods.<n>We present an analysis of the non-asymptotic resource requirements of a quantum SDP solver.
  arXiv  Detail & Related papers  (2025-02-21T12:54:05Z)
• Sum-of-Squares inspired Quantum Metaheuristic for Polynomial Optimization with the Hadamard Test and Approximate Amplitude Constraints [76.53316706600717]
  Recently proposed quantum algorithm arXiv:2206.14999 is based on semidefinite programming (SDP) We generalize the SDP-inspired quantum algorithm to sum-of-squares. Our results show that our algorithm is suitable for large problems and approximate the best known classicals.
  arXiv  Detail & Related papers  (2024-08-14T19:04:13Z)
• Dependency-Aware Compilation for Surface Code Quantum Architectures [7.543907169342984]
  We study the problem of compiling quantum circuits for quantum computers implementing surface codes.<n>We solve this problem efficiently and near-optimally with a novel algorithm.<n>Our evaluation shows that our approach is powerful and flexible for compiling realistic workloads.
  arXiv  Detail & Related papers  (2023-11-29T19:36:19Z)
• Accelerating Cutting-Plane Algorithms via Reinforcement Learning Surrogates [49.84541884653309]
  A current standard approach to solving convex discrete optimization problems is the use of cutting-plane algorithms. Despite the existence of a number of general-purpose cut-generating algorithms, large-scale discrete optimization problems continue to suffer from intractability. We propose a method for accelerating cutting-plane algorithms via reinforcement learning.
  arXiv  Detail & Related papers  (2023-07-17T20:11:56Z)
• Enhancing Quantum Algorithms for Quadratic Unconstrained Binary Optimization via Integer Programming [0.0]
  In this work, we integrate the potentials of quantum and classical techniques for optimization. We reduce the problem size according to a linear relaxation such that the reduced problem can be handled by quantum machines of limited size. We present numerous computational results from real quantum hardware.
  arXiv  Detail & Related papers  (2023-02-10T20:12:53Z)
• Approximate encoding of quantum states using shallow circuits [0.0]
  A common requirement of quantum simulations and algorithms is the preparation of complex states through sequences of 2-qubit gates. Here, we aim at creating an approximate encoding of the target state using a limited number of gates. Our work offers a universal method to prepare target states using local gates and represents a significant improvement over known strategies.
  arXiv  Detail & Related papers  (2022-06-30T18:00: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)
• Improving Quantum Computation by Optimized Qubit Routing [0.0]
  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. We present numerical results for the integrated allocation and token swapping problem.
  arXiv  Detail & Related papers  (2022-06-02T20:32:18Z)
• 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)

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.