The Bitter Truth About Quantum Algorithms in the NISQ Era
arXiv:2006.02856 · doi:10.1088/2058-9565/abae7d
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 (43)
- Quantum Computing in the NISQ era and beyond
- A Quantum Approximate Optimization Algorithm
- Quantum machine learning in feature Hilbert spaces
- Error mitigation for short-depth quantum circuits
- Circuit-centric quantum classifiers
- Quantum random access memory
- A Theory of Quantum Error-Correcting Codes
- Quantum Networks for Elementary Arithmetic Operations
- Quantum Error Correction for Beginners
- Validating quantum computers using randomized model circuits
- Synthesis of Quantum Logic Circuits
- tket : A Retargetable Compiler for NISQ Devices
- Quantum Circuits for General Multiqubit Gates
- Quantum-state preparation with universal gate decompositions
- Robust data encodings for quantum classifiers
- Resource-Aware Quantum Programming with General Recursion and Quantum Control
- Efficient Networks for Quantum Factoring
- Quantum Circuit Simplification and Level Compaction
- Complete 3-Qubit Grover Search on a Programmable Quantum Computer
- Concrete Categorical Model of a Quantum Circuit Description Language with Measurement
- Mitigation of readout noise in near-term quantum devices by classical post-processing based on detector tomography
- Addition on a Quantum Computer
- Fast Quantum Modular Exponentiation
- A Software Methodology for Compiling Quantum Programs
- Circuit-Based Quantum Random Access Memory for Classical Data
- ScaffCC: Scalable Compilation and Analysis of Quantum Programs
- 64-Qubit Quantum Circuit Simulation
- Quantum Algorithm Implementations for Beginners
- Machine learning for discriminating quantum measurement trajectories and improving readout
- Quantum autoencoders to denoise quantum data
- Practical optimization for hybrid quantum-classical algorithms
- Quantum Analog-Digital Conversion
- Gate-error analysis in simulations of quantum computers with transmon qubits
- Impact of qubit connectivity on quantum algorithm performance
- A Roadmap for Automating the Selection of Quantum Computers for Quantum Algorithms
- Loading Classical Data into a Quantum Computer
- Comparing the Overhead of Topological and Concatenated Quantum Error Correction
- Qubit Allocation for Noisy Intermediate-Scale Quantum Computers
- Quantum implementation of elementary arithmetic operations
- Fast Quantum Modular Exponentiation Architecture for Shor's Factorization Algorithm
- Quantum Compiler Optimizations
- On the depth overhead incurred when running quantum algorithms on near-term quantum computers with limited qubit connectivity
- Quantum Random State Generation with Predefined Entanglement Constraint
Cited by in corpus (59)
- Quantum PUF for Security and Trust in Quantum Computing
- Quantum Software Engineering: Roadmap and Challenges Ahead
- Quantum Machine Learning for Digital Health? A Systematic Review
- Quantum simulation of dissipative collective effects on noisy quantum computers
- Configurable sublinear circuits for quantum state preparation
- Computation of molecular excited states on IBM quantum computers using a discriminative variational quantum eigensolver
- Investigating the effect of circuit cutting in QAOA for the MaxCut problem on NISQ devices
- Low-rank quantum state preparation
- Warm-Starting and Quantum Computing: A Systematic Mapping Study
- Architectural Vision for Quantum Computing in the Edge-Cloud Continuum
- AGP-based unitary coupled cluster theory for quantum computers
- Thermodynamics of quantum trajectories on a quantum computer
- Implementation of Measurement Reduction for the Variational Quantum Eigensolver
- Approximate encoding of quantum states using shallow circuits
- Quantum algorithms for scientific computing
- Mitigating crosstalk errors by randomized compiling: Simulation of the BCS model on a superconducting quantum computer
- Hybrid Quantum-Classical Heuristic for the Bin Packing Problem
- Special Session: Noisy Intermediate-Scale Quantum (NISQ) Computers -- How They Work, How They Fail, How to Test Them?
- On the effects of biased quantum random numbers on the initialization of artificial neural networks
- Variational quantum eigensolver with linear depth problem-inspired ansatz for solving portfolio optimization in finance
- Automatic Depth-Optimized Quantum Circuit Synthesis for Diagonal Unitary Matrices with Asymptotically Optimal Gate Count
- Topological Quantum Gates in Homotopy Type Theory
- Quantum and Quantum-Inspired Stereographic K Nearest-Neighbour Clustering
- QTN-VQC: An End-to-End Learning framework for Quantum Neural Networks
- The T-Complexity Costs of Error Correction for Control Flow in Quantum Computation
- Quantum SWAP gate realized with CZ and iSWAP gates in a superconducting architecture
- Synergistic Dynamical Decoupling and Circuit Design for Enhanced Algorithm Performance on Near-Term Quantum Devices
- Error estimation in current noisy quantum computers
- Amplitude amplification-inspired QAOA: Improving the success probability for solving 3SAT
- Parametrized constant-depth quantum neuron
- Assisted quantum simulation of open quantum systems
- Characterization, synthesis, and optimization of quantum circuits over multiple-control -rotation gates: A systematic study
- An example of use of Variational Methods in Quantum Machine Learning
- Scalability Challenges in Variational Quantum Optimization under Stochastic Noise
- Constant Depth Code Deformations in the Parity Architecture
- Quantum algorithm for learning secret strings and its experimental demonstration
- Joint Wire Cutting with Non-Maximally Entangled States
- Hybrid Quantum Applications Need Two Orchestrations in Superposition: A Software Architecture Perspective
- QCEDA: Using Quantum Computers for EDA
- ArsoNISQ: Analyzing Quantum Algorithms on Near-Term Architectures
- Optimized synthesis of circuits for diagonal unitary matrices with reflection symmetry
- Basis set generation and optimization in the NISQ era with Quiqbox.jl
- A Quantum Information Theoretic View On A Deep Quantum Neural Network
- Linear decomposition of approximate multi-controlled single qubit gates
- Harnessing Quantum Computing for Energy Materials: Opportunities and Challenges
- Improving Qubit Routing by Using Entanglement Mediated Remote Gates
- The Quantum Monadology
- Scalable quantum simulator with an extended gate set in giant atoms
- Comparing Quantum Service Offerings
- On the Differential Topology of Expressivity of Parameterized Quantum Circuits
- Robustness of the quantum Mpemba effect against state-preparation errors
- Hybrid Quantum Classical Graph Neural Networks for Particle Track Reconstruction
- Post-Quantum Security: Origin, Fundamentals, and Adoption
- Performance Evaluations of Signed and Unsigned Noisy Approximate Quantum Fourier Arithmetic
- Jenga-Krotov algorithm: Efficient compilation of multi-qubit gates for exchange-only qubits
- A Useful Metric for the NISQ Era: Qubit Error Probability and Its Role in Zero Noise Extrapolation
- Hybrid Data Management Architecture for Present Quantum Computing
- Detailed Account of Complexity for Implementation of Some Gate-Based Quantum Algorithms
- The Effect of Noise on the Performance of Variational Algorithms for Quantum Chemistry