On quantum backpropagation, information reuse, and cheating measurement collapse
Authors: Amira Abbas
Robbie King
Hsin-Yuan Huang
William J. Huggins
Ramis Movassagh
Dar Gilboa
Jarrod Ryan McClean
Venue: NeurIPS 2023 spotlight (2023)
Keywords: Backpropagation
quantum computing
shadow tomography
gentle measurement
TL;DR: We prove that resources to compute gradients of parameterized quantum models will not scale as efficiently as neural networks equipped with backpropagation, by reduction to a well-known problem in quantum information theory.

Abstract: The success of modern deep learning hinges on the ability to train neural networks at scale. Through clever reuse of intermediate information, backpropagation facilitates training through gradient computation at a total cost roughly proportional to running the function, rather than incurring an additional factor proportional to the number of parameters -- which can now be in the trillions.  Naively, one expects that quantum measurement collapse entirely rules out the reuse of quantum information as in backpropagation. But recent developments in shadow tomography, which assumes access to multiple copies of a quantum state, have challenged that notion.  Here, we investigate whether parameterized quantum models can train as efficiently as classical neural networks. We show that achieving backpropagation scaling is impossible without access to multiple copies of a state.  With this added ability, we introduce an algorithm with foundations in shadow tomography that matches backpropagation scaling in quantum resources while reducing classical auxiliary computational costs to open problems in shadow tomography. These results highlight the nuance of reusing quantum information for practical purposes and clarify the unique difficulties in training large quantum models, which could alter the course of quantum machine learning.

On quantum backpropagation, information reuse, and cheating measurement collapse
Amira Abbas Google Quantum AI, Venice, California 90291, USA University of KwaZulu-Natal. South Africa QuSoft, University of Amsterdam, Science Park 123, 1098 XG Amsterdam, The Netherlands
Robbie King
Department of Computing and Mathematical Sciences, Caltech, Pasadena, CA 91125, USA
Hsin- Yuan-Yuan Ba Huang
Department of Computing and Mathematical Sciences, Caltech, Pasadena, CA 91125, USA Institute for Quantum Information and Matter, Caltech, Pasadena, CA 91 125, USA
William J. Huggins
Google Quantum AI, Venice, California 90291, USA
Ramis Movassagh Google Quantum AI, Venice, California 90291, USA
Dar Gilboa
Google Quantum AI, Venice, California 90291, USA
Jarrod R. McClean
Google Quantum AI, Venice, California 90291, USA jucclean@@oogle.com
Abstract
The success of modern deep learning hinges on the ability to train neural networks at scale. Through clever reuse of intermediate information, backpropagation facilitates training through gradient computation at a total cost roughly proportional to running the function, rather than incurring an additional factor proportional the number of parameters which can now be in the trillions. Naively, one expects that quantum measurement collapse entirely rules the reuse of quantum information as in backpropagation. But recent developments in shadow tomography, which assumes access multiple copies quantum state, have challenged that notion. Here, we investigate whether parameterized quantum models can train efficiently as classical neural networks. We show that achieving backpropagation scaling is impossible without access multiple copies of state. With this added ability, we introduce an algorithm with foundations in shadow tomography that matches backpropagation scaling in quantum resources while reducing classical auxiliary computational costs to open problems shadow tomography. These results highlight the nuance of reusing quantum information for practical purposes and clarify the unique difficulties in training large quantum models, which could alter the course of quantum machine learning.
37th Conference on Neural Information Processing Systems (NcurIPS 2023).

---

Update needed
Update ieneded
Update ifneeded
learning:
Rotute
Rotute
Apply operations
Impal staless
Thresood check
Threshuld
Rotate Oppolylog M
Threshald check
Ol Oppolylog( MY
O(Mpolylog(
Oppolylog( (Mf))
check
Forward:
F(8)
Backward:
[F
Figure Quantum backpropagation algorithm. Our proposal for quantum backpropagation consists of an online shadow tomography protocol, coupled with a threshold search procedure [Aaron- son al., 2018, Bädescu and O'Donnell, 2021]. The algorithm Opolyyog (M)) of which roughly n. batches are needed, where is n qubit quantum state. A classically constructed hypothesis state a is also necessary for the algorithm. Crucially, quantum states and the hypothesis state are rotated before each threshold check, to rotate through the layers of a quantum neural network F(0), E RM and reuse information for gradients. This enables a cost reduction from ( polylog.M) to O(M polylog to compute the full gradient. For convenience, we suppress precision factors which scale as O(1/E*) for this proposal.
executed in batches of size
Introduction
Computing gradients through backpropagation is crucial to the success of modern deep neural net- works. Rather than a naive manifestation the chain rule to compute gradients, backpropagation leverages white-box knowledge of a computational graph, well as intermediate values, asymptot- ically improve run times [Goodfellow et al., 2016, Rumelhart et al., 1986, LeCun et al., 2015, 1989, Bengio et al., 2014]. Remarkably, computing the gradient of, say, neural network function with respect to all its parameters, can be done at a total cost roughly proportional to running the function, instead of incurring an additional factor proportional to the number of parameters. This relative scaling, owed to backpropagation, has facilitated the training of very deep networks, with parameter counts now in order of 10 accompanied with unparalleled empirical success [Goodfellow et al., 2016, Szegedy et al., 2017, landola et al., 2016, Wu et al., 2019]. When considering the number of function calls required to compute gradients, backpropagation in classical circuits remains expo- nentially more efficient with respect to the number of parameters, than the best known algorithms for determining gradients of parameterized quantum circuits with without the aid of quantum computer [Gilyén et al., 2019, Van Apeldoorn et al., 2020, Brandão et al., 2017, Jordan, 2005, Schuld and Killoran, 2022]. Nevertheless. the allure of large-scale models inspires the need for efficient training of parameterized quantum models [Kandala et al.. 2017, Farhi et al., 2014, Cerezo et al., 2021], which frequently arise in fields like quantum machine learning and quantum chemistry. But backpropagation scaling cannot be matched, practically reaching overparameterized regimes may be impossible, even before accounting for additional challenges like barren plateaus [McClean et al., 2018, Wang et al., 2021, Cerezo et al., 2020]. Since trainability influences the power and applicability of model, this could radically shift the current trajectory of preferred quantum models.
In this work, we provide an operational definition of backpropagation. and subsequently determine its feasibility for parameterized quantum models. We investigate learning algorithms with and without quantum memory, where the former is able to store a product of multiple copies of a particular state, perform joint quantum operations followed by an entangled measurement. Whereas, learning algorithm without quantum memory can only perform operations on each copy, implement a (conditional) measurement, and use the resulting classical data. Without access to multiple copies, we highlight that all known methods to compute gradients of simple variational models, do not achieve an overhead in line with backpropagation, unless one considers very special cases. Interestingly, closely related probabilistic classical analogues can exhibit backpropagation scaling, which points out that the barrier in the quantum setting is due to quantum phenomena. an attempt to mimic classical backpropagation, which leverages information reuse to produce a favourable scaling, we lean similar concept a quantum setting, namely gentle measurements [Aaronson, 2019, Aaronson and Rothblum, 2019, Bádescu and O' Donnelll 2021]. When combined with online learning [Aaronson

---

et al., 2018], this technique has proven useful in problems like shadow tomography as it aims to conserve quantum resources, but has yet to be explored in the context of backpropagation. In an information-theoree sense, when access to multiple copies of a state is provided, a modification of existing shadow tomography routines enables backpropagation scaling if one restricts costs to the quantum overhead and ignores the classical cost incurred to implement known shadow tomography schemes. We present our proposed quantum backpropagation algorithm in Figure which highlights the reduction in quantum resources due to the ability to exploit structure in quantum neural network and reuse information through gentle measurement. Unfortunately, the true computational efficiency of our scheme remains open question and rule out general strategy based on gentle measurement alone, by linking to computational models known to be more powerful than those contained in the complexity class of BQP [Aaronson et al., 2016]. Despite failure to achieve backpropagation scaling in this general setting, the construction is suggestive of approximate or restricted models that may yield the desired scaling without violating complexity-theoreii bounds. This avenue remains rich for future work. We hope that these results illustrate the difficulty of replicating backpropagation scaling in parameterized quantum circuits and inspires the development of alternative quantum models that can train at scale.
2 Backpropagation scaling
comprehensive overview of gradient evaluation, given by automatic differentiation on classical computers, can be found in Griewank and Walther [2008]. The key advantage, however, can be summarized in one sentence: computational and memory resources employed compute gradients of a function are bounded multiples of those used to compute the function. We use this bound to define the requirements for backpropagation scaling.
Definition 1 (Backpropagation scaling). Given parameterized function F(Ø), A E RM, let (0) be an estimate of the gradient vector accurate to within some constant ε in the infinity norm. The total computational cost incurred to obtain F' (0) with backpropagation is bounded such that
TIME(F" S ct TIME(F(O)),
and
MEMORY(F'(0) < Cm (F))) where Ct, Cm polylog(M) (M), and TIME(-) and MEMORY() capture the time and space complexity respectively, for either computing the function F its gradient F".
(2)
As further specification of backpropagation scaling in Definition 1, one can specify whether one achieves this scaling in quantum resources, classical resources, or all resources. While it is, of course, the goal to achieve this scaling in all resources, the distinction remains relevant due to the ability to leverage classical resources in order to improve the scaling in quantum resources, which we elaborate on in Section 5. In purely classical models, like neural networks, the overhead for both time and memory can be constant, and typically by small factor. This efficiency has been instrumental for training very large models and is arguably the main contributor to the success of modern day machine learning. Given that variational quantum models, which utilize parameterized quantum circuits, are believed to be the most promising candidates to solve quantum machine learning tasks, we investigate their ability to reproduce this scaling.
Variational quantum models
Variational algorithms have become go-to approach when looking to solve various optimization and machine learning problems on quantum devices [Cerezo al., 3021]. We present a slightly restricted model for case of analysis which still covers very broad range of practical scenarios. Notably, if backpropagation scaling cannot be achieved in this simplified setting, it is unlikely to succeed in a more sophisticated one.
Definition 2 (Simple variational model). Consider an initial quantum state p and a quantum circuit with M parameterized operations U,(0), e- -i,,,, where each P, is Pauli operator acting on up to n qubits. We define a simple variational quantum model as the parameterized function
F(0) Tr(Op(O)),
(3)
3

---

where O is a Hermitian and unitary observable, and the quantum state p(0) is expressed as p(0) ((O)pU(() In the most general case, will be an unknown quantum state that we refer to as the quantum data setting, but we will also be interested in the simplified setting where p(0)
({)(0) (x) and (bb(0) = (()) (0) 60m = I U,(0,) 8o
In the simplified setting, the hth gradient component of F(0) can be expressed as
[F)), 2 Re
(o)
I 10
II m=k+1
18 Pm
(-iPk)
II
c 18:
10)
(4)
It becomes clear that computing all M components involves large number of common operations. At face value, one might think it straightforward to exploit this overlap of operations to gain computa- tional efficiency, as is done classically. The problem is that intermediate information in quantum circuit not easily retrievable without consequence, which investigated in the following section.
4 Learning algorithms without quantum memory
Recall that a learning algorithm without quantum memory would perform operations and measure- ments on each individual copy of quantum state. In this regime, which is prominent in current quantum machine learning settings, we have the following proposition.
Proposition 3 (Backpropagation scaling is impossible for quantum data using single copies). Given the quantum data setting where one seeks to train a variational model using copies of the unknown state p and the additional constraint of no quantum memory, then buckpropagation scaling is not possible in the general case.
Proof. Take the Pauli circuit model above and let us consider the case of possible Pauli operators P3 on qubits, such that M = (44)). If we take the special case of quantum data and initializing all 8, = 0, then the gradient with respect to each of the parameters is given by the expected value of all possible Pauli operators n qubits on the unknown quantum state p. up to a small constant. If no quantum memory is available, that is, we only have the ability to perform mcasurements on single copies a time, then by Chen et al. [2022, Corollary 5.9], the minimal number of copies of p lower bounded by 22(2 /E?) in order to predict all Pauli operators to at most e-error with probability 2/3. Hence, backpropagation scaling not possible in general in the single copy case.
Notably, Proposition 3 is based on an information-theoree the simplified case, / = 10)(0), or even when p simply guaranteed to be a pure state generated by polynomial sized circuit, which we detail in Appendix C. Hence, for the simplified case and polynomial complexity pure state cases, we must turn to computational arguments. Furthermore, if it were possible to find polynomial time algorithm for the approach in Appendix C. then it would be possible to efficiently clone pseudo-randon states, which is not believed to be possible [Ji et al., 2018], despite the fact that they pure states generated by polynomial sized circuits (see Appendix C.2). The following remark aims to clarify the status of current methods for approaching this problem.
separation that does not generalize to
Remark 4 (Current gradient methods fail to achieve backpropagation scaling). Given a variational model (()) defined in (3) with time complexity
TIME(F(0) = ((M/**),
for some integer l and precision E, then all known schemes to estimate the gradient of F(O) to the same precision, do not, in general, achieve time complexity in line with backpropagation scaling.
We briefly explain why known gradient methods fail, but defer details to Appendix A. A promising gradient algorithm put forth in Jordan [2005] requires only a single black-box query to a function to estimate its full gradient with desired precision. But, as shown in Gilyén et al. [2019], when considering variational models, a different query model must be applied and the original single- query advantage becomes unattainable. The authors derive lower bounds requiring a quantum computational cost of (M M
/e²) and in high precision regime, O(M / M M/s) is worst-case

---

optimal [Huggins et al., 2021] when using black-box simplified model of (()). In other contexts, it is also sometimes argued that the simultaneous perturbation stochastic approximation (SPSA) algorithm is computationally efficient since it requires two function evaluations to estimate the gradient, irrespective of M. This seemingly satisfies the scaling required, however, as M increases, the variance of the gradient estimate increases and, thus, to counteract this, either a smaller learning rate must be used increasing the number of optimization steps or more samples are needed to estimate the gradient with an appropriate accuracy at every step. We derive a sample complexity bound in Appendix A.2.3 which demonstrates SPSA's inability to exhibit backpropagation scaling. Thus far, other sampling schemes constructed to estimate the gradient of F F(),, like the parameter-shin rule, perform destructive measurements that typically only retrieve a partial amount of information for one component of the gradient. As result, reducing the infinity norm error in the gradient with reasonable probability, has a cost that scales like converging each component, i.e.
(IME(F((O)) & M (F()(F(O))
(5)
= =Ö(M²/E*)
(6)
which unfortunately, does not achieve backpropagation scaling.
While this quadratic dependence the number of parameters may not seem problematic, linear dependence was the necessary catalyst in the age of modern deep learning, with overparameterized networks that perform exceedingly well practical tasks. We illustrate the consequences of quadratic scaling in Appendix A.2, Figure 2, where one could wait up to a day to evaluate a single gradient estimate of model with fewer than 10 000 parameters.
But perhaps neural networks are not fair benchmark. One could dig deeper in automatic differenti- ation literature to investigate whether a direct classical analogue for these parameterized quantum circuits attains hackpropagation scaling. Interestingly, particular analogue can.
Proposition 5 (Classical analogue achieves backpropagation scaling). Parameterized Markov chains, which are much closer classical analogues to variational models than neural networks, exhibit buckpropagation scaling.
We detail the proof and scaling comparison in Appendix B by drawing an analogy between quan- tum and classical probabilistic states. Under some reasonable assumptions on the set of classical operations, the desired scaling is indeed possible in analogous classical parameterized stochastic processes. The formulation of this classical-quantum analogy allows us to probe the root cause of why backpropagation scaling is so difficult obtain in the quantum variational setting. The origin of the challenge lies within quantum measurement collapse and the inability to read out intermediate states while continuing a computation, rather than the probabilistic formulation of the problem. In the classical setting, one is always promised to be in computational basis state, making it possible to do perfect measurements destrructively at intermediate steps. It remains an interesting open question to better understand the performance separation on practical tasks between quantum variational methods and this type of classical analogue, given the advantage trainability of the latter.
Although Proposition 3 presents a strict lower bound ruling out backpropagation in the quantum data case with single copies, this leads one wonder whether backpropagation scaling is possible when one has access to multiple copies. Moreover, destructive quantum measurements are the inhibitor of backpropagation scaling in single copies, so perhaps there is some middle ground where one could perform measurements that are only partially destructive on multiple copies. This idea has led breakthroughs in the shadow tomography problem, which we examine next in the context of backpropagation.
5 Reusing multiple copies through gentle measurement
By allowing access multiple copies of p. it is especially interesting note that gentle measurements can facilitate backpropagation scaling in all resources, when considering the special case outlined in Proposition 3. We first define gentle measurement, followed by the special case construction.
Definition 6 (Gentle measurement). Fix a subset of quantum mixed states S. A measurement F is a-gentle on S if for every state p E S, and every outcome y of F, the pest-selected state PF=y obeys
||er=y
el1 S a,
where E [0, 1]. Hence, the smaller the a, the less damage incurred by p.
5

---

Proposition 7 (A special case variational model achieves backpropagation scaling). Given a vari- ational model F(0) tr (U))) where (()) II - V for some fixed unitary V, setting to zero and = I, the tthh gradient component may be written as
F' [0) Re (Tr(VoV'
Im (Tr[VpViP.))
(7)
Then all M gradient components can be estimated to within a fixed precision e using (log(MM) /=*) function calls, and thus,
TIME(F (0) - ((oo
which is in line with backpropagation scaling.
With use of an ancilla qubit and a slightly modified circuit, the imaginary components of which represent gradient components, can be estimated with O M/E*) copies of for all k via application of V and two-copy Bell measurements of the resulting state that harness gentleness. Similarly, using (log(MM)EE)) copies along with the magnitude information from the Bell measurements, one may estimate the sign of the gradient components using majority vote scheme that also exploits gentleness. The total number of copies scales as Olog / inducing time complexity of (logg(M) M/e²) with efficient classical overhead. The details of the implementation are discussed in Huang et al. [2021, Appendix E].
Proof.
L
This result indicates that there are at least some choices of circuits and generators for which back- propagation scaling can be achieved using gentle measurements. The exception naturally leads one to ask if this may be possible in more general cases with techniques like shadow tomography [Aaronson, 2019], however, with just a small perturbation away from this special case, the same technique no longer works, and the general computational efficiency remains unknown [Aaronson and Rothblum, 2019, Bädescu and O'Donnell, 2021]. In the subsequent section, we adapt shadow tomography results and exploit the sequential structure in variational models equipped with quantum data, to obtain backpropagation scaling in quantum resources, but leave open the question of classical computational efficiency. This represents substantial progress over current gradient methods for these models.
5.1 A quantum-efficient protocol for backpropagation
Our main contribution in this more general quantum data setting with multi-copy access, is the establishment of connection between gradient estimation and shadow tomography. This gives an exponential improvement to the sample complexity of the input state from Ó(M) to Opolyyog (M)) for computing gradients. It also gives a quadratic improvement in the number of quantum operations from Ö(M²) to (M.) analogous to classical backpropagation. The algorithm is depicted diagram- matically in Figure 1. Our proposal, however, houses large caveat: it requires the classical storage and manipulation of a hypothesis state, which results in an exponential classical overhead, unless an approximation scheme unavoidable in general, since removing it would imply that quantum advice can always be simulated by classical advice. Nevertheless, the exponential saving in sample complexity could be important in settings where the labelled quantum states coming from Nature are limited, and valuable. In Huang al. [2022] for example, there were sources of quantum data that, when limited in quantity, could achieve a substantial data advantage over classical learners even in the range of 20-40 qubits. In this size range, keeping the classical model in full detail would be completely feasible without ruining the potential for quantum advantage. Further, the linear scaling of quantum operations, even in the face of exponential classical overhead, could be beneficial if classical computation is extremely cheap when compared to quantum computation.
be effectively applied. It is argued in Aaronson [2019] that this cost is
Our protocol will apply an even more general model than Equation (3), which we term quantum neural network.
Definition 8 (Quantum neural network). Let a quantum neural network be variational quantum circuit on n + qubits, numbered 0, 1,...,,, n. Qubits 1.... n act as the data register, which will take as input an unknown quantum state (4p) to be classified. Qubit 0 acts as the output register, which is measured in the Z-basis and initialized to J0). The variational circuit belongs to the following simple class
u())= 10 PM UM .... e 10 U1:

---

where } are fixed (n + 1) -qubit Pauli operators and {Uk} } are fixed circuits. The output prediction on (()) then given by quantum neural network function defined as
QNNa(1+)) (0K()) (0) Z 4()00)0)) El-1.1].
(8)
Note that running the circuit on (0)(p) gives coin flip Ber( + (ONN((11)) rather than QNN (lN)( itself. This allows us to estimate QNN (((i)) to E precision with high probability by running the circuit poly(==") times, as usual. Furthermore, note the sequential nature of the function's 's gradients, highlighted in a similar sense in Equation (4). This leads to the following theorem.
Theorem (Quantum-efficient backpropagation). Given an unknown qubit input state (4),, there exists an explicit algorithm which produces estimates by for all k. 1..., M such that lbg 30, (NN(((1))))))))))))))))))) S using only
n (nlog* M
m 0
copies of (4)) The required number of quantum operations for the proposed algorithm is (mM) which is quasi-linear in M. However, classical storage of hypothesis state is used and incurs classical cost of M 22(m)) when no effective approximation schemes are known.
The full details of the proof and the explicit quantum backpropagation algorithm are given in Appendix D. We first show that estimating the gradient component 0g, QNo)(l reduces to estimating the expectation value of certain traceless Hermitian unitary operator on (p)))) Shadow tomography results then imply that estimating all gradient components precision is possible using only poly (log M, n1, adapt an improved shadow tomography protocol from Bådescu and O'Donnell [2021] that makes use of gentle measurements and is online. The key difference in our proposal, which enables to achieve linear scaling in M, is the reuse of quantum computation in way reminiscent of backpropagation through observation that one rotate through the layers of the quantum neural network sequentially and estimate the appropriate expectation value between each rotation step, as shown in Figure 1. Naive implementation the shadow tomography protocol for gradients would yield Ó(M) quantum operations, in line with most existing methods for quantum gradient estimation.
copies of (p)) In order to fully specify the algorithm, we
5.2 Reduction from shadow tomography
We now show that a fully efficient algorithm for computing gradients would give rise fully efficient shadow tomography procedure for observables which can be efficiently implemented. This very general class of observables, however, not known to have computationally efficient shadow tomography protocol. Thus, this connection presents yet another obstacle to improving the exponential classical run time of our quantum backpropagation algorithm since removing the exp(n) classical run time overhead in general, necessitates breakthrough in shadow tomography.
Definition 10 (Shadow tomography problem). Let & be a class of two-outcome measurements with outcomes in {+1). Given unknown n-qubit quantum state (ı)), and known measurements E EM. E ε, output estimates by..... by E [-1, 1] such that bbç - (w)Ex S E Vk. In 8m where m is small possible.
particular, do this via mcasurement of | (1))@m
Definition 11 (Poly-time observables). A poly-time observable on n qubits is defined to be an observable of the form UT Z where U is a poly-size circuit.
The shadow tomography problem is well-studied in quantum information theory. There are indeed special cases where this problem may produce a favourable scaling in M and outlined in Proposition 7. But, in general, it is not trivial to remove the exponential classical cost when it comes to shadow tomography.
Theorem 12 (Shadow tomography reduction). Suppose there is an algorithm which can estimate the gradients de @NNx(lW)), k= = 1,.., M, to precision e, with m copies of (b). and with runtime T. Then, this gives an afgorithm for shadow tomography of poly-time observables, to precision šn with m copies of (1b) and runtime
E....,EEr Eas given by E U Z, Uv. where {Ux} are poly-size circuits. Construct the quantum neural network with the following
Proof. Consider an instance of shadow tomography on n qubits, with E
7

---

variational circuit
((0))))o) dh Go. C H,Ho1))1)
e.... 0.
= 12 U1 (11+)
where
Ú1 1. & U1
U² = 1. @ UN k-1 M<ksM
Then, by Equation (7), the gradients at 0 = Oare
do. QNNo(16))la=
2 Re (1)00,
Re (+1(1)0) ... U0 UK+1 (iYo @ (.)0k...01++)))
2 Re (i/ @ o.))Ue..Ui1))))
=2(+<Wl11 @ (X, @ (1) ++))+
=2(+ s +))l+)|b)
Thus computing the gradients allows us solve the shadow tomography instance.
Seeing as there is no known classically efficient procedure for shadow tomography with respect to poly-time observables, this reduction illustrates the difficulty of replicating true backpropagation scaling in general.
5.3 A fully gentle gradient strategy
Shadow tomography makes use of multiple copies and hypothesis state model, often stored classically, to require a minimal number of destructive measurements. It is useful to examine the limits of gentle measurement alone for gradient estimation in order to reduce the classical overhead. In particular, it would be ideal if it were possible to use a small number of copies (e.g. polylog (1/a:) of quantum state to achieve a-gentleness in the general case through simple, direct measurement scheme. While we do not explicitly construct a protocol here, this capability would naturally lead to scheme for gradient estimation that achieves backpropagation scaling. This capability, however, would also allow us to violate known query lower bounds for the unstructured search problem. Thus, for our gradient purposes, seems as if successful schemes must limit the number of potentially destructive accesses to a quantum state via the use of a classical model. We formalize the general failure of gentle measurement alone in the following theorem.
Theorem 13 (Repeated gentle measurements). Assume it is possible perform arbitrary two- outcome measurement gently by using up to a polylogarithmic number of copies of the state. Specifi- cally, assume that any measurement can be made a-gentle by using (pooylog(1/oo) copies the state. Such an ability leads to violation of known query bounds given by Grover's 's search algorithm. and thus, cannot be possible in general.
Proof. The proof is adapted from results in Aaronson et al. [2016]. Consider the n-qubit Grover state after iterations with an ancilla present to mark the state (x)).
sin (2i + 1)0) |x) [1) + cos((2: (2i + 1)0)
Σ
(y) 10)
(9)
[E(O, vyter VM
where 0 arcsin 2 For each of the M 2n possible marked elements v, one can define two- element POVM of the form {[>) [1) (x| (1), I - (x:) [1) (ar (1]). One may ensure that the marked bit string is found with high probability by performing measurement of each of these POVMs with respect to the Grover state Ō(2") times, even the case where the state constructed with a single Grover oracle query. Performing this procedure using standard, destructive, measurements of the POVMs would require a fresh set of oracle queries with each round. However, using sufficiently gentle measurements removes this requirement. If the distance between the pre- and post- most-measurement

---

states is sufficiently small, one obtains results that are close to those that one would obtain from a fresh copy of the state. In order to guarantee that the marked bit string can be extracted with high probability, we demand that the state obtained after any number of measurement rounds be within 2g" in the trace distance of the state prior to any measurements'. To guarantee that the state be sufficiently unchanged by the end of the series of ((22)) measurements, each measurement should therefore be copies of the original state, each of which is prepared using the Grover oracle set number of times. By performing the whole sequence of measurements gently, one can avoid biasing the result too much before the marked state found. Hence, one can identify x with high probability, using poly(n) < 2n/2 Grover oracle calls, which is violation of known lower bounds [Grover, 1996]. In Appendix E.4, we discuss how sufficiently gentle measurements lead to violation of known bounds when considering a different notion of time complexity that combines measurements and oracle queries.
By assumption, this is possible with polylog(22n) or simply poly(n).
Remark 14 (Shadow tomography does not violate known bounds). After seeing this result, one might question how this relates to shadow tomography schemes that use gentle mcasurement plus classical computation. It is consistent when one considers that a-gentleness considered in isolation must apply to both the number of distinct measurements one may perform and the precision to which one performs a particular repeated measurement. That is, from the point of view of gentle measurement alone, gentleness to high precision E, are on the same footing and hence, must respect known bounds for information extraction. Indeed, all known shadow tomography schemes are consistent with number of copies of the state scaling polynomially with 1/e, despite scaling logarithmically in the number of distinct measurements, which prevents the above violation of known Grover query and time complexity bounds. This reflects an asymmetry between the number of distinct measurements and the precision of single measurement present in all shadow tomography schemes and noted in the original work on the topic [Aaronson, 2019] that hypothesized that there are fewer independent observables within a quantum state than one might expect intuitively. The success of shadow tomography schemes, as distinct from simple gentle measurement, depends crucially on the existence of models that update quickly enough limit the number of measurements made the actual quantum states.
different measurements and gentleness on repeated measurement
5.4 Approximate schemes
The failure of a fully gentle approach points to the necessity of a classical model to enable backpropa- gation scaling. But, the key challenge in the general application of the proposed shadow tomography algorithm is the use of an explicit classical representation of the quantum state, which in general, scales exponentially with system size. While there have been few special cases found that have fully efficient schemes, like with Pauli operators [Huang et al., 2021]. the case of whether there exists an efficient computational scheme for poly-time observables remains open. However, an exact scheme may not be required in practice, especially when dealing with noisy data. This raises the possibility of using approximate classical representations of the state. For example, is known that in cases where states exhibit low entanglement, they may be efficiently represented by matrix product or tensor network states [White, 1992, Perez-Gareia et al., 2006, Cramer et al., 2010, Evenbly and Vidal, 2015, Orús, 2019]. Moreover, in the case of shadow tomography, one is not explicitly seeking an exact representation of the density matrix, but rather a proxy, capable reproducing the desired observables with high probability. This relaxation of requirements may render an approximation scheme effective, even when the true state is challenging to represent with a particular ansatz. This area represents an interesting and potentially fruitful research direction that could dramatically increase the efficiency of training in quantum machine learning models, and we leave it open for future work.
Discussion
Special cases aside, the inadequacy of current gradient methods to provide backpropagation scaling in parameterized quantum models leaves room for many questions. One particular conclusive direction
'This choice distance guarantees that, even the presence of damage, the POVM used to identify the actual marked element will correctly return a positive result with probability at least 2 ". Likewise, any POVM corresponding to an unmarked element will incorrectly return a positive result with probability at most 1-
9

---

would be developing a concrete computational argument to rule out backpropagation scaling in the multi-copy setting, thereby confirming the true computational complexity of shadow tomography. Even though the proposed information-efficien scheme in this study fails to satisfy classical cost requirements of backpropagation, the possibiliity of a computationally efficient procedure remains open, especially for cases with known, structured observables. Similarly, failure in the general case of gentle measurements again suggests potential approximate or restricted models that may be more trainable. One may find an alternative architecture where gradient computation has favorable scaling, and even though the model is perhaps not as powerful or universal, it may still be useful in practice. Interestingly, closely related probabilistic classical analogues to variational models can exhibit backpropagation scaling. If the difficulty to achieve an efficient scaling is due to inherently quantum properties, perhaps backpropagation is not the correct method for optimization of quantum models, which seems to be a growing belief for classical models too, albeit for completely different reasons (Hinton, 2022]. We hope that these results spark the development of either alternative quantum models that can train at scale or new methods for efficient optimization.
References
Scott Aaronson. Shadow tomography of quantum states. SIAM Journal Computing. 49(5): STOC18-360 1-6818888888000 2019.
Scott Aaronson and Guy N Rothblum. Gentle measurement of quantum states and differential privacy. In Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing, pages 322-333, 2019.
Scott Aaronson, Adam Bouland, Joseph Fitzsimons, and Mitchell Lee. The space" just above" bqp- In Proceedings of the 2016 ACM Conference on Innovations in Theoretical Computer Science, pages 27 1-200, 2016.
Scott Aaronson, Xinyi Chen, Elad Hazan, Satyen Kale, and Ashwin Nayak. Online learning of quantum states. Advances in neural information processing systems, 31, 2018.
Ryan Babbush, Jarrod R McClean, Michael Newman, Craig Gidney, Sergio Boixo, and Hartmut Neven. Focus beyond quadratic speedups for error-corrected quantum advantage. PRX Quantum, 2(1):010103, 2021.
Costin Bädescu and Ryan O' O'Donnell. Improved quantum data analysis. In Proceedings of the 53rd Annual ACM SIGACT Symposium on Theory of Computing, pages 1398-1411, 2021.
John Baez and Jacob Biamonte. Quantum techniques for stochastic mechanics. arXiv preprint arXiv:/209.3633 2012.
Marcello Benedetti, Erika Lloyd, Stefan Sack, and Mattia Fiorentini. Parameterized quantum circuits as machine learning models. Quantum Science and Technology, 4(4):043001, 2019.
Yoshua Bengio, Eric Laufer, Guillaume Alain, and Jason Yosinski. Deep generative stochastic networks trainable by backprop. In International Conference on Machine Learning, pages 226- 234. PMLR, 2014.
Fernando GSL Brandão, Amir Kalev, Tongyang Li, Cedric Yen-Yu Yu Lin, Krysta M Svore, and Xiaodi Wu. Quantum sdp solvers: Large speed-ups, optimality, and applications to quantum learning. arXiv preprint arXiv: 171000281,.0 2017.
Matthias C Caro, Hsin-Yuan Huang, Marco Cerezo, Kunal Sharma, Andrew Sornborger, Lukasz Cincio, and Patrick J Coles. Generalization in quantum machine learning from few training data. Nature communications, 13(1):4919, 2022. URL https: //tp://ww..../ nature. com/ wwwm/otiiiii.//eo. /arriiettees 841467-022-32555
Marco Cerezo, Akira Sone, Tyler Volkoff, Lukasz Cincio, and Patrick J Coles. Cost-function- dependent barren plateaus in shallow quantum neural networks, 2020. URL htttps://aaxitt htggabbs/2001.0055
10

---

Marco Cerezo, Andrew Arrasmith, Ryan Babbush, Simon C Benjamin, Suguru Endo, Keisuke Fujii, Jarrod McClean, Kosuke Mitarai. Xiao Yuan, Lukasz Cincio, al. Variational quantum algorithms. Nature Reviews Physics, 3(9):6256644 2021.
Sitan Chen, Jordan Cotler, Hsin-Yuan Huang, and Jerry Li. Exponential separations between learning with and without quantum memory. In 2021 IEEE 62nd Annual Symposium on Foundations of Computer Science (FOCS), pages 574-585. IEEE, 2022.
Marcus Cramer, Martin B Plenio, Steven T Flammia, Rolando Somma, David Gross, Stephen D Bartlett, Olivier Landon-Cardinal, David Poulin, and Yi-Kai Liu. Efficient quantum state to- mography. Nat. Commun., 1:149, 2010. ISSN 2041-1723. attt::/dde doi. www....g./110/ 1038/ 01338/cooms1144
doi: 10.1008/ncommsl11 147. URL
Glen Evenbly and Guifre Vidal. Tensor network renormalization. Physical review letters, 115(18): 180405, 2015. URL https j/wra///oorassaaa aps http:///////bbttttttto//oo////// 115. 180405
Edward Farhi, Jeffrey Goldstone, and Sam Gutmann. A quantum approximate optimization algorithm. arXiv preprint arXiv: 1411.4028 2014.
Julien Gacon, Christa Zoufal, Giuseppe Carleo, and Stefan Woerner. Simultaneous perturbation
stochastic approximation of the quantum fisher information. Quantum, 5:567, 2021.
András Gilyén, Srinivasan Arunachalam, and Nathan Wiebe. Optimizing quantum optimization algorithms via faster quantum gradient computation. In Proceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms, pages 1425-1444. SIAM, 2019.
Goodfellow, Yoshua Bengio, and Aaron Courville. Deep leurning. MIT press, 2016.
Andreas Griewank and Andrea Walther. Evaluating derivatives: principles and techniques of algorithmic differentiation. SIAM, 2008
Lov K Grover. fast quantum mechanical algorithm for database search. In Proceedings of the twenty-eighth annual ACM symposium on Theory of computing, pages 212-219, 1996.
Geoffrey Hinton. The forward-forwee algorithm: Some preliminary investigations. arXiv preprint arXiv:2212.133355, 2022.
Thomas Hoffmann and Douglas Brown. Gradient estimation with constant scaling for hybrid quantum machine learning. arXiv preprint arXiv:2211.1399 2022.
Hsin-Yuan Huang, Richard Kueng, and John Preskill. Predicting many properties of quantum
system from very few measurements. Nature Physics, 16(10);0000-1055 1057, 2020.
Hsin- Huang, Richard Kueng, and John Preskill. Informaation-theoretii bounds on quantum advantage machine learning. Physical Review Letters, 126(19):190505, 2021.
Hsin-Yuan Huang, Michael Broughton, Jordan Cotler, Sitan Chen, Jerry Li, Masoud Mohseni, Hartmut Neven, Ryan Babbush, Richard Kueng, John Preskill, et al. Quantum advantage in learning from experiments. Science, 376(6598): 182-1186, 2022. URL httphttss://w..cciiie science. org/doi/abs//ue ww1////cienei abn7293.
William Huggins, Kianna Wan. Jarrod McClean, Thomas E O' O'Brien, Nathan Wiebe, and Ryan Babbush. Nearly optimal quantum algorithm for estimating multiple expectation values. arXiv preprint X /tt::2//1.0992 100983,, 2021.
Forrest N landola, Song Han, Matthew W Moskewicz, Khalid Ashraf, William Dally, and Kurt Keutzer. Squeezenet: Alexnet-level accuracy with 50x fewer parameters and< 0.5 mb model size. arXiv preprint arXiv:1602.07336 2016.
Zhengfeng Ji, Yi-Kai Liu, and Fang Song. Pseudorandom quantum states. In Advances in Cryptology- CRYPTO 2018: 38th Annual International Cryptology Conference, Santa Burbura, CA, USA, August 19-23, 2018, Proceedings, Part III 38, pages 126-152. Springer, 2018. URL https: //www. iacr org/ archive httpai////cpp220000/9993//////// /199399//933977/9993777 .df..

---

Stephen P Jordan. Fast quantum algorithm for numerical gradient estimation. Physical review letters, 95(5):050501, 2005.
Abhinav Kandala, Antonio Mezzacapo, Kristan Temme, Maika Takita, Markus Brink, Jerry Chow, and Jay M Gambetta. Hardware-efficient variational quantum eigensolver for small molecules and quantum magnets. nature, ():2())22)222222 246, 2017.
Yann LeCun, Bernhard Boser, John Denker, Donnie Henderson, Richard Howard, Wayne Hubbard, and Lawrence Jackel. Handwritten digit recognition with back- pocc-propagation network. Advances in neural information processing systems, 2, 1989.
Yann LeCun, Yoshua Bengio, and Geoffrey Hinton. Deep learning. nature, 521(7553))436-444 2015.
Jarrod R McClean, Sergio Boixo, Vadim Smelyanskiy, Ryan Babbush, and Hartmut Neven. Barren plateaus in quantum neural network training landscapes. Nature communications, 9(1): 2018.
Kosuke Mitarai, Makoto Negoro. Masahiro Kitagawa, and Keisuke Fujii. Quantum circuit learning. Physical Review A, 98(3):032309, 2018.
Román Orús. Tensor networks for complex quantum systems. Nature Reviews Physics, 1(9):538-555 -500 2019. URL https::/www.naturree nature. ceaaturee.cm/ariiieeeeeee.eseeee -et.eeee/e//2411--0000000 019-00867700
David Perez-Garcia, Frank Verstracte, Michael M Wolf, and Ignacio Cirac. Matrix product state representations. arXiv preprint quant-ph/0608199, 2006. URL https: org/ abs/
quant-ph/0668117.
David Rumelhart, Geoffrey E Hinton, and Ronald Williams. Learning representations by back-propagating errors. nature, (23 1986.
Maria Schuld and Nathan Killoran. Is quantum advantage the right goal for quantum machine learning? Prx Quantum, 3(3):030101, 2022.
Maria Schuld, Ville Bergholm, Christian Gogolin, Josh Izaac, and Nathan Killoran. Evaluating analytic gradients on quantum hardware. Physical Review A, 99(3):03233,, 2019.
James C Spall. Adaptive stochastic approximation by the simultancous perturbation method. IEEE transactions on automatic control, 45(10):1839-1883 2000.
Christian Szegedy, Sergey Ioffe, Vincent Vanhoucke, and Alexander Alemi. Inception-v4, inception- resnet and the impact of residual connections on learning. In Proceedings of the AAAI conference artificial intelligence, volume 31, 2017.
Joran Van Apeldoorn, András Gilyén, Sander Gribling, and Ronald de Wolf. Quantum sdp-solvers: Better upper and lower bounds. Quantum, 4:230, 2020.
Samson Wang, Enrico Fontana, Marco Cerezo, Kunal Sharma, Akira Sone, Lukasz Cincio, and Patrick J Coles. Noise-induced barren plateaus in variational quantum algorithms, Nature commu- nications, 12(1):1-11, 2021.
Steven R White. Density matrix formulation for quantum renormalization groups. Physical review letters, 69(19)22863, 1992. URL https://journal: aps httpppr//absttatt/o... 1103/ PhysRevLett 28633.
Zifeng Wu, Chunhua Shen, and Anton Van Den Hengel. Wider or deeper: Revisiting the resnet model for visual recognition. Puttern Recognition, 90:1 19-133, 2019.
12

---

A Resource scaling for quantum backpropagation methods
What comprises classical memory and time complexity, is purposely left vague. The details depend on the constituent types of operations needed to compute a function and its gradients, as well as the memory access model available. But, details aside, backpropagation merely refers to gradient computation in a particular manner, and, any reasonably successful implementation of it incurs constant overhead in relative complexity. as captured by Equations (1) and (2). With this in mind, we elaborate on the operational definition of quantum backpropagation scaling in terms of memory. Thereafter, we explain the failure of various current gradient methods to achieve backpropagation scaling.
A.1
Memory complexity of the function
Recall the function of interest F(0) F(0) = tr)p( where O an observable and p(0) is
parameterized quantum state built from M parameters, acting either an unknown initial state p or simplified initial state p = [o)o]. Classifying the memory used to compute the function combination of n qubits, plus storage for each of the M parameters with appropriate precision, 6, implies
(F))) = Ö + M log(1/))).
(10)
To derive the computational cost, assume unit cost access any element of the circuit family {U₃) If an incoherent measurement scheme is used, measuring O and estimating F(0) to an acceptable fixed precision, E, on repeated preparations of p(0) incurs a cost that scales TIME(F(0)) some integer k: This sets the scene for the computational requirements of computing (0),, which should, importantly, be achieved with modest space overhead truly replicate backpropagation.
( ), for
A.2 Current gradient methods
Replicating classical backpropagation efficiency in quantum setting requires more effort, which we elaborate next by discussing how and why current gradient methods fail to achieve this efficiency. For further illustration, Figure provides a hypothetical comparison between the popular gradient method the parameter-shift rule and true quantum backpropagation. The plot incorporates assumptions about time to compute native quantum operations taken from Babbush et al. [2021].
A.2.1 Naive sampling
The gradient of the function F()) expressed in Equation (4) also takes simpler form using the parameter-shift rule and properties of Pauli generators [Mitarai et al., 2018, Schuld et al., 2019]
[F)()),, F(0 + ग 0t),
(11)
where 0g is unit vector along the thth direction of O. Thus far, sampling schemes constructed to estimate (11), perform a destructive measurement that typically only retrieves a partial amount of information for one component of the gradient. As result, reducing the infinity norm error in the gradient such that we expect [IF((0) (0)ll S s with reasonable probability, has cost that scales like converging each component, i.e.
TIME(F'(0)) x M log M TIME(F(0))
(12)
(13)
While this quadratic dependence on the number of parameters may not seem problematic, linear dependence was the necessary catalyst in the age of modern deep learning, with overparameterized networks that perform exceedingly well on practical tasks.
A.2.2 Fast gradient algorithm
A method put forth by Jordan [2005] numerically estimates the gradient of classical black-box function at a given point, using quantum computer. The algorithm impressively requires a single black-box query to estimate the full gradient with desired precision, whilst satisfying the memory
13

---

107
Quantum backpropagation
Number of parameters (log scale)
Parameter-shift rule
x 000
106
X 150
10a
9 000
x 3650
X 2 000
10.
750
240
102
x
100
seconds
minute
hour
day
Time (log scale)
Figure 2: Quantum backpropagation scaling. The parameter-shif rule is plotted alongside true quantum backpropagation scaling. On the z-axis is time in number of seconds required to compute single estimate of the gradient in log scale, with common time points stated explicitly. On the y-axis the number of parameters, also in log scale, that may be optimized using each method, for given amount of time. We make simple assumptions, motivated from the work in Babbush et al. [2021], I. Namely, we assume minimum system size of 100 qubits. Further, assuming a favourable time of 10ps to compute one parameterised operation which is 1 order of magnitude less than the time to compute one Toffoli gate), the time for one primitive is lower bounded by 100 x 10ps Tg. Scaling in time is then roughly M T, for the parameter-she rule and M polylog(M) T. for quantum backpropagation. Furthermore, E 0(1)
requirement (2). We elaborate on the connection between this approach and backpropagation on quantum computer when the function considered is classical and reversible, in Appendix B. But, as shown by Gilyén et al. [2019], when parameters are considered to be rotation angles like those in variational circuits, a different query model needs to be applied and the original single-query advantage becomes unattainable. With the appropriate query model, the known bounds imply using amplitude estimation, and, in a high precision regime, Ô(M / M/E) is worst-case optimal even with commuting Pauli operators [Huggins et al., 2021]. This worst-case bound was proved in setting where operators commute, indicating that commutativity need not be helpful in other settings.
computational cost of (MM
A.2.3 Simultaneous perturbation stochastic approximation (SPSA) algorithm
few studies have investigated the of the simultaneous perturbation stochastic approximation (SPSA) algorithm to optimize parameterized quantum circuits [Benedetti et al., 2019, Hoffmann and Brown, 2022, Gacon et al., 2021]. It argued that SPSA is computationally efficient since its requires two function evaluations to estimate the gradient, irrespective of M. This seemingly satisfies the scaling we require, however, the approximation of the gradient has limited accuracy which affects the number of optimization steps needed for SPSA to converge to a minimum. As M increases, the variance of the gradient estimate increases and, thus, to counteract this, smaller learning rate must be used increasing the number of optimization steps or more samples are needed estimate the gradient with an appropriate accuracy at every step. In either case, one cannot escape a dependence on M, which indirectly affects the number of function evaluations needed to estimate gradients or perform gradient- based optimization adequately. More formally, the gradient estimator for component j of function, given by SPSA, is
FO))), = F(O + cD) - F(B cA)
(14)
2cA
where is step size constant and A E I is size M random variable with independent, zero-mean, bounded second moments, and bounded inverse moments, i.e. E(IA),) is uniformly bounded for all
14

---

j. A common choice for A is a Bernoulli random variable with equal probabilities of being +1 or -1 for every entry.
Consider a special case, F, for pedagogical purposes such that the gradient at the point is a constant ! along all coordinates, the function is nearly linear at the point examined, and the number of coordinates M is large in a central limit theorem sense. We then have, F*(O); = for all j. and F(O + cÂ) F(0) + F' (' A F(O) + eg 1' A R F(0) + (O, M). On quantum computer, the estimator will be constructed by taking independent measurements of F(O + cA) and then rescaling the sample mean by 1/2cAj. We then see that the variance of individual term in this case is given by
Var VarlF'(0)) = F(O) + +
(15)
As such the number of samples required to reach precision e with high probability in even a single gradient component scales as
Ng F(0)/c+ gM
(16)
22
which clearly increases linearly with the number of components M, and does not achieve the desired scaling despite the estimator being constructed from only two function calls. It is also worth noting that the estimates for each component of the gradient are highly correlated across the vector, which can lead to larger errors than would otherwise expected under alternative norms. This is intuitively expected, as it should not generally be possible to determine M independent random variables from a single value without increasing the precision of the estimates at least proportionately. We note in passing that generally to obtain an unbiased estimator one must also take to be on the order of but this dependence can be improved with higher order formulas to e for some > 1 [Spall, 2000], but this is not central to our study.
B Classical backpropagation in quantum circuits
In order to frame the discussion, it is worth considering a number of closely related setups as they would appear if performed on quantum computer. In particular, in similar notation and cost models, its interesting to consider how classical backpropagation would look in a quantum circuit for a deterministic classical function and perhaps the closer classical analog, classical parameterized Markov processes on the space of probabilistic bits.
B.1 Classical functions
First we will look at an entirely classical function using reversible arithmetic for the purposes of analogy, using a simplified function but with simple generalizations available. This will be helpful for setting the stage in terms of notation and scaling, and also help make connection with the gradient algorithm of Jordan [2005]. Consider a classical function f that depends on some set of parameters E R via more elementary functions ft. For this example, we assume a simple dependency graph for the overall function f R + R is the simple composition of elementary functions, = fN o fN-1 o ... o f1. Given this structure, we denote a set of intermediate variables 2,, such that z v; for E [1, M) and = (=((t)) ) for i E [M + 1. ni] where a(i) is the subset of variables needed to evaluate /i, noting that we are implicitly including a trivial set of elementary functions f; that are simply the identity operation. We also assume that no depends on itself, each appears exactly once, and derivatives of the elementary operations are readily available, that is a simple function for evaluating (x(2) is available for any input
Given these definitions, we are ready to describe the algorithm for obtaining the gradient (.)( We consider universal precision 5 for all parameters and function values, such that classical numbers use (log(1/ ())) qubits for their representation. For initialization, we store each of the parameters I; in their own quantum register !),, to run the circuit fully within the quantum computer. In the first step, we run the function evaluation in the so-called forward pass and store the intermediate values 2; each in their own quantum register })~ using the elementary implementations of fi as reversible circuits. Taking now an additional set of auxiliary registers, }}^ with the same size as the intermediate variables, assign X, = 1, and compute the backwards pass according to reversible
15

---

implementations of X - EiE @z)fi(En(t) where ((i) is the outgoing nodes for intermediate
variables 2,. In the final step, may simply read off the À register to find Vz A1:M-
Considering a general auxiliary register x)x+ these steps may be written in quantum form as
x) 10)= 10)> a - Forward xx)_ |=) 10), (ry) - Backward [x) 12), 1 (ro)
(17)
where ry and r. denote the state of the arithmetic trash register after the forward and backwards pass respectively. Given our precision specification, the size of each of the I register is ((M) and the size of the 2 and À registers are ((N). This representation is bit wasteful in that as the backwards pass proceeds one can overwrite the intermediate values with when they are no longer needed, but writing it this way clarifies the steps. If we assume typical setup where the number of free parameters is roughly on par with the number of elementary functions, then we see that the total storage for the primary registers is (() and similar for the ancillary register. Similarly, the amount of computation required in both the forward and backwards pass is (MM), or approximately twice the cost of evaluating the function in the forward direction, meeting the scaling requirements of backpropagation with some small overhead for maintaining reversibility.
It is useful to compare some aspects of this approach to the quantum algorithm of Jordan for evaluating gradients of classical functions using single black box function query [Jordan, 2005]. Considering only the computation, if we approximate the forward pass and backwards pass to each be the same cost as one black box function query, then up to log factors in precision of evaluation this method is a constant factor of two more expensive. Said another way, there is no quantum advantage in evaluating the gradient when one has white box access to the classical function implementation and satisfies the simple dependencies requirements. In terms of storage requirements, the algorithm of Jordan requires the same x register. but makes no use of the intermediate variable registers such as 2 or À (which can be combined in real implementations to be approximately the size of the register). This use of intermediate storage is sometimes characterized as a form of dynamic programming, where the storage of intermediate variables reduces overall computational complexity. Moreover, this version takes advantage of analytical gradients of the subfunctions which can be evaluated to high precision more easily than depending the finite difference formulations of gradient algorithms in Jordan's technique.
So in summary, both quantum implementation of classical backpropagation and Cordan's technique have a computational cost that is constant in the number of parameters if our cost model considers overall function evaluations the cost model. This represents exponential improvement over naive finite difference computations or symbolic evaluation of derivatives one element at a time. The backpropagation technique utilizes an extra storage register and knowledge of the problem structure, as is common in dynamic programming, while Jordan's 's algorithm needs only black-box queries. Both of the techniques assume bitwise access to the oracle as classical function.
B.2 Classical parameterized Markov chains
In the previous section, the comparison of classical backpropagation and Jordan's 's algorithm made use of bitwise access to classical, deterministic function. The case of classical function encoded in bits helps frame the discussion in not only scaling but also the sense in which classical parameterized functions are perhaps not the best analog for parameterized quantum circuits. A key aspect of this difference was highlighted in Gilyén et al. [2019] by showing that in the black box setting. it was more appropriate to consider current parameterized quantum circuits in which case they prove lower bound of at least M1/2 calls to the black box (in contrast to O(1)), ruling out the desired backpropagation scaling except for special cases. This contrast motivates asking whether the intuitive origin of this lower bound is related more to the black box nature of the access, the quantum nature of the parametcrization, or merely the probabilistic features of the parameterization. Here we show that a classical analog to parameterized quantum circuits, namely parameterized Markov processes do indeed allow the analog of classical backpropagation which helps highlight that the difficulty in achieving constant scaling is due to the quantum nature of the problem.
phase amplitude oracle,
To draw an analogy between quantum and probabilistic classical states for our purposes, we will introduce a small number of analogous concepts that are considered in greater depth by Baez and Biamonte [2012]. A parameterized quantum state (v(()) is an L normalized state such that
16

---

Is ds lbb(s; 0) = 1, that is often formulated as parameterized quantum circuit acting on a known initial state as [b) = U()) [0) where U is a unitary transformation. In contrast, parameterized classical probability vector (a)( is a positive L' normalized probability vector such that Is ds (5s;;) 0) = 1, that may be formulated as a parameterized classical circuit acting on a known reference state as [T) = (0) [0) where U is a left-stochastic operation in this case. As a connection between the two, one may consider classical transformations as the set of transformations restricted to the diagonal of a quantum density matrix, and note that it is always possible to represent classical probability process as a quantum process, albeit non-uniquely, but the converse is of course not true in general.
The corresponding analog of expected values of Hermitian operators quantum states will be expected values with diagonal operators O. Such operators are well defined for expected values on both classical and quantum states and are identical when the quantum populations are equal to the classical probabilities. In setting up for the computation of gradients with respect to the parameter vectors, will consider objective functions defined by the same observable O and sequence of operations that each depend on a single parameter. That is, the corresponding classical and quantum objectives with these assumptions may be concisely defined by
((0) | ds 0())
U: (((0)))))))) = (()
(18)
f(0). = -se ds O()) (+) = (O)u
(19)
Our question here will be if the restriction to parameterized classical stochastic processes allows the desired scaling in determining gradients of an expected value with the given parameters. The evaluation of gradients with respect to parameters in quantum circuits relies largely the fact that anti- Hermitienn operators generate unitary evolutions, and we may exploit that relationship to expected values explicitly. There is a direct analogy to this for general
determine gradients stochastic operators, in that they are generated by so-called infinitesimal stochastic operators. defined by E; Hij = O. With this definition, in finite dimensions they characterize the family of Markov semi-groups via exponentiation as (t) = exp( Ht). For our purposes, it suffices that this yields a well defined operator for evaluation of single parameter derivatives.
In order to properly compare the two settings, we need to make clear a number of assumptions on the operators U, and corresponding operators H, that mirror assumptions in the quantum case, allowing efficient implementation. To begin, we assume each (0,) is a simple operation, analogous to a quantum gate or Pauli operator, such that it is defined as tensor product on classical probabilistic bit space, and evaluating the transition probability between two basis states is efficient to do at high precision. In general, the basis could change between steps and the process could remain efficient, however for simplicity we consider the standard computational basis here. Moreover, we assume that the operation that generates the U., which we denote H; is simple to evaluate between hasis states, and has a bounded norm || = 1, so that parameters 0g have consistent and reasonable scales. Similarly, we will restrict ourselves to observables O with reasonable norms, i.c. ||O]| = 1.
With these assumptions, we investigate derivatives of a classical stochastic process under different sampling schemes. Let's imagine we have a stochastic process U, much like a variational circuit, which we write as
U())= II U.(O.)
(20)
where each U, is stochastic process with a corresponding generator H;, such that (+())) = Hx,(O.H.)
(21)
de (.,) (..)
(22)
We will be sampling the expected value of some observable O which is a diagonal matrix in our construction, and the function value we are interested in optimizing, given a initial probability distribution thn can be written in number of ways, but some are
f()
(
(23)
/ ou
(24)
17

---

Now if we take the gradient of this function with respect to the parameters, we find
f = Ōo, ((0)0
(25)
U,
UnVo A>1
II
(26)
J
U J
Uk
(27)
kDi
Using this construction, one can store the trajectory and lean path-integral formalism to use a single sampling process to take independent samples of all the gradient components with each stochastic sample that is taken. One way write this is to borrow the path-integral like formalism using resolutions of the identity as
((0) = / 0 II
U
(28)
Σ /
Olin) (iN|UN (N-1) (1--)(---U 461
i
= Σ (w)(iN)))))(((
where we p(11, -.. iN) to represent the probability of particular configuration that was sampled, and similarly O(iv) for the value of the final configuration. We assume that for each individual configuration is possible to compute the transition probability between individual configurations, e.g. (iN] UN -1) which is typically true in the classical case as well. As a result, for a given path, we use re-weighting to make that path produce an unbiased sample for the gradient component we interested in as well. In particular, writing the same for the shifted gradient estimator for component j merely requires substituting the relevant matrix element
(ig UG 1i5-1)
(29)
hence we can estimate the gradient using samples re- re-weighted by
(1, H2U, (
00,
Σ pli iN) $1.-..,88
O(in)
(30)
where the weighting factors also assume to be efficiently computable by construction of the elementary operations Us, which is analogous to the quantum generators typically used as well, defined as simple operations lifted into large spaces by tensor products. This suggests the following procedure for efficiently estimating gradients with respect to parameters in the classical analog of quantum variational circuits.
1. Draw a sample from نi and store this configuration as |i)), which may be represnted efficiently as a classical bit string.
2. For each elementary operation U,, sample the next classical configuration with probability determined by U, and store the configuration as liz).
3. Upon reaching the final configuration, evaluate O(ix) from the definition of to determine the value of the objective.
4. Using the stored path, {. for each elementary step, sample ( O(ix) and store the value in vector to be used in a running average that determines the gradient.
5. Repeat this procedure until the uncertainty in the estimate for each gradient component is as low as desired.
is easy to see from the above procedure that the variance the estimate of each individual gradient component does not have explicit dependence on the number of elementary steps. This can be seen from Equation (30), which only has an explicit dependence on points in the chain. Alternatively, from our assumptions designed to mirror the case of quantum circuits, know the variance of
18

---

these estimators is controlled by the value of the product of the number of parameters or steps in the sampling process. may appear that the quantity estimated could be unbounded, but if we move the denominator into p. the result is again probability distribution multiplied only by values determined by the numerator here. As result, analogous to backpropagation in the bitwise function case, by storing the intermediate configurations {(i,)) at a cost memory of O(M), we see that evaluating the gradient requires a number of samples that is independent of M.
S 1, independent
From this, we see that indeed the desired scaling is possible in the case of the analogous classical parameterized stochastic processes on tensor product spaces. The formulation as a sum over paths also allows us make connection the gentle measurement results the main text, in that we are always promised to be in a computational basis state, making it possible to do gentle measurement at intermediate steps with unit probability. This division allows us to help identify the origin of challenges in achieving backpropagation scaling as a problem with quantum measurement collapse and the inability read out intermediate states while continuing a computation, rather than the probabilistic formulation of the problem. In addition, one may make the classical generators H; non-commutative with each other and suffer no additional difficulties in estimating the gradient components, unlike in the quantum case. It remains interesting question to better understand the performance separation on practical tasks between quantum variational methods and this type of classical analog, given the advantage in trainability of the classical construction.
C Polynomial complexity circuits
It is reasonable to ask if we can first rule out backpropagation when only given access to single copies of a state. A useful tool rule out the possibility of certain tasks is information--heeretiic bounds, however, we show here that these are not sufficient to rule out quantum backpropagation scaling on single copies as the task remains information theorttiiiyttrrrtcllllly viable under the assumption of polynomial length variational circuit, thanks to classical shadows. On the other hand, standard computational arguments illustrate the difficulty in acheiving the desired scaling.
C.1 Information-efficieen with classical shadows
The idea behind classical shadows is to create a classical representation of a state p. that allows one to affordably estimate other properties of interest, like expectation values of observables [Huang et al., 2020]. In general, the number of samples, N, needed to predict say, Tr[Eip] .... Tr p] within additive error e, with high probability is
N ((log(() max; E shadoo/ /
where || lbbldow is norm influenced by the particular measurement primitive chosen to implement the classical shadow scheme. While general quantum states can be hard determine, the additional constraint of a state being generated by polynomial complexity variational circuit allows us to strengthen our statements.
Definition 15 (Polynomial complexity circuit). We say circuit is polynomial complexity circuit if it is composed from a fixed gate set G that may be applied between any two qubits with a maximum number of gates scaling polynomially in n, the number of qubits. Additionally, we will call it a polynomial complexity parameterized circuit if each gate in the elementary set is defined by a bounded number of parameters.
With this at hand, we have the following.
of polynomial complexity circuits). p= [Wbbbb be the density matrix of a pure state generated from a quanttum circuit of polynomial complexity built from a gate set of size G applied between any two qubits, with at most p(n) total gates, where p(n) is polynomial in the number of qubits, n. With these definitions, there are at most K = (nG))p(n) of these circuits. Then, p can be explicitly determined using St(log()) K) (K)/e²) = (2(p(() log()))) single-copy measurements and classical search procedure.
Proposition 16 UIfoommtionnefficcinn
Proof. Given that (z)) generated from polynomial complexity circuit, denote the possible states created by such a circuit as lo.). With the above definitions it is easy to see that the total number of
19

---

possible states that can be generated by a single step is G²G, and hence with p(n) possible choices, the total number of states is K = (nG)2p(m)) If the underlying set of operations used to generate the state is unknown, it still possible to cover the space of two-qubit operations to diamond distance error with a number of operations scaling polynomially in 1/c and p(n) [Caro et al., 2022]. If we denote this number of extended operations as G', then the argument proceeds as before terms of asymptotic scaling by replacing G' with G'. Performing Clifford classical shadows with E; (o:) for 1, ..., K, one can estimate the fidelity, i.e. Tr[E: Xx) J. for within additive error e using (loog /s/)) single copies of (1)). Since (v)) is generated by one of the K circuits, searching for an E, that provides the maximum fidelity, allows one to find Tr[E, [eeee] = 1, with high probability, and thus, explicitly determine (eb), and circuit that generated it by using classical simulation of the family of circuits, that will generally scale both exponentially in n and K.
With this knowledge, one may proceed to compute expectation values classically to determine gradients or indeed any desired expected value feature of the state. Whilst this procedure allows us to determine (15) and a circuit for creating it, executing it incurs quantum hardware costs dominated by the Clifford circuits needed for the classical shadow protocol which are of polynomial depth, but contain entangling gates which are limiting in practice. Even more concerning, is the classical cost of pros-procsssing. Obtaining the maximum fidelity involves storing K = (n + p(n)) ((p(()) values and searching over them, which can be expensive. Additionally, the final computation of the expectation values needed for backpropagation, requires knowing and storing M exponentially large matrices, over and above the cost compute the expectation values. And so, backpropagation scaling remains untenable with this implementation.
C.2 Computational hardness on polynomial complexity circuits
The result and algorithm (a brute force search) used in Proposition 16 demonstrate the information- theoretic efficiency of determining almost anything one would want to know about a state if we are guaranteed that both a pure state and generated by polynomial complexity circuit. The classical computational procedure is clearly inefficient, but this begs the question of whether an efficient procedure might exist in general, especially given the existence of an efficient procedure for special cases. Here we argue that no efficient procedure can exist in the most general case, unless it is possible to efficiently clone pseudo-random quantum states.
Proposition 17 (Computational hardness of polynomial complexity circuits). Under standard crypto- graphic assumptions, efficient computational procedure exists to identify pure state of polynomial complexity to trace distance e.
Proof. A pseudo-random quantum state is defined to be a pure state of polynomial complexity that no efficient computational algorithm given polynomial number of copies of the state can distinguish from the Haar random state. Using the procedure described in Proposition 16, a circuit that can recreate the state trace distance can be found using a polynomial number copies of the state. If the procedure that finds this circuit is also computationally efficient, then the state can be cloned efficiently, violating the no-cloning theorem for reeudo-random states shown in Ji et al. [2018], which merely rests upon standard cryptographic assumptions.
This result demonstrates that even if we know a state is a pure state generated from a polynomial complexity circuit, it is computationally infeasible to identify it under cryptographic assumptions despite the iiformmtiion-thooreee which the backpropagation problem could remain challenging, and that the most effective strategies must make use of known structure in the observables and states to achieve computational efficiency in analogy to known special cases.
efficiency. This suggests that there are states and observables for
D Shadow tomography protocol for gradients
For much of this manuscript it has been assumed that one has complete white-box access to the input state p = (O)) In a more traditional quantum setting, however, this may not be the case. One may be given access to unknown quantum states, or partially unknown states, and tasked to process them for some machine learning task. In such an instance, the input states usually referred to as
20

---

quantum data, and insights pertaining to this model set up can be found in Huang et al. [2021]. In this section, we discuss some details around this model type, which we call a quantum neural network and is defined in Definition (8).
D.1 Gradients as observables
Before presenting our algorithm for performing quantum backpropagation, we begin with the follow- ing remark on quantum neural networks which allows us to exploit a shadow tomography procedure. Remark 18 (Gradient of quantum neural network). The Ath gradient component of the quantum neural network may be expressed
Do. QNN (NN)((p))> 2 Re (,,
2 Re vn)
where
(v) (iPa)e 10 U1 U. (0)p)p
c(0+t 4) UK...
11 U110)14)
(4a) = U 10t1 Uhee 10 P's Zoe wy PM UM........... 80 P U1
If one defines
u = 310x++) PuU,,
u Ubt1 10 Ube Pm Z0e
40 PM UM ... e00, Uu,
then, given copy of (p)) one may attach an ancilla qubit labelled in the }+) state (in addition to the output qubit 0). In doing so, consider applying çontrol-24 conditional on the ancilla being (0), and control-U4, (+) conditional on the ancilla being [1). This produces the state
(10) A [1) (x)).
Measuring on the ancilla qubit, the expectation
1 2 (1o (1((0)))xx v (1)1*x)) = Re (4x Mx
= de QNN ((1)))
2
This implicitly gives an operator on |+) (p) whose expectation value is _0,, QNN (l)))) Moreover, we can implement this measurement with ((M) quantum operations.
D.2
Proof of Theorem 9
In order to prove Theorem 9, we need to discuss and modify two concepts: online learning and threshold search [Aaronson et al., 2018, Bädescu and O'Donnell, 2021].
D.2.1 Online learning quantum states
As in Aaronson et al. [2018], suppose we have access to a stream (E1, bi),... (EM bar) where each by ( Ex/ (b). We want compute hypothesis states , which are mixed states stored classical memory, such that
wk depends only on (Ei, b1).... ... (Eg-1, bx-1) (the online condition)
(1b) Eg [b)] for as few as possible
One may produce the following theorem.
Theorem 19. [Aaronson et al., 2018, Theorem 1] In the above setting, there is explicit strategy for outputting kypothesis states wi,... was such that (Tr(Fgeu {1b) Fx [/)] >> e for at most 0
values of k. This holds even if the measurements by noisy, and only satisfy lbg (+b) Exlx)) S
21

---

Two remarks are in order: first, the problem setup and algorithm presented in Theorem 19 are both completely classical. Second, this theorem says nothing about computational runtime. Implementa- tion of the algorithm in Theorem 19 using techniques from convex optimization will require runtime polynomial in the dimension of the Hilbert space poly(2").
D.2.2 Quantum Threshold Search
Bädescu and O' O'Donnell [2021] promote online learning to shadow tomography protocol using a procedure which they call threshold search. This gives an improved version of the quantum private multiplicative weights algorithm proposed in Aaronson and Rothblum [2019]. The difference between the online learning setting from the previous section and general shadow tomography, is that in practice, are typically not given the expectation values {bæ} and must measure them ourselves. This is where threshold search comes in handy. Suppose we possess some copies (w5) of a quantum state and are given a stream (E1, a1). ai)...... ..... (EM, am) where each og is supposed be a guess such that Ra {1 Ex (5).. Threshold search is a subroutine which, given only logarithmically many copies of the state, can check in an online fashion whether there is an ag which errs by more than E. More formally, we have the following theorem.
Theorem 20. [Bädescu and O D'Donnell, 2021, Lemma 5.2] Given m copies of an n-qubit quantum G.M, there is an algorithm
state | @m, 16)@mm M observables -1 S Ei..... EM S and guesses 01,..., G,M
which outputs either
aak
[b)))) S Wk.
Or |a - (1b) PAX > ie when in fact [bx. - (1b) Fg(())] S fe for a particular and value
by-
does so using number of copies only
log" M
O
e2
Furthermore, the algorithm is online in the sense that:
The algorithm is initially given only M and E. It then selects m and obtains (8)88..
Next, observable/threshold pairs (E1, a1), (Ez, o2),... are presented to the algorithm in sequence. When each Eg,, 0k) is presented, the algorithm must either 'pass', or else halt and output lax - ( E | 7.c.
If the algorithm passes on all (Fg, ax) pairs, then it ends by outputting las- (v) Ex((>) S Vk:
We stress that this subroutine requires quantum memory and multi-copy measurements, and uses gentle measurements in an essential way. One able check whether or aş is inside the threshold without greatly disturbing the copies of the quantum state. We are now ready to state the full shadow tomography protocol from Bädescu and O' O'Donnell [2021]. The idea run the online learning algorithm from Theorem 19 in parallel with threshold search, and Bädescu and O' DDnnelll [2021, Theorem 1.4] tells us that this algorithm succeeds outputting estimates (bx with high probability.
(v5) Eg [+) S
When applying Algorithm 1 the observables corresponding gradients described in Appendix D.I, we can exploit that the observables are related sequentially. In between each round k, we rotate both, the states stored in quantum memory and the classical online learner, so that implementing the measurement of the next gradient only requires runtime independent of M. Since these rotations are unitary and do not reduce the quality of any approximations, the same proof as Bädescu and O' O'Donnell [2021, Theorem 1.4] will apply. This establishes Theorem 9.
By Bädescu and O'Donnell [2021, Theorem 1.4], this algorithm obtains estimates bb 00 QNNx(I+)) S e for each & by taking the number of copies to be
nnog? 2 M
m = 0
c4
22

---

Algorithm Online and gentle shadow tomography
Input: m copies of the unknown input state (16) &m m registers each with n qubits. Output: Estimates by R (1b) En (v=)
1.
Set R = O and mo = O log M) ( We need R batches, each with mo copies, so
m Rmg copies in total. This gives in total
nog'" M
m
2. Initialize the online learner wi according the online learning algorithm.
3. Start with the first batch of copies (&b) @mo.
4. For each k = , M:
(a) Use the online learner to predict a = Tr( (xwk))
(b) Use threshold search to check |ax- - (1b Ei |
(c) If threshold search passes |ax- (vbl Fa S E,
i. Output estimate by <- ag-
ii. Leave the online learner unchanged Wi+1 Wk-
(d) If threshold search concludes |ag (v> Bx|b>| > A and in fact lbg. (1b) Ex/}) S l.c
Output estimate by-
ii Update online learner with by (6b Ex (b) get wk+1-
iii. Discard the current batch and move onto a fresh batch mm).
Moreover, the required number of quantum operations
O(mM)= = o n.M log M
This is quasi-linear in M. With naive storage of the entire density matrix of the hypothesis state wis the classical cost is
M 2())
Which also linear in M, but unfortunately exponential the input size n. We present the full algorithm for gradient estimation using online shadow tomography with threshold search in Algorithm 2.
23

---

Algorithm 2 Shadow tomography protocol for gradients of a quantum neural network
Input: m copies of the unknown input state (p)) m registers each with n qubits. Output: Estimates by 2 20, ((2)) for k = .,..., .M
1. Set R ( and mo O log" )) We need R batches, each with mo copies, m = Rmg copies in total. This gives
2²
12 log" M
0
g
2. Define for each I,..., M
1 (10)1va) + +1))(b))
(wb) V2
and recall from Remark 18 that
(Nh k/h) = 2 do QNN x(+)
3. Attach the output qubit and an ancilla qubit the +) state to each register. Label the output qubit O and the ancilla qubit *.
4. To each register, do the following:
(a) Apply control-24, V conditional on the ancilla being (0). This requires ((1) quantum operations.
(b) Apply control-U conditional on the ancilla being [1). This requires O(M) quantum operations. This step is analogous to the initial forward pass in classical backpropaga- tion.
(c) This produces the state ) ymmm
5. Initialize the online learner wi according to the online learning algorithm.
6. Start with the first batch of copies [x1] Sm
7. For k = 1,... M, do the following. This loop is analogous to the backward pass in classical
backpropagation.
(a) Use the online learner to predict a = Tr(X.wH,
(b) Use threshold search to check |ag (1/x /.x)l.
This takes time independent of M.
(c) If threshold search passes |ax (vx) X- (ba) Se.
Output estimate by <- dg.
ii Leave the online learner unchanged wh+1 + Wk-
(d) threshold search concludes |as (w/ (//llX,//x)) A and fact [bx.
E,
i. Output estimate by
ii Update online learner with by No (s/e/X,/bs) (bx) to get ws+1-
iii. Discard the current batch and move onto a fresh batch.
(e) To each register in the current batch and the unused batches, do the following:
i. Apply control- (e +
Px) conditional the ancilla being 10).
This implements (4 (14 ) and only requires O(1) quantum operations.
ii Apply control-e 102+1 UR+1 conditional on the ancilla being [1). This imple-
ments 41 (0) (2(()) and only requires 0(1) quantum operations.
iii. This produces in each batch (a noisy approximation to) the state |/x4)) Smm,
(f) Also apply the rotations in Step (e) to the hypothesis state wk+1 classical memory.
The online learner now approximates (1/++al
24

---

E Fully gentle gradient estimation
In this section, motivate for a need perform sequential and gentle measurements individual gradient states, as opposed to superpositions of them. Thereafter, we discuss general strategies based on gentle measurements alone, performed on single and multiple copies.
E.1 Considering individual gradient states
While we briefly motivated the need for sequential reuse information in measurements in the main text, here we further motivate such a construction as a necessary, but perhaps not sufficient condition for our purposes. Given that one can create a superposition over all the potential gradient components cost that only requires a single function call, it is natural to ask if this ability gives us any headway in achieving our goals. Consider exploiting the superposition over all gradient states
(V)
Σ 1=1
Ch
(Ax)
II jEA
10
Σ ch [Ax) l1he),
(31)
using at most c. calls to the family {U,} and some ancillary qubits (Ag) associated with the hth gradient state.? Creating such superposition weakens our ability to extract each gradient component's signal upon measurement, and thus, requires more samples to distinguish between gradient components with desired precision. From a cost perspective, it remains optimal or equivalent consider gradient states ($xx) individually. To make this more concrete, consider a state discrimination task, with the following lemma at hand.
Lemma 21 (Optimal two-state discrimination). Any quantum algorithm that distinguishes two states P1 and p2 using single copy of each state with probability at least 0.9 requires
++zller 2 + -Plllp1
- P2ll.r 2 0.9.
(32)
Now we may proceed to the state discrimination task, where it is clear superposition is not helpful. Proposition 22. Consider the two-state discrimination task for two scenarios. First, given (2m) and (ém), where (uml@m) = O, there is a measurement strategy that can distinguish the states with single measurement. Second, given the states
M
1
Aa) (1b))
(33)
VM
and
M
An) lox)
(34)
M
where (bb)) = (ox) for every lo except the copies are required by any strategy aiming to discriminate (V) from (b) with reasonably high success probability.
th component and (1mllm)= = 0 as before, then ((M)
Proof. The first scenario follows straightforwardly from Lemma (21) since there is overlap between (pm) and (dm) - hence, their trace distance 1 and Equation (32) always holds. For states in uniform superposition over all M components, the overlap is 1 1/M which is close unity for large M, indicating the difficulty of the task when the states mostly overlap. Given access to N copies of (V) and (D), to discriminate with probability least 0.9 requires
2
(W 2N 0.9,
(35)
or cquivalently
1 2N
1
0.36
(36)
M
implying that N = ?(M) in order to discriminate successfully with the desired probability.
Fc is some small constant.
25

---

From Proposition (22), we have the immediate corollary.
Corollary 23. It is either optimal or equivalent in cost to consider gradient states individually, as opposed to a superposition over them all.
Proof. Replacing the uniform superposition in Equations (33) and (34) to the more general, [V) =
Σx=1 (Ax) libx) and | >x= Cp (Aa) (ox) the number of samples needed to discriminate
the mh component scales as N ~ 1/cm- Since en E [0, 1]. it is clear that en = 1 is optimal. If there M components, then ci. 1/M and hence, N ~ M. Assuming the superposition state (V)
incurs a cost proportional to M, the number of samples required to differentiate between components in the wave function will imply an overall cost that scales M².
E.2 A case for sequential and gentle measurement
Whilst the cost equivalence presented in Corollary 23 implies no benefit from superposition of gradient states, also suggests that, one is to obtain backpropagation scaling, individual gradient states must be utilized in more resource efficient manner. Drawing inspiration from backpropagation, one could instead use the state |t/t.) to make measurement, then update it to (1x+1) without substantially disturbing it, it would then be possible to perform all of the measurements at overall cost scaling like (M)) We illustrate such a benefit by means of an example using fictitious non-destructive measurements in Algorithm 3.
Algorithm 3 Gradient estimation with modified, non-destructive swap test
Input: Three registers initialized to |+) (0) (0)
Output: Gradient vector estimate for F(0)
1. Apply U(f) UM to the second register, controlled on the first being 0. Cost ~ M.
2. Apply (U) to the third register, conditional on the first being 1. Cost ~> M and the state becomes
10) 10) +
V2 (00) (MM) > (0) + (1) (0) (A)),
where / = UM 10) and (A) = OU U1 10). By assumption, all U, and O are hermitian and unitary.
3. For k in (M, 1,.... 1}:
(a) Apply and update (vxx) = iPP læbe conditioned on ancilla being O. Cost 1.
(b) Perform den-eustruetive swap test on the state
(10) (bbe) (0) + [1) 10) (A))
/2
to estimate [F)), = 2 Tm (A/pha) with no damage to the state. Cost ~ 1.
(c) k > apply and update (A) = Ut (A] conditional on ancilla being 1. Cost ~
(d) k > apply and update [2/k-1) = (iP%) (xxx) conditional on ancilla being 0. Cost 1.
The procedure naturally breaks down in real quantum computer at Step (3b) due the reliance non-destructive measurements. Substituting these for gentle measurements, which are only partially non-destructive but, at least, theoretically possible, one may still aspire exploit the structure of the problem and achieve backpropagation scaling as in Algorithm 3.
E.3
Gentle measurement on single copies
The need to reuse a state enough times to extract every gradient component, imposes constraints on the gentleness of measurements made. While the use of multiple copies may enhance the ability straightforward see why this approach would not work in general, when given access to single copy of p. Using scheme like the modified swap test in
to leverage gentle measurements,
26

---

Algorithm 3, implies that each measurement must be on average 1/M -gentle in order to reuse the state M times to extract each gradient component without damaging the state to the point that least one observable on the state is completely wrong. Enforcing such a constraint, leads to measurements that are trivial i.e. they barely depend on p and cannot yield enough information about gradients. We recap some useful lemmas whose proofs can be found in Aaronson and Rothblum [2019] to make this more concrete.
Lemma 24 (Additivity of damage). Let be some mixed state and let S S2,.... Sus be general quantum operations. Suppose for all j. we have
[| - -plls S Saj,
then
(SM-
pller S 0n +... OMM-
Lemma 25 (Trivial measurement). Given measurement M and parameter 2 O, suppose that for every two orthogonal pure states (ı²) and (Ø), and every possible outcome y of M, we have (l(M()W)) outputs v] I e (l(M) outputs y). Then M is n-trivial. Further, let E1 + Ex.- I be the POVM elements of M. Assume without loss of generality that the outcome corresponds to the element E E₁. Then.
(vb) E (b> S e (Ø) E (0).
holds for all states, not just all orthogonal (W) 1()--
Lemma 26 (Triviality lemma). Suppose a measurement is a-gentle on all states. Then the measure- ment In [1+4a) 1-44 -trivial so particular, D(a))-tivial provided S 4.01
Equipped with these lemmas, we proceed to demonstrate the difficulty of gentle gradient estimation with single-copy access to pure state.
Theorem 27. sequence of M measurements on a single-copy pure state that is 1/M-gentl at every step to extract every gradient component, will be trivial.
Proof. Choose circuit such that gradient state differs substantially, i.e. [1]x)))(txl Key for all measurements. In other words, there is a unitary that must be applied to advance from gradient component i j. otherwise there will be measurement that produces the incorrect result if no such unitary is applied. Fix {A, 1- - Aj as the POVM elements of a gentle measurement. Assume without loss of generality that the outcome of measuring the gradient component with respect given state corresponds to the element A = A A. and
(p)(p) pller S
(37)
where
S(p) = ApAt
Tr[Ap]
Using single copy of |4>x to extract all M gradient components, requires advancing the state after measuring gently at each step, and thus, each measurement step must on average 1/M-gentee to ensure
par Il. < 1,
(38)
where PM is the density matrix representation of the advanced gradient state (WAr) = UMU1 (e). If we allowed for any more damage at a particular step, we could eventually reach a point where subsequent measurements yield incorrect results, as the cumulative damage to the state may exceed 1. While the gentleness could be distributed across each gradient component in different ways, from the above lemma, we see that the more gentle the operator, the more trivial it becomes. Hence, if we had (M - 1) 0 --gentle measurements, they would be infinitely trivial and provide no information with informative measurement. Hence, the least trivial set of measurements that achieve an average of 1/M gentleness would be to have each mcasurement be 1/M gentle. By Lemma (26), then each measurement will be (LL/M)-trivin which implics
Tr[Ap:] S e 1/M Tr[Apt+]]
for any two gradient states pts Pi+ . As M increases, the estimates for all gradient components will converge. Therefore, the measurement operator has an exponentially vanishing dependence on the input states themselves and hence, provides little-to-no information about the gradient components.
27

---

E.4 Multiple copies and non-collapsing measurements
Non-adaptive, non-collapsing measurements are, by assumption, measurements that do disturb the state of a quantum system at all. Under this assumption, the complexity class, non-adaptive Collapse- free Quantum Polynomial time (naCQP) was introduced. With this ability, searching through an unstructured M-element list can be performed in Ó(M time, which faster than the optimal lower bound of ((M²) given by Grover's search algorithm [Grover, 1996]. Importantly, time complexity in naCQP measured the number of oracle queries plus the number of non-collapsing measurements. This definition considered more fitring, since any task in naCQP allows for exponentially many non-collapsing measurements to be made and should thus, be accounted for.
Interestingly, one may still violate Grover's bound by allowing for approximately non-collapsing measurements. First, note that
- IP-- =0
for non-collapsing measurements, where p' the normalized state after measurement. In the approximately non-collapsing regime, assume that measurement operator can be applied to tensor product the state & such that
||00 / a.
As a + 0, we recover the non-collapsing measurement regime. In the gradient setting, approximately non-collapsing measurements are merely gentle measurements. This leads to the following. Proposition 28. A sufficiently gentle measurement used for gradient extraction can solve unstruc- tured search problem in ((M)) time.
Proof. Reformulating the gentle gradient task as search problem, let M = 2", Consider the state
sin((2i + 1)0) (x)) [1) + cos((2i + 1)0)
Σ
x
1y) 0))
(39)
(E wrt
after applying = M Grover iterations, where (x) is the marked state. The probability of measuring the marked state is sin((2i 1)0) = 1/M Suppose we create the state (y))@m, where m (log((M) (M) by using M log( (M) Grover queries. By having access multiple copies of [v).
assume that one may implement a 1/M-gentle measurement on the copies as required for gradient estimation. Then, the probability of observing the marked state after a single gentle measurement log( /M) $. By performing M gentle measurements on the log(M) copies, the probability of
obtaining the marked state at least once is greater than 1 - e lolog(a)) = 1 - x/: using only Ö(M+) Grover oracle queries and ((M+) partially non-collapsing measurements, and thus, runs in time Ö(M +).
28


Reviews:
[{"review_id": "70j6jscCto", "reviewer": "Reviewer_Hoi6", "summary": "The authors go over the backpropagation scheme for both classical and quantum machine learning methods. They also propose a novel quantum backpropagation algorithm based on quantum shadow tomography to reuse information and reduce the time complexity. ", "questions": "1. Whether this level of space complexity on the classical device is acceptable?\n2. Could you be more explicit about and also highlight the potential impact of this paper on the quantum machine learning society?\n", "limitations": "The major limitation is whether this paper fits the scope of the research paper in NeurIPS. ", "rating": 7, "confidence": 4, "soundness": 4, "presentation": 3, "contribution": 4, "strengths": "1. This paper provides a link between quantum backpropagation and quantum shadow tomography, which are both important in quantum computing.\n2. This paper provides a thorough background check on quantum backpropagation, information reuse scheme in QST, and backpropagation scaling problem.\n3. This paper is technically sound.", "weaknesses": "1. This paper is more like a report paper than a research paper to me, since the main contribution is to discuss in detail how reusing information can benefit quantum backpropagation, and the proposed algorithm seems quite trivial.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for their helpful comments on our work and are grateful for the positive feedback. Regarding the reviewer’s questions, we have the following responses:\n\nThe proposed algorithm: While the proof that our algorithm works leans heavily on the existing machinery of shadow tomography, we believe the connection of shadow tomography to a dynamic program through rotations at each threshold check to be an interesting contribution.  A naive implementation of shadow tomography with the same observables does not achieve a quasi-linear scaling in M, even with exponential offline computational effort, and at a glance it is not obvious this scaling is achievable due to the sequential nature of the program.  This challenge is also highlighted by the fact that no other gradient method for parameterised quantum circuits achieves a quasi-linear scaling in M. This represents substantial progress in this regard, but of course, as the reviewer points out, the classical storage may be an inhibitor, which we leave as an open problem.\n\nAcceptable space complexity: We believe that the answer here depends on the context of what the ultimate goal is, and what resources one has available relative to the problem size. In general, however, this (classical) space cost is indeed prohibitive and we suggest that future research try to address this issue by finding more efficient offline representations of states.  For small quantum learning applications, e.g. a number of qubits < 50, the exponential offline representation may be acceptable due to data advantages in manipulating the state.  This is in contrast to seeking strict computational advantages.  However at larger sizes, an efficient computational representation is sure to be needed, and efficient approximations or special cases remain an interesting open direction.\n\nImpact: In traditional machine learning, the efficient scaling of backpropagation has a strong influence in the architecture of learning models.  Certainly if the scaling in number of parameters was quadratic, billion parameter deep networks would essentially impossible today.  Hence, what seems like a small scaling difference has historically had an immense impact on the models used, and we believe this could be true in the quantum case as well. Parameterized quantum models are very popular in the field of quantum machine learning and there seems to be some ignorance around the scaling of resources to train such models, naively appealing to the success of large classical networks without accounting for the fundamental scaling difference of all previous schemes. Additionally, there have been no proposals for gradient methods of parameterized circuits which achieve quasi-linear scaling in M. Bringing these issues to light is much needed and developing a more efficient gradient procedure is much needed. We believe our work addresses these issues and provides much needed intuition as to why parameterized quantum models struggle to exhibit favorable scaling like that seen in neural networks equipped with backpropagation.\n\nRelevance for Neurips: Interest in quantum machine learning has increased greatly over the years, with accompanying (and sometimes bold) claims that quantum computers will improve current machine learning methods in some manner. Many papers aiming to demonstrate a quantum advantage use parameterized quantum models and often ignore the problem of resource scaling as the model size increases. Establishing clear results in this regard, is important for the machine learning community as a whole to get a sense of issues prevalent in these commonly used quantum machine learning models and how they may impact proposed results. Thus, we believe our work is relevant to both quantum and classical machine learning researchers.\n\nAgain, we would like to thank the reviewer for their insightful feedback and positive assessment of our work. We hope that these additional comments help clarify any open questions and we would happy to supply more details if needed. \n"}, {"review_id": "9AYtMkbN3x", "reviewer": "Reviewer_mok7", "summary": "The paper studies the scaling of computing the gradient of a quantum neural network. While in the classical case we can use backpropagation, which gives the same linear scaling for computing the gradient and the forward pass, in the quantum case, we would naively have to run a circuit for each component of the gradient, leading to a squared complexity in the number of parameters, which prevents studying quantum models with large number $M$ of parameters.\nThe authors formulate this problem in the language of shadow tomography and apply ideas from that field to the problem at hand.\nThis shows that while an $M\\log M$ scaling is possible using polylog copies of the input state. This comes at a drawback of classical cost that scales as $2^n$ with $n$ the number of qubits. Resolving this exponential scaling would resolve some open problems in shadow tomography.", "questions": "- Can you add a related work section to highlight the novelty with respect to previous work?\n- Can you explain what is rotate/threshold check in figure 1? Can you add more intuition around proposition 7 to see how gentle measurements are used, e.g. what is alpha in this case? What is the role of $\\sigma$? \n- Can you comment on what problems could benefit from the proposed protocol, namely small $n$ and large $M$?\n- Can you explain why approximations to $\\sigma$ using for example tensor networks could be more robust than just simulating the quantum neural network with tensor network?", "limitations": "- As the authors say several time, the main limitation is that their algorithm come with a classical exponential scaling that limits its applicability. ", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 2, "contribution": 2, "strengths": "- Relevant problem in quantum ML.\n- Connection with shadow tomography and application to scaling of gradient computation is new and can lead to new ways to think about the problem\n- Rigorous statements supporting scaling \n- Well written paper", "weaknesses": "- The paper relies on quantum information concepts that are not necessarily familiar with the ML audience at the conference.\n- When talking about memory requirements of backprop in classical neural networks, one needs to store activations for reverse mode autodiff. This leads to memory that scales with the number of layers, while in the quantum case by analogy the number of qubits does not scale with the number of layers. The authors could comment about this.\n- I was confused by Prop. 3: is the proof considering the case of a number of parameters $4^n$? I am not sure what we learn from this example since it does not seem to be part of the quantum neural networks we would like to train.\n- The classical scaling as $2^n$ required for the proposed algorithm restricts a lot the class of problem for which this protocol can be useful. \n", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We highly appreciate that the reviewer regards our paper as well-written and technically sound, and we are grateful for their comments and insightful feedback. We aim to answer the questions raised below and would be happy to provide any further details as needed:\n\nRelated work section: We would be happy to add a related work section as suggested by the reviewer, or to more explicitly point out the novelty of our contribution in the introduction. For readability, related work is currently referenced mainly in Remark 4, which demonstrates the current scaling for proposed gradient methods.  This comparison to related work helps highlight the need for improved scaling in many quantum gradient methods.\n\nRotate/threshold check: In figure 1, the rotate blocks can be understood as sequentially applying parameterized operations in the quantum neural network in order to estimate the next gradient component. Intuitively, this is similar to sequential layers in a neural network. The threshold check uses sigma, the hypothesis state, to estimate gradient components and check whether these estimates are acceptable. It does so by performing a gentle operation using copies in memory that checks if the gradient estimate exceeds a particular threshold. If the threshold is not exceeded, the protocol advances to the next rotation and threshold check. If the threshold is exceeded, then a destructive measurement is performed and a fresh batch of copies are then needed to execute the rest of the protocol. A full description is given in the supplementary material.\n\nIntuition around Proposition 7: This proposition succeeds largely due to two factors, special properties of Paul operators and the ability to perform measurements on multiple copies. The procedure first exploits the fact that while two Pauli operators do not necessarily commute, i.e. P_1 P_2 \\neq P_2 P_1, the tensor product P_1 \\otimes P_1 does commute with P_2 \\otimes P_2. With such an observation, and the ability to measure two copies, the procedure is able to estimate the magnitude of every gradient component with a number of copies that scales logarithmically in M, since measurements on two copies can be performed such that they are not completely destructive (i.e. alpha is small). Then, using the magnitude information, the procedure performs a so-called majority vote measurement to extract sign information. This too can be done in a gentle manner thanks to the promise induced by the magnitudes being a certain size (the smaller components are ignored). \n\nThe role of sigma: Sigma is crucial to the success of our proposed algorithm, as well as other state-of-the-art shadow tomography protocols. It acts as a proxy for our true quantum state of interest and is used in the protocol to estimate gradients offline. The hypothesis state is typically refined as one conducts a particular protocol, such that it better approximates the true quantum state and we can then use it to obtain better estimates of the gradient. Refining sigma is the key to succeeding with quasi-linear scaling, as one can rigorously show that there will be a bounded number of updates necessary.  Without proof that sigma updates “quicky” we would be reduced to naive measurement collapse, as is shown in Appendix E to be inefficient.\n\nProblems that could benefit from the proposed protocol (small n, large M): This is a good question and an ongoing area of research. At present, there are proposed schemes to take advantage of quantum data (see for example, quantum advantage in learning from experiments) that see substantial advantages at a modest number of qubits ~20-40 using kernel schemes.  There the advantage results from quantum data availability, so classical computational simulation provides no competition.  Schemes utilizing parameterized quantum circuits may require a large number of parameters to learn from the same quantum states, and as such M may be in the 10’s of thousands or greater such that M >> n, in such cases it is not unreasonable to bear the burden of the classical computational expense incurred with current schemes to estimate the gradient.  In practice, quantum hardware is currently forced to keep n small, and there have been some empirical studies about overparameterizing such a model.   The empirical results of classical, overparameterized networks support the idea that best performance may lie beyond a phase transition in a large, overparameterized regime, and reaching such a regime is likely to require a nearly linear overall scaling.\n\nOn tensor network approximations to σ - Our meaning here is that the requirements of shadow tomography are less stringent than more standard measures of accuracy, such as trace distance, which quantify worst case error on observables.  In the case of shadow tomography, it is only asked that most observables be correct, most of the time, colloquially speaking.  As a result, even hypothesis states that are strictly speaking, orthogonal to the true state, can satisfy this requirement and numerical approximations such as tensor network states may get many relevant observables correct.\n\nWe thank the reviewer again for carefully reviewing our work and providing helpful feedback. If there are still any open questions for the reviewer, we will be happy to discuss and look forward to the upcoming discussion period."}, {"review_id": "Wq8A0ZksJo", "reviewer": "Reviewer_efhf", "summary": "The paper explores whether parameterized quantum models can achieve comparable training efficiency to classical neural networks. From the perspective of reusing quantum information, the paper demonstrates that achieving backpropagation scaling in quantum models is not feasible without access to multiple copies of a state. With access to multi-copies assumption, the authors propose an algorithm that achieves backpropagation scaling using gentle measurement and online learning while reducing classical auxiliary computational costs. These findings shed light on reusing quantum information for the challenges of training large quantum models.\n", "questions": "1. In proposition 7(193), as the variational model is defined as the trace of a quantum state, i.e. $tr[U_\\theta \\rho U_\\theta^\\dagger]$, the loss will always be constant 1, so no matter what $\\theta$ we choose the gradient will always be 0, so it is confusing that what's the contribution of the gradient in such setting and whether in the general case, it also achieves $O(\\frac{\\log(M)}{\\epsilon^4})$ backpropagation scaling. \n2. In the proof of theorem 12(281), As in definition 8, $\\mathcal{U}(\\theta)=e^{-i\\theta_M P_M}\\dots U_1$, why each parameter $\\theta_i, i\\in[M]$ associated with the same $P_i=Y_0\\otimes Z_1$ and whether the first term in the Pauli string $P_i$ should not be $X_0$ when observable set as $Z_0$?\n3. when we choose random Pauli strings $P_j$ and the initial setting of $\\theta$ is NOT 0, whether the theorem 12 still holds?\n", "limitations": " ", "rating": 5, "confidence": 3, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "The paper investigates the backpropagation in quantum models which is interesting and of general interest to the community of QML. It combines online learning and shadow tomography to achieve $O(polylog(M))$ sample complexity for gradient estimation. ", "weaknesses": "1. Even though the proposed method achieves $O(polylog(M))$ of sample complexity, it also requires exponential classical resources which is not practical for handling a large system.\n2. It only provides the theoretical analysis and does not give some proof-of-principle numerics.\n3. Some necessary details and the related brief introduction of the proposed methods should be listed in the manuscript instead of supplementary.\n", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We would like to thank the reviewer for taking the time to go through the manuscript and provide useful feedback and suggestions. We are glad that the reviewer sees our work as relevant for the quantum machine learning community and we have drafted a response to the reviewer’s questions below:\n\nRegarding proposition 7 - We thank the reviewer for their careful reading of the paper.  Indeed the listed formula is incorrect and was meant to be updated to a form similar to that in Equation (8), using an ancilla qubit to correctly form the reduction to the measurement of all Pauli operators.  This will be corrected in all updated versions of the draft, but no essential results in the paper change from altering this example case.\n\nQuestion about the proof of theorem 12(281): It is true that each theta_i is associated to the same Pauli generator Y_0 \\otimes Z_1. However, note that the U_i layers are all different, and encode the observables of the shadow tomography problem we are reducing from.\n\nIf theta is not 0, does theorem 12 still holds: The main aim of this argument is to show that estimating gradients is a strictly harder task than performing shadow tomography. We show the reduction holds even for the special case of initialization to zero, which we believe makes our case even stronger. Also note that the layers U_i can be interpreted as consisting of gates where theta are not zero.\n\nWe hope that these comments are helpful for the reviewer and we would be happy to provide any further details in the discussion period. We thank the reviewer again for taking the time to review our work and considering it for Neurips 2023. \n"}, {"review_id": "E9J0ekIe1v", "reviewer": "Reviewer_vTRX", "summary": "This paper explores the efficiency of training parameterized quantum models, from the perspective of backpropagation scaling. By leveraging some recent developments in shadow tomography and accessing multiple copies of a quantum state, the authors propose an algorithm that matches backpropagation scaling in quantum resources and reduces additional classical computational costs. The results provide valuable insights into the reusability of quantum information and the results are potentially meaningful for the future of quantum machine learning.", "questions": "- Could the authors provide more insights into the practical implications of the results and its potential applications?\n- How do the results of this work extend to other quantum neural networks?\n- There are a certain number of existing works on the gradients of quantum neural networks. How does Proposition 7 advance the known works?\n- What is the relationship between this work and the problem of the barren plateau?", "limitations": "NA.", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "- The paper investigates a timely and relevant topic in quantum machine learning, comparing the efficiency of training parameterized quantum models to classical neural networks.\n- The authors leverage recent developments in shadow tomography, providing a novel approach to study a meaningful problem on quantum neural networks.\n- The proposed algorithm matches backpropagation scaling in quantum resources and reduces classical auxiliary computational costs.\n- The angle of this work to study quantum neural networks is novel.", "weaknesses": "- The primary analysis is limited to quantum neural networks based on variational quantum circuits, which restricts the scope of the paper as many other types of quantum neural networks exist.\n- The application of the results to general quantum machine learning algorithms is not convincingly demonstrated.\n- The paper lacks a clear and well-motivated example demonstrating the application of the proposed methods, making it difficult to assess its practical implications and usefulness.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We are grateful for the positive feedback from the reviewer and thank them for taking the time to provide an insightful review. We seek to address the reviewer’s concerns and questions below and would be happy to have any further discussions on any points that may remain unclear:\n\nPractical implications and applications: Many of the current architectural approaches in classical deep learning stem from the efficient scaling of gradient computations in number of parameters.  If the scaling was quadratic in number of parameters, as is the case in current quantum algorithms, no billion parameter networks would be usable.  If large sizes are needed to cross into an effective overparameterized regime, even in the quantum case, this would be virtually impossible.  This has the potential to dramatically shift the preferred architectures from quantum neural networks to kernel methods, or specialized networks made for training, as is sometimes done classically.  In either case, there can be large shifts in design choices and successful algorithms from this small factor alone.\n\nExtension of results to other quantum neural networks: Our results are pretty general and encompass almost all architectures termed ``quantum neural networks’’. Equation 8 defines a QNN model and one may see by the general form of U(theta) that layers of parameterized rotations and any fixed operations may be applied. \n\nApplication of proposition 7 to known results: One example application of the results of proposition 7, is that it allows the magnitude of all Pauli observables to be measured using only 2 copies at a time, with a logarithmic number of repetitions.  This allows the screening step for Adapt VQE to be done with only a log number of repetitions in the candidate pool of operators, which is an exponential improvement over recently proposed schemes.  If more copies can be kept in quantum memory, this can be used to determine the signs as well, but this is not a requirement for improving current Adapt VQE operator pool schemes.\n\nRelationship with barren plateaus: The relationship between our work and the barren plateaus result is somewhat orthogonal. While the findings of both works indicate a difficulty in training quantum circuits, we examine the scaling of resources needed to estimate gradients to within some fixed precision. If one experiences a barren plateau where gradients are exponentially vanishing, a higher precision would be needed to extract enough information to update gradients.  \n\nWe thank the reviewer again for providing us with useful feedback and hope that these comments helped clarify the questions posed by the reviewer. \n"}]

Author rebuttal:

Meta-review: This paper explores the efficiency of training parameterized quantum circuits, from the perspective of backpropagation scaling. By leveraging quantum shadow tomography, the authors propose an algorithm that matches backpropagation scaling in quantum resources. This paper provides valuable insights into quantum machine learning especially the reusability of information in the backpropagation.

This paper investigates a timely and relevant topic in quantum machine learning, the training efficiency of parameterized quantum models, from a novel perspective. The proposed algorithm leverages the recent development in quantum shadow tomography and also matches the backpropagation scaling in quantum resources to reduce the classical computational costs. The authors also provide rigorous theoretical analysis to support their statements and demonstrate a clear view of how to transfer the insights from classical neural networks to parameterized quantum models.

Several problems regarding the practical use, the exponential scaling, and the scope of application are raised by reviewers and are solved by the authors' rebuttal.
Decision: Accept (spotlight)