Improved Qubit Routing for QAOA Circuits

• URL: http://arxiv.org/abs/2312.15982v1
• Date: Tue, 26 Dec 2023 10:26:10 GMT
• Title: Improved Qubit Routing for QAOA Circuits
• Authors: Ayse Kotil, Fedor Simkovic, Martin Leib
• Abstract summary: We develop a qubit routing algorithm with classical run time for the Quantum Approximate Optimization Algorithm (QAOA) We show that it improves upon existing state-of-the-art routing algorithms for QAOA circuits defined on $k$-regular as well as Erd"os-Renyi problem graphs of sizes up to $N leq 400$.
• Score: 0.0
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: We develop a qubit routing algorithm with polynomial classical run time for the Quantum Approximate Optimization Algorithm (QAOA). The algorithm follows a two step process. First, it obtains a near-optimal solution, based on Vizing's theorem for the edge coloring problem, consisting of subsets of the interaction gates that can be executed in parallel on a fully parallelized all-to-all connected QPU. Second, it proceeds with greedy application of SWAP gates based on their net effect on the distance of remaining interaction gates on a specific hardware connectivity graph. Our algorithm strikes a balance between optimizing for both the circuit depth and total SWAP gate count. We show that it improves upon existing state-of-the-art routing algorithms for QAOA circuits defined on $k$-regular as well as Erd\"os-Renyi problem graphs of sizes up to $N \leq 400$.

Related papers

• SWAP-less Implementation of Quantum Algorithms [0.0]
  We present a formalism based on tracking the flow of parity quantum information to implement algorithms on devices with limited connectivity. We leverage the fact that entangling gates not only manipulate quantum states but can also be exploited to transport quantum information.
  arXiv  Detail & Related papers  (2024-08-20T14:51:00Z)
• Algorithm-Oriented Qubit Mapping for Variational Quantum Algorithms [3.990724104767043]
  Quantum algorithms implemented on near-term devices require qubit mapping due to noise and limited qubit connectivity. We propose a strategy called algorithm-oriented qubit mapping (AOQMAP) that aims to bridge the gap between exact and scalable mapping methods.
  arXiv  Detail & Related papers  (2023-10-15T13:18:06Z)
• Robust Qubit Mapping Algorithm via Double-Source Optimal Routing on Large Quantum Circuits [11.391158217994782]
  Duostra is tailored to address the challenge of implementing large-scale quantum circuits on real hardware devices. It operates by efficiently determining optimal paths for double-qubit gates and inserting SWAP gates. It yields results of good quality within a reasonable runtime.
  arXiv  Detail & Related papers  (2022-10-04T01:47:11Z)
• Matching Pursuit Based Scheduling for Over-the-Air Federated Learning [67.59503935237676]
  This paper develops a class of low-complexity device scheduling algorithms for over-the-air learning via the method of federated learning. Compared to the state-of-the-art proposed scheme, the proposed scheme poses a drastically lower efficiency system. The efficiency of the proposed scheme is confirmed via experiments on the CIFAR dataset.
  arXiv  Detail & Related papers  (2022-06-14T08:14:14Z)
• 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)
• Not All SWAPs Have the Same Cost: A Case for Optimization-Aware Qubit Routing [15.018468499770242]
  Near-term NISQ quantum computers and relatively long-term scalable quantum architectures do not offer full connectivity. A quantum compiler needs to perform qubit routing to make the circuit compatible with device layout. In this paper, we observe that the aforementioned qubit routing is not optimal, and qubit routing should textitnot be independent on subsequent gate optimizations.
  arXiv  Detail & Related papers  (2022-05-21T13:36:44Z)
• 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)
• Fidelity-Guarantee Entanglement Routing in Quantum Networks [64.49733801962198]
  Entanglement routing establishes remote entanglement connection between two arbitrary nodes. We propose purification-enabled entanglement routing designs to provide fidelity guarantee for multiple Source-Destination (SD) pairs in quantum networks.
  arXiv  Detail & Related papers  (2021-11-15T14:07:22Z)
• Solving correlation clustering with QAOA and a Rydberg qudit system: a full-stack approach [94.37521840642141]
  We study the correlation clustering problem using the quantum approximate optimization algorithm (QAOA) and qudits. Specifically, we consider a neutral atom quantum computer and propose a full stack approach for correlation clustering. We show the qudit implementation is superior to the qubit encoding as quantified by the gate count.
  arXiv  Detail & Related papers  (2021-06-22T11:07:38Z)
• Lower Bounds and Optimal Algorithms for Smooth and Strongly Convex Decentralized Optimization Over Time-Varying Networks [79.16773494166644]
  We consider the task of minimizing the sum of smooth and strongly convex functions stored in a decentralized manner across the nodes of a communication network. We design two optimal algorithms that attain these lower bounds. We corroborate the theoretical efficiency of these algorithms by performing an experimental comparison with existing state-of-the-art methods.
  arXiv  Detail & Related papers  (2021-06-08T15:54:44Z)
• Improving the Performance of Deep Quantum Optimization Algorithms with Continuous Gate Sets [47.00474212574662]
  Variational quantum algorithms are believed to be promising for solving computationally hard problems. In this paper, we experimentally investigate the circuit-depth-dependent performance of QAOA applied to exact-cover problem instances. Our results demonstrate that the use of continuous gate sets may be a key component in extending the impact of near-term quantum computers.
  arXiv  Detail & Related papers  (2020-05-11T17:20:51Z)

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.