Algorithm-Aware Qubit Mapping

Yanjun Ji, Ilia Polian

Published Dec 30, 2022• 1 citation

Abstract

Algorithm-Aware (AlgAw) qubit mapping aims at directly providing the solutions to qubit mapping of algorithms with regular structures based on the algorithm’s features. Although the exact method provides a high-quality solution, its compilation time grows exponentially with the circuit size. To improve its scalability, we propose the AlgAw qubit mapping. The main idea is to first determine the subcircuits in an algorithm to be mapped, then analyze the optimal solutions of small-scale subcircuits found by exact methods to obtain solutions of large-scale subcircuits, and finally reconstruct the entire circuit and assign parameters. Applying AlgAw to the Quantum Approximate Optimization Algorithm (QAOA) on linear and T-shaped subtopologies produces optimal and scalable solutions for arbitrary numbers of qubits and depths, which is critical to the algorithm’s performance on Noisy Intermediate-Scale Quantum (NISQ) computers. Compared to Qiskit, Tket, and SWAP-Network, AlgAw produces the least number of CNOT gates and the lowest circuit depth. Furthermore, AlgAw takes only a few seconds to obtain a circuit with a hundred qubits that satisfies the connectivity constraints. The benchmarking results on Quantum Processing Units (QPUs) show that AlgAw qubit mapping yields higher values of approximation ratio than others. AlgAw can also be applied to other algorithms such as the Variational Quantum Eigensolver (VQE).

DOI: 10.36227/techrxiv.21786146.v1

Related papers

Algorithm-Aware Qubit Mapping

Yanjun Ji, Ilia Polian

Algorithm-aware (AlgAw) qubit mapping aims at directly providing the solutions to qubit mapping of algorithms with regular structures based on the algorithm's features. Although exact methods can provide high quality solutions, their compilation time grows exponentially with circuit size. To improve scalability, we propose the AlgAw qubit mapping approach. The main idea is to first identify subcircuits in an algorithm to be mapped, then analyze optimal solutions for small scale subcircuits found by exact methods, extend these solutions to large scale subcircuits, reconstruct the entire circuit and assign parameters, and finally map pretranspiled circuits onto the target quantum devices. Applying AlgAw to the quantum approximate optimization algorithm (QAOA) on linear and T-shaped subtopologies produces optimal and scalable solutions for arbitrary numbers of qubits and depths, which is critical to the algorithm's performance on near-term quantum devices. Compared to other methods including Qiskit, Tket, and SWAP-network, AlgAw produces the least number of CNOT gates and the lowest circuit depth for the pretranspiled circuits. Furthermore, AlgAw takes only a few seconds to construct a resulting circuit having a hundred qubits. The benchmarking results on IBM quantum devices show that AlgAw qubit mapping yields better performance than others. AlgAw is applicable to other variational quantum algorithms (VQAs) and can also be applied to other algorithms.

Dec 30, 20222 citations

Algorithm-Aware Qubit Mapping

Yanjun Ji, Ilia Polian

Algorithm-aware (AlgAw) qubit mapping aims at directly providing the solutions to qubit mapping of algorithms with regular structures based on the algorithm’s features. Although exact methods can provide high quality solutions, their compilation time grows exponentially with circuit size. To improve scalability, we propose the AlgAw qubit mapping approach. The main idea is to first identify subcircuits in an algorithm to be mapped, then analyze optimal solutions for small scale subcircuits found by exact methods, extend these solutions to large scale subcircuits, reconstruct the entire circuit and assign parameters, and finally map pretranspiled circuits onto the target quantum devices. Applying AlgAw to the quantum approximate optimization algorithm (QAOA) on linear and T-shaped subtopologies produces optimal and scalable solutions for arbitrary numbers of qubits and depths, which is critical to the algorithm’s performance on near-term quantum devices. Compared to other methods including Qiskit, Tket, and SWAP-network, AlgAw produces the least number of CNOT gates and the lowest circuit depth for the pretranspiled circuits. Furthermore, AlgAw takes only a few seconds to construct a resulting circuit having a hundred qubits. The benchmarking results on IBM quantum devices show that AlgAw qubit mapping yields better performance than others. AlgAw is applicable to other variational quantum algorithms (VQAs) and can also be applied to other algorithms.

Sep 11, 20230 citations

Tackling the Qubit Mapping Problem with Permutation-Aware Synthesis

Ji Liu, Ed Younis, Mathias Weiden +3 more

We propose a scalable, hierarchical qubit mapping and routing algorithm that harnesses the power of circuit synthesis. First, we decompose large circuits into subcircuits small enough to be directly resynthesized. For each block, we pre-synthesize them for all permutations of its input and output qubits. Following this offline step, we employ a permutation-aware, block-based generalization of the popular SABRE mapping algorithm. This mapping step stitches together blocks by choosing an input-output permutation that minimizes intrablock gate count and required inter-block communication (SWAP and bridge gates). Our approach has a twofold advantage: 1) circuit synthesis may eliminate more two-qubit gates than other optimizing compilers; 2) considering all permutations of input and output qubits eliminates communication operations transparently. In contrast, other mapping algorithms can only introduce communication operations. We show that we can produce better-quality circuits than commercial compilers: shorter by up to 68% (18% on average) fewer gates than Qiskit, up to 36% (9% on average) fewer gates than Tket. We outperform BQSkit, a permutation-unaware, synthesis-based compiler, by up to 67% (21% on average) fewer gates. We also exceed experimental optimal mappers such as OLSQ in quality (10.7% shorter circuits) and time to solution. Our scalable, heuristic approach can be seamlessly integrated into any quantum circuit compiler or optimization infrastructure, and it applies well to any qubit technology, such as superconducting and trapped ions.

arXiv:2305.02939IEEE International Conference on Quantum Computing and Engineering (QCE)Sep 17, 202327 citations

Algorithm-oriented qubit mapping for variational quantum algorithms

Yanjun Ji, Xi Chen, Ilia Polian +1 more

Variational algorithms are among the first practical applications of quantum computing, but their performance is limited by today's noisy intermediate-scale quantum (NISQ) devices. The authors propose scalable, depth-optimal solutions to overcome these limitations by integrating optimal mapping algorithms applied to small submodules of a given NISQ computer (focusing on popular linear and T- and H-shaped subtopologies). Identification of the best qubits combined with postselection keeps the error rate in check. The team reports up to 82% reduction in circuit depth and an average of 138% better success probability, thus paving the way for reliable quantum computing ecosystems of tomorrow.

arXiv:2310.09826Physical Review AppliedMar 11, 202512 citations

A Hardware-Aware Heuristic for the Qubit Mapping Problem in the NISQ Era

Siyuan Niu, Adrien Suau, Gabriel Staffelbach +1 more

Due to several physical limitations in the realization of quantum hardware, today's quantum computers are qualified as noisy intermediate-scale quantum (NISQ) hardware. NISQ hardware is characterized by a small number of qubits (50 to a few hundred) and noisy operations. Moreover, current realizations of superconducting quantum chips do not have the ideal all-to-all connectivity between qubits but rather at most a nearest-neighbor connectivity. All these hardware restrictions add supplementary low-level requirements. They need to be addressed before submitting the quantum circuit to an actual chip. Satisfying these requirements is a tedious task for the programmer. Instead, the task of adapting the quantum circuit to a given hardware is left to the compiler. In this article, we propose a hardware-aware (HA) mapping transition algorithm that takes the calibration data into account with the aim to improve the overall fidelity of the circuit. Evaluation results on IBM quantum hardware show that our HA approach can outperform the state of the art, both in terms of the number of additional gates and circuit fidelity.

arXiv:2010.03397IEEE Transactions on Quantum EngineeringJan 1, 2020103 citations

Connectivity-Aware Qubit Mapping and CNOT Cost Minimization for Quantum Hashing Circuits

I. Zinnatullin, Kamil Ravilevich Khadiev, I. A. Nikitin

Abstract Current quantum computers are noisy intermediate-scale quantum (NISQ) devices. Execution of quantum algorithms, represented as quantum circuits in the quantum circuit model, on such hardware requires transformation of the original circuits to comply with the hardware’s physical constraints, a process known as transpilation. One of the main constraints is limited qubit connectivity. In this work, we present an algorithm that transforms a quantum hashing circuit to satisfy architectural connectivity constraints while minimizing the number of CNOT gates (CNOT cost). The considered algorithm constructs a mapping from logical qubits to physical qubits that minimizes the CNOT cost of the resulting circuit. We optimize circuits for IBM Quantum devices.

Russian MicroelectronicsDec 1, 20252 citations