Parallel Token Swapping for Qubit Routing

• URL: http://arxiv.org/abs/2411.18581v1
• Date: Wed, 27 Nov 2024 18:26:16 GMT
• Title: Parallel Token Swapping for Qubit Routing
• Authors: Ishan Bansal, Oktay Günlük, Richard Shapley,
• Abstract summary: We provide the first known constant factor approximation algorithms for the parallel token swapping problem on graph topologies that are commonly found in modern quantum computers. We also study the so-called stretch factor of a natural lower bound to the problem, which has been shown to be useful when designing reconfigurations for the qubit routing problem.
• Score: 2.280359339174839
• License:
• Abstract: In this paper we study a combinatorial reconfiguration problem that involves finding an optimal sequence of swaps to move an initial configuration of tokens that are placed on the vertices of a graph to a final desired one. This problem arises as a crucial step in reducing the depth of a quantum circuit when compiling a quantum algorithm. We provide the first known constant factor approximation algorithms for the parallel token swapping problem on graph topologies that are commonly found in modern quantum computers, including cycle graphs, subdivided star graphs, and grid graphs. We also study the so-called stretch factor of a natural lower bound to the problem, which has been shown to be useful when designing heuristics for the qubit routing problem. Finally, we study the colored version of this reconfiguration problem where some tokens share the same color and are considered indistinguishable.

Related papers

• The graph alignment problem: fundamental limits and efficient algorithms [0.9246334723892301]
  The noisy version of the graph isomorphism problem aims to find a matching between the nodes of two graphs which preserves most of the edges. This thesis focuses on understanding the fundamental information-theoretical limits for this problem, as well as designing and analyzing algorithms that are able to recover the underlying alignment in the data.
  arXiv  Detail & Related papers  (2024-04-18T15:31:13Z)
• 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)
• Discrete Graph Auto-Encoder [52.50288418639075]
  We introduce a new framework named Discrete Graph Auto-Encoder (DGAE) We first use a permutation-equivariant auto-encoder to convert graphs into sets of discrete latent node representations. In the second step, we sort the sets of discrete latent representations and learn their distribution with a specifically designed auto-regressive model.
  arXiv  Detail & Related papers  (2023-06-13T12:40:39Z)
• Algorithmic Theory of Qubit Routing [4.316090167342715]
  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.
  arXiv  Detail & Related papers  (2023-05-03T12:02:40Z)
• 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)
• Parallelization techniques for quantum simulation of fermionic systems [0.0]
  Mapping fermionic operators to qubit operators is an essential step for simulating fermionic systems on a quantum computer. We investigate how the choice of such a mapping interacts with the underlying qubit connectivity of the quantum processor.
  arXiv  Detail & Related papers  (2022-07-25T18:41:59Z)
• Graph Neural Network Bandits [89.31889875864599]
  We consider the bandit optimization problem with the reward function defined over graph-structured data. Key challenges in this setting are scaling to large domains, and to graphs with many nodes. We show that graph neural networks (GNNs) can be used to estimate the reward function.
  arXiv  Detail & Related papers  (2022-07-13T18:12:36Z)
• Quantitative approach to Grover's quantum walk on graphs [62.997667081978825]
  We study Grover's search algorithm focusing on continuous-time quantum walk on graphs. Instead of finding specific graph topologies convenient for the related quantum walk, we fix the graph topology and vary the underlying graph endowed Laplacians.
  arXiv  Detail & Related papers  (2022-07-04T19:33:06Z)
• 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)
• From Quantum Graph Computing to Quantum Graph Learning: A Survey [86.8206129053725]
  We first elaborate the correlations between quantum mechanics and graph theory to show that quantum computers are able to generate useful solutions. For its practicability and wide-applicability, we give a brief review of typical graph learning techniques. We give a snapshot of quantum graph learning where expectations serve as a catalyst for subsequent research.
  arXiv  Detail & Related papers  (2022-02-19T02:56:47Z)
• Quantum Optimization for the Graph Coloring Problem with Space-Efficient Embedding [0.0]
  We introduce a novel space-efficient quantum optimization algorithm for the graph coloring problem. Our circuits are deeper than the ones of the standard approach. To explore currently available alternatives, we perform a study of random graph coloring on a quantum annealer.
  arXiv  Detail & Related papers  (2020-09-15T18:34:17Z)

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.