Tackling the Qubit Mapping Problem with Permutation-Aware Synthesis

• URL: http://arxiv.org/abs/2305.02939v1
• Date: Thu, 4 May 2023 15:39:54 GMT
• Title: Tackling the Qubit Mapping Problem with Permutation-Aware Synthesis
• Authors: Ji Liu, Ed Younis, Mathias Weiden, Paul Hovland, John Kubiatowicz, Costin Iancu
• Abstract summary: We propose a novel hierarchical qubit mapping and routing algorithm. In the second stage permutation-aware synthesis (PAS), each block is optimized and synthesized in isolation. In the third stage a permutation-aware mapping (PAM) algorithm maps the blocks to the target device based on the information from the second stage.
• Score: 9.885057869188087
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We propose a novel hierarchical qubit mapping and routing algorithm. First, a circuit is decomposed into blocks that span an identical number of qubits. In the second stage permutation-aware synthesis (PAS), each block is optimized and synthesized in isolation. In the third stage a permutation-aware mapping (PAM) algorithm maps the blocks to the target device based on the information from the second stage. Our approach is based on the following insights: (1) partitioning the circuit into blocks is beneficial for qubit mapping and routing; (2) with PAS, any block can implement an arbitrary input-output qubit mapping that reduces the gate count; and (3) with PAM, for two adjacent blocks we can select input-output permutations that optimize each block together with the amount of communication required at the block boundary. Whereas existing mapping algorithms preserve the original circuit structure and only introduce "minimal" communication via inserting SWAP or bridge gates, the PAS+PAM approach can additionally change the circuit structure and take full advantage of hardware-connectivity. Our experiments show that we can produce better-quality circuits than existing mapping algorithms or commercial compilers (Qiskit, TKET, BQSKit) with maximum optimization settings. For a combination of benchmarks we produce circuits shorter by up to 68% (18% on average) fewer gates than Qiskit, up to 36% (9% on average) fewer gates than TKET, and up to 67% (21% on average) fewer gates than BQSKit. Furthermore, the approach scales, and it can be seamlessly integrated into any quantum circuit compiler or optimization infrastructure.

Related papers

• Linear Circuit Synthesis using Weighted Steiner Trees [45.11082946405984]
  CNOT circuits are a common building block of general quantum circuits. This article presents state-of-the-art algorithms for optimizing the number of CNOT gates. A simulated evaluation shows that the suggested is almost always beneficial and reduces the number of CNOT gates by up to 10%.
  arXiv  Detail & Related papers  (2024-08-07T19:51:22Z)
• A two-circuit approach to reducing quantum resources for the quantum lattice Boltzmann method [41.66129197681683]
  Current quantum algorithms for solving CFD problems use a single quantum circuit and, in some cases, lattice-based methods. We introduce the a novel multiple circuits algorithm that makes use of a quantum lattice Boltzmann method (QLBM) The problem is cast as a stream function--vorticity formulation of the 2D Navier-Stokes equations and verified and tested on a 2D lid-driven cavity flow.
  arXiv  Detail & Related papers  (2024-01-20T15:32:01Z)
• Direct pulse-level compilation of arbitrary quantum logic gates on superconducting qutrits [36.30869856057226]
  We demonstrate any arbitrary qubit and qutrit gate can be realized with high-fidelity, which can significantly reduce the length of a gate sequence. We show that optimal control gates are robust to drift for at least three hours and that the same calibration parameters can be used for all implemented gates.
  arXiv  Detail & Related papers  (2023-03-07T22:15:43Z)
• A SAT approach to the initial mapping problem in SWAP gate insertion for commuting gates [0.8057006406834467]
  Most quantum circuits require SWAP gate insertion to run on quantum hardware with limited qubit connectivity. A good initial mapping for the swap strategy reduces the number of required swap gates. We present a SAT-based approach to find good initial mappings for circuits with commuting gates transpiled to the hardware.
  arXiv  Detail & Related papers  (2022-12-12T02:53:45Z)
• Wide Quantum Circuit Optimization with Topology Aware Synthesis [0.8469686352132708]
  Unitary synthesis is an optimization technique that can achieve optimal multi-qubit gate counts while mapping quantum circuits to restrictive qubit topologies. We present TopAS, a topology aware synthesis tool built with the emphBQSKit framework that preconditions quantum circuits before mapping.
  arXiv  Detail & Related papers  (2022-06-27T21:59:30Z)
• Efficient variational synthesis of quantum circuits with coherent multi-start optimization [1.3108652488669734]
  We consider the problem of synthesis into a gate set consisting of the CNOT gate and arbitrary single-qubit (1q) gates. A key idea we propose is to use parametrized two-qubit (2q) controlled phase gates, which can interpolate between the identity gate and the CNOT gate. This coherent optimization of the architecture together with 1q gates appears to work surprisingly well in practice.
  arXiv  Detail & Related papers  (2022-05-02T18:00:03Z)
• Software mitigation of coherent two-qubit gate errors [55.878249096379804]
  Two-qubit gates are important components of quantum computing. But unwanted interactions between qubits (so-called parasitic gates) can degrade the performance of quantum applications. We present two software methods to mitigate parasitic two-qubit gate errors.
  arXiv  Detail & Related papers  (2021-11-08T17:37:27Z)
• String Abstractions for Qubit Mapping [0.0]
  We introduce a novel qubit mapping approach, string-based qubit mapping. Key insight is to prioritize the mapping of logical qubits that appear in longest repeating non-overlappings of qubit pairs accessed. We compare our new mapping scheme against two quantum compilers and two device topologies.
  arXiv  Detail & Related papers  (2021-11-05T20:07:57Z)
• Clifford Circuit Optimization with Templates and Symbolic Pauli Gates [11.978356827088595]
  The Clifford group is a finite subgroup of the unitary group generated by the Hadamard, the CNOT, and the Phase gates. Here we consider the problem of finding a short quantum circuit implementing a given Clifford group element. Our methods aim to minimize the entangling gate count assuming all-to-all qubit connectivity.
  arXiv  Detail & Related papers  (2021-05-05T19:18:35Z)
• Time-Sliced Quantum Circuit Partitioning for Modular Architectures [67.85032071273537]
  Current quantum computer designs will not scale. To scale beyond small prototypes, quantum architectures will likely adopt a modular approach with clusters of tightly connected quantum bits and sparser connections between clusters. We exploit this clustering and the statically-known control flow of quantum programs to create tractable partitionings which map quantum circuits to modular physical machines one time slice at a time.
  arXiv  Detail & Related papers  (2020-05-25T17:58: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.