{'fraction_non_alphanumeric': 0.03935651727802411, 'fraction_numerical': 0.00879475246436293, 'mean_word_length': 4.333203048661325, 'pattern_counts': {'":': 0, '<': 0, '<?xml version=': 0, '>': 0, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 2, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
Noise resistance of adiabatic quantum computation using random matrix theory

Besides the traditional circuit-based model of quantum computation, several quantum algorithms based on a continuous-time Hamiltonian evolution have recently been introduced, including for instance continuous-time quantum walk algorithms as well as adiabatic quantum algorithms. Unfortunately, very little is known today on the behavior of these Hamiltonian algorithms in the presence of noise. Here, we perform a fully analytical study of the resistance to noise of these algorithms using perturbation theory combined with a theoretical noise model based on random matrices drawn from the Gaussian Orthogonal Ensemble, whose elements vary in time and form a stationary random process.


I. INTRODUCTION
There has been a growing interest recently for the concept of Hamiltonian-based quantum algorithms, as opposed to the standard circuit-based paradigm of quantum computing. The Hamiltonian algorithms rely on the continuous time evolution of a quantum register according to the Schrödinger equation, and include in particular the quantum search algorithms by adiabatic evolution [1] or by continuous quantum walks [2,3]. While these algorithms may be translated into circuit-based algorithms so that they could be implemented on a "standard" quantum computer [4,5], another possibility is to consider a "continuous" quantum computer specifically designed to run this type of algorithms [6]. For a realistic implementation, it seems therefore crucial to investigate how well such a quantum computer would behave in the presence of noise. Until now, this question has only been addressed for some specific algorithms subject to some very particular noise. For instance, Childs et al. have considered an adiabatic quantum algorithm for solving combinatorial problems [7] affected by an error modeled by an extra term which is random but deterministically evolves in time [8]. While this study was purely numerical, later on Shenvi et al. [9] analytically analyzed the effect of a Markovian stochastic variable perturbing the amplitude of the oracle Hamiltonian in the specific case of the analog analogue of Grover's search algorithm [10]. In contrast, the purpose of the present paper is to derive more generic results for an Hamiltonian-based algorithm perturbed by a noise that is described by a stationary gaussian random process. This makes it possible to carry out a fully analytical treatment of the tolerance to noise, although this is at the price of some (fairly general) assumptions on the noise model and of the use of perturbation theory. This paper is organized as follows. In Section II, we describe our theoretical model of noise based on the Gaussian Orthogonal Ensemble. In Section III, we use perturbation theory to analyze the effect of noise on a timeindependent Hamiltonian evolution and apply our results to the analog analogue of quantum search. In Section IV, we consider the tolerance to noise of a time-dependent quantum algorithm by adiabatic evolution, and then fo-cus on the quantum search by local adiabatic evolution. Finally, in Section V, we conclude by discussing the scaling of the noise-induced error probability as a function of the noise bandwidth.

II. NOISE MODEL
Suppose we have an ideal (noiseless) Hamiltonian algorithm based on the HamiltonianH(t), At the end of the computation (t = T ), we obtain the state |ψ(T ) , which, after measurement, defines the output of the algorithm. Now, suppose that a perturbation εh(t) adds to the ideal Hamiltonian: Instead of |ψ(T ) , we will get at the end of the computation a different state |ψ(T ) . The problem in the following will be to evaluate the error probability induced by the perturbation. In order to derive analytical results, we will have to make some assumptions on the noise term εh(t). First, we limit ourselves to a noise of small amplitude ε ≪ 1, so that the use of perturbation theory is justified. Second, we assume that, in any basis |ϕ k (k =, 0 . . . , N − 1) of the N -dimensional Hilbert space where the computation takes place, the matrix elements of h(t) are normal random variables: More specifically, we assume that the matrix h(t) is drawn from a Gaussian Orthogonal Ensemble (GOE), so that the variance σ 2 kl of its elements is defined by σ 2 kl = (1 + δ kl )σ 2 , where σ 2 is an overall variance (see [11] for more details on random matrix ensembles). Moreover, any two distinct elements of a GOE matrix are taken as independent random variables, Even though the above assumptions are not based on a specific physical source of noise, they may be justified by considering that the noise is generally caused by many independent sources of error which, combined together, finally result in a random Hamiltonian drawn from a GOE as a consequence of the central-limit theorem.
Furthermore, we assume that the random matrix elements h kl (t) evolve in time as some stationary random process with an autocorrelation function [12] For instance, a very typical noise model we can use is a white noise with a high-frequency cut-off ω 0 (see for instance [13]), which yields However, to be slightly more general, we will only assume later on that the autocorrelation function is of the type as well as some other regularity conditions (see next sections). Thus, we only need to assume that R(τ ) is a function of ω 0 τ . Finally, as we will be interested in the scaling of the perturbed Hamiltonian-based algorithm as a function of the size of the problem, N , we need to properly define the dependence of the noise term in N . For the scaling analysis to be sensible, we must keep a constant signalto-noise ratio as N increases, that is, the eigenvalues of h(t) should scale similarly to those ofH(t). As a result of Wigner's semi-circular law, we know that the density of eigenvalues of GOE matrices for N ≫ 1 is given by Therefore, to keep a constant signal-to-noise ratio, we have to impose that σ 2 =Ē 2 /4N , whereĒ is of the order of the eigenvalues ofH(t).

A. Perturbation theory
Let us study first the simplest case of a timeindependent Hamiltonian evolution. The solution of the ideal Schrödinger equation is where |ϕ k and E k are the eigenstates and eigenvalues of the ideal Hamiltonian and the amplitudesb k follow from the initial conditions. By use of perturbation theory, we can study the effect of a small time-dependent perturbation εh(t) on the ideal HamiltonianH. Expanding the solution of the perturbed equation in the basis formed by the solutions of the non-perturbed equation, that is, and introducing this expression into the Schrödinger equation, we geṫ where ω kl = (E k − E l )/ . Using the same initial state as for the ideal evolution, i.e., b k (0) =b k , we obtain the system of equations Using standard perturbation theory (see e.g. [14]), this may be solved iteratively, building step by step the expansion of b k (t) in increasing orders in ε. From this solution, one can derive (an expansion of) the error probability p err introduced by the perturbation εh(t). As the matrix elements of h(t) are random variables, so will p err be, and we will only have access to its statistics. In particular, we will focus on its mean p err . Using our assumption that h(t) is a random matrix drawn from a GOE, we can show that where we have introduced the integrals which correspond to the coupling between the states |ϕ k and |ϕ l that is effected by the perturbation. Our problem now is to evaluate these integrals. We see that they only depend on the the noise model via the autocorrelation function f (x) and the high-frequency cut-off ω 0 , while they depend on each particular instance of the problem via the spectrum of the ideal Hamiltonian or the frequencies ω kl (as well as the computation time T ). Therefore, I ± kl vary for different instances of a problem.
However, we can derive some general expressions, which remain valid for a fairly large class of problems. First of all, since I ± kl are integrals over a domain of size T 2 and as the amplitude of their integrand is bounded by 1, we immediately see that, whatever the values of ω kl and ω 0 , we have the upper bound Furthermore, we note that the I + kl couplings only appear between the eigenstates that are initially populated, and may therefore be viewed as the interferences caused by the noise between these states. As there is in general a small and fixed number of eigenstates |ϕ k that are populated (b k = 0) in the algorithm [18], Eq. (14) implies that there will be a fixed number of I + kl terms contributing to the expression of p err . In contrast, the number of I − kl terms, corresponding the the coupling of the initially populated states to all others, will in general grow with the dimension N of the Hilbert space. Therefore, the scaling of the average error probability p err will mostly depend on the integrals I − kl , which is why we now focus on these in what follows. By changing the integration variables to u = t 1 − t 2 and v = t 1 + t 2 , we get which is the integral of a modulated oscillation. For a white noise (7), we get by direct integration where Si(x) is the sine integral function. Depending on the value of ω 0 , we may consider two limiting regimes: for a high cut-off frequency ω 0 ≫ ω kl , we get while for a low cut-off frequency ω 0 ≪ ω kl , we have Although Eqs. (19) and (20) are only valid, strictly speaking, for a white noise, we obtain similar results for a general function f (x). In the high-ω 0 regime, since the autocorrelation function R(τ ) usually tends to zero as τ increases [i.e., h kl (t + τ ) becomes less and less correlated with h kl (t) for increasing τ ], Eq. (19) follows from the approximation cos(ω kl u)f (ω 0 u) = 1 + O(ω kl /ω 0 ). In the low-ω 0 regime, we must integrate a rapidly oscillating function over many periods, which is treated in Appendix A. Under very general regularity conditions on f (x) [19], we may use the lemma 2 twice, and finally recover Eq. (20). It is interesting to note that in the low frequency regime, the coupling integral does not depend on the computation time T . We will see that, at least for the algorithms considered here, this causes a very different behavior of the scaling for this regime, as compared to the high-ω 0 regime.

B. Analog quantum search
Let us recall the principle of Farhi and Gutmann's analog quantum search [10]. Suppose that we may apply an oracle Hamiltonian (21) to the system, withĒ denoting an energy scale of the system. The problem is to prepare the system in the (unknown) solution state |m . In [10], it is shown that this may be achieved by preparing the system in the uniform superposition of all states and applying the constant during a time This results in a quadratic speed-up with respect to a classical search in an unstructured database of size N . In order to study the robustness of this quantum algorithm against a stationary gaussian noise as defined in Sec. II, let us first consider the spectrum of the ideal HamiltonianH = H 0 + H f (see Fig. 1). We assume, for simplicity and without loss of generality, that the problem admits the solution m = 0. The two lowest eigenvalues ofH, that is are non-degenerate and correspond to the ground and first-excited states, whereas the N − 2 times degenerate eigenvalue E 2 = 2Ē corresponds to the eigenstates Expressing |ψ(t = 0) = |ψ 0 in terms of the eigenstates |ϕ k of the ideal HamiltonianH, we get As a consequence, the instantaneous state of the ideal algorithm |ψ(t) is given by Eq. (10) with andb k = 0 for k ≥ 2. Only two states are populated during the ideal algorithm, and the average error probability (14) becomes where we have used the normalization condition |b 0 | 2 + |b 1 | 2 = 1 and the fact that I − kl = I − k2 for l ≥ 2. For this algorithm, the bound (16) gives |I ± kl (t)| ≤ π 2 /8, which is independent of N . Therefore, only the first term of Eq. (30), which represents the coupling of the ground and first excited states (the only initially populated states) to the N − 2 others, can grow with N and must be taken into account in the scaling analysis. Let us focus on this term in the two limiting regimes considered above.
For a noise with a high cut-off frequency, Eq. (19) yields which is valid if ω 0 ≫Ē. Clearly, I − k2 should be of order 1/N for p err not to grow with N , which imposes the condition Thus, in this regime, the cut-off frequency of the noise must increase as the square root of the size of the problem in order to keep a probability of error of constant order. In the case of a noise with a low cut-off frequency, Eq. (20) yields so we see that p err will not grow with N as long as ω 0 ≪Ē. Interestingly, this upper bound on the cut-off frequency does not depend on the size of the problem.
We conclude that the influence of noise on the analog quantum search algorithm is negligible if the noise varies either very slowly or very rapidly with respect to the natural time scale of the problem /Ē. For the typical case of a white noise with high frequency cut-off, the exact integration (18) shows that for intermediate values of the cut-off frequency ω 0 ∼Ē/ , the average error probability scales as ε 2 √ N for a given signal-to-noise ratio ε (see Fig. 2). This means that there exists a forbidden band for the cut-off frequency ω 0 if we want to keep our algorithm robust with respect to a constant noise (i.e., a noise that scales with N so to keep a constant signal-to-noise ratio). Alternatively, we see that the signal-to-noise ratio ε should scale as N −1/4 in order to keep the error probability p err constant for a cut-off frequency ω 0 of order E/ . In other words, for an increasing problem size N , the noise variance σ 2 must decrease faster thanĒ 2 /4N for the algorithm to remain immune to noise. Finally, let us mention that ε ∼ N −1/4 coincides with the result of Shenvi et al. [9], even though their noise model was less general than ours since they only considered an error in the magnitude of the oracle Hamiltonian, modeled as a Markovian stochastic variable with Gaussian distribution.

A. Adiabatic approximation
Let us recall the adiabatic approximation, which is at the basis of the quantum algorithms by adiabatic evolution. Qualitatively speaking, the idea is as follows: if a quantum system is prepared in its ground state and its Hamiltonian varies "slowly enough", it remains in a state close to the instantaneous ground state of the Hamiltonian at any time. To be more precise, let us consider the Schrödinger equation for a time-dependent Hamiltonian (see [14] for details), To solve this equation, we express its solution |ψ(t) in the basis formed by the instantaneous eigenstates |ϕ k (t) of the HamiltonianH(t), where E k (t) are the corresponding instantaneous eigenvalues ofH(t). By inserting this expression into Eq. (34), we find the system of differential equationṡ .
If the quantum system is initially in its ground state |ψ(0) = |ϕ 0 (0) , these equations can be integrated, givinḡ b k (t) = δ 0k (37) As in perturbation theory, these equations may be solved iteratively, which gives after one iteration b (1) for k = 0. Now if the variation dH/dt of the Hamiltonian is slow enough, or more specifically if and under suitable regularity conditions, we may integrate Eq. (38) by parts as shown in Appendix A, which yields b (1) We see that, at the first order, the amplitudes |b k (t)| are bounded by 2δ k . This first-order (so-called adiabatic) approximation is acceptable if |b 0 (t)| 2 stays close to 1, that is, if the probabilityp(t) = k =0 |b k (t)| 2 of hopping to any excited state remains small. In other words, if the adiabatic condition is satisfied, thenp(t) ≤ δ 2 ≪ 1, with δ ≪ 1 being a "slowness" parameter. Now, suppose that a time-dependent perturbation εh(t) adds to the ideal HamiltonianH(t). We again express the solution of the perturbed Schrödinger equation in the basis formed by the instantaneous eigenstates of H(t), We may again solve this system of equations iteratively, which gives after one iteration b (1) for k = 0. As before, this first-order approximation remains valid provided that the probability p(t) = k =0 |b k (t)| 2 of hopping to any excited state remains small.
Let us now evaluate the average error probability at the end of the evolution t = T using the same model as before for the perturbation h(t). Defining the error probability as p err = p(T ), we have wherep err =p(T ) is the error probability of the ideal adiabatic evolution. Let us note that |ϕ k (t 1 ) = |ϕ k (t 2 ) in general, so that we do not immediately recover the autocorrelation function of one particular matrix element of h(t). However, as the different matrix elements of h(t) are independent in a particular basis, we have If |ϕ k (t) varies sufficiently smoothly for 0 ≤ t ≤ T , then the first factor is of order 1 − O((t 1 − t 2 ) 2 /T 2 ). Thus, we may approximate it by 1 as long as ω 0 T ≫ 1, that is, if the noise varies quickly compared to the adiabatic evolution. In that case, we get for the average error probability where the integrals represent the coupling of the ground state to the excited states induced by the perturbation. The adiabatic condition generalizes in the case of such a perturbation to Similarly to the case of the perturbed time-independent Hamiltonian evolution, the effect of the perturbation on the adiabatic evolution mainly depends on the coupling integrals I − k0 , which are bounded by and can be approximated as (51) or in the limiting regimes of high or low cut-off frequency ω 0 , respectively, where ω min

B. Adiabatic quantum search
The principle of the adiabatic quantum search [1] is to apply the Hamiltonian H 0 =Ē(I − |ψ 0 ψ 0 |) to a system prepared in its ground state |ψ 0 and then to progressively switch the Hamiltonian H 0 to the Hamiltonian H f =Ē(I − |m m|), where m is the solution of the search problem. If this switch is done slowly enough, the system will stay in the instantaneous ground state of the Hamiltonian and thus end up in the ground state of H f , i.e., the solution state |m . The instantaneous Hamiltonian is chosen as where s = s(t) is an evolution function which must be optimized so as to reduce the computation time while respecting the adiabatic condition (41) (see [15,16] for details). In this case, this condition may be rewritten as Without loss of generality, we may once again suppose that m = 0. The instantaneous eigenstates ofH(s) are where are the instantaneous eigenvalues ofH(s) (see Fig. 3). Since ||H f − H 0 || ≤Ē, taking an evolution function s(t) that satisfies complies with the adiabatic condition (54), and then leads to a computation time Consider that some noise, modeled again as a stationary gaussian random process, perturbs the evolution. Equation (47) then reads where I − k0 ≤ π 2 /(64δ 2 ) as a result of Eq. (50). Let us emphasize that, while it was only the excitation to the first excited state that was critical for the ideal adiabatic algorithm, in this case it is the coupling of the ground state to all excited states that could make the algorithm fail, since their number grows as the size N of the problem. Moreover, this bound already suggests that the coupling integrals I − k0 -and therefore the error probability -could increase when the evolution slows down (δ decreases) which means there must be a compromise between a slow evolution, very close to perfect adiabaticity, and a fast evolution, more robust to noise.
As before, let us consider the two limiting regimes of a high or a low cut-off frequency ω 0 . In the case of a high cut-off frequency ( ω 0 ≫Ē), Eq. (51) yields exactly as for the analog quantum search except for the factor 1/δ. The latter factor shows that in order to keep the algorithm robust to noise, the cut-off frequency has to increase not only as the the size of the database N grows (just as for the analog quantum search), but also as the evolution slows down (δ decreases). More precisely, we see that the perturbed adiabatic condition (49) is satisfied only if (compare with Eq. (32)). When the cut-off frequency becomes very low ( ω 0 ≪Ē), Eq. (52) implies that the coupling integrals behave as for all excited states except the first one (i.e., for k ≥ 2). For the first excited state (k = 1), we have ω min 10 ∼ E/ √ N so Eq. (52) does not yield a useful result. Instead, we simply use the general bound I − k0 ≤ π 2 /(64δ 2 ). Therefore, the adiabatic condition is satisfied here as long as ω 0 ≪Ē (just as for the analog quantum search), but also if ε ≪ δ.
In summary, we recover essentially the same effects for the adiabatic quantum search as for the analog quantum search, that is, the influence of noise becomes negligible only in the case of a very high or a very low cut-off frequency ω 0 , apart from the influence of the slowness parameter δ. Regarding this latter parameter, we see that while decreasing δ gets the ideal evolution closer to adiabaticity and therefore reduces the error probability without noise, in the presence of noise it imposes that ε decreases -i.e., that the signal-to-noise ratio increases -in both regimes of a high or low cut-off frequency (or that the high cut-off frequency increases as 1/δ 3 ).

V. CONCLUSION
We have studied the resistance of Hamiltonian quantum algorithms (including adiabatic algorithms) to a noise that is modeled as a random matrix whose elements are stationary gaussian random processes within a fixed bandwidth. This statistical noise model is generic, and should therefore make our analysis valid over a large class of physical systems, regardless of the exact origin of the added noise. Another main advantage of this noise model is that it makes it possible to perform a fully analytical scaling analysis. Our general result is that the Hamiltonian algorithms are resistant to noise (i.e., the error probability p err does not increase with increasing problem sizes N ) as long as the cut-off frequency of the noise is either very high or very low with respect to the inverse of the characteristic time-scale of the systemĒ/ . Asides from the influence of the slowness parameter δ in the case of the adiabatic algorithms, this resistance is essentially similar for adiabatic and time-independent Hamiltonian algorithms. Our results are in good agreement with the numerical study of Childs et al. in [8]. They even corroborate the results of Shenvi et al. [9], although their noise model was rather different, which supports the idea that using random matrix theory provides a rather general description of noise.
Roughly speaking, the two limiting regimes of high or low cut-off frequencies can be understood in the following way. If the frequency components of the noise are much below the inverse of the characteristic time-scale of the system, it is intuitively clear that the noise cannot effect transitions to undesired states. On the contrary, if the noise spectrum spreads over a band which is much broader than the inverse of the characteristic timescale of the system, then the noise spectral density is low around the frequencies that effect undesired transitions. In the intermediate region, we found that the error probability unfortunately scales as √ N [20], which implies that some error correction is needed to make Hamiltonian algorithms scalable. This last point is particularly important as it is plausible that the source of noise occurring in a physical system typically varies on a time scale comparable to the natural time scale of the system, so that the less favorable regime ( ω 0 ∼Ē) may be the most common situation.
Coming back to the two limiting regimes, let us notice that the high cut-off frequency increases towards higher frequencies when N raises [see Eqs. (32) and (65)]. Consequently, the Hamiltonian algorithms will in practice not be scalable in the high cut-off frequency regime too, since the noise should spread over an arbitrarily large spectrum to keep the error probability low. In this case, some kind of error correction should also be implemented if the size of the problem becomes too large. The case of a low cutoff frequency, however, is more favorable. Indeed, the situation is quite different here as the error probability stays small as soon as the cut-off frequency is lower than some fixed value, even when the size of the problem increases. This fault tolerance may be explained by the fact that the spectral density of noise does not contain frequencies close to resonances, and thus will not efficiently couple different eigenstates of the ideal Hamiltonian.
It should be emphasized that it is not the possible excitation to one particular state that makes the algorithm fail, but the fact the dimension of the Hilbert space increases with the problem size, and hence the number of states that could be accidentally populated as well. This means, in the case of adiabatic computation, that even if the gap between the ground and first excited states decreases, the algorithm may remain robust to a noise with a low cut-off frequency (even if this frequency remains constant) as long as the gap between the ground states and the other excited states remain lower bounded. Therefore, the algorithm would remain scalable in the case of a low cut-off frequency as long as the natural frequencies of the ideal Hamiltonian are much larger than the frequencies contained in the noise. Of course, throughout this analysis, we always made the assumption that the signal-to-noise ratio remains essentially constant when the size of the Hilbert space where the computation takes place becomes large, which may practically not be the case. Thus, even in this low cutoff frequency regime, it may be necessary to devise error correction techniques for Hamiltonian -and in particular adiabatic -quantum algorithms.
Note: A few days ago, a related paper appeared on the quant-ph preprint server, which also considers the use of random matrix theory in adiabatic quantum computing but with a distinct goal, namely to analyze the spectral statistics of the Hamiltonian over a large class of problems along an adiabatic (but noiseless) evolution [17].

APPENDIX A
In this appendix, we give a useful tool to evaluate integrals of an oscillating function such as b a dxF (x)e iωx . (A1) The basic idea relies on Riemann-Lebesgue's lemma: This lemma suggests that the integral (A1) will be relatively small if ω is sufficiently large. The purpose of this appendix is to quantify this idea.
First of all, as long as F (x) is differentiable on [a, b], we may integrate (A1) by parts: The order of the error introduced by neglecting the last term may be evaluated as follows: (A3) We see that the accuracy of this approximation increases with the oscillation frequency ω. Moreover, if (1/ω N )d N F /dx N → 0 for N → ∞, this error approaches zero as N increases and we prove the following lemma:  While this result is helpful to study a time-independent Hamiltonian evolution, in the case of an adiabatic evolution the typical frequencies become time-dependent. However, using the same method, we easily generalize this lemma to the case of a varying frequency ω(x). Lemma 3 Let the function F (x) be infinitely differentiable on [a, b]. If