Hybrid quantum-classical algorithms in the noisy intermediate-scale quantum era and beyond

I. INTRODUCTION

• The need for algorithms suited to NISQ hardware followed the emergence of experimental platforms limited in computation size and quality.The perspective includes gate-model devices as well as analog optimization, simulation, and machine learning through quantum annealing.Source: §I · p. 1
• VQAs pair short-depth parameterized quantum circuits with a classical variational loop, and experimental demonstrations have applied NISQ devices to chemistry, machine learning, and combinatorial optimization.VQAs were introduced with the variational quantum eigensolver (VQE).Source: §I · p. 1
• The perspective examines hybrid algorithms broadly, beyond variational algorithms and hybrid quantum annealing, and develops both a definition and a view of their place in computing.It also considers how these algorithms emerged and how they may be run on hardware.Source: §I · p. 2
• The authors argue that hybrid algorithms are likely to persist beyond the NISQ era, with quantum processors playing a role like specialized classical accelerators.They see no clear advantage in algorithms being purely quantum.Source: §I · p. 2

II. WHAT IT MEANS TO BE HYBRID

• Hybrid algorithms require non-trivial quantum and classical resources and cannot be sensibly described, even abstractly, without reference to the classical computation.The paper distinguishes this from classical processing that merely supports a quantum algorithm’s implementation.Source: §II · pp. 2–3
• QEC decoding can demand substantial classical resources, but its classical strategy depends on device architecture rather than the quantum algorithm, so QEC alone does not make an algorithm hybrid.In the paper’s account, classical processing diagnoses errors and determines operations that return the state to the logical subspace.Source: §II · pp. 2–3

A. Grover’s algorithm

• Grover’s search assumes coherent access to an oracle that checks whether a label is marked.Labels are mapped to computational basis states in a Hilbert space of size N.Source: A. Grover’s algorithm · p. 4
• For M ≪ N, Grover’s algorithm finds a marked state with probability quickly approaching unity, giving a quadratic speedup over classical search.The problem is to find any of M marked labels among N labels using an oracle that checks whether a label is marked.Source: A. Grover’s algorithm · p. 4
• Checking an output with the oracle and repeating the algorithm until a marked state is confirmed preserves the quadratic speedup and is too trivial to make the algorithm meaningfully hybrid.The paper treats this as ordinary classical control rather than an integral classical component of the computational model.Source: A. Grover’s algorithm · p. 4

B. Shor’s algorithm

• Shor’s polynomial-time factoring algorithm is widely regarded as the first useful quantum algorithm to achieve a speedup over purely classical methods.It factors products of two large prime numbers, a task described as thought impossible classically.Source: B. Shor’s algorithm · p. 4
• The algorithm reduces factoring to finding the period of modular exponentiation, then uses quantum phase estimation to produce a value for classical continued-fraction analysis.Classical checks validate candidate periods and compute the final factors.Source: B. Shor’s algorithm · pp. 4–5
• Shor’s algorithm is hybrid: classical greatest-common-divisor and continued-fraction steps surround the quantum phase-estimation call that provides its speedup.The classical processing transforms the factoring problem into a form the quantum processor can handle efficiently and makes its output useful.Source: B. Shor’s algorithm · pp. 4–5

III. ALGORITHM EXAMPLES

• Quantum annealing uses continuous-time quantum dynamics and quantum fluctuations to search an optimization problem’s solution space.Its development includes adiabatic quantum computing, which uses the adiabatic theorem to guarantee a solution if run long enough [44].Source: A. Quantum Annealing and… · p. 5
• Adiabatic quantum computing can match gate-model Grover speedup on unstructured search, and quantum annealing can in some cases outperform classical annealing [45, 46].Source: A. Quantum Annealing and… · p. 5
• A typical quantum-annealing protocol evolves a transverse-field Ising Hamiltonian toward a problem Hamiltonian whose lower-energy states represent better solutions.The transverse-field driver induces quantum fluctuations that play a role qualitatively similar to temperature in simulated annealing.Source: A. Quantum Annealing and… · p. 5

1. Hybrid forms of quantum annealing

• Reverse annealing begins from a heuristic guess, turns the transverse-field driver on and off, and aims to transfer amplitude to the problem Hamiltonian’s ground state.A classical loop can feed each measured output into the next run as a new initial state, a scheme called iterated reverse annealing.Source: §1 · p. 6
• Numerical and experimental work found that biased-driver annealing can improve performance, but technical limitations required incorporating the bias into the problem Hamiltonian experimentally [34] [54].The reported energy-redistribution conditions apply to biased-driver protocols but not reverse annealing.Source: §1 · p. 6
• Reverse annealing and biased-driver annealing make algorithms hybrid by incorporating classical prior knowledge of a solution into the protocol.Biased-driver protocols also use the guess state as the biased driver’s ground state [31–34].Source: §1 · p. 6
• Reverse annealing can use a good guess to search locally: moderate fluctuations avoided a broad false minimum and found a narrower true minimum in an experimental demonstration.By contrast, the figure caption reports that traditional forward annealing did not solve the engineered problem.Source: §1 · p. 7, Figure 3 · p. 8
• Reverse annealing served as the mutation operator in a quantum-assisted genetic algorithm, with classical population initialization, recombination, and selection [37].Source: §1 · p. 7
• Reverse annealing also enabled quantum-annealer simulations of geometrically frustrated spin systems by initializing the system in a previously found configuration.One study reported potential evidence of a scaling advantage over classical path-integral quantum Monte Carlo.Source: §1 · p. 7
• Reverse-annealing results vary by setting: coherent variants performed better for highly symmetric problems, while open-system effects enhanced iterated reverse annealing but could harm adiabatic annealing [69].The analysis of phase-transition mitigation assumes a coherent rather than dissipative setting.Source: §1 · pp. 7–8
• Other hybrid approaches use classical variational loops or machine learning to optimize annealing schedules and counter-diabatic terms [71] [75].Tree-search algorithms and neural networks have been used to learn schedules that appear to have the effect of counter-diabatic driving and transfer between instances.Source: §1 · p. 8

1. Variational Quantum Eigensolver

• NISQ-era VQE places much of the computation on classical hardware and calls the quantum processor for small subproblems suited to it.Source: §1 · pp. 8–9
• VQE uses a parameterized quantum circuit to prepare states, estimates their Hamiltonian expectation value by repeated measurements, and classically minimizes that value to approximate a ground state.The variational principle bounds the ground-state energy, with equality when the prepared state is a ground state.Source: §1 · p. 9

2. Quantum Approximate Optimization Algorithm

• QAOA is a combinatorial-optimization algorithm whose common form is a VQE-style variational algorithm with an ansatz inspired by quantum annealing.Its problem Hamiltonian encodes the optimization cost, while the driver or mixer Hamiltonian induces transitions between basis states.Source: §2 · p. 9
• QAOA typically uses a small number of layers because large p requires deep circuits that quickly become impractical, especially in the NISQ era.At small p, its 2p parameters can be optimized in a classical variational loop.Source: §2 · p. 10

• An ansatz that is too simple may exclude relevant states, while adding parameters increases circuit depth and NISQ noise, limiting solution quality.Source: §3 · p. 10
• Domain-specific ansatze can suit a problem but require deep native-gate circuits, whereas hardware-efficient ansatze are easier to implement but can produce barren plateaus.Barren plateaus are regions of vanishing gradients that make classical optimization harder.Source: §3 · p. 10
• Excessive ansatz expressivity can create barren plateaus, producing tension between representing the desired solution and keeping the circuit trainable.Circuit noise can also lead to barren plateaus, and they may impede gradient-free optimization as well.Source: §3 · p. 10
• Correlating circuit parameters can reduce the search space and produce larger gradients, while problem-inspired ansatze or starting conditions may help trainability.For encoding non-binary information, domain-wall encoding is qubit-efficient for general annealing interactions, but gate-model encoding tradeoffs remain an active research area.Source: §3 · p. 10

• QAE estimates the probability a of measuring a good state, and the original algorithm achieves a quadratic speedup over classical sampling in required calls.Source: C. Quantum Amplitude Estimation · p. 11
• QAE applies Grover-like iterations in varying counts to amplify the amplitude by different amounts, then uses observed good-state outcomes to infer it.The original QAE uses phase estimation, while newer algorithms use classical post-processing instead.Source: C. Quantum Amplitude Estimation · p. 11
• Maximum-Likelihood QAE runs Grover-type circuits at several iteration counts, records good and bad outcomes, and classically maximizes their joint likelihood to estimate the amplitude.Source: C. Quantum Amplitude Estimation · p. 11
• Larger Grover iteration counts yield sharper likelihood peaks, and maximizing the combined likelihood can give an accurate amplitude estimate; MLQAE can achieve the quadratic speedup for suitable iteration sequences.Variants also address limited circuit depth and noise.Source: C. Quantum Amplitude Estimation · p. 12, Figure 5 · p. 12

• VQE can find ground or other eigenstates of a chemical-system Hamiltonian, from which properties such as Green’s functions or chemical properties can be calculated.Source: D. Quantum subroutines within quantum… · p. 12
• For larger correlated-materials simulations, one proposal treats a small active space with VQE and its environment less accurately using density functional theory.Source: D. Quantum subroutines within quantum… · p. 12
• Classical quantum Monte Carlo methods face a fermionic sign problem that can make accurate sampling computationally infeasible below certain temperatures, while their existing classical wrappers make them natural candidates for hybrid algorithms.Source: D. Quantum subroutines within quantum… · p. 12
• In the DMFT workflow, an impurity interacts with a non-interacting bath, and bath parameters are iteratively updated until Green’s functions converge before an outer loop improves the DFT solution.Source: D. Quantum subroutines within quantum… · p. 13
• Bauer et al. propose replacing the impurity Green’s-function calculation with a quantum subroutine using adiabatic state preparation and quantum phase estimation to prepare a ground state for measurement.The figure shows the outer DFT loop and the impurity calculation as the swappable component, which can also be done classically.Source: D. Quantum subroutines within quantum… · p. 13, Figure 6 · p. 13

A. Larger computations on smaller hardware - Entanglement forging

• Entanglement forging partitions a 2N-qubit system into two N-qubit halves and expresses its density operator using a Schmidt decomposition.Local unitaries act on each half, and the Schmidt coefficients are VQE variational parameters; expectation values are sampled in a weighted way using products of those coefficients.Source: A. Larger computations on smaller… · p. 14
• High-accuracy water-molecule ground-state energies were found using a ten-qubit mapping on five superconducting qubits in real hardware.The work used entanglement forging along with heuristic enhancements.Source: A. Larger computations on smaller… · p. 14
• The approach is not expected to scale well generally, but weak entanglement across the split can leave only a few dominant Schmidt coefficients and make approximation manageable.Expectation values can then be approximated with a manageable number of samples.Source: A. Larger computations on smaller… · p. 14

B. Additional controls

• Additional controls in analog processors can enable richer hybrid techniques with experimental gains, including reverse annealing protocols already available inside devices but not exposed to external users.The authors urge considering how existing experimental techniques might serve computational purposes different from their original ones.Source: B. Additional controls · p. 14

C. Co-locating the quantum and classical computing power

• Communication between classical and quantum components is not free, and internet signal latency could become a major barrier; some applications may need still faster communication.The authors note co-location efforts at Jülich and suggest cryogenic classical computation could benefit superconducting-qubit systems.Source: C. Co-locating the quantum and… · p. 14

V. THE BIG PICTURE: SPECIALIZED ACCELERATORS

• Classical heterogeneous systems pair general-purpose CPUs with specialized processors, such as GPUs for parallel numerical operations or ASICs for faster, more energy-efficient specific tasks.The paper presents quantum processors as fitting this pattern: a CPU can call a QPU for specialized subroutines, including phase estimation or VQE ansatz preparation.Source: §V · p. 15

VI. THE FUTURE OF HYBRID ALGORITHMS

• Hybrid algorithms have emerged through varied routes: some adapt pure quantum algorithms, some replace classical methods with quantum calls, and others respond to hardware capabilities.The paper gives QAE, Shor’s algorithm, hybrid materials and chemistry algorithms, and variational or annealing methods as examples.Source: §VI · p. 15
• The authors consider hybrid algorithms likely to persist into useful, potentially fault-tolerant quantum computing, because quantum processors may not outperform classical bits on every metric and hybrid components may further improve production systems.They compare this trajectory with classical co-processors augmenting rather than displacing older paradigms.Source: §VI · p. 16
• Whether an algorithm is hybrid depends more on how classical computation fits its overall model than on how much classical computing power it uses.The paper notes that some algorithms can be classified as both hybrid and non-hybrid.Source: §VI · p. 16