Topological-Graph Dependencies and Scaling Properties of a Heuristic Qubit-Assignment Algorithm
Open Access
- 16 March 2022
- journal article
- research article
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Transactions on Quantum Engineering
- Vol. 3, 1-14
Abstract
The qubit-mapping problem aims to assign and route qubits of a quantum circuit onto a NISQ device in an optimized fashion, with respect to some cost function. Finding an optimal solution to this problem is known to scale exponentially in computational complexity; as such, it is imperative to investigate scalable qubit-mapping solutions for NISQ computation. In this work, a noise-aware heuristic qubit-assignment algorithm (which assigns initial placements for qubits in a quantum algorithm to qubits on a NISQ device, but does not route qubits during the quantum algorithm's execution) is presented and compared against the optimal brute-force solution, as well as a trivial qubit assignment, with the aim to quantify the performance of our heuristic qubit-assignment algorithm. We find that for small, connected-graph algorithms, our heuristic-assignment algorithm faithfully lies in between the effective upper and lower bounds given by the brute-force and trivial qubit-assignment algorithms. Additionally, we find that the topological-graph properties of quantum algorithms with over six qubits play an important role in our heuristic qubit-assignment algorithm's performance on NISQ devices. Finally, we investigate the scaling properties of our heuristic algorithm for quantum processors with up to 100 qubits; here, the algorithm was found to be scalable for quantum-algorithms which admit path-like graphs. Our findings show that as the size of the quantum processor in our simulation grows, so do the benefits from utilizing the heuristic qubit-assignment algorithm, under particular constraints for our heuristic algorithm. This work thus characterizes the performance of a heuristic qubit-assignment algorithm with respect to the topological-graph and scaling properties of a quantum algorithm which one may wish to run on a given NISQ device.Keywords
All Related Versions
This publication has 68 references indexed in Scilit:
- Synthesis and optimization of reversible circuits—a surveyACM Computing Surveys, 2013
- Quantum Algorithms for Quantum Field TheoriesScience, 2012
- Atomic physics and quantum optics using superconducting circuitsNature, 2011
- Quantum computing with realistically noisy devicesNature, 2005
- Strong coupling of a single photon to a superconducting qubit using circuit quantum electrodynamicsNature, 2004
- Quantum dynamics of single trapped ionsReviews of Modern Physics, 2003
- Quantum cryptographyReviews of Modern Physics, 2002
- Quantum Computations with Cold Trapped IonsPhysical Review Letters, 1995
- Laplacian matrices of graphs: a surveyLinear Algebra and its Applications, 1994
- A note on two problems in connexion with graphsNumerische Mathematik, 1959