arXiv:1811.08985

On the Influence of Initial Qubit Placement During NISQ Circuit Compilation

Alexandru Paler

Published Nov 22, 2018• 1 citation

Abstract

Noisy Intermediate-Scale Quantum (NISQ) machines are not fault-tolerant, operate few qubits (currently, less than hundred), but are capable of executing interesting computations. Above the quantum supremacy threshold (approx. 60 qubits), NISQ machines are expected to be more powerful than existing classical computers. One of the most stringent problems is that computations (expressed as quantum circuits) have to be adapted (compiled) to the NISQ hardware, because the hardware does not support arbitrary interactions between the qubits. This procedure introduces additional gates (e.g. SWAP gates) into the circuits while leaving the implemented computations unchanged. Each additional gate increases the failure rate of the adapted (compiled) circuits, because the hardware and the circuits are not fault-tolerant. It is reasonable to expect that the placement influences the number of additionally introduced gates. Therefore, a combinatorial problem arises: how are circuit qubits allocated (placed) initially to the hardware qubits? The novelty of this work relies on the methodology used to investigate the influence of the initial placement. To this end, we introduce a novel heuristic and cost model to estimate the number of gates necessary to adapt a circuit to a given NISQ architecture. We implement the heuristic (source code available on github) and benchmark it using a standard compiler (e.g. from IBM Qiskit) treated as a black box. Preliminary results indicate that cost reductions of up to 10\% can be achieved for practical circuit instances on realistic NISQ architectures only by placing qubits differently than default (trivial placement).

DOI: 10.48550/arxiv.1811.08985

Related papers

NISQ circuit compilers: search space structure and heuristics

Alexandru Paler, Alwin Zulehner, Robert Wille

Noisy, intermediate-scale quantum (NISQ) computers are expected to execute quantum circuits of up to a few hundred qubits. The circuits have to satisfy certain constraints concerning the placement and interactions of the involved qubits. Hence, a compiler takes an input circuit not conforming to a NISQ architecture and transforms it to a conforming output circuit. NISQ hardware is faulty and insufficient to implement computational fault-tolerance, such that computation results will be faulty, too. Accordingly, compilers need to optimise the depth and the gate count of the compiled circuits, because these influence the aggregated computation result error. This work discusses the complexity of compilation with a particular focus on the search space structure. The presented analysis decomposes the compilation problem into three combinatorial subproblems for which heuristics can be determined. The search space structure is the result of analysing jointly the gate sequence of the input circuit and its influence on how qubits have to be mapped to a NISQ architecture. These findings support the development of future NISQ compilers.

Jun 19, 201812 citations

NISQ circuit compilation is the travelling salesman problem on a torus

Alexandru Paler, Alwin Zulehner, Robert Wille

Abstract Noisy, intermediate-scale quantum (NISQ) computers are expected to execute quantum circuits of up to a few hundred qubits. The circuits have to conform to NISQ architectural constraints regarding qubit allocation and the execution of multi-qubit gates. Quantum circuit compilation (QCC) takes a nonconforming circuit and outputs a compatible circuit. Can classical optimisation methods be used for QCC? Compilation is a known combinatorial problem shown to be solvable by two types of operations: (1) qubit allocation, and (2) gate scheduling. We show informally that the two operations form a discrete ring. The search landscape of QCC is a two dimensional discrete torus where vertices represent configurations of how circuit qubits are allocated to NISQ registers. Torus edges are weighted by the cost of scheduling circuit gates. The novelty of our approach uses the fact that a circuit’s gate list is circular: compilation can start from any gate as long as all the gates will be processed, and the compiled circuit has the correct gate order. Our work bridges a theoretical and practical gap between classical circuit design automation and the emerging field of quantum circuit optimisation.

arXiv:1806.07241Quantum Science and TechnologyFeb 15, 20214 citations

Quantum Circuit Pruning: From NISQ Architectures to Fault-Tolerant Operations

Pau Escofet, Carmen G. Almudéver, Sergi Abadal +1 more

We present a routing-aware pruning strategy for quantum circuits that selectively removes parametric two-qubit gates whose computational contribution is outweighed by the fidelity cost of their execution, and assess it across both Noisy Intermediate-Scale Quantum (NISQ) and fault-tolerant quantum computing (FTQC) architectures. Each two-qubit gate of a circuit is evaluated by comparing an architecture-independent lower bound on the fidelity cost of omitting the gate against a hardware-specific model for the routing execution cost in each setting. We additionally provide an analytical characterization of the pruning boundary as a function of rotation angle, qubit distance, and hardware noise. Simulations on benchmark circuits demonstrate gate count reductions of up to 48.6% and fidelity improvements of up to 47.7% in the NISQ regime, while a feasibility analysis on FT hardware indicates that pruning is expected to remain relevant across a range of code distances and physical error rates. These results establish routing-aware pruning as a practical and unified compilation strategy across the quantum computing stack.

quant-pharXiv:2610.00669IEEE Transactions on Circuits & Systems II Express BriefsOct 2, 20260 citations

Quantum Science and Technology / NISQ circuit compilation is the travelling salesman problem on a torus

Alexandru Paler, Alwin Zulehner, Robert Wille

Noisy, intermediate-scale quantum (NISQ) computers are expected to execute quantum circuits of up to a few hundred qubits. The circuits have to conform to NISQ architectural constraints regarding qubit allocation and the execution of multi-qubit gates. Quantum circuit compilation (QCC) takes a nonconforming circuit and outputs a compatible circuit. Can classical optimisation methods be used for QCC? Compilation is a known combinatorial problem shown to be solvable by two types of operations: (1) qubit allocation, and (2) gate scheduling. We show informally that the two operations form a discrete ring. The search landscape of QCC is a two dimensional discrete torus where vertices represent configurations of how circuit qubits are allocated to NISQ registers. Torus edges are weighted by the cost of scheduling circuit gates. The novelty of our approach uses the fact that a circuit's gate list is circular: compilation can start from any gate as long as all the gates will be processed, and the compiled circuit has the correct gate order. Our work bridges a theoretical and practical gap between classical circuit design automation and the emerging field of quantum circuit optimisation.

Jan 1, 202119 citations

Integration of Machine Learning with Quantum Computing: Compilation of Quantum Circuit for Efficacy on Noisy Intermediate-Scale Quantum Devices

M. Praba, Ahmad Abdelhafiz Ali Samhan, V. Samuthira Pandi +3 more

Hybridizing machine learning (ML) with quantum computing has become an attractive strategy to increase computational power on Noisy Intermediate Scale Quantum (NISQ) devices. Although these can be potentially quantum advantage devices, their qubit numbers and noise are bounded and there are challenges when it comes to practical quantum circuit realization. This work concentrates on the creation of optimized quantum circuits via ML-based strategies, to enhance the performance of the circuits, to reduce the error rate and to accommodate the particular noise profile of the hardware of NISQ devices. The resulting suboptimal mappings with little or no consideration of noise and hardware topology in traditional quantum compilers can ruin the fidelity of quantum algorithm. Leveraging machine learning, and specifically reinforcement and supervised learning methods, our method learns to optimize compilation strategy for specific quantum hardware architecture. The paper proposes a framework that uses machine learning models to predict qubit mappings, gate decompositions, and transpilation paths that minimize gate depth and error accumulation. We also investigate transfer learning methods for propagating the learned compilation strategies to novel NISQ machines. Such methods are empirically validated on both simulated and real quantum hardware backends, providing evidence of circuit depth, execution time and error reductions. The results show that ML-assisted compilation can achieve better success probabilities for benchmark quantum algorithms like VQE and QAOA than conventional compilers. Furthermore, the work examines the interpretability of ML models providing hardware-aware optimization recommendations and understanding the noise patterns and methods of error correction. Our work highlights the key role of ML for transferring between theoretical quantum algorithms and their practical NISQ implementations. This integration boosts the immediate applicability of existing quantum devices and provides a basis for adaptive and scalable likelihood-based compilation for the era of fault-tolerant quantum computation. Our results motivate further investigation of hybrid classical-quantum workflows, in which ML iteratively improves compilation in accordance with changing hardware noise and capabilities. By improving quantum circuit compilation onNISQ computers, this work is taking steps toward the realization of quantum advantage in application scenarios such as optimization, cryptography, and quantum simulation without needing to wait for fully fault-tolerant large-scale quantum computers.

Asian Conference on Innovation in Technology (ASIANCON)Aug 22, 20251 citation

Survey on Quantum Circuit Compilation for Noisy Intermediate-Scale Quantum Computers: Artificial Intelligence to Heuristics

Janusz Kusyk, Samah Mohamed Saeed, M. Ümit Uyar

Computationally expensive applications, including machine learning, chemical simulations, and financial modeling, are promising candidates for noisy intermediate scale quantum (NISQ) computers. In these problems, one important challenge is mapping a quantum circuit onto NISQ hardware while satisfying physical constraints of an underlying quantum architecture. Quantum circuit compilation (QCC) aims to generate feasible mappings such that a quantum circuit can be executed in a given hardware platform with acceptable confidence in outcomes. Physical constraints of a NISQ computer change frequently, requiring QCC process to be repeated often. When a circuit cannot directly be executed on a quantum hardware due to its physical limitations, it is necessary to modify the circuit by adding new quantum gates and auxiliary qubits, increasing its space and time complexity. An inefficient QCC may significantly increase error rate and circuit latency for even the simplest algorithms. In this article, we present artificial intelligence (AI)-based and heuristic-based methods recently reported in the literature that attempt to address these QCC challenges. We group them based on underlying techniques that they implement, such as AI algorithms including genetic algorithms, genetic programming, ant colony optimization and AI planning, and heuristics methods employing greedy algorithms, satisfiability problem solvers, dynamic, and graph optimization techniques. We discuss performance of each QCC technique and evaluate its potential limitations.

IEEE Transactions on Quantum EngineeringJan 1, 202183 citations