Algorithmic Theory of Qubit Routing

• URL: http://arxiv.org/abs/2305.02059v2
• Date: Sun, 14 May 2023 12:03:40 GMT
• Title: Algorithmic Theory of Qubit Routing
• Authors: Takehiro Ito, Naonori Kakimura, Naoyuki Kamiyama, Yusuke Kobayashi, Yoshio Okamoto
• Abstract summary: We study the qubit routing problem from the viewpoint of theoretical computer science. We prove that the qubit routing problem is NP-hard. We give a minimization-time algorithm when each qubit is involved in at most one two-qubit gate.
• Score: 4.316090167342715
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: The qubit routing problem, also known as the swap minimization problem, is a (classical) combinatorial optimization problem that arises in the design of compilers of quantum programs. We study the qubit routing problem from the viewpoint of theoretical computer science, while most of the existing studies investigated the practical aspects. We concentrate on the linear nearest neighbor (LNN) architectures of quantum computers, in which the graph topology is a path. Our results are three-fold. (1) We prove that the qubit routing problem is NP-hard. (2) We give a fixed-parameter algorithm when the number of two-qubit gates is a parameter. (3) We give a polynomial-time algorithm when each qubit is involved in at most one two-qubit gate.

Related papers

• Solving The Travelling Salesman Problem Using A Single Qubit [0.0]
  The travelling salesman problem (TSP) is a popular NP-hard-combinatorial optimization problem. We present an algorithm that solves an arbitrary TSP using a single qubit by invoking the principle of quantum parallelism. The underlying framework of our algorithm is a quantum version of the classical Brachistochrone approach.
  arXiv  Detail & Related papers  (2024-07-24T12:06:37Z)
• Full Characterization of the Depth Overhead for Quantum Circuit Compilation with Arbitrary Qubit Connectivity Constraint [6.799314463590596]
  In some physical implementations of quantum computers, 2-qubit operations can be applied only on certain pairs of qubits. In this paper, we fully characterize the depth overhead by the routing number of the underlying constraint graph.
  arXiv  Detail & Related papers  (2024-02-04T08:29:41Z)
• 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)
• Quantum Worst-Case to Average-Case Reductions for All Linear Problems [66.65497337069792]
  We study the problem of designing worst-case to average-case reductions for quantum algorithms. We provide an explicit and efficient transformation of quantum algorithms that are only correct on a small fraction of their inputs into ones that are correct on all inputs.
  arXiv  Detail & Related papers  (2022-12-06T22:01:49Z)
• Complexity-Theoretic Limitations on Quantum Algorithms for Topological Data Analysis [59.545114016224254]
  Quantum algorithms for topological data analysis seem to provide an exponential advantage over the best classical approach. We show that the central task of TDA -- estimating Betti numbers -- is intractable even for quantum computers. We argue that an exponential quantum advantage can be recovered if the input data is given as a specification of simplices.
  arXiv  Detail & Related papers  (2022-09-28T17:53:25Z)
• 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)
• Optimizing Tensor Network Contraction Using Reinforcement Learning [86.05566365115729]
  We propose a Reinforcement Learning (RL) approach combined with Graph Neural Networks (GNN) to address the contraction ordering problem. The problem is extremely challenging due to the huge search space, the heavy-tailed reward distribution, and the challenging credit assignment. We show how a carefully implemented RL-agent that uses a GNN as the basic policy construct can address these challenges.
  arXiv  Detail & Related papers  (2022-04-18T21:45:13Z)
• Locality-aware Qubit Routing for the Grid Architecture [1.4459640831465588]
  We introduce a locality-aware qubit routing algorithm based on a graph theoretic framework. Our algorithm is designed for the grid and certain "grid-like" architectures.
  arXiv  Detail & Related papers  (2022-03-21T20:46:39Z)
• Benchmarking Small-Scale Quantum Devices on Computing Graph Edit Distance [52.77024349608834]
  Graph Edit Distance (GED) measures the degree of (dis)similarity between two graphs in terms of the operations needed to make them identical. In this paper we present a comparative study of two quantum approaches to computing GED.
  arXiv  Detail & Related papers  (2021-11-19T12:35:26Z)
• 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)
• 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.