Survey on Quantum Circuit Compilation for Noisy Intermediate-Scale Quantum Computers - Artificial Intelligence to Heuristics
Abstract : 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.
? A variety of small superconducting processors, with varying architectures, already exist.
? Therefore, existing quantum hardware is not suited to implement the deep and highly connected circuits required for the UCC and similar ansätze for applications beyond basic demonstrations such as the H2 molecule.
? These three requirements make that certain existing algorithms are better suited for PQC optimization and are more commonly used, and that new algorithms are being developed specifically for PQC optimization.
? The latter being quasiparticles obeying continuous or anyonic statistics, and existing only in two-dimensional confinement.
? Quantum computing (QC) aims to solve intractable computational problems by leveraging quantum mechanical principles like superposition and entanglement to manipulate information efficiently.
? In a QC application, a set of qubits are initialized to encode a given problem including its data input.
? In the optimization-based variants of our compiler, we implement the above goals by posing the compilation problem as a constrained optimization problem to be solved by a satisfiability modulo theory (SMT) solver.
? The optimization problem has variables and constraints which express program information, machine topology constraints, and machine error information.
• Most of the originally proposed quantum algorithms require millions of physical qubits to incorporate these QEC techniques successfully.
• The Fermi-Hubbard model with its few and simple interaction terms is proposed as the most promising near-term application of the method.
• Alternative methods to measure the overlap without the use of control unitaries have been proposed .
• In classical machine learning, the natural gradient was proposed that adapts the update rule to the nonEuclidean metric of the parameter space.
• We now review various NISQ algorithms that have been proposed to tackle quantum chemistry and many-body physics related problems.
? We used or created Scaffold programs for each benchmark and obtained LLVM IR using the ScaffCC compiler
? Using real-system evaluations our work determines the relative importance of these parameters and compares the performance of heuristic and optimal techniques.
? Simulated or scaled success rates may not correlate well with real performance.
? Making good use of NISQ hardware, however, requires very efficient, near-optimal mappings of algorithms onto them.
? Under this policy, for CNOT gate, we set reliability tracking variables based on the junction used for routing.
? The degree of the qubit is the number of CNOTs in which the qubit is used.
|