Topological-Graph Dependencies and Scaling Properties of a Heuristic Qubit-Assignment Algorithm
arXiv:2103.15695 · doi:10.1109/TQE.2022.3160015
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 \textit{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.
arXiv commentAccepted for publication in IEEE Transactions on Quantum Engineering
References in corpus (50)
- Quantum Computing in the NISQ era and beyond
- Quantum Cryptography
- Supplementary information for "Quantum supremacy using a programmable superconducting processor"
- Quantum Machine Learning
- Circuit Quantum Electrodynamics: Coherent Coupling of a Single Photon to a Cooper Pair Box
- Quantum computational advantage using photons
- Advances in Quantum Cryptography
- Logic gates at the surface code threshold: Superconducting qubits poised for fault-tolerant quantum computing
- Quantum computational chemistry
- Trapped-Ion Quantum Computing: Progress and Challenges
- Atomic physics and quantum optics using superconducting circuits
- Quantum Computing with Very Noisy Devices
- 14-qubit entanglement: creation and coherence
- Quantum Error Correction for Beginners
- Synthesis of Quantum Logic Circuits
- Photonic quantum information processing: a concise review
- A CMOS silicon spin qubit
- Demonstration of the trapped-ion quantum-CCD computer architecture
- Quantum Algorithms for Quantum Field Theories
- A blueprint for demonstrating quantum supremacy with superconducting qubits
- Quantum Simulation of Electronic Structure with Linear Depth and Connectivity
- Superconducting Quantum Computing: A Review
- A quantum information processor with trapped ions
- Synthesis and Optimization of Reversible Circuits - A Survey
- Blueprint for a Scalable Photonic Fault-Tolerant Quantum Computer
- Building a fault-tolerant quantum computer using concatenated cat codes
- Software Mitigation of Crosstalk on Noisy Intermediate-Scale Quantum Computers
- Synthesis of Quantum Circuits for Linear Nearest Neighbor Architectures
- Fault-tolerant quantum error detection
- Compiling quantum circuits to realistic hardware architectures using temporal planners
- Applications of Near-Term Photonic Quantum Computers: Software and Algorithms
- Optimality Study of Existing Quantum Computing Layout Synthesis Tools
- A Hardware-Aware Heuristic for the Qubit Mapping Problem in the NISQ Era
- Extracting Success from IBM's 20-Qubit Machines Using Error-Aware Compilation
- Timing and resource-aware mapping of quantum circuits to superconducting processors
- Generalized swap networks for near-term quantum computing
- On the qubit routing problem
- Fusion-based quantum computation
- Fault-Tolerant Operation of a Quantum Error-Correction Code
- Finding the ground state of the Hubbard model by variational methods on a quantum computer with gate errors
- Full-Stack, Real-System Quantum Computer Studies: Architectural Comparisons and Design Insights
- Towards Quantum Simulations in Particle Physics and Beyond on Noisy Intermediate-Scale Quantum Devices
- cQASM v1.0: Towards a Common Quantum Assembly Language
- Effects of gate errors in digital quantum simulations of fermionic systems
- Nearly optimal quantum algorithm for generating the ground state of a free quantum field theory
- Using Reinforcement Learning to Perform Qubit Routing in Quantum Compilers
- Qubit Allocation for Noisy Intermediate-Scale Quantum Computers
- Deterministic Algorithms for Compiling Quantum Circuits with Recurrent Patterns
- Using Spectral Graph Theory to Map Qubits onto Connectivity-Limited Devices
- The Quantum Theil Index: Characterizing Graph Centralization using von Neumann Entropy
Cited by in corpus (6)
- Mapping quantum circuits to modular architectures with QUBO
- Interaction graph-based characterization of quantum benchmarks for improving quantum circuit mapping techniques
- SpinQ: Compilation strategies for scalable spin-qubit architectures
- Near-Term Spin-Qubit Architecture Design via Multipartite Maximally-Entangled States
- Low-Depth Flag-Style Syndrome Extraction for Small Quantum Error-Correction Codes
- Lightcone Bounds for Quantum Circuit Mapping via Uncomplexity