PaperlayerView exact revision on arXiv

Source-linked AI summary

Noisy intermediate-scale quantum (NISQ) algorithms

Kishor Bharti, Alba Cervera-Lierta, Thi Ha Kyaw, Tobias Haug, Sumner Alperin-Lea, Abhinav Anand, Matthias Degroote, Hermanni Heimonen, Jakob S. Kottmann, Tim Menke, Wai-Keong Mok, Sukin Sim, Leong-Chuan Kwek, Alán Aspuru-Guzik

arXiv:2101.08448v2quant-phcond-mat.stat-mechcs.AIcs.LG

TL;DR

The paper addresses how to use limited, noisy quantum hardware while fault-tolerant machines remain impractical. It reviews NISQ computational paradigms, algorithms, applications, benchmarking, and software, emphasizing their structures, advantages, and limitations. The review presents NISQ as a broad framework for exploiting current devices and guiding future development, while highlighting hardware noise, optimization bottlenecks, and fault-tolerance requirements.

  • Problem

    NISQ devices have limited qubit counts, short coherence times, and noise, motivating methods that maximize their available computational resources before fault-tolerant quantum computing is practical.

  • Method

    The review synthesizes NISQ algorithms, their modular structures, applications, theoretical and experimental challenges, benchmarking methods, and quantum programming software.

  • Results

    The review identifies a diverse NISQ algorithmic landscape spanning applications such as quantum chemistry, machine learning, optimization, eigensolvers, sampling, and error mitigation.

  • Takeaways & Limitations

    NISQ research combines algorithm and hardware progress to exploit current quantum resources while developing techniques relevant to longer-term fault-tolerant computation.

  • Takeaways & Limitations

    NISQ optimization is limited by shallow coherence-compatible circuits and the large measurement cost required to estimate observables precisely.

Abstract

from arXiv · show

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.

I. INTRODUCTION

NISQ devices offer limited, noisy quantum resources while fault-tolerant quantum computing remains a long-term goal. This review organizes NISQ algorithms, applications, challenges, benchmarking, and software within computational-complexity constraints.

  • Motivation: Fault-tolerant quantum computing may require millions of physical qubits and decades of development, whereas existing NISQ devices contain roughly 100 noisy, non-error-corrected qubits.NISQ devices aim to exploit current hardware while informing longer-term fault-tolerant approaches.
  • Computational context: The review uses complexity classes, reductions, and known examples such as factoring to frame the computational scope of quantum algorithms.It notes that some containment relations remain unproven, including whether P equals NP.
  • Experimental progress: Experimental progress includes Gaussian boson sampling with 50 indistinguishable single-mode squeezed states, where quantum advantage was observed in sampling time complexity.The review presents this as an example of experimental progress toward quantum advantage.
  • Motivation: NISQ algorithms are constrained by hardware noise and short coherence times, which restrict practical quantum circuits to shallow depths.The NISQ label is hardware-focused, while near-term refers to algorithms intended for devices available in the next few years.
  • Review scope: The review surveys NISQ algorithms and techniques across quantum machine learning, quantum chemistry, and combinatorial optimization, and discusses their challenges and applications.It also covers theoretical and experimental challenges, error mitigation, trainability, hardware mapping, benchmarking, and quantum software tools.

3. Other objective functions

VQA objective functions can extend beyond mean energy, while circuit design and state preparation determine optimization quality and hardware compatibility. The section describes objective alternatives, ansatz construction, and decomposition methods.

  • Objective functions: CVaR evaluates the α-tail of the energy distribution, interpolating between the sample mean at α = 1 and the sample minimum as α approaches 0.It is defined from energy-basis measurements arranged in non-decreasing order.
  • Objective functions: The CVaR and Gibbs objectives reduce to mean energy in suitable hyperparameter limits and have empirically outperformed mean energy on certain combinatorial optimization problems.The relevant limits are α →1 for CVaR and η →0 for the Gibbs objective.
  • State preparation: A VQA state is prepared by applying a parameterized unitary U(θ) to an initial state, which may itself be generated by a parameterized preparation unitary.Initial states can encode data, exploit superpositions, or represent Hartree–Fock approximations.
  • State preparation: A good initial state can place optimization closer to the optimum, helping convergence toward the solution.The choice of initial state may exploit known properties of the expected final state or the target application.
  • Parameterized quantum circuits: Ansatz selection trades problem suitability against hardware constraints because it affects convergence, solution quality, circuit depth, and native-gate cost.Ansätze are commonly categorized as problem-inspired or hardware-efficient.
  • Unitary decomposition: Suzuki–Trotter decomposition approximates hard-to-implement unitaries by decomposing their generators into non-commuting, readily implementable operators and finite evolution steps.Pauli-string evolutions can be further decomposed into primitive one- and two-qubit gates, with physics-specific structure reducing gate counts.

Quantum Approximate Optimization Algorithm.

Variational circuits balance problem structure against hardware constraints, while measurement and optimization costs remain central challenges for NISQ implementations.

  • Hardware-efficient ansätze: Hardware-efficient ansätze use restricted gate sets and connectivity topologies tailored to device architectures.Their layers combine single-qubit gates with entangling gates applied across multiple or all qubits.
  • Hardware-efficient ansätze: Gate choice, connectivity, and ordering determine the covered Hilbert-space region and convergence speed for a given problem.
  • Intermediate ansätze: Intermediate ansätze can use native exchange-type gates while respecting variational symmetries and reducing parameter counts in quantum chemistry problems.This approach is illustrated for molecules including H2 and LiH.
  • Expectation-value estimation: Expectation values are estimated by rotating observables into the computational basis and sampling measurement outcomes.Pauli-x and Pauli-y measurements are transformed into the Pauli-z basis before readout.
  • Expectation-value estimation: ε ∝ 1/√Ns: estimating Pauli-string expectation values more precisely requires increasing the number of single-shot measurements.Finite sampling introduces an additive estimation error whose size decreases with the inverse square root of the sample count.
  • Parameter optimization: PQC optimizers must limit measurements, operate with short coherence times, and tolerate noisy, shot-limited objective estimates.These constraints make measurement or function-evaluation count a significant runtime consideration.
  • Parameter optimization: QNG has reported advantages over other gradient methods and can be generalized to noisy quantum circuits.
  • Parameter optimization: One stochastic-gradient sampling strategy can evaluate only one Pauli term at a single quadrature point, reducing measurement requirements.The method is presented as an extreme sampling regime for accelerating VQA optimization.

III. OTHER NISQ APPROACHES

Other NISQ approaches include analog and hybrid methods that avoid adaptive PQC parameter tuning, especially quantum annealing and adiabatic computation. These methods encode optimization problems into Hamiltonians, but finite-temperature and hardware-connectivity constraints can affect outcomes.

  • Quantum annealing: Quantum annealing uses quantum-mechanical fluctuations, controlled by an annealing schedule, to explore optimization solution spaces.The approach is analogous to simulated annealing, which uses thermal fluctuations.
  • Adiabatic quantum computation: In the limit T →∞, evolution initialized in the ground state of H(0) yields a ground state of H(1).
  • Adiabatic quantum computation: Adiabatic quantum computation evolves from the ground state of an initial Hamiltonian toward the ground state of a final Hamiltonian under a time-dependent schedule.The formal setup uses k-local Hamiltonians and assumes a smoothly varying Hamiltonian with a unique ground state.
  • Quantum annealing: QA permits diabatic transitions caused by finite temperature, rapid Hamiltonian changes, and environmental noise, making excited-state trapping possible.
  • QUBO encoding: QUBO minimizes x^T Qx + c^T x over binary variables and can be mapped to finding the ground state of a diagonal Ising Hamiltonian.
  • Quantum annealing: Limited qubit connectivity requires additional engineering constraints, including minor embedding, when implementing annealing problems.

B. Gaussian boson sampling

Gaussian boson sampling (GBS) replaces photon-state inputs with Gaussian states and samples measurement outcomes after linear optical processing. Its computational structure supports quantum-advantage experiments and heuristic applications in graph analysis, chemistry, optimization, and machine learning.

  • Protocol and computational basis: GBS uses Gaussian states as optical inputs, which can be created deterministically and provide more degrees of freedom than standard boson sampling.Standard boson sampling is associated with matrix permanents, whereas GBS is computationally equivalent to sampling from matrix Hafnians.
  • Computational hardness and experiments: GBS has supported quantum-advantage demonstrations, including a photonic experiment with 50 indistinguishable single-mode squeezed states and exponentially scaling Torontonian sampling time with photon clicks.GBS became the second platform reported to demonstrate quantum computational supremacy, followed by dynamically programmable nanophotonic-chip work.
  • Protocol and computational basis: A GBS circuit prepares vacuum-derived squeezed states, applies an interferometer of phaseshifters and beamsplitters, and measures photon numbers in each mode.Photon-number-resolving detectors implement the final Fock-basis measurement.
  • Protocol and computational basis: GBS measurement probabilities are controlled through the covariance matrix, which determines the matrix sampled by the Hafnian.For pure Gaussian states, the resulting A matrix is symmetric; photon counts determine row and column deletions or repetitions in the constructed matrix.
  • Applications: GBS has also been applied to molecular vibrational spectra, electron-transfer reactions, molecular docking, stochastic optimization, and unsupervised learning.Variational GBS methods update squeezing and interferometer parameters using measurement outcomes.
  • Applications: Graph applications dominate because graph adjacency matrices naturally fit the symmetric A matrix, enabling dense-subgraph identification, max-clique initialization, graph fingerprints, and stochastic search.The Hafnian counts perfect matchings, while GBS sampling can provide nonuniform graph-informed randomness for classical algorithms.

IV. THEORETICAL CHALLENGES

Theoretical challenges in NISQ variational algorithms include barren plateaus, the trade-off between expressibility and trainability, and reachability limits at finite circuit depth. Analyses of QAOA also establish universality and complexity-theoretic guarantees while identifying optimization difficulties.

  • Barren plateaus: Randomly initialized parameterized quantum circuits can develop barren plateaus, where objective-function gradients decay exponentially with the number of qubits.This behavior is linked to circuits approaching unitary 2-designs and the exponentially large Hilbert-space dimension.
  • Barren plateaus: Noise, decoherence, entanglement, and circuit initialization can affect barren-plateau behavior, motivating strategies that reduce the effective search-space dimension.Proposed approaches include physically informed initial states, parameter correlations, blockwise initialization, and fixed parameters.
  • Parameter dimension: Expressibility measures how closely states sampled from a parameterized circuit approach the Haar distribution, but greater expressibility generally trades off against trainability.Suggested remedies include correlating parameters, restricting rotation angles, and interpolating between fixed and random angles.
  • Parameter dimension: Alternating layered ansätze can combine relative expressibility with the absence of barren plateaus in certain regimes, while their required depth depends on system size and correlation length.In critical VQE phases, the layer count must exceed a system-size-dependent threshold for exponential improvement.
  • Reachability: At finite fixed depth, QAOA can exhibit reachability deficits for MAX-2-SAT, MAX-3-SAT, and graph-optimization problems when clause or graph density exceeds critical values.The critical depth p* determines when optimal solutions can be reached up to a threshold.
  • Theoretical guarantees of the QAOA algorithm: QAOA has been shown to implement universal quantum computation, while efficient classical sampling of even p = 1 output distributions would imply collapse of the polynomial hierarchy.Optimal-control analyses further indicate that bang-anneal-bang protocols can outperform bang-bang protocols, whose local minima proliferate at large total time.

V. PROGRAMMING AND MAXIMIZING NISQ UTILITY

NISQ devices have limited qubits, short coherence times, and noisy operations, motivating methods that maximize available quantum resources without full quantum error correction. The review discusses error mitigation approaches that estimate ideal observables through repeated noisy measurements and classical post-processing.

  • NISQ devices offer roughly 50–100 qubits and permit only a restricted number of gate operations because of noise and short coherence times.
  • Quantum error mitigation suppresses errors in expectation values without extra qubits by combining multiple circuit runs with classical post-processing.
  • Noise-scaling: Zero-noise extrapolation estimates a noiseless expectation value by operating a quantum program at multiple effective noise levels and extrapolating the results.
  • Noise-scaling: Circuit folding and gate folding increase noise while leaving ideal circuits unchanged, and unlike time scaling they do not require full back-end control.
  • Probabilistic error cancellation: Gate-set-tomography-based mitigation avoids explicit noise-model knowledge and targets localized Markovian errors, whereas probabilistic error cancellation requires correct error-model knowledge.
  • Error mitigation limitations: The PEC outcome is centered around the ideal value but has larger variance, while individual error-channel reduction removes first-order error under a perfect-channel-removal assumption.

B. Circuit compilation

NISQ circuit compilation translates theoretical circuits into hardware-compatible operations while addressing native gate sets, circuit depth, and restricted qubit connectivity. Compilation quality matters because naive routing can substantially increase depth and exposure to errors.

  • Quantum compilation maps algorithms to device-specific instructions while accounting for native gates, qubit connectivity, and circuit depth.
  • Circuit decomposition: A raw translation into native gates can produce large circuit depth, and decomposing multi-qubit gates may be challenging.
  • The qubit mapping problem: Qubit routing addresses unavailable two-qubit connections; naive SWAP insertion can significantly increase circuit depth on sparsely connected topologies.
  • The qubit mapping problem: The qubit mapping problem is NP-complete, motivating heuristic, reinforcement-learning, exact-solver, and architecture-specific approaches.
  • The qubit mapping problem: Selecting qubits with favorable error rates and coherence times, or minimizing circuit depth, can improve the performance of a hardware mapping.
  • Applications: Fermionic and qubit ADAPT-VQE variants generated optimized circuits with reduced depths and CNOT counts compared with previous ansatz constructions.
  • Applications: PECT optimized 12-qubit LDCA circuits for estimating LiH and H2O ground-state energies, extending previous LDCA optimizations limited to 8 qubits.

A. Many-body physics and chemistry

Many-body physics and chemistry motivate quantum simulation because classical resources can grow exponentially with system size. The review outlines mappings from fermionic, bosonic, and anyonic descriptions to qubits and discusses variational ground-state estimation and its sampling costs.

  • Classical methods often struggle with many-body simulation because required resources increase exponentially with the number of particles.
  • Fermionic systems: Fermionic creation and annihilation operators can be mapped to qubit operators using transformations including Jordan–Wigner, Bravyi–Kitaev, and Ball-Verstraete-Cirac.
  • Fermionic systems: The Jordan–Wigner mapping represents qubit states as occupation-number vectors and uses Pauli-z strings to preserve fermionic anticommutation properties.
  • Bosonic systems: Truncated bosonic modes can be represented in finite-dimensional bases and translated into Pauli words through encodings such as standard binary or compact encoding.
  • Anyonic systems: An anyonic algebra can be mapped isomorphically to Pauli words while preserving its defining relations, including fermionic and hard-core bosonic limits.
  • Electronic structure: The electronic-structure problem is a prominent VQA task in which continuous many-electron systems are discretized, second-quantized, and encoded into qubits.
  • Electronic structure: Ground-state estimation is generally QMA-hard, but approximate solutions may be sought for larger systems or faster than classically possible methods.
  • Variational algorithms: VQE cost estimation requires O(1/ϵ^2) samples for additive error ϵ, while quantum phase estimation uses O(log(1/ϵ)) samples at greater computational cost.

4. Variational quantum eigensolver for excited states

Variational quantum eigensolver methods have been extended to target excited states by penalizing known lower states, optimizing multiple orthogonal inputs, or expanding a low-energy subspace. These approaches enable spectral estimation on quantum processors but introduce additional optimization and measurement requirements.

  • Finding excited states and Hamiltonian spectra is important in quantum chemistry and many-body physics.
  • The folded-spectrum method minimizes C(θ) = ⟨(H −λ)^2⟩U(θ) to target the eigenstate nearest an approximate energy λ.It requires approximate knowledge of the desired excited-state energy and estimation of ⟨H^2⟩.
  • Orthogonally constrained VQE adds projectors onto previously found states, so the ground state of the modified Hamiltonian yields the next excited state.The projector overlap can be measured with a SWAP test, inverse circuits, or randomized measurements.
  • Subspace expansion and real-time-evolution bases provide alternative routes to excited states by solving generalized eigenvalue problems.These methods have been demonstrated for small molecules and extended with adaptive circuit construction and imaginary-time evolution.
  • Weighted SSVQE minimizes energy over k mutually orthogonal inputs and can obtain all k eigenstates in one optimization routine.Increasing the number of optimized states makes the optimization landscape and minimization effort more complex.
  • Recent experiments have determined molecular and many-body Hamiltonian spectra with superconducting processors by Fourier transforming observable dynamics.The procedure prepares a Fock state overlapping the eigenstates whose eigenvalues are sought.

7. Simulating open quantum systems

NISQ methods simulate open-system dynamics using quantum trajectories, ancillas, variational states, or hybrid density matrices. Their practical limits include growing qubit and circuit resources, feedback and trainability problems, difficult measurements, and unresolved quantum advantage for complex nonequilibrium systems.

  • Open-system dynamics can be recovered by sampling pure-state trajectories evolved with a non-Hermitian Hamiltonian and random quantum jumps.
  • Ancilla-based NISQ simulation implements unitary dynamics with Suzuki-Trotter decomposition and non-unitary dynamics through ancilla entanglement and measurement.
  • Superconducting hardware requires a new set of ancilla qubits at every timestep, causing linear qubit growth, while circuit depth generally scales polynomially with simulation time.
  • Variational quantum simulation extends to quantum jumps and mixed-state Lindblad dynamics, but inherits feedback-loop, trainability, and controlled-unitary requirements.
  • GQAS replaces a density matrix with a hybrid density matrix whose coefficients are stored classically while quantum registers represent the associated states.Validity requires normalization Tr(βE) = 1 and positive semidefiniteness.
  • GQAS measures overlap matrices on the quantum computer and lets the classical computer simulate the dynamics without a quantum-classical feedback loop.The absence of feedback can substantially speed computation on currently available quantum computers.
  • A variational steady-state approach minimizes ⟨0|⊗2N U†(θ)L†LU(θ)|0⟩⊗2N, but direct expectation-value measurement is difficult and requires an additional transformation.
  • For nonequilibrium Green’s functions, existing hybrid proposals assume noninteracting composite particles, and quantum advantage for highly complex steady-state setups remains unestablished.

13. Quantum computer-aided design

Quantum computer-aided design uses quantum processors to simulate photonic and superconducting hardware, addressing device-design problems that can exceed classical simulation resources. The paradigm aims to improve performance prediction and reduce experimental testing cycles.

  • Quantum computer-aided design simulates quantum hardware on quantum computers when classical simulation of hardware properties becomes intractable.The proposals target improved device-performance prediction and reduced experimental testing cycles.
  • Optical path modes are mapped to qubits and quantum optical elements to digital circuits, enabling flexible simulation of photonic setups.The framework simulates Boson sampling and optimizes a setup for preparing a high-dimensional multipartite entangled state.
  • Superconducting circuit modules with coupled transmon qubits are represented by Hamiltonians in multi-level operators and mapped to data qubits.A multi-level VQE extension is used to determine the spectrum of the superconducting hardware.
  • The review focuses its QML discussion on algorithms processing data quantum-mechanically that can run on NISQ computers.
  • Variational quantum classifiers can encode data into Hilbert space and train circuit parameters to separate classes, often using target states and single-qubit measurements.Using one qubit for training reduces objective-function estimation to measuring that qubit’s probability distribution.
  • A ten-qubit quantum Boltzmann machine learned mixtures of randomly generated Bernoulli distributions more effectively than a classical Boltzmann machine in generative applications.
  • Quantum Circuit Born Machines suit current NISQ hardware, serve as benchmarks, and have been applied to image and financial-data generation.They can potentially outperform classical computers by sampling distributions that are difficult for classical computers.

C. Combinatorial optimization

NISQ approaches encode combinatorial optimization objectives as Hamiltonian ground-state problems and use QAOA-based methods to seek approximate solutions. Results vary by problem and depth: p=1 QAOA can outperform quantum annealing on specific instances, but does not generally beat classical Max-Cut methods.

  • Combinatorial optimization seeks an optimal object from a finite set and includes problems such as traveling salesman, scheduling, Max-Cut, and Boolean satisfiability.
  • QAOA maps an optimization objective into a problem Hamiltonian and searches for a bit-string whose approximation ratio meets a desired target.The ratio is defined as r* ≤ C(z)/Cmax.
  • Max-Cut: 0.692 is the p = 1 QAOA approximation ratio for unweighted 3-regular graphs, below the best classical ratio of 0.9326.
  • Other applications: QAOA parameters optimized for one typical clustering instance can transfer to other instances when the objective value concentrates.
  • Max-Cut: Recursive QAOA repeatedly fixes maximally correlated qubit pairs as constraints, reducing the problem until the remaining instance is classically easy.
  • Max-Cut: For p = 1, QAOA can solve specific problems perfectly while quantum annealing struggles to find the solution.The cited comparison reports unit probability for QAOA on those instances.

2. Other combinatorial optimization problems

The review surveys NISQ algorithms for factoring, matrix decomposition, linear systems, and related numerical tasks. These methods map problems to variational or Hamiltonian formulations, with demonstrations including factoring simulations and classically tractable linear systems.

  • Factoring: Factoring is classically hard and beyond current NISQ resources at cryptographic sizes, motivating near-term algorithms based on Hamiltonian ground-state search.A 2048-bit RSA instance is estimated to require 10^5 logical qubits and circuit depth on the order of 10^9.
  • Factoring: Variational quantum factoring uses QAOA to find the ground state of a 4-local Ising factoring Hamiltonian.The Hamiltonian is constructed from binary multiplication constraints and carry bits.
  • Singular value decomposition: NISQ SVD algorithms variationally determine singular values and vectors, with proof-of-principle image compression and proposed recommendation-system applications.
  • Linear system problem: 2300 × 2300 linear systems were solved to ϵ-suboptimality using a measurement-based variational approach, including cases that remain classically tractable.
  • Linear system problem: For linear systems, runtime depends on matrix size, sparsity, condition number κ, and additive error ϵ; HHL has stated complexity O(log(N)s^2κ^2/ϵ).

4. Non-linear differential equations

The review extends NISQ applications beyond optimization and numerical linear algebra to nonlinear equations, foundational tests, control, metrology, fidelity estimation, and lattice field theory. These proposals use hybrid or variational procedures, with demonstrations at modest system sizes and application-specific settings.

  • Non-linear differential equations: Nonlinear differential equations cannot generally be reduced to linear systems when nonlinearities are large, motivating dedicated NISQ simulation methods.
  • Non-linear differential equations: NLQAS simulates the nonlinear Schrödinger equation without controlled unitaries, while other proposals use ancillary registers or address fluid dynamics.NLQAS was demonstrated for an 8-qubit system.
  • Foundations: The variational consistent history algorithm uses a quantum computer to compute the decoherence functional and a classical computer to tune history parameters.
  • Quantum optimal control: NISQ quantum control frameworks optimize controls against a cost function, including approaches intended to reduce the resource-scaling difficulties of classical methods.
  • Fidelity estimation: Variational quantum fidelity estimation bounds fidelity efficiently for low-rank states through variational diagonalization, eigenbasis matrix elements, and final fidelity estimation.The bounds improve monotonically with truncation rank and become exact at the full rank.
  • Nuclear physics: A VQA approach proposes reducing lattice-QFT computational cost by computing optimized interpolating operators for quantum-field states.

B. Quantum volume

Quantum volume benchmarks the largest square random circuit a NISQ device can implement successfully, complementing gate-level metrics with an architecture-agnostic performance measure. Its usefulness is limited by classical simulation requirements, while application benchmarks target structured circuits more directly.

  • Quantum volume: Quantum volume is the largest square random-circuit width and depth for which heavy-output probability exceeds 2/3.
  • Model circuit: Each quantum-volume layer randomly permutes qubit labels and applies Haar-random two-qubit unitaries, leaving one qubit idle when the width is odd.
  • Heavy-output generation: Heavy outputs have probabilities above the median, and the benchmark seeks samples with at least 2/3 heavy outputs; ideal and fully depolarized devices approach approximately 0.85 and 0.5, respectively.
  • Limitations: Quantum-volume evaluation is not scalable because it requires classical simulation of the model circuit's heavy-output-generation problem.
  • Reported values: At the time of writing, Honeywell H1 achieved log2 VQ = 9, while IBM Montreal demonstrated log2 VQ = 6.
  • Application benchmarks: Hardware benchmarks may not predict structured VQA performance, so application benchmarks compare device outputs with exact classical results for specific tasks.Examples include VQE experiments and effective fermionic length.

A. NISQ ALGORITHMS AND TOOLS TABLES

The review organizes NISQ algorithms across application domains and surveys the optimization methods used to train parameterized quantum circuits. It also describes gradient, gradient-free, curvature-based, and measurement-efficient strategies, along with their reported advantages and limitations.

  • Application tables: The review catalogs NISQ algorithms for many-body physics, chemistry, machine learning, combinatorial optimization, numerical solvers, finance, and other applications.The application tables span Tables I–VI.
  • Software tools: The review lists open-source quantum software libraries and external libraries for programming, simulation, chemistry, machine learning, circuit compilation, and quantum control.Software packages may target real hardware, translate across libraries or simulators, or integrate external functionality.
  • Optimization methods: VQA parameter optimization is supported by finite differences, parameter-shift gradients, quasi-Newton methods, heuristic initialization, quantum natural gradients, and evolutionary strategies.These methods estimate gradients, adapt updates to parameter-space geometry, approximate curvature, or reduce optimization overhead.
  • Optimization methods: Finite differences trade approximation accuracy against measurement cost because smaller ϵ require more quantum-hardware samples.The numerator difference becomes smaller as ϵ decreases, increasing sampling demands.
  • Optimization methods: The quantum natural gradient and Hessian-based methods improve escape from flat parameter-landscape regions, while the Hessian-based method requires fewer training epochs than QNG in simulations.Both methods leverage local curvature information, although the text notes that deeper comparison is needed.
  • Optimization methods: Doubly stochastic gradients drastically reduce measurements by evaluating only a subset of Hamiltonian expectation values, potentially as little as one Pauli term per quadrature point.The method uses finite measurements for only a subset of Hamiltonian terms.

C. Resource-aware optimizers

VQA optimizers increasingly account for quantum-resource costs rather than treating optimization as a general-purpose black-box task. Shot-frugal and noise-aware strategies reduce measurement demands and can improve noisy VQE optimization.

  • Resource-aware optimization: Early VQA optimizers were largely general-purpose and black-box, with little emphasis on reducing quantum resources.These methods were described as more costly and error-prone than their classical counterparts.
  • Shot-frugal optimization: ROSALIN addresses the prohibitive shot requirements for estimating expectation values used to compute VQA objectives.It distributes measurements through weighted random sampling and uses iCANS to allocate shots for partial derivatives.
  • Shot-frugal optimization: ROSALIN was shown through VQE optimizations to outperform iCANS and Adam, especially in the presence of noise.Its gain depends on the learning rate, the cost function’s Lipschitz constant, and estimates of gradient components and variances.
  • Noise-aware optimization: SPSA reduces gradient-estimation cost by using two function evaluations instead of the O(p) evaluations required by finite differences for p parameters.Its hyperparameters are determined from experimental statistical-noise levels, and convergence has been studied for various PQCs.
Loading 2101.08448v2…