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

Hybrid quantum-classical algorithms are central to much of the current research in quantum computing, particularly when considering the noisy intermediate-scale quantum (NISQ) era, with a number of experimental demonstrations having already been performed. In this perspective, we discuss in a very broad sense what it means for an algorithm to be hybrid quantum-classical. We first explore this concept very directly, by building a definition based on previous work in abstraction/representation theory, arguing that what makes an algorithm hybrid is not directly how it is run (or how many classical resources it consumes), but whether classical components are crucial to an underlying model of the computation. We then take a broader view of this question, reviewing a number of hybrid algorithms and discussing what makes them hybrid, as well as the history of how they emerged, and considerations related to hardware. This leads into a natural discussion of what the future holds for these algorithms. To answer this question, we turn to the use of specialized processors in classical computing.The classical trend is not for new technology to completely replace the old, but to augment it. We argue that the evolution of quantum computing is unlikely to be different: hybrid algorithms are likely here to stay well past the NISQ era and even into full fault-tolerance, with the quantum processors augmenting the already powerful classical processors which exist by performing specialized tasks.


I. INTRODUCTION
The first proposals for the creation of computing resources based on the principles of quantum mechanics emerged in the 1980s [1][2][3]. This led quickly to the discovery, throughout the 1990s, of a number of quantum algorithms for toy problems designed to show a complexity theoretic separation between quantum and classical computation [4][5][6]. In the mid-to-late 1990s, however, Peter Shor developed the polynomial-time quantum algorithm for factoring products of large prime numbers, [7,8] now widely-regarded as the first useful quantum algorithm that achieves a speedup over purely classical counterparts.
The explosion of interest in quantum computing that resulted from Shor's work is partly responsible for the rapid development thereafter of early experimental quantum hardware that could run small, noisy instances of quantum algorithms (see [9][10][11][12][13][14][15][16][17][18][19][20][21][22] among others). However, as these experimental platforms with severe limits on computation size and quality emerged, it quickly became apparent that for quantum computers to be useful in the nearand mid-term, the community needed to find algorithms tailored to this era of quantum computing * a.callison@ucl.ac.uk † nicholas.chancellor@gmail.com (later termed the "noisy intermediate-scale quantum" (NISQ) era [23]). This includes not only algorithms run on gate model quantum devices, but also analog optimization, simulation, and machine learning through quantum annealing [24].
Perhaps the most influential development in the field of gate-model NISQ-suitable quantum algorithms is the framework of variational quantum algorithms (VQAs) that was introduced with the variational quantum eigensolver (VQE) [25]. These algorithms make use of short-depth parametrized quantum circuits, particularly suited to NISQ hardware, embedded in an otherwise classical variational loop, a structure that is manifestly hybrid quantumclassical. While some of the other quantum algorithms discovered previously are also hybrid, VQAs offered a clear demonstration on the potential computing power available by coupling quantum and classical resources together. Thus, due to VQAs, hybrid quantum-classical algorithms have been an integral part of quantum algorithms research ever since, including through experimental demonstrations of applying NISQ devices to problems in quantum chemistry [25][26][27], machine learning [28,29], and combinatorial optimization [30].
Separately from VQAs, the key advance which has allowed for hybrid techniques in analog quantum computing is the notion of biased search [31][32][33][34], a family of techniques that allow the system to be called as a subroutine within a broader algorithm, aided by previously results [33,35]. These can be arXiv:2207.06850v1 [quant-ph] 14 Jul 2022 used in simple ways such as biasing toward a previously found good solution from a classical greedy search [36], or in more complicated ways such as in genetic algorithms [37].
In this perspective, we take a broad view of hybrid quantum-classical algorithms, going beyond variational algorithms and hybrid quantum annealing. We discuss what it means to be a hybrid algorithm, in the broadest sense of being necessarily a combination of quantum and classical computation. We explore this question both in the literal sense of developing a definition and in the more abstract sense of where these algorithms sit within the space of quantum computing and more broadly computing in general.
First, we propose that defining hybrid algorithms should be done in terms, not of the computation itself, but of the abstract model of the computation, and whether or not that model requires significant classical computation (computation which does not need a quantum hardware to be performed). We further examine how hybrid algorithms are developed and find that there are many paths, and that this development can be driven by any number of factors, including the capabilities and limitations of the hardware, the discovery of issues with "pure" quantum algorithms, and the identification of bottlenecks in current classical methods.
Furthermore, we consider the long and successful history of specialized processors being used within classical computing and note that, while quantum computers can be very powerful and greatly enhance computational capabilities, it is likely that they will play a role similar to many of these other accelerators. Finally, looking to the future, we see no clear advantage in algorithms being "purely" quantum, and therefore argue that hybrid algorithms are likely here to stay, rather than just an artifact of the NISQ era.
We start in section II by discussing how a useful definition can be constructed, and how to make the distinction between pure and hybrid quantum algorithms meaningful. Within this discussion, we reference two of the most iconic quantum algorithms: Shor's algorithm, which we argue is in fact hybrid, and Grover's algorithm, which we argue is not. In section III, we discuss examples of hybrid quantumclassical algorithms and how they fit into the definition. Next, in section IV we examine the considerations that must be made when thinking of how hybrid algorithms will be run on real hardware. We then, in section V, examine the bigger picture; in particular, how classical computation makes use of heterogeneous hardware arrangements as specialized accelerators and argue that quantum processors are likely to follow as similar path. Finally, in section VI, we conclude by discussing the future of hybrid algorithms.

II. WHAT IT MEANS TO BE HYBRID
To begin a meaningful discussion of hybrid quantum-classical algorithms, it is first necessary to establish an understanding of what it means for a quantum algorithm to be considered a hybrid algorithm and what makes hybrid algorithms different from other quantum algorithms. For this task, it is essential to develop a working definition of the term "hybrid" in this context. An agreed upon, meaningful and useful definition can help facilitate communication and allow a useful grouping of similar algorithms. It is tempting to argue that simple techniques such as "repeat until success" play an important role in almost all quantum algorithms, and therefore almost all quantum algorithms should be considered hybrid. While potentially a valid viewpoint, this approach does not lead to a useful definition: if everything is hybrid, then the term "hybrid quantum algorithm" has little meaning.
Rather than considering to be hybrid any quantum algorithm for which the implementation is supported by classical computing, it seems that the salient feature connecting hybrid quantum-classical algorithms is that the use of classical processing is fundamentally inseparable from the computational model. While we will discuss later in this section what exactly this term means, for now it suffices to think of this as the basic theoretical description of how a system solves problems. As a starting point, therefore, we propose the following definition of a hybrid quantum-classical algorithm: Definition. An algorithm that requires non-trivial amounts of both quantum and classical computational resources to run, and which cannot be sensibly described, even abstractly, without reference to the classical computation.
While the term "non-trivial" in this context is open to interpretation, a sensible interpretation is that the classical computation should go beyond simple repetition and conditioning on measurement outcomes.
Quantum error correction [38] (QEC) provides a simple example of classical computers supporting quantum algorithms, but in which the classical computation is not fundamentally tied into the computational model. In devices with QEC, the quantum computation occurs only on a small part of the device's Hilbert space, known as the logical subspace. The logical subspace is chosen such that almost all physical errors will take the system out of this subspace; that is, errors within the subspace are unlikely. Well-chosen measurements than can be performed to detect whether the state has left the logical subspace without destroying the quantum information (more correctly, the error will lead to a superposition over the logical subspace and the error subspaces, but the measurement will force the state to collapse onto one of the subspace, a mechanism referred to as error digitization). Classical analysis on these measurement outcomes can then be used to diagnose the error and to determine the quantum operations required to rotate the state back into the logical subspace, in a mechanism known as decoding. The high-level structure of typical QEC strategies is shown in Fig. 1, and a thorough review can be found in [38].
Decoding of quantum error correction can be very intensive in terms of classical computing resources [39]; however, the fundamental model of (noise-free) gate-model quantum computing does not depend on how the errors are corrected. Similarly, the classical strategy for decoding does not depend on exactly what quantum algorithm is running, only on the device architecture. We would therefore argue that the fact that classical computing resources are required to protect a fault tolerant quantum algorithm does not in itself make the algorithm hybrid. A fault tolerant algorithm can be hybrid in the sense that the quantum component of the algorithm can be run in a fault-tolerant way, but the fact that the algorithm relies on QEC does not in itself make it hybrid.
To approach the question of when a quantum computation is hybrid, it is useful to first look at work which has already been done in understanding when a physical system computes. The Abstraction-Representation theory [40] of computation was motivated by exactly this question [41]. The key distinction which abstraction representation theory draws between a physical system which is computing and one which is not is that a system undergoing computation has information encoded in it and a corresponding abstract model for the computation it is doing. In other words, computation is not about what a system is doing so much as what it is representing.
By abstraction-representation theory, a physical system needs to be paired with a (possibly imperfect) abstract model of the computation it is doing. For example, a gate-model quantum computer can be abstractly represented by a quantum circuit (possibly including random elements from noise), a coherent quantum annealer could be represented by the Schrödinger equation, and a dissipative quantum annealer by a master equation.
To understand whether a computation is hybrid High-level schematic of typical forms of QEC in which some classical processing is used to protect a quantum algorithm from errors.
or not, it is necessary to think in terms of what the role classical computation plays within this model. Returning to the example of QEC, the model for fault-tolerant quantum computing is already a (noise free) quantum circuit, and the classical computation is just performing a supporting role in ensuring that the model is accurate enough. For contrast, consider a variational algorithm; in this case the classical computation is directly involved within the computational model, it gives the updates for the gate parameters and fundamentally cannot be removed from the computational model.
To demonstrate the differences between pure quantum algorithms and hybrid quantum-classical algorithms, we now turn to two widely-known algorithms: Grover's algorithm for searching unsorted databases, and Shor's algorithm for integer factorization. In what follows, we argue that Grover's algorithm should not be considered meaningfully hybrid, while Shor's algorithm should. We discuss other example of hybrid algorithms in more detail in section III.

A. Grover's algorithm
Grover's algorithm [42] is a well-known quantum algorithm for solving the 'unstructured search' problem. For the purpose of this section we limit ourselves to "pure" implementations of Grover's algorithm, where the entire problem is phrased as an unstructured search; we discuss more sophisticated algorithms based on the same amplitude amplification principle as Grover's algorithm in section III C. Very simply, this is the problem of finding any of M marked labels among a set of N ≥ M of labels, given knowledge of the numbers M and N access to an oracle that is able to check whether a particular label j is marked. Many computational problems can be phrased as unstructured search, such as database search and some forms of constraintsatisfaction. Without access to additional structure among the labels, the only option for solving unstructured search classically is to repeatedly select labels, either randomly or in a particular order, which has a time complexity that scales as O N M . The labels j are mapped to computational basis states |j of a Hilbert space of size N , and we assume coherent access to the oracle; that is, it is possible to apply a unitary operator O check defined by It can be shown that by initialising the quantum computer in the uniform superposition state |s = a state is produced that can be measured in the computational basis to return a marked state with probability P marked (r) = sin 2 ((2r + 1)θ) where θ = M N . Thus, by choosing a marked state can be found with a probability that quickly approaches unity for M N . This represents a quadratic speedup over what is possible classically.
While single run of the algorithm does not guarantee a marked state with unit probability, the output can be checked via the oracle and the algorithm repeated a small number of times until a marked state is confirmed, without affecting the quadratic speedup. It would not be useful to consider a quantum algorithm with this trivial level of classical postprocessing to be hybrid, as it is difficult to imagine any useful quantum algorithms which did not contain at least these elements of classical control.

B. Shor's algorithm
Shor's polynomial-time algorithm [8] for factoring products N = p 1 p 2 of two large prime numbers p 1 and p 2 , a feat thought to be impossible classically, is regarded as the first useful quantum algorithm to have been invented. Given the risk a practical implementation of Shor's algorithm would have on much of modern computer security, it is perhaps the most high-profile quantum algorithm, and is seen as a quintessential example of the power of quantum computing.
However, Shor's algorithm is far from being a purely quantum algorithm, and should certainly be considered a hybrid algorithm. The algorithm relies on a polynomial-time reduction of the factoring problem to the problem of finding the order r of a periodic function, and is described in Algorithm 1. It can be seen that almost all of the steps are entirely classical, including the calculation of greatest common divisors via the classical Euclidean algorithm in steps 2 and 9 and the classical continued-fraction expansion in step 6. The only part of the algorithm that is quantum is the call to the quantum phase estimation circuit (see Fig. 2) in step 5, which forms the core of the order-finding subroutine.
Algorithm 1 Structure of Shor's algorithm 1: Randomly select a from 1 < a < N 2: Compute K = gcd(a, N ) classically, via Euclidean algorithm 3: If K = 1, K is a factor of N , so return a and exit.
Otherwise, continue to step 4. 4: Implement the a-dependent unitary Ua that acts as Ua |x n = |a x mod N . 5: Perform quantum phase estimation (QPE), via a circuit like the one shown in Fig. 2, with a q-qubit control register where N 2 < 2 q < 2N 2 , on Ua with the initial state of the target register set to |1 (the binary representation of 1), to produce an integer y.
6: Use classical continued-fraction expansion to produce an irreducible fraction approximation d r of y 2 q for which r < N and the approximation error is small (< 1 2 q+1 ). 7: If r is odd or it is true that a r 2 = −1 mod N , go back to step 1. Otherwise r is highly likely to be the period of the modular exponentiation with base a, f (x) = a x mod N , so continue to step 8. 8: If r is the period of the modular exponentiation (which can be checked classically), continue to step 9. Otherwise, go back to step 6, and find a different irreducible fraction with a different r. If out of candidates, go back to step 1. 9: Compute gcd(a r 2 − 1, N ) and gcd(a r 2 + 1, N ) classically, via the Euclidean algorithm. These are now guaranteed to be non-trivial factors of N , so return these and exit.
While it is absolutely true that the quantum part of Shor's algorithm provides the speedup over the best known purely classical methods, a significant (but polynomial) amount of classical processing is done before and after the call to the quantum subroutine in step 5 in order to transform the problem into a specific form that the quantum processor can handle efficiently. This classical processing includes calls to identifiable classical algorithms such as the Euclidean algorithm, In other words, what is being calculated by the quantum computer is not directly useful without the surrounding classical steps.
Having discussed two of the possibly most iconic quantum algorithms, in the next section we get into a more detailed discussion about other important examples of hybrid algorithms. This is not intended to be an exhaustive list, but to start a discussion on what it means to be hybrid under different contexts, and to provide examples that can help extend these to other algorithms.

A. Quantum Annealing and Continuous-Time Quantum Computing
Quantum annealing (QA) consists of using continuous-time dynamics of a quantum system to solve an optimization problem by searching the solution space through quantum fluctuations. QA as we know it today was proposed in the late 1990s by Kadawaki and Nishimori [24] (although a similar suggestion for chemistry related problems had been made earlier [43]). After the development of the basic principles of QA, Farhi et al. introduced the specific case of adiabatic quantum computing (AQC) [44] in which the adiabatic theorem of quantum mechanics guarantees a solution if the algorithm is run long enough. Roland and Cerf than showed that AQC can attain the same speedup as the gate model Grover's algorithm on unstructured search [45], while around the same time Santoro et al. further developed the theory of QA and showed that it can in some cases outperform classical annealing algorithms [46]. For a complete review of AQC, see [47], and for a more application-focused review of QA, see [48]. For a forward looking perspective on techniques which operate outside of the adiabatic limit see [49].
Since it's inception, QA has grown to encompass a variety of protocols, but the typical structure involves implementing a time-dependent transverse Ising model Hamiltonian where T is the total annealing time, A and B are monotonic control functions such A(0) B(0) and A(1) B(1), and the 'problem Hamiltonian' H P is of the form where the couplings J jk and fields h j define the problem of interest such that lower-energy eigenstates of H P correspond to better quality solutions. In this way, QA is qualitatively similar to its classical analog simulated annealing, but with the physical quantum fluctuations/tunneling induced by the transverse field 'driver' term − n j=1 X j playing the role of a simulated temperature. QA protocols typically start the system in the ground state of the transverse-field driver term, and aim to set the controls functions A and B such that the system is driven toward low energy states of the problem Hamiltonian.

Hybrid forms of quantum annealing
Much of the work on hybrid algorithms in continuous-time quantum computing has focused on protocols which allow an educated guess at the solution to be incorporated into the protocol.
The idea of incorporating a heuristic guess was first proposed by Perdomo-Ortiz et al. [31], in a scheme which has come to be known as (one variant of) reverse annealing. In this scheme, the standard QA Hamiltonian of Eq. (5) is replaced with where s is a schedule function that starts at s(0) = 0, ends at s(1) = 1 and monotonically increases in between. The hat function pre-multiplying the transverse field driver is a function that begins and ends at zero, but is positive in between, such as hat(s) = sin(πs); that is, the transverse field driver is turned on and then off during the anneal. The completely new ingredient is the initial Hamiltonian where g j is a sign such that g j = 1 (g j = −1) if the jth bit of the heuristic guess is 0 (1). The ground-state of the initial Hamiltonian H init is then the guess state, and the annealing protocol aims to transfer a non-trivial amount of the amplitude into the true ground-state of the problem Hamiltonian H P , with the transverse field turned up and then down in order to assist this transfer via quantum fluctuations. It is worth noting that, since the aim of a reverse annealing run is to improve upon a a previously known reasonable solution, it is possible to embed reverse annealing in a classical loop, whereby the output state measured one run is then incorporated as the initial state (with the appropriate initial Hamiltonian) for the next run. This hybrid structure was suggested in [31], and schemes of this sort have come to be known as iterated reverse annealing. Other protocols have been proposed that have also come to be known as reverse annealing. For example, Chancellor [33] and Yamashiro et. al [50] propose using the standard QA Hamiltonian of Eq. (5), but simply initializing to the guess state and using a schedule that begins entirely in the problem Hamiltonian  [51]. In [50], this two-term form of reverse annealing is embedded in a classical loop and is also called iterated reverse annealing (in fact, this is where the term was coined).
A third form of reverse annealing, proposed by Ohkuwa et. al [52], uses a Hamiltonian of the form where s(0), λ(0) = 0, s(1), λ(1) = 1, and both are monotonically increasing between. Recognising that the system begins in the instantaneous ground-state at t = 0 and is targeting the instantaneous groundstate at t = T , this protocol can in principle be run adiabatically, and has come to be known as adiabatic reverse annealing. This Hamiltonian in Eq. (9) is quite similar to that described by Eq. (7) (in principle, the Eq. (7) protocol could also be run adiabatically), but the additional freedom that arises from having two schedule functions, s and λ, offers additional flexibility for the annealing path. An independent proposal that incorporates a heuristic guess by using a biased driver Hamiltonian, instead of by reverse annealing, was given by Duan et al. [32] (later studies of this protocol can be found in [34] and to a lesser extent in [53]). An example of such a protocol is to modify the transverse-field driver term to include a bias towards a particular guess state; that is, where b j is a positive number representing the strength of the bias and g j = 1 (g j = −1) is the jth bit of the guess is 0 (1). The initial state should also be biased towards the guess state, such that it remains the ground-state of the biased driver. Graß [34] showed numerically that biasing both toward and away from solution candidates can improve performance of annealing protocols, and has also experimentally demonstrated that biased-driver QA can work in practice [54] (although technical limitations meant the bias had to be included as part of the problem Hamiltonian instead). Callison et al. [53] demonstrated that traditionally formulated QA is subject to an energy redistribution mechanism if certain conditions are met, and the conditions are met in the biased-driver protocols proposed of [32,34] (but not in the reverse annealing protocols).
Since both reverse QA and biased-driver QA fundamentally incorporate classical information, in the form of previous knowledge of the solution, into the protocol itself, any algorithm which makes use of them is necessarily hybrid. Many of the earlier papers focused on how closed system quantum annealing could incorporate prior knowledge, but later work explored how these ideas can be used in more sophisticated algorithms that use QA as a subroutine. An influential example is the work by Chancellor [33], in which it was proposed how a known experimental protocol (see: [55]) on a dissipative quantum annealer could be used within analogues of classical population annealing [56,57] and parallel tempering [58,59] algorithms. Furthermore, Chancellor [35] proposed a general formalism to understand annealing protocols that accept initial conditions, such as reverse anneals. Within a week of the first appearance of this paper on the arχiv pre-print repository, Neven independently proposed a QA-based parallel tempering algorithm in the AQC 2016 opening remarks [60]. After this, D-Wave Systems Inc. made the necessary controls to perform a reverse annealing protocol (and, in fact, coined the term "reverse annealing" [61]) using a similar method to the proposal in [33]. The D-Wave implementation of reverse annealing most closely resembles the two-term proposals of [33,50], except that it operates in the dissipative regime.
The capability to perform reverse annealing has lead to numerous experimental studies. Venturelli and Kondratyev [36] demonstrated that incorporating the result of a greedy search can improve the performance of a quantum annealer on a portfolio optimization problem. Ottaviani and Amendola [62] as well as Golden and O'Malley [63] demonstrated that reverse annealing can aid in matrix factorization. Chancellor [64] demonstrated how these techniques can be combined with other advanced controls to trade off between optimality and flexibility within solutions. Chancellor and Kendon [65] demonstrated that the underlying principle behind using reverse annealing for local search was correct and examined the effect of noise levels.
Data from an experimental demonstration of using reverse annealing for local searching, first presented in [65], are shown in Fig. 3. These experiments were performed by constructing an Ising system with known pathological behaviour for QA. This was achieved by creating a "broad" false minimum where strong quantum fluctuations were allowed. The system was than initialized near (in the sense of number of bitflips) a much "narrower" true minimum (see the cartoon inset of Fig. 3). The results demonstrate that searching the solution locally by starting from a 'good guess' and accessing only moderate fluctuations through reverse annealing) allowed the broad false minimum to be avoided, thereby validating reverse annealing as a tool for search solution spaces locally, a key ingredient for hybrid QA algorithms.
A clear demonstration of a hybrid quantumclassical algorithm employing reverse annealing as a quantum (although not fully-coherent) subroutine was provided by King et al. in [37]. In that work, reverse annealing is used as the mutation operator in an otherwise classical genetic algorithm. The algorithm is shown in Algorithm 2.
Algorithm 2 Quantum-Assisted genetic algorithm of [37] 1: classically initialize the population as N random states 2: FOR generation IN generations: with probability mutation rate, use quantum reverse annealing, starting from individual to create mutated individual 5: add mutated individual to population classically combine pair to create offspring 10: add offspring to population 11:

12:
exit loop if a stopping condition is met 13: discard old individuals from population to maintain desired size N 14: END FOR Perhaps most surprisingly, reverse annealing has aided not just optimization, but also quantum simulation using quantum annealers; in particular, demonstrations that quantum annealers can be used to simulate geometrically frustrated spin systems. The quantum simulations by King et al. [66,67] are only feasible through use of the reverse annealing feature to initialize the system in a previously found configuration. This is of particular interest since the work in [67] shows potential evidence of a scaling advantage over classical techniques based on path-integral quantum Monte Carlo.
There has also been significant numerical and theoretical work on understanding reverse annealing. Ohkuwa et al. [52] showed that reverse annealing techniques could mitigate or even remove a first order phase transition in highly symmetric problems, though the analysis assumes a coherent rather than dissipative setting. In a similar vein, Yamashiro et al. [50] showed that a more coherent version of reverse annealing works better than dissipative reverse annealing for solving highly symmetric problems, and discussed how protocols similar to those proposed here could be experimentally implemented with an existing feature on D-Wave devices. show that open quantum system effects can enhance the performance of iterated reverse annealing [68] (using a Hamiltonian of the form of Eq. (5) with a nonmonotonic schedule), but could be detrimental in the case of adiabatic quantum annealing [69] (using a Hamiltonian of the form of Eq. (9)). Overall, reverse annealing has been identified as a key technique to eventually realising a quantum advantage through annealing techniques, especially in settings where coherence is low. In fact, in a recent forward-looking perspective, Crosson and Lidar [49] only rank QA in a moderately decoherent setting as promising if reverse annealing techniques are used.
Moving away from strategies that incorporate prior knowledge into the anneal, there are a number of other approaches to hybridizing QA, many of which involve optimizing QA schedules to increase success probability without requiring the runtime to grow toward the adiabatic limit, and fall under the umbrella of shortcuts to adiabaticity [70]. For example, in [71], a parameterized counter-diabatic term is introduced to the Hamiltonian to mitigiate harmful aspects of the diabatic evolution, and its parameters are variationally-optimized in a classical loop, similar to variational algorithms in the gate model (see subsection III B). Related work is presented in [72,73] An alternative approach to hybridizing QA is to use classical machine-learning techniques to design annealing schedules for particular problems or problem types. For example, Chen et. al [74] show that a combination of tree-search algorithms and neural networks can be used to learn effective annealing schedules that appear to have the same effect as deliberately including counter-diabatic driving terms and which can be transferred between instances. A genetic algorithm is used for similar purposes by Hegde et. al in [75].

Variational Quantum Eigensolver
The NISQ era of quantum computing is characterized by devices with limited spatial (e.g number of qubits) and temporal (e.g achievable coherence time) resources. As such, near-term quantum algorithm design must focus on extracting as much performance as possible out of these limited resources. Hybrid algorithms offer a natural way to do this, by performing much of the computational effort on classical hardware and calling the quantum processor only for small subproblems to which it is particularly well-suited. A well-known and illustrative example is the Variational Quantum Eigensolver (VQE) [25], a class of algorithms intended for NISQ devices that combines small quantum circuits and classical optimization techniques to approximate eigenstates of a Hamiltonian H, typically ground-states, and associated eigenenergies. Comprehensive overviews of VQEs and related variational algorithms are available elsewhere [76,77], but we give a brief description here to illustrate a key example of a hybrid algorithm.
In VQE, a quantum processor is used to prepare a state where |Ψ init is an easily-prepared initial state. The unitary operator U (θ) is the action of a parameterized quantum circuit (PQC); that is, a circuit with a fixed form (a carefully chosen ansatz) but a dependence on a set of parameters θ. For Hamiltonians H which can be expressed as sums over polynomiallymany products of Pauli operators, the state |Ψ(θ) can be repeatedly prepared and measured O(1/ 2 ) times to efficiently estimate the expectation value E Ψ,H (θ) = Ψ(θ)|H|Ψ(θ) to some desired precision . The variational principle gives the inequality where E (H) 0 is the ground-state energy of the Hamiltonian H, and Eq. (12) becomes an equality only when |Ψ(θ) is a ground-state of the Hamiltonian H. Thus, if the ansatz U (θ) is sufficiently expressive, minimising the expectation value E Ψ,H (θ) over the parameters θ will yield a good approximation to the ground-state Ψ (H) 0 . The minimization can be performed by inserting the quantum processor into a feedback loop that incorporates a classical optimization algorithm; the original proposal [25] used the Nelder-Mead simplex method [78], but more recent work has used other optimization methods (see the reviews [79,80] for examples). Fig. 4 shows a schematic of the VQE algorithm.

Quantum Approximate Optimization Algorithm
The Quantum Approximate Optimization Algorithm (QAOA) is an algorithm for combinatorial optimization first proposed by [81] and which quickly inspired a number of others works developing the idea further [82][83][84][85][86][87]. While some forms of QAOA may be considered to be purely quantum algorithms [81], it is typically hybrid in form. In fact, QAOA in its most common form can be considered to be an example of a VQE algorithm applied to combinatorial optimization, with an ansatz inspired by QA (see subsection III A). The ansatz usually takes the form where p is the number of QAOA layers and α = (α 1 , . . . , α p ), β = (β 1 , . . . , β p ) are 2p variational parameters. The classical 'problem Hamiltonian' H P is a Hamiltonian into which, as in QA, a combinatorial optimization cost function has been mapped such that its eigenstates corresponds to candidate solutions and its eigenvalues correspond to their costs. The 'driver' or 'mixing' Hamiltonian H D is a Hamiltonian which induces transitions between basis states. As in QA, this is typically a simple single-body transverse field Hamiltonian H D = − n k=1 X k applied to the qubits, although this has been generalized [87] to include a much broader class of mixing Hamiltonians, in a similar algorithm known as the Quantum Alternating Operator Ansatz, sharing an acronym with the original algorithm. In a typical QAOA implementation the initial state |gs(H D ) is the ground-state of the mixer Hamiltonian H D .
The ansatz in Eq. (13) is inspired by the QA algorithm in the sense that the parameters α, β can be chosen such that the unitary that prepares the ansatz can be expressed as a Trotterization of a QA protocol; that is In practice, running a QAOA algorithm with a large number p of layers in order to approach the QA limit requires a large circuit depth that quickly becomes impractical, particularly in the NISQ era. Instead, QAOA algorithms are typically considered at a small number of layers, even sometimes p = 1 (e.g in [88]). For a small number of layers, there are a manageable number of parameters α, β which can be optimized in a classical variational loop as with other variational algorithms, as described in section III B 1. Other strategies for optimizing the parameters have also been considered, such as posing the optimization as a learning and task and employing reinforcement learning [89] to find good parameters that can even be transferred between problem instances of different sizes.

Difficulties with variational algorithms
The performance of a variational algorithm, including QAOA, will depend strictly on the choice of ansatz for the PQC U (θ). Most critically, if the ansatz is too simple, the set of accessible states {|Ψ(θ ) : ∀θ} may exclude a large portion of the physically-relevant state-space, meaning that it is not possible to achieve a good approximation to the target state Ψ . This can be avoided by increasing the number of independent parameters θ in the ansatz, but this comes at the cost of increased circuit depth, which for NISQ devices will lead to increased noise, again limiting the quality of achievable solutions.
In principle, matching the form of the ansatz to the problem under consideration can also improve VQE performance; for example, the unitary coupled cluster ansatz is known to be particular suitable for problems in quantum chemistry [25,90,91]. However, such domain-specific ansatze often require large circuit depths to implement in terms of gates native to quantum processors. An alternative approach is to employ "hardware-efficient ansatze", which are designed to be easy to implement on real hardware [25,92]. Unfortunately, the hardwareefficient approach has been observed to lead to "barren plateaus", regions of the optimization landscape with vanishing gradients, making the classical optimization much harder to perform. A useful discussion of ansatz design is available in [93].
An understanding is emerging that the origin of the barren plateaus relates to the expressivity of the ansatz, [94]. In particular, if an ansatz is too expressive then the broadness of the search of the space leads to barren plateaus since the majority of the solution space will consist of low quality solutions which are relatively unaffected by small changes. This leads to tension between having an ansatz which is expressive enough to accurately describe a desired solution, but not so expressive that it is no longer trainable. It has also been found that there is a distinct mechanism by which noise in the circuit can lead to barren plateaus [95]. The fact that barren plateaus cause gradients to vanish begs the question whether they will be problematic if optimization of parameters is performed with a gradient free method, unfortunately, recent work suggests that they are still an impediment [96]. While barren plateaus are a significant obstacle to variational algorithms, the situation is far from hopeless, and there are strategies which have shown some success. For example, it has been demonstrated in [97] that reducing the size of the search space by correlating circuit parameters can lead to large gradients (therefore destroying the plateaus). While many error mitigation strategies do not improve the trainability of noisy variational algorithms, some can [98]. Furthermore, progress may be made by choosing ansatze or starting conditions which are inspired by the problem being solved. For example, it is known that QAOA can describe digitized QA, and indeed optimal QAOA protocols have been found to be very similar (but not identical) to digitized annealing [99,100] and sophisticated mathematical tools have been developed to understand when an ansatze will and will not be trainable due to barren plateaus [101].
A related, but distinct question is how to encode information which is not naturally binary into a quantum computer. In particular this raises the question of binary encodings, where bitstrings are used directly to represent configurations, or encoding individual variables using unary (qubits required scale linearly with the number of configurations) encodings. In the case of annealing, the inability to efficiently engineer higher order terms means that it can be shown mathematically that a kind of unary encoding (domain-wall) is the most efficient method in terms of qubit usage for completely general interactions [102]. However, for gate model approaches, the tradeoff is far more complicated and encoding strategies remains an area of active research [103][104][105][106] with many open questions. For example, to the best of our knowledge only Plewa et. al. [106] have performed simulations to test the domain-wall encoding in a gate model setting.

C. Quantum Amplitude Estimation
Quantum Amplitude Estimation (QAE) algorithms are collection of quantum methods to solve the following problem. Given black-box access to some unitary quantum algorithm A on n qubits a unitary oracle O that partitions the computational basis states into a set of 'good' states G and 'bad' states B, find the probability (referred to as the amplitude in this context) a that a computational basis measurement on the output of the algorithm |ψ = A |ψ 0 , where |ψ 0 is an easily-prepared reference state (typically the all-zero state |0 n ), produces a 'good' state.
Given no other information about the structure of the algorithm A or the 'good'/'bad' partition, the only option to solve this problem classically (aside from the unavoidable quantum run of the algorithm A and the call to the oracle O to check the state) is to simply run the algorithm A, measure the output state, check if it is 'good', and repeat to build up statistics. To achieve an estimateã of the amplitude a to within an error ε, this approach requires a number of calls N (sampling) calls to the algorithm A that scales as The first QAE algorithm was proposed in [107], and achieves a quadratic speed-up over classical sampling; that is, the required number of calls N (QAE) calls to the algorithm A to achieve an estimateã of the amplitude a to within an error ε scales as It was later shown that practical implementations of a QAE algorithm would have the potential to speed-up a wide range of important applications; in particular, it was shown by [108] that QAE can be used to achieve a quadratic (up to logarithmic factors) speed-up for Monte Carlo algorithms by enhancing the sampling convergence rate. Given the importance of Monte Carlo algorithms in a broad range of areas, from chemistry [109] to statistical physics [110] to computational finance [111], practical implementations of QAE algorithms would have a significant impact.
The QAE algorithm of [107] is a purely quantum algorithm, relying on the phase-estimation procedure similar to that shown in Fig. 2, and involves many complicated controlled unitary operations that may be difficult to implement. After the work in [108] showed potential uses of QAE, many new forms of QAE were developed [112][113][114][115] that replaced the phase-estimation procedure with classical post-processing, but the core workings of the algorithm remained the same. All forms of QAE involve constructing Grover-like iteration operators [42] similar to Eq. (2). The algorithms work by repeating the Grover iteration operator different numbers of times to amplify the amplitude a by different amounts, and detecting which numbers of iterations produce a large probability of measuring 'good' states. The original algorithm of [107] uses phaseestimation to do this, while more recent QAE algorithms make use classical post-processing instead.
An illustrative example of a hybrid QAE algorithm is the Maximum-Likelihood QAE (MLQAE), proposed by Suzuki et al. [113]. In MLQAE, Grovertype circuits are run at various different numbers m of iterations to produce the states where the angle θ a is defined by sin 2 θ a ≡ a and Π G (Π B ) is a projection operator on to the 'good' ('bad') subspace of the computational basis. Then, these output states are measured, and it is recorded whether the outcome is 'good' or 'bad'. This process is repeated for some number N shot of shots, and a measurement record h = (h m ) m is constructed, where h m is the number of 'good' states produced by N shot shots of the circuit with m Grover iterations. A likelihood function L(θã; h) for the measurement record is then built, = m sin 2 ((2m + 1)θã) hm × By classically maximising this likelihood function (or its logarithm), the angle θ a , most likely to produce the measurement record can be determined, and hence an estimateã for amplitude a can be found. This is illustrated in Fig. 5. Fig. 5(a) shows an illustration of the likelihood L m (θã; h m ) of a Grover-like QAE circuit with m Grover iterations (m larger for lower plots) to produce h m 'good states' from N shot runs, with the angle θã. It can be seen that smaller numbers m of iterations produce a small number of broad peaks (a small number of rough regions where the true θ a might be), while larger m values produce many sharp peaks (which can help identify an accurate estimate if the rough region is known). The overall likelihood function, illustrated in Fig. 5(b), can be maximized to find an accurate estimate of the angle θ a (and hence the amplitude a). It can be shown [113] that for some sequences of choices of m, MLQAE can achieve the same quadratic speedup (Eq. (17) compared to the scaling of classical sampling (Eq. (16)). Various modifications to MLQAE have been developed, including dealing with limited circuits depths and with noisy circuits [116][117][118], but all versions offer a clear illustration of the power of (nontrivial) classical and quantum processing working together to produce speedups over what is possible by classical processing alone.

D. Quantum subroutines within quantum chemistry and materials simulations
A promising direction of research for early quantum algorithms is the development of quantum methods for solving problems in quantum chemistry. Systems for which quantum mechanics must be taken into account to calculate important properties tend in the general case to be hard to treat with purely classical techniques; this is due to the exponential growth of the size of the Hilbert space compared to the system size. Directly exploiting the quantum nature of quantum computers could lead to very natural techniques for these problems.
One approach that is the subject of much recent research [76,119] is to apply the hybrid VQE algorithm described in subsubsection III B 1. By choosing the HamiltonianĤ used in the VQE loop to be the Hamiltonian of the chemical system under study (as well as suitable VQE ansatz), the VQE procedure can be used to find the ground state (or other eigenstates) of the Hamiltonian, from which other important properties can be calculated (e.g the Green's function [120], or various chemical properties. While the direct VQE approach may be suitable for problems that are small enough to fit on near-term quantum devices (but are nonetheless large enough to be difficult for classical methods), for larger problems (such as for correlated materials simulations) a more involved approach must be taken. One proposal from Ma et. al [121] considers separating a full system into a small active space, with an effective quantum Hamiltonian, and its environment, which can be treated less accurately via density functional theory (DFT). The small active space can then be treated with VQE to learn about the electronic properties of the whole system.
Many purely classical algorithms for quantum chemistry and materials rely on quantum Monte Carlo [122,123], a family of classical algorithms which can, to some extent, emulate quantum systems in thermal equilibrium. Quantum Monte Carlo is limited for fermionic systems, however, by what is known as the sign problem, where accurate sampling can become computationally infeasible below certain temperatures [124]. These algorithms have the advantage of providing ready-made classical wrappers to add in quantum components, and are therefore natural candidates for early hybrid quantumclassical algorithms, such as the example presented in [120]. While a full review of hybrid quantumclassical materials and chemistry algorithms, including methods which are based on time evolution rather than ground state preparation is beyond the scope of our current work, Bauer et al. review the algorithmic opportunities in [119].
To give a flavour of how these algorithms work, we focus on work by Bauer et al. [120] which addresses the significant computational challenge to simulate the properties of strongly-correlated materials where the independent-electron approximation intrinsic to the standard DFT breaks down. This work explores the dynamical mean field theory (DMFT) method (see [125] for a thorough review), which can be applied to materials expressible as lattice models. The DMFT approach which recasts the material as a local site (known as an 'impurity') interacting with the rest of the system expressed as a non-interacting bath. The total Hamiltonian is written as where is the impurity Hamiltonian that will be treated carefully, where f † (f ) operators create (annihilate) a fermion in one of N local orbitals and the hopping and interaction integrals t ab and U abcd are determined from the underlying material. The noninteracting bath Hamiltonian has the form where the b † (b) operators create (annihilate) a fermion in one of the bath modes (considered to be infinitely many, but can be truncated to a finite number of modes if necessary). The remaining term, describes the interaction between the impurity and the bath. While at this level of description the bath mode energies j and interactions V aj are free parameters, the core of the DMFT algorithm is to iteratively update these parameters in a self-consistent way until the Green's function of the impurity model and the relevant local terms of the lattice Green's function converge to match. This DMFT scheme is used within an additional outer loop that uses the information it provides about the correlated electrons to iteratively improve a DFT solution.
The structure of the outer loop is shown in Fig.  6(a). The step in which the impurity Green's function is calculated is shown with a dashed border to indicate that it is this piece of the algorithm that can be swapped out for a hybrid quantum-classical subroutine. This step is expanded in Fig. 6(b). Classically, there are various ways to calculate the Green's function, such as by a quantum Monte Carlo algorithm as discussed previously in this section. However, to overcome the inherent computational challenges of classical approaches, Bauer et al. [120] propose using a combination of adiabatic state preparation (using AQC to 'compute' approximations to Hamiltonian eigenstates) and quantum phase estimation [126] to prepare the ground state, from which the Green's function can be measured.

A. Larger computations on smaller hardware -Entanglement forging
Since near-term quantum processors will have only a limited number of qubits available, it is worthwhile to consider how classical processing can be used to apply hybrid algorithms to problems that may not otherwise fit on small devices. An illustrative example of such a method is the recent entanglement forging, due to [127]. In that work, Eddins et al. show how a quantum system mapped to 2N qubits can be studied on a device with only N qubits, by breaking the 2N -qubit system into two Nqubit partitions and expressing the density operator ρ = |Ψ Ψ| of the system in terms of the Schmidt decomposition where |b k are computational basis states for an N -qubit, U, V are unitary operators local to each half of the bipartition.
The non-negative,realvalue Schmidt coefficients λ k are treated as variational parameters for a VQE circuit (see subsection III B 1). In this representation, expectation values Ψ|O|Ψ of 2N -qubit operators of the form where |φ can be single basis states |b k or uniform superpositions of two basis states. These expectation values can be computed on N qubits, and are then sampled in a weighted way according to the coefficients λ k λ j .
While this will not scale well in the general case, systems that are only weakly-entangled across the bipartition will have only a small number of dominant Schmidt coefficients λ k ; thus the expectation value Ψ|O|Ψ can be well-approximated with a manageable number of samples. In [127], entanglement forging (along with some heuristic enchancements) is used to find ground-state energies of various geometries of the water molecule with highaccuracy, via a ten-qubit mapping, usimg only 5 superconducting qubits on real quantum hardware.

B. Additional controls
In the case of QA and other non-universal analog processors, we see that sometimes hybrid techniques required additional controls. The most prototypical example here is reverse annealing as discussed in subsubsection III A 1, which allows for hybrid techniques. These controls are important because they allow a much richer variety of techniques which have demonstrated real gains in experiments. In particular, in this example the controls were actually already available within the underlying device (the protocol described in [55] is essentially reverse annealing combined with some other techniques), but had not been made available to external users. It is therefore highly important to think about how existing experimental techniques could be used in computation for different purposes than they were originally intended.
C. Co-locating the quantum and classical computing power When discussing computations at the abstract level we have so far, it is easy to forget that communication between classical and quantum systems is not free. While the currently dominant model of cloud access to quantum computers is very useful for proof-of-concept experiments, the time required to send signals over the internet between quantum and classical components could prove to be a major barrier. There are already efforts to colocate quantum computing resources with powerful classical high performance computing, for example through the Jülich supercomputing centre's JUNIQ program [128].
Some computation may require even faster communication between quantum and classical components; for qubit technology such as superconducting qubits which operate on chip substrates at ultra-low temperatures, this means that classical computation at cryogenic temperatures (although possibly not as cold as the quantum computer) could be beneficial. Inspired by the quantum computing use cases, there have been numerous studies in this direction [129][130][131][132][133]. As we discuss in section V, there are also many types of classical processors, each with their strengths and weaknesses; any of these could potentially be useful candidates to co-locate with quantum computers.

V. THE BIG PICTURE: SPECIALIZED ACCELERATORS
Throughout this work, we have offered many examples showing how classical and quantum processors can potentially be used together to perform computational tasks much more efficiently than what is possible with a classical processor alone. While a quantum processor is certainly quite different, both practically and theoretically, from any kind of classical processor, different types of proces-sors working together is already a common structure within purely classical computing; there are many classical examples of specialized co-processors, to which specific kinds of processing are offloaded, and this is sometimes known as heterogeneous or heterotic. A thorough discussion of heterotic computing is available in [134]. In this section, we will briefly describe some examples of classical heterotic computing and offer some intuition for how quantum processors can naturally fit into this framework.
Graphics Processing Unit -The clearest example of classical heterogeneous computing is that of a computer's central processing unit (CPU) working together with graphics processing unit (GPU) [135]. A typical GPU consists of, among other things, a much larger number of cores than a typical CPU, and these cores are particularly suited to the kinds of three-dimensional vector-matrix operations needed for graphics processing, such as translations and rotations in space. Typically, the same calculation needs to happen many different times on independent inputs; for example, every point on a threedimensional object needs to move in the same way, with only the starting conditions different for each point. The large number of small cores on a GPU allows this to happen to happen at a greatly accelerated pace [135] compared to the relatively small number of (more general purpose) cores on a CPU can manage. Typically, the computation is arranged such that the CPU hands off these specific tasks to the GPU when needed.
More recently, GPU technology has been used for applications beyond graphics processing but which also require the same large-scale parallelization of small numerical operations, such as machine learning calculations (e.g via TensorFlow [136]).
Application-specific integrated circuit -An Application-specific integrated circuit (ASIC) [137] can be thought of as a processor designed and manufactured to carry out a specific computational task much more quickly and with much more energy efficiency than can be achieved by a programming a general-purpose processor such as a CPU. An example of an ASIC with these properties is Intel's Quick Sync video technology; these circuits are used for rapidly converting video between different formats, and are integrated with Intel CPUs to handle these specific workloads [138]. Similar hardware, known as Field-programmable Gate Arrays (FPGAs) [139], can be reprogrammed at the hardware level after being deployed.
a. Neuromorphic processors -Many modern classical algorithms are based mimicking the behaviour of the human brain through the use of software-defined neural networks. While this approach is proving successful in many areas, stan-dard processors are proving to be limited by particular bottlenecks, such as the communication between the core and memory. To avoid these limitations, the emerging development of neuromorphic processors [140] aim to emulate the behaviour of the human brain directly at the hardware level, leading to hardware that can run artificial intelligence applications much more efficiently than standard processors.
b. Quantum computers as specialized coprocessors -The specialized accelerators described here all show how hardware designed and optimized for a specific type of computational work can operate in tandem with a standard processor, such as a CPU, to enhance overall computational efficiency. Hybrid quantum-classical algorithms, including the ones described in this work, fit naturally into this framework; a quantum processing unit (QPU) can be called by a general purpose classical CPU to accelerate specific computational subroutines, such as the phase estimation component of Shor's algorithm (see subsection II B) or the ansatz preparation component of a VQE algorithm (see subsubsection III B 1). From this perspective, hybrid quantum-classical algorithms are a continuation of a traditional pattern in the development of computer technology. While the operating principles of a quantum computer are quite different from their classical counterparts, the way they fit into larger architectures (and the surrounding concerns) are not fundamentally something which has not been encountered before.

VI. THE FUTURE OF HYBRID ALGORITHMS
The development path of hybrid algorithms is not universal and does not always involve a nonhybrid precursor; while hybrid forms of QAE grew out of the original pure form of QAE (and indirectly out of Grover's search, a pure quantum algorithm), many others came about in different and varied ways. Shor's algorithm for example emerged from the fact that a quantum algorithm fulfilled a niche application which allowed for a very powerful computational tool. This is similar to many hybrid materials and chemistry algorithms, which have developed out of classical algorithms by replacing classical methods such quantum Monte Carlo with quantum computing calls. In the case of variational algorithms, as well as hybrid forms of quantum annealing, the capabilities of the hardware has driven the development of algorithms. A key lesson to draw from these stories is that there is not one way to develop hybrid algorithms: they can emerge in a multitude of different ways.
An immediate question which arises from this discussion is whether hybrid algorithms are just a phase in the evolution of quantum computing, and when (and if) large, fully fault-tolerant quantum computers come into existence, will hybrid algorithms still be used? If we look at the evolution of classical computing technologies, we can find a hint. As new, advanced co-processors have been developed classically they have not displaced older paradigms, but rather been added to them to perform specialized tasks. We do not see any reason to believe that the evolution of quantum computers will be any different. Quantum computers are not intrinsically faster at simple applications like adding numbers, and even if large numbers of high-quality qubits became readily available, it is doubtful that they would ever be better than classical bits by all metrics, in which case heterotic computing would be the most sensible paradigm, as it currently is in the world of classical computing. We find it unlikely that once quantum hardware advances to the stage of genuine usefulness non-hybrid algorithms will ever be deployed in a "production" setting, for the simple reason that it is likely that further improvements could be made by adding a hybrid component.
From our discussion so far, we have seen that hybrid algorithms are most meaningfully classified in terms not of how much classical computing power they use, but how that computation fits into the overall model. While there are notable algorithms which are both hybrid and non-hybrid, a pattern which has appeared both in terms of Grover's algo-rithm and subsequent QAE techniques, and quantum annealing and subsequent hybrid versions, is that non-hybrid algorithms often evolve into richer, more powerful, hybrid variants. This pattern is likely not incidental, it is often easier to first imagine algorithms in a more "pure" setting and then allow them to evolve. This suggests an interesting relationship between hybrid and non-hyrbid algorithms: the non-hybrid setting is a useful incubator for hybrid techniques which will later be implemented. As such, we are not suggesting that hybrid algorithms are the only class of quantum algorithms which are worthwhile to study, but that it is probably most appropriate to think of non-hybrid algorithms as the foundations of new algorithms which are yet to be developed.