Noisy intermediate-scale quantum (NISQ) algorithms

2021/01/31 by Kishor Bharti, Alba Cervera-Lierta, Thi Ha Kyaw +14 · 35 citations
Computer Science · Physics and Astronomy · #Quantum Computing Algorithms and Architecture #Quantum Information and Cryptography #Quantum many-body systems #cond-mat.stat-mech #cs.AI #cs.LG #quant-ph

paper · pdf · doi:10.1103/revmodphys.94.015004

published as Rev. Mod. Phys. 94, 015004 (2022) · Added new content, Modified certain parts and the paper structure

arxiv created 2021/10/06 · openalex publication_date 2022/02/15 · arxiv updated 2022/02/17 · openalex created_date 2022/02/24 · openalex updated_date 2026/08/01

Abstract

A universal fault-tolerant quantum computer that can solve efficiently problems such as integer factorization and unstructured database search requires millions of qubits with low error rates and long coherence times. While the experimental advancement towards realizing such devices will potentially take decades of research, noisy intermediate-scale quantum (NISQ) computers already exist. These computers are composed of hundreds of noisy qubits, i.e. qubits that are not error-corrected, and therefore perform imperfect operations in a limited coherence time. In the search for quantum advantage with these devices, algorithms have been proposed for applications in various disciplines spanning physics, machine learning, quantum chemistry and combinatorial optimization. The goal of such algorithms is to leverage the limited available resources to perform classically challenging tasks. In this review, we provide a thorough summary of NISQ computational paradigms and algorithms. We discuss the key structure of these algorithms, their limitations, and advantages. We additionally provide a comprehensive overview of various benchmarking and software tools useful for programming and testing NISQ devices.

Citations

• Open systems dynamics: Simulating master equations in the computer
• NWChem: A comprehensive and scalable open-source solution for large scale molecular simulations
• Natural Gradient Works Efficiently in Learning
• Quantum Annealing in the Transverse Ising Model
• Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming
• A Practical Introduction to Tensor Networks: Matrix Product States and Projected Entangled Pair States
• Adiabatic Quantum Computation Is Equivalent to Standard Quantum Computation
• On the limited memory BFGS method for large scale optimization
• Simulated Quantum Computation of Molecular Energies
• Matrix Factorization Techniques for Recommender Systems
• Matrix product states, projected entangled pair states, and variational renormalization group methods for quantum spin systems
• Elementary gates for quantum computation
• Good Quantum Error-Correcting Codes Exist
• Fault-tolerant quantum computation by anyons
• Polynomial-Time Algorithms for Prime Factorization and Discrete Logarithms on a Quantum Computer
• Quantum theory, the Church–Turing principle and the universal quantum computer
• Global entanglement in multiparticle systems
• Simulating physics with computers
• Keldysh field theory for driven open quantum systems
• Quantum Machine Learning
• Error mitigation for short-depth quantum circuits
• Tapering off qubits to simulate fermionic Hamiltonians
• Beating the random assignment on constraint satisfaction problems of bounded degree
• A blueprint for demonstrating quantum supremacy with superconducting qubits
• Quantum Algorithm for Systems of Linear Equations with Exponentially Improved Dependence on Precision
• A quantum algorithm to train neural networks using low-depth circuits
• Quantum Computing in the NISQ era and beyond
• Cloud Quantum Computing of an Atomic Nucleus
• Machine learning with controllable quantum dynamics of a nuclear spin ensemble in a solid
• A quantum alternating operator ansatz with hard and soft constraints for lattice protein folding
• Multi-objective evolutionary algorithms for quantum circuit discovery
• Machine learning and the physical sciences
• Subspace Variational Quantum Simulator
• Classical and Quantum Bounded Depth Approximation Algorithms
• A Survey of Quantum Learning Theory
• Minimizing State Preparations in Variational Quantum Eigensolver by Partitioning into Commuting Families
• Quantum Filter Diagonalization: Quantum Eigendecomposition without Full Quantum Phase Estimation
• Quantum Hamiltonian-Based Models and the Variational Quantum Thermalizer Algorithm
• Noise-Resilient Quantum Dynamics Using Symmetry-Preserving Ansatzes
• On the Classical Hardness of Spoofing Linear Cross-Entropy Benchmarking
• How to Teach AI to Play Bell Non-Local Games: Reinforcement Learning
• A Variational Quantum Algorithm for Preparing Quantum Gibbs States
• Re-epithelialization and immune cell behaviour in an ex vivo human skin model
• Predicting Many Properties of a Quantum System from Very Few Measurements
• Recent developments in the PySCF program package
• The Quantum Approximate Optimization Algorithm Needs to See the Whole Graph: A Typical Case
• P SI4 1.4: Open-source software for high-throughput quantum chemistry
• The Quantum Approximate Optimization Algorithm Needs to See the Whole Graph: Worst Case Examples
• Fundamentals of Molecular Integrals Evaluation
• Variational Hamiltonian Diagonalization for Dynamical Quantum Simulation
• A QUBO Formulation for Qubit Allocation
• Fault-Tolerant Operation of a Quantum Error-Correction Code
• Quantum Assisted Eigensolver
• Effective Compression of Quantum Braided Circuits Aided by ZX-Calculus
• Prospects and challenges of quantum finance
• Quantum computational advantage using photons
• Anomalous collapses of Nares Strait ice arches leads to enhanced export of Arctic sea ice
• Supervised quantum machine learning models are kernel methods
• Optimal training of variational quantum algorithms without barren plateaus
• Quantum principal component analysis only achieves an exponential speedup because of its state preparation assumptions
• A learning algorithm for boltzmann machines
• GEO: Enhancing Combinatorial Optimization with Classical and Quantum Generative Models
• Generation of High-Resolution Handwritten Digits with an Ion-Trap Quantum Computer
• Unitary transformation of the electronic Hamiltonian with an exact quadratic truncation of the Baker-Campbell-Hausdorff expansion
• Portfolio rebalancing experiments using the Quantum Alternating Operator Ansatz
• Quantum Convolutional Neural Networks for High Energy Physics Data Analysis
• O(N³) Measurement Cost for Variational Quantum Eigensolver on Molecular Hamiltonians
• Learning to learn with quantum neural networks via classical neural networks
• Robust Implementation of Generative Modeling with Parametrized Quantum Circuits
• For Fixed Control Parameters the Quantum Approximate Optimization Algorithm's Objective Function Value Concentrates for Typical Instances
• Performance of the Quantum Approximate Optimization Algorithm on the Maximum Cut Problem
• PennyLane: Automatic differentiation of hybrid quantum-classical computations

Cited by

• Quantum machine learning for complex systems: paradigms, applications, and challenges
• Limitations of quantum hardware for molecular energy estimation using VQE
• Leveraging analog quantum computing with neutral atoms for solvent configuration prediction in drug discovery
• Calculating the Energy Profile of an Enzymatic Reaction on a Quantum Computer
• Efficient strategies for reducing sampling error in quantum Krylov subspace diagonalization
• Quantum computing for extracting nuclear resonances
• Symmetry-enhanced Counterdiabatic Quantum Algorithm for Qudits
• Stabilizer configuration interaction: Finding molecular subspaces with error detection properties
• The Role of Quantum Computing in Advancing Scientific High-Performance Computing: A perspective from the ADAC Institute
• Inference of maximum parsimony phylogenetic trees with model-based classical and quantum methods
• Planted Solutions in Quantum Chemistry: Generating Non-Trivial Hamiltonians with Known Ground States
• Symmetry-based quantum algorithms for open-shop scheduling with hard constraints
• Sparse Quantum State Preparation for Strongly Correlated Systems
• Generative quantum combinatorial optimization by means of a novel conditional generative quantum eigensolver
• Quantum Spectral Clustering: Comparing Parameterized and Neuromorphic Quantum Kernels
• Ground-state reachability for variational quantum eigensolvers: a Rydberg-atom case study
• Iterative Harrow-Hassidim-Lloyd quantum algorithm for solving resonances with eigenvector continuation
• Noise tolerance via reinforcement: Learning a reinforced quantum dynamics
• Quantum thermodynamics and semi-definite optimization
• A compiler for universal photonic quantum computers
• Make Some Noise! Measuring Noise Model Quality in Real-World Quantum Software
• Quantum computing and artificial intelligence: status and perspectives
• Learning to Program Quantum Measurements for Machine Learning
• A coherent approach to quantum-classical optimization
• Quantum-Enhanced Classification of Brain Tumors Using DNA Microarray Gene Expression Profiles
• Quantum Vision Transformers
• First-principles open quantum dynamics for solids based on density-matrix formalism
• Classical Interfaces for Controlling Cryogenic Quantum Computing Technologies
• Quantum computing of fluid dynamics using the hydrodynamic Schrödinger equation
• Path Matters: Industrial Data Meet Quantum Optimization
• Prospects of Quantum Computing for Molecular Sciences
• Shadows of quantum machine learning
• Sampling-based Quantum Optimization Algorithm with Quantum Relaxation
• Energy Landscape Plummeting in Variational Quantum Eigensolver: Subspace Optimization, Non-iterative Corrections and Generator-informed Initialization for Improved Quantum Efficiency
• Hybrid Reinforcement Learning-based Sustainable Multi-User Computation Offloading for Mobile Edge-Quantum Computing
• Error mitigation for variational quantum algorithms through mid-circuit measurements

Related

• Where are we heading with NISQ?
• The Quantum Computer Puzzle (Expanded Version)
• The Argument against Quantum Computers
• Quantum Computing in the NISQ era and beyond
• Full-stack quantum computing systems in the NISQ era: algorithm-driven and hardware-aware compilation techniques