Can small quantum systems learn?
Abstract
We examine the question of whether quantum mechanics places limitations on the ability of small quantum devices to learn. We specifically examine the question in the context of Bayesian inference, wherein the prior and posterior distributions are encoded in the quantum state vector. We conclude based on lower bounds from Grover’s search that an efficient blackbox method for updating the distribution is impossible. We then address this by providing a new adaptive form of approximate quantum Bayesian inference that is polynomially faster than its classical anolog and tractable if the quantum system is augmented with classical memory or if the low–order moments of the distribution are protected using a repetition code. This work suggests that there may be a connection between fault tolerance and the capacity of a quantum system to learn from its surroundings.
I Introduction
Quantum systems have, at first glance, an incredible capacity to store vectors. Only qubits suffice to represent a vector in . This, in part, is the origin of all of the celebrated exponential speedups that quantum computing offers Shor (1994); Lloyd et al. (1996); Childs et al. (2003); Harrow et al. (2009). At the same time, from a computational learning perspective, quantum states can be approximately described much more efficiently Aaronson (2007). Indeed, the tension between this ability of a small quantum register to store a very high–dimensional vector and the perspective offered by learning raises an important question: can a quantum agent with a logarithmically sized quantum memory efficiently learn from its surroundings? Here, we seek to shed light on this question by investigating Bayesian inference as a way to model the quantum agent inferring properties about its surroundings. We will see that lower bounds on quantum query complexity of unstructured search place severe limitations on the ability of the system to learn exactly. Nonetheless, we will also see that quantum mechanics reveals new possibilities for approximate learning that are not present in classical Bayesian inference.
Bayes’ rule is the heart of Bayesian inference. It gives the correct way to update a prior distribution that describes the users’ initial beliefs about a system model when a piece of experimental evidence is received. If is a piece of evidence (an observable variable) and denotes a candidate model for the experimental system (a latent or hidden variable), then Bayes’ rule states that the probability that the model is valid given the evidence (denoted ) is
(1) 
where is known as the likelihood function and is assumed to either be either numerically or inferred emperically. This form of learning has a number of advantages for applications in quantum information processing Granade et al. (2012); Ferrie and Granade (2014). Firstly, it is highly robust to noise and experimental imperfections. Secondly, it is broadly applicable to almost every data processing problem. Finally, Bayesian inference provides a probability distribution rather than a point estimate of the model. This allows the uncertainty in the inferred parameter to be directly computed.
There are several features that can make Bayesian inference computationally expensive, especially for scientific applications. Perhaps the biggest contributor to the cost of these algorithms is the dimensionality of the model space. Typically the latent variable is parameterized by a vector in , which means that precisely performing an update requires integrating over an infinite number of hypotheses. Such integrals are often intractable, which limits the applicability of exact Bayesian inference.
A natural question to ask at this point is whether quantum computing could make inference tractable. Quantum advantages are seen for a wealth of other machine learning protocols Aïmeur et al. (2006); Wiebe et al. (2014a, b); Lloyd et al. (2013, 2014); Boixo et al. (2015), so it stands to reason that it may be able to provide advantages here as well. This issue is has been recently discussed in Low et al. (2014), which uses ideas from quantum rejection sampling Harrow et al. (2009); Ozols et al. (2013) to accelerate the inference process. Their work leaves a number of important issues open. The method has success probability that shrinks exponentially with the number of updates attempted. Furthermore, the algorithm cannot be applied in an online fashion nor can it be applied to continuous problems or those with stochastically varying latent variables. We address these issues here by providing a quantum algorithm that can implement Bayesian inference in an online fashion by periodically classically caching a model of the posterior distribution. This approach allows the quantum agent to revert to a previous model in the event that the update process fails, which allows the process to be implemented efficiently under reasonable assumptions on the likelihood function.
Ii Quantum Bayesian updating
In order to investigate the question of whether small quantum systems can learn efficiently, we will examine the issue through the lens of Bayesian inference. Our first objective in this section is to provide a concrete definition for what we mean by a quantum Bayesian update and show a protocol for implementing a quantum Bayesian update. We will then show that this method cannot generically be efficient and furthermore that asymptotic improvements to the algorithm or an inexpensive error correction algorithm for its faults would violate lower bounds on Grover’s search. These results motivate our definition of “semi–classical” Bayesian updating in the subsequent section.
A key assumption that we make here and in the subsequent text is that the visible and latent variables are discrete. In other words, we assume that each experiment has a discrete set of outcomes and there are a discrete set of hypotheses that could explain the data. Continuous problems can, however, be approximated by discrete models and we provide error bounds for doing so in Appendix B. We then invoke these assumptions in the following definition of a quantum Bayesian update.
Definition 1.
A quantum Bayesian update of a prior state performs, for observable variable and likelihood function , the map
In order to formalize this notion of quantum Bayesian updating within an oracular setting we will further make a pair of assumptions.

There exists a selfinverse quantum oracle, , that computes the likelihood function as a bit string in a quantum register: .

A constant is known such that for all .
An interesting consequence of the above assumptions and Definition 1 is that in general the Bayesian update is nonunitary when working on this space. This means that we cannot implement a quantum Bayesian update deterministically without dilating the space. The following lemma discusses how to implement such a non–deterministic quantum Bayesian update. It can also be thought of as a generalization of the result of Low et al. (2014) to an oracular setting.
Lemma 1.
Given an initial state and the state can be prepared using an expected number of queries to that is in .
Proof.
Using a single call to and adding a sufficient number of ancilla qubits, we can transform the state into
(2) 
Then by applying the rotation to the ancilla qubit, controlled on the register representing , we can enact
(3) 
Next the right most qubit register is measured and if a result of is obtained then the resultant state is
(4) 
which gives a probability distribution that corresponds to that expected by Bayes’ rule. The probability of this occurring is .
Since the process is heralded, amplitude amplification can be used to boost the probability of success for the successful branch quadratically Brassard et al. (2002). Thus the average number of queries is in as claimed. ∎
If the Bayesian algorithm is used solely to post–process information then one update will suffice to give the posterior distribution. In online settings many updates will be needed to reach the final posterior distribution. If updates are required then the probability of all such updates succeeding given a sequence of observed variables is at most
(5) 
This shows that the probability of success generically will shrink exponentially with .
The exponential decay of the success probability with can be mitigated to some extent through amplitude amplification on the condition that all updates are successful This reduces the expected number of updates needed to
(6) 
but this strategy is obviously insufficient to rid the method of its exponentially shrinking success probability. Furthermore, we will see that there are fundamental limitations to our ability to avoid or correct such failures.
While the success probability in general falls exponentially, not all failures are catastrophic. We show in Appendix A that a radius of convergence exists such that if the prior distribution is sufficiently close to a delta–function about the true value of the latent variable, and the likelihood function is well behaved, then this updating strategy will cause it to converge to the delta–function. This convergence occurs even if the user ignores the fact that inference errors can occur and does not attempt to correct such errors. This means that, for discrete inference problems, the computational complexity of inferring the correct latent parameter need not be infinite.
The reason why the errors in quantum rejection sampling cannot, in general, be efficiently corrected stems from the fact that quantum Bayesian inference algorithm described in Lemma 1 can be thought of as a generalization of Grover’s algorithm Grover (1996). Grover’s problem (with one marked element) seeks to find where is a blackbox Boolean function that is promised to have a unique such that . The generalization to multiple marked elements is similar. The reduction between the two problems is formally proved below.
Lemma 2.
Grover’s problem with items and marked items reduces to Bayesian inference on a prior on .
Proof.
Let be a Boolean function that takes the value iff where . Identifying the set by querying this function is equivalent to Grover’s problem. Consider the following likelihood function on a two–outcome space where corresponds to finding a marked state and corresponds to finding an un–marked state:
(7) 
We also have that , but this fact is not needed for the proof.
It is then easy to see that and thus a likelihood evaluation is equivalent to a query to . This means that we can solve Grover’s problem using the following algorithm.

Set the prior to be .

Set , which corresponds to pretending that an experiment was performed that found a marked entry.

Compute .

Output all such that .
The validity of this algorithm is easy to verify from (1) and it is clear that the posterior distribution is a uniform distribution over . Since and is uniform, all elements in the support of the posterior distribution have probability and thus Grover’s problem can be solved using Bayesian inference. This algorithm will succeed classically using queries to , rather than the queries required in the worst case scenario if a Bayesian framework is not adopted.
∎
This reduction of Grover’s problem to Bayesian inference brings with it tight lower bounds on the query complexity of solving the problem Boyer et al. (1996). We can exploit these bounds to show limitations on quantum systems ability to perform Bayesian inference and correct erroneous measurements that occur in the application of the method of Lemma 1. The following theorem states two such restrictions, which show that the method of Lemma 1 cannot be trivially improved nor can its failures be inexpensively corrected.
Theorem 1.
Let be a blackbox quantum update algorithm that performs a quantum Bayesian update on an arbitrary pure state using queries to the oracle and is heralded and has success probability for . The following are impossible.

A blackbox algorithm capable of performing a quantum Bayesian update of an arbitrary pure quantum state of the form that uses queries to that is heralded and has success probability .

A blackbox algorithm that requires queries to to undo the effects that applies to the arbitrary state upon a failed update.

A blackbox algorithm capable of performing a quantum Bayesian update of an arbitrary pure quantum state of the form that, for all , uses on average queries to .
Proof.
Seeking a contradiction, assume that there exists a quantum algorithm that can perform a quantum Bayesian update using queries that succeeds with probability for any likelihood function . Next, let us choose the likelihood function to be that used in (7) in the reduction proof of Lemma 2 and take . It is clear from Lemma 1 that must be chosen for this problem. Then by assumption the state , where , can be found with probability . Since each application of the algorithm requires queries and success is heralded, queries are needed on average to learn using amplitude amplification Brassard et al. (2002), which violates lower bounds for the average query complexity for Grover’s problem Boyer et al. (1996). Therefore algorithm , which is described in 1, is impossible.
Again seeking a contradiction, consider the following likelihood function with outcomes ,
(8) 
For each , can be computed using a single query to and vice versa, thus a query to this likelihood function is equivalent to a call to . Thus (1) gives that the posterior probability after measuring is
(9) 
Therefore measurements of suffice to amplify the probability from to .
Similarly, unless or . Since is a probability this is impossible. Therefore the posterior probability is monotonically increasing with the number of successful updates. Thus if we define and to be the components of the quantum state after quantum updates then is a monotonically increasing function of .
In practice, it would be unlikely that sequential measurements would all yield (i.e. give noisy information about the marked state), but the user of a quantum Bayesian updating algorithm can always pretend that this sequence of observations was obtained (similar to Lemma 2) in order to simulate the search. Given the observable variables follow this sequence, Lemma 1 shows that there exists a quantum algorithm that can perform each such update with probability of success
(10) 
since and .
If we were not able to correct errors then (10) shows that the probability of successfully inferring the marked state is since updates are needed; however, by assumption each failure can be corrected using queries. Therefore by attempting quantum Bayesian updates, correcting any errors that might occur and repeating until success, a successful update can be obtained with an average number of queries that is in
(11) 
because for any . Since successful quantum updates are made in the inference process, the marked state can be inferred within probability using queries to the likelihood function. A to the likelihood function is equivalent to a query to Grover’s oracle and thus error correction method (described in 2) is impossible.
Finally, the impossibility of method directly follows from Lemma 2 and lower bounds on Grover’s search. ∎
These impossibility results show that the quantum updating procedure of Low et al. (2014) and Lemma 1 cannot be improved without making assumptions about the underlying prior distributions or likelihood functions. From this we conclude that quantum Bayesian updating, as per Definition 1, is inneficient in general. This means that small quantum systems that attempt to store the prior and posterior vectors as a quantum state vector cannot do so efficiently, let alone output salient properties of the state, without making such assumptions.
This inefficiency is perhaps unsurprising as exact Bayesian inference is also classically inefficient. In particular, an efficient sampling algorithm from a distribution that is a close approximation to the posterior distribution would imply Dagum and Luby (1993). A quantum algorithm capable of efficient Bayesian inference for general models would similarly imply that , which is false under reasonable complexity theoretic conjectures.
Although it may not be surprising that quantum Bayesian updating is not generically efficient, it is perhaps surprising that both it and classical updating fail to be efficient for different reasons. Classical Bayesian updating fails to be efficient because it needs to store prior and posterior probabilities for an exponentially large number of hypotheses; however, its cost scales linearly with the number of updates used. In contrast, quantum Bayesian updating scales polynomially with the number of hypotheses considered but scales exponentially with the number of updates. This invites the question of whether it is possibile to combine the best features of quantum and classical Bayesian updating. We do so in the subsequent section, wherein we show how a classical model can be stored for the system that can be reverted to in the event that a failure is observed in a quantum Bayesian update.
Iii Semi–classical Bayesian updating
Approximations are therefore often needed to make both classical as well as quantum Bayesian inference tractable. However, the purpose of these approximations is very different. Classical methods struggle when dealing with probability distributions in high–dimensional spaces, and sophisticated methods like sequential Monte–Carlo approximations are often employed to reduce the effective dimension Liu and West (2001); Minka (2001); Van Der Merwe et al. (2000). However, the non–linear nature of the update rule and the problem of extracting information from the posterior distribution are not issues in the classical setting. Our quantum algorithm has the exact opposite strengths and weaknesses: it can easily cope with exponentially large spaces but struggles emulating the nonlinear nature of the update rule.
We attack the problem by making our quantum algorithm a little more classical, meaning that through out the learning process we aim to learn an approximate classical model for the posterior alongside the quantum algorithm. This classical model allowsus to approximately re–prepare the state should an update fail throughout the updating process. This removes the exponential scaling, but results in an approximate inference. We refer to this procedure as quantum resampling as it is reminiscent of resampling in sequential Monte–Carlo algorithms or other particle filter methods such as assumeddensity filtering Minka (2001). In order to prepare the distribution, we model the posterior distribution as a Gaussian distribution with mean and covariance equal to that of the true posterior. This choice is sensible because once the Gaussian distribution is specified, the Grover–Rudolph state preparation method Grover and Rudolph (2002) can be used to prepare such states as their cumulative distribution functions can be efficiently computed. Alternatively, for one–dimensional problems, such states could be manufactured by approximate cloning.
We are now equipped to define a semiclassical Bayesian update.
Definition 2.
A semi–classical Bayesian update of a prior state on , for a discrete observable variable , likelihood function and family of probability distributions parameterized by the vector , maps
We call this process semi–classical updating because it yields an approximate classical model for the posterior distribution. This model can take many forms in principle; as an example, we could consider this model to be a Gaussian distribution that has the same mean and standard deviation as the posterior distribution. Semi–classical Bayesian updating will be discussed in more detail in the following section, but for now we will focus on quantum Bayesian updating.
We need a means to measure the expectation values and components of the covariance matrix of the posterior for this method to work. We provide such a method, based on the Hadamard test, below.
Lemma 3.
Given a unitary operator such that , an observable and an estimate , there exists a quantum algorithm to estimate within error with probability at least using applications of and queries to an oracle such that .
Proof.
By following the reasoning in Lemma 1, we can prepare the following state using one query to and one application of :
(12) 
The probability of measuring is
(13) 
This probability can be learned within additive error using samples and hence can be learned within error using samples.
This probability can also be learned using the amplitude estimation algorithm. Amplitude estimation requires that we mark a set of states in order to estimate the probability of measuring a state within that set. Here we mark all states in (13) where the rightmost qubit is . The amplitude estimation algorithm then requires queries to and the above state preparation method to estimate the probability to within error and store it in a qubit register Brassard et al. (2002). Amplitude estimation has a probability of success of at least . The result then follows from taking . ∎
We now turn our attention to estimating the mean and covariance of the posterior distribution that arises from quantum updating. This is not quite a trivial application of Lemma 3 because our method for performing the update is nonunitary, which violates the assumptions of the Lemma. We avoid this problem by instead estimating these moments in a two–step probability estimation process. This approach is described in the following corollary.
Corollary 1.
Assume that is a vector containing each and each evaluated over the prior and where is the operator corresponding to or depending on the index . The mean and covariance matrix can be computed within error in the max–norm using queries to .
Proof.
Our method works by classicially looping over all the components of the vector, which we denote . For each , we then need to prepare the following state conditioned on evidence to compute the corresponding probability
(14) 
where is of the form or depending on the value of .
We cannot directly apply the previous lemma to learn the requisite values because the method for preparing the posterior probability distribution is non–unitary. We address this by breaking the parameter estimation process into two steps, each of which involves learning a separate probability that we call and . Let be the probability of performing the quantum Bayesian update. Let be the probability of both performing the update and measuring the right most qubit in (12) to be . This probability is
(15) 
where is either of the form or depending on the index and refers to the expectation of a quantity in the posterior state. Therefore can be computed from and via
(16) 
If we estimate and within error then the error in is from calculus since . Therefore can be estimated to within error if . Bounds on the cost of amplitude estimation give the cost of this to be Brassard et al. (2002)
(17) 
The result then follows from noting that there are different values of that need to be computed to learn the expectation values needed to compute the components of the posterior mean and covariance matrix. ∎
This shows that if we require modest relative error (i.e. ) and is reasonably tight then this process is highly efficient. In contrast, previous results that do not use these factors that incorporate apriori knowledge of the scale of these terms may not be efficient under such assumptions.
Below we combine these ideas to construct an online quantum algorithm that is capable of efficiently processing a series of pieces of data before outputting a classical model for the posterior distribution in the quantum device. This result is key to our argument because it provides a result that one can fall back on if an update fails, thereby removing the problem of exponentially shrinking success probability at the price of only retaining incomplete information about the posterior distribution.
Theorem 2.
Let be a family of approximations to the posterior distribution parameterized by the posterior mean and the posterior covariance matrix and be a set of observable variables. Then a semi–classical update of a quantum state can be performed using a number of queries to that is in
Proof.
The algorithm is simple.

Perform quantum Bayesian updates, but without measuring the qubits that determine whether the updates succeed or fail.

Use the method of Corollary 1 to learn the mean and covariance matrix of the quantum posterior distribution.

Return these quantities, which give a parameterization of the approximation to the posterior distribution.
After step 1, we have from the independence of the successes that the probability of all updates succeeding is . Thus step 2 can be performed using preparations of the posterior state from Corollary 1. Since each such preparation requires queries to the total query complexity required to learn the posterior mean and variance is
(18) 
Finally, since the algorithm outputs the mean and covariance matrix of the posterior distribution, it outputs a function that captures (to within error ) the first two moments of the posterior distribution. Thus the algorithm clearly performs a semi–classical update as per Definition 2. ∎
The complexity of the above approximate quantum inference algorithm cannot be easily compared to that of exact Bayesian inference because both algorithms provide very different pieces of information. Until very recently, no natural analogue of our quantum method could easily be found in the literature. The result of Wiebe et al. (2015) provides such a classical analogue. The classical query complexity of their algorithm is quadratically worse in its scaling with .
Although we obtain a quadratic advantage in the scaling with , it would be nice to obtain further algorithmic advantages using amplitude amplification. Further advantages can be obtained in cases where the probabilities and are small by using amplitude amplification to boost these probabilities and then work backwards to infer the non–boosted probabilities. Below we formally prove a theorem to this effect that formalizes a similar claim made informally in Wecker et al. (2015).
Theorem 3.
Let be a unitary operator such that where for , and let be a projector such that and . Then can be estimated to within error using applications of with high probability.
Proof.
Our proof follows the same intuition as that of the proof of amplitude estimation in Brassard et al. (2002) except rather than performing amplitude estimation on we use amplitude amplification to first boost the probability and then use amplitude estimation to learn the boosted probability. The actual value of is then inferred from the amplified value of learned in the amplitude estimation step.
First by following Lemma 1 in Brassard et al. (2002) we can apply a sequence of reflection operators that contains applications of to form a unitary operation such that performs, up to a global phase,
(19) 
Since is a unitary operation, amplitude estimation can be used to learn to within error by using Theorem 12 of Brassard et al. (2002) with probability at least using applications of . Thus using the Chernoff bound, can be estimated within the same error tolerance using operations with high probability.
Since contains operators, the total number of applications of needed to infer this is . However, although is inferred within error , this does not imply that is. If we define this estimated value to be and assume that then
(20) 
If there is an error of in then Taylor analysis implies that
(21) 
Since the error is . Hence if we desire error in then it suffices to take . Thus applications of are needed to infer to within error .
Although this may seem to suggest that taking large always leads to a better inference of , this is not necessarily true for this inversion process. This is because if
(22) 
then (20) no longer holds. Ergo for small . Since the user does not know , the best that can be done is to take since taking also guarantees (22) does not hold for . Therefore the number of applications of , for , needed to learn within error with high probability scales as
(23) 
as claimed. ∎
As an additional note, this method described in this section is not limited to tracking the values of static latent variables. If the latent variable has itself explicit time dependence then the above approach can be modified to robustly track its variation in time. This is discussed in more detail in Appendix C.
Iv Adaptive experiment design
In science and engineering, inference problems frequently involve decision variables that can be set in order to optimize the performance of the algorithm. For example, in the phase estimation algorithm such a decision variable may be the amount of time that the system is allowed to evolve for. Finding locally optimal parameters for inference can be computationally challenging (especially for online learning problems). Here, we show that our algorithm allows for quantum computing to be used to perform Bayesian experiment design with significant advantages over classical methods.
In practice, Bayesian experiment design is often posed in terms of finding experiments which maximize a utility function such as the information gain or the reduction in a loss function. Once a utility function is chosen, the argmax can be found by gradient ascent methods provided that the derivatives of the utility can be efficiently computed. In particular, since the reduction in the quadratic loss is given by the posterior variance, our algorithm allows for computing gradients of the corresponding utility function.
Formally, we need to define two quantities: the loss function and the Bayes risk. In doing so, we will assume without loss of generality that the model parameters are renormalized such that all components of lie in . The loss function represents a penalty assigned to errors in the in our estimates of . We consider here the multiparameter generalization of the meansquared error, the quadratic loss. For an estimate ,
(24) 
Letting be the Bayesian mean estimator for the posterior and considering the singleparameter case,
(25) 
Having defined the loss function, the risk is the expectation of the loss over experimental data, , where is taken to depend on the experimental data. The Bayes risk is then the expectation of risk over both the prior distribution and the outcomes,
(26) 
The Bayes risk for the quadratic loss function is thus the trace of the posterior covariance matrix, averaged over possible experimental outcomes. We want to find that minimizes the Bayes risk, so that a reasonable utility function to optimize for is the negative posterior variance,
(27) 
The application of our algorithm is now made clear: like classical particle filtering methods, our algorithm can estimate expectation values over posterior distributions efficiently. Thus, can be calculated using quantum resources, including in cases where classical methods alone fail. In the finite dimensional setting that we’re interested in we simply replace these integrals by sums over the corresponding variables. The derivatives of can then be approximated for small but finite as
(28) 
Thus if consists of different components then calculations of the utility function are needed to estimate the gradient for a finite value of . This is the intuition behind our method, the performance of which is given in the following theorem.
Theorem 4.
Assume that the prior distribution has support only on the interval and that the observable varible has support only on distinct values; then each component of the gradient of can be computed within error using on average queries to the likelihood function and the prior, for .
Proof.
The utility function can be directly computed on a quantum computer, but doing so is challenging because of the need to coherently store the posterior means of the distribution. We simplify this by expanding the square in (27) to find
(29) 
We then compute each of these terms individually and combine the results classically to obtain an estimate of .
The double integral term in (29) is the easiest to compute. It can be computed by preparing the state
(30) 
The probability of measuring the right most qubit to be is
Therefore the desired probability can be found by estimating the likelihood of observing divided by the total number of outcomes . A direct application of amplitude estimation gives that the expectation value can be learned within error using preparations of the initial state and evaluations of the likelihood function.
Since the probability of success is known to be bounded above by , Theorem 3 implies that state preparations are needed to estimate the integral if we define to be a reflection operator that imparts a phase if and only if the ancilla qubit equals .
The numerator can be estimated in exactly the same fashion, by preparing the state
(31) 
Note that the numerator, , is not : it is in fact as seen by the Cauchy–Schwarz inequality and
(32) 
The triple integral in (29) is much more challenging. It can be expressed as
The integral over in this expression is difficult to compute in superposition. So instead, we forgo directly integrating over using the quantum computer and instead compute the integrand quantumly and classically integrate over . In many models will be small ( is not uncommon) hence a polynomial reduction in the scaling with will often not warrant the additional costs of amplitude amplification.
For fixed , the first step is to compute , which can be estimated by preparing the state
(33) 
and estimating, , the probability that the right–most qubit is , which is the required probability. This can be learned within error using amplitude estimation, which requires queries to the initial state and the likelihood oracle Brassard et al. (2000).
For simplicity let us define the integral to be and the approximation to the integral as . We then see from the triangle inequality that if we estimate the denominator to within error then
(34) 
Therefore under these assumptions it is necessary to estimate to within error to achieve error . We can accelerate this inference process by observing that
(35) 
since . Theorem 3 can then be used to estimate within error using queries. Since we need error the number of query operations needed to infer within error is in . This process needs to be repeated classically times so the total cost is for this step as well. Thus we see from (34) that the total error can be made less than , with high probability, using a number of queries that scales as .
The analysis of the quadrouple integral is exactly the same and requires queries on average. Thus the cost of evaluating the utility function to within error with high probability is .
Given an algorithm that can compute using a number of queries that scales as , we can estimate the derivative using a centered difference formula. In particular we know that
(36) 
where and is a vector parallel to the unit vector . Since we cannot compute exactly, the error we want to bound is
(37) 
where is the approximation to the utility function that has error at most . The error is then
(38) 
Since is a free parameter that we will choose to make both sources of error equivalent. This corresponds to . This gives an overall error of
(39) 
If we wish to make this error then it suffices to take . Since the cost of computing within error with high probability is the cost estimates follow. ∎
This shows that we can use quantum techniques to achieve a polynomial speedup over classical methods for computing the gradient using sampling, which would require queries. It is also worth noting that high–order methods for estimating the gradient may be useful for further improving the error scaling.
Another interesting feature of this approach is that we do not explicitly use the qubit string representation for the likelihood to prepare states such as (33). Similar states could therefore also be prepared for problems such as quantum Hamiltonian learning Wiebe et al. (2014c) by eschewing a digital oracle and instead using a quantum simulation circuit that marks parts of the quantum state that correspond to measurement outcome being observed. This means that these algorithms can be used in concert with quantum Hamiltonian learning ideas to efficiently optimize experimental design, whereas no efficient classical method exists to do so because of the expense of simulation.
V Quantum Bayesian updating using repetition codes
While we have addressed a semi–classical form of learning for quantum Bayesian inference, an interesting remaining question is whether the form of quantum Bayesian inference that we consider has a well defined classical limit. The hope would be that such a protocol would also be an approximate Bayesian method, but would not be susceptible to the probabilistic failures that plague the quantum approach. We can reach such a limit by using a repetition code to perform a protocol that is similar to semi–classical updating, but does not involve storing classical information. We also focus on the onedimensional case in the following, but generalization to the multidimensional case is straightforward.
The repetition code that allows us to reach the classical limit of the quantum algorithm is trivial:
(40) 
In order to learn the mean from such a state without destroying it, we need to add an additional register that stores an estimate of the meanvalue to a fixed number of bits of precision. This can be achieved using a simple arithmetic circuit. We denote this state as
(41) 
where is an approximation to the mean that is truncated to give error . For simplicity, we drop the explicit dependence of on in the following.
Let be the true mean. Then as each of the distributions over the constituent is independent and assuming that , the Chernoff bound states that
(42) 
Thus the probability of measuring a mean that deviates more than from is at most if
(43) 
This implies that for every and every discretization error there exists a value of such that the probability of measuring the discretized mean to be is at least .
Let then
(44) 
Thus up to error , we can treat the state after learning the mean as identical to the state that existed before learning . Ergo despite the fact that the used in the distribution are no longer identically distributed, we can treat them as if they were while incurring an error of at most in the estimate of . From the triangle inequality, it is then straight forward to see that after such steps that the total error incurred in the final state (as measured by the trace distance) is at most , which can be made at most by choosing
(45) 
This in turn means that the error in the inference of after steps is at most . The exact same argument can be applied to learn the mean–square value of and so the standard deviation can be learned in a similar fashion.
If is sufficiently large, then any branches that fail can be immediately repopulated by a distribution from a two–parameter family of distributions . This further carries an advantage because it does not necessitate that the entire distribution be approximated at each iteration, unlike semi–classical updating.
This shows that a redundant encoding can be used in order to protect the low–order moments against the effects of measurement. Therefore means that even if some updates fail then these results can be erased and replaced with a Gaussian approximation to the posterior distribution (for example). An explicit classical register is not needed in this approach, although since the entanglement of the expectation value register with the remaining qubits approaches zero. In this sense, it becomes a classical register and this result can also be thought of as an examination of the classical limit of quantum Bayesian updating.
While this shows that repetition codes can allow the algorithm to proceed without classical memory, it makes substantial demands on the memory. For even modest problems, it is likely to require thousands of copies of the state in order to be able to resist the effects of measurement back action on the state. This shows that while error correction can allow quantum systems able to learn efficiently without classical memory, the resulting systems will seldom be small. This suggests that there may be a tradeoff between system size and robustness that may make learning in small quantum systems highly challenging.
Vi Conclusion
Our main contribution of this paper can be thought of as an analysis of the ability of small quantum systems’ capacity to learn. In it we have examined a class of quantum learning algorithms that require only logarithmic memory to update a register that stores its beliefs about a latent variable that it must infer from a set of observable variables that whose likelihoods are only known through access to a quantum oracle. We show that such algorithms cannot in general be efficient, but provide a semi–classical algorithm that uses classical memory to circumvent this problem within the context of approximate Bayesian inference.
Our semi–classical algorithm has a number of performance advantages over classical methods. It also can leverage quantum superposition to provide quadratic advantages for experiment design and also can be used to track the motion of time–dependent latent variables. We further demonstrate the need to store the model in classical memory is in principle superflous because a quantum repetition code can be used to robustly encode this information in the quantum state. This suggests that while small quantum systems may not be able to efficiently learn (especially in an online setting), redundant information can be used to protect the knowledge gained by the quantum system against the potentially destructive impacts of the non–linear transformations required by Bayesian inference. This supports the conjecture that error correction is intimately linked to learning.
Although our work suggests that small quantum systems may face substantial difficulties when trying to perform Bayesian inference in an oracular setting, much more work is needed in order to provide a complete answer to the question. In particular, a firm definition is needed in order to address the question of what learning even means for quantum systems outside of the confines of the definition we implicitly assume through our consideration of Bayesian updating. A suitable answer to this question may not only shed light on the nature of learning in physical systems but also help us come to grips with the limitations that arises from trying to reason using agents whose ephemeral memories are kept in quantum states of matter.
Acknowledgements.
We would like to thank J. Combes and J. Yard for valuable feedback and discussion as well as J. Emerson for suggesting the idea of quantum learning agents.References
 Shor (1994) P. W. Shor, in Foundations of Computer Science, 1994 Proceedings., 35th Annual Symposium on (IEEE, 1994) pp. 124–134.
 Lloyd et al. (1996) S. Lloyd et al., Science 273, 1073 (1996).
 Childs et al. (2003) A. M. Childs, R. Cleve, E. Deotto, E. Farhi, S. Gutmann, and D. A. Spielman, in Proceedings of the thirtyfifth annual ACM symposium on Theory of computing (ACM, 2003) pp. 59–68.
 Harrow et al. (2009) A. W. Harrow, A. Hassidim, and S. Lloyd, Physical Review Letters 103, 150502 (2009).
 Aaronson (2007) S. Aaronson, Proceedings of the Royal Society A: Mathematical, Physical and Engineering Science 463, 3089 (2007).
 Granade et al. (2012) C. E. Granade, C. Ferrie, N. Wiebe, and D. G. Cory, New Journal of Physics 14, 103013 (2012).
 Ferrie and Granade (2014) C. Ferrie and C. E. Granade, Physical Review Letters 112, 130402 (2014).
 Aïmeur et al. (2006) E. Aïmeur, G. Brassard, and S. Gambs, in Advances in Artificial Intelligence (Springer, 2006) pp. 431–442.
 Wiebe et al. (2014a) N. Wiebe, A. Kapoor, and K. M. Svore, arXiv preprint arXiv:1412.3489 (2014a).
 Wiebe et al. (2014b) N. Wiebe, A. Kapoor, and K. Svore, arXiv preprint arXiv:1401.2142 (2014b).
 Lloyd et al. (2013) S. Lloyd, M. Mohseni, and P. Rebentrost, arXiv preprint arXiv:1307.0411 (2013).
 Lloyd et al. (2014) S. Lloyd, M. Mohseni, and P. Rebentrost, Nature Physics 10, 631 (2014).
 Boixo et al. (2015) S. Boixo, G. Ortiz, and R. Somma, The European Physical Journal Special Topics 224, 35 (2015).
 Low et al. (2014) G. H. Low, T. J. Yoder, and I. L. Chuang, Physical Review A 89, 062315 (2014).
 Ozols et al. (2013) M. Ozols, M. Roetteler, and J. Roland, ACM Transactions on Computation Theory (TOCT) 5, 11 (2013).
 Brassard et al. (2002) G. Brassard, P. Hoyer, M. Mosca, and A. Tapp, Contemporary Mathematics 305, 53 (2002).
 Grover (1996) L. K. Grover, in Proceedings of the twentyeighth annual ACM symposium on Theory of computing (ACM, 1996) pp. 212–219.
 Boyer et al. (1996) M. Boyer, G. Brassard, P. Høyer, and A. Tapp, arXiv preprint quantph/9605034 (1996).
 Dagum and Luby (1993) P. Dagum and M. Luby, Artificial Intelligence 60, 141 (1993).
 Liu and West (2001) J. Liu and M. West, in Sequential Monte Carlo Methods in Practice, edited by D. Freitas and N. Gordon (SpringerVerlag, New York, 2001).
 Minka (2001) T. P. Minka, in Proceedings of the Seventeenth conference on Uncertainty in artificial intelligence (Morgan Kaufmann Publishers Inc., 2001) pp. 362–369.
 Van Der Merwe et al. (2000) R. Van Der Merwe, A. Doucet, N. De Freitas, and E. Wan, in NIPS (2000) pp. 584–590.
 Grover and Rudolph (2002) L. Grover and T. Rudolph, arXiv preprint quantph/0208112 (2002).
 Wiebe et al. (2015) N. Wiebe, C. Granade, A. Kapoor, and K. M. Svore, arXiv preprint arXiv:1511.06458 (2015).
 Wecker et al. (2015) D. Wecker, M. B. Hastings, N. Wiebe, B. K. Clark, C. Nayak, and M. Troyer, arXiv preprint arXiv:1506.05135 (2015).
 Brassard et al. (2000) G. Brassard, P. Hoyer, M. Mosca, and A. Tapp, arXiv preprint quantph/0005055 (2000).
 Wiebe et al. (2014c) N. Wiebe, C. Granade, C. Ferrie, and D. Cory, Physical Review Letters 112, 190501 (2014c).
 Isard and Blake (1998) M. Isard and A. Blake, International Journal of Computer Vision 29, 5 (1998).
Appendix A Asymptotic Stability of Updating
Interestingly, this process of classically learning a model for the posterior need not be repeated forever. If the true model has sufficient support in the final posterior then classical feedback is irrelevant because the quantum algorithm will converge to the true model as if for all , regardless whether success or failure is observed. This is summarized in the following theorem.
Theorem 5.
There exists such that if then the method of Lemma 1 converges to if the failure and success branches are treated equivalently and