The Bitter Truth About Quantum Algorithms in the NISQ Era

Abstract

Implementing a quantum algorithm on a NISQ device has several challenges that arise from the fact that such devices are noisy and have limited quantum resources. Thus, various factors contributing to the depth and width as well as to the noise of an implementation of an algorithm must be understood in order to assess whether an implementation will execute successfully on a given NISQ device. In this contribution, we discuss these factors and their impact on algorithm implementations. Especially, we will cover state preparation, oracle expansion, connectivity, circuit rewriting, and readout: these factors are very often ignored when presenting an algorithm but they are crucial when implementing such an algorithm on near-term quantum computers. Our contribution will help developers in charge of realizing algorithms on such machines in (i) achieving an executable implementation, and (ii) assessing the success of their implementation on a given machine.

References in corpus (14)

• A Quantum Approximate Optimization Algorithm
• Quantum random access memory
• Synthesis of Quantum Logic Circuits
• t$|$ket$⟩$ : A Retargetable Compiler for NISQ Devices
• Quantum-state preparation with universal gate decompositions
• Quantum Circuit Simplification and Level Compaction
• Fast Quantum Modular Exponentiation
• Circuit-Based Quantum Random Access Memory for Classical Data
• ScaffCC: Scalable Compilation and Analysis of Quantum Programs
• Machine learning for discriminating quantum measurement trajectories and improving readout
• Practical optimization for hybrid quantum-classical algorithms
• Gate-error analysis in simulations of quantum computers with transmon qubits
• Quantum implementation of elementary arithmetic operations
• Quantum Compiler Optimizations

Cited by in corpus (7)

• Special Session: Noisy Intermediate-Scale Quantum (NISQ) Computers -- How They Work, How They Fail, How to Test Them?
• Quantum and Quantum-Inspired Stereographic K Nearest-Neighbour Clustering
• Assisted quantum simulation of open quantum systems
• An example of use of Variational Methods in Quantum Machine Learning
• Hybrid Quantum Applications Need Two Orchestrations in Superposition: A Software Architecture Perspective
• Detailed Account of Complexity for Implementation of Some Gate-Based Quantum Algorithms
• Hybrid Data Management Architecture for Present Quantum Computing