QuACK: Accelerating Gradient-Based Quantum Optimization with Koopman Operator Learning
Authors: Di Luo
Jiayu Shen
Rumen Dangovski
Marin Soljacic
Venue: NeurIPS 2023 spotlight (2023)
Keywords: Koopman operator
quantum optimization
machine learning
TL;DR: We develop Quantum-circuit Alternating Controlled Koopman learning for accelerating quantum optimization

Abstract: Quantum optimization, a key application of quantum computing, has traditionally been stymied by the linearly increasing complexity of gradient calculations with an increasing number of parameters. This work bridges the gap between Koopman operator theory, which has found utility in applications because it allows for a linear representation of nonlinear dynamical systems, and natural gradient methods in quantum optimization, leading to a significant acceleration of gradient-based quantum optimization. We present Quantum-circuit Alternating Controlled Koopman learning (QuACK), a novel framework that leverages an alternating algorithm for efficient prediction of gradient dynamics on quantum computers. We demonstrate QuACK's remarkable ability to accelerate gradient-based optimization across a range of applications in quantum optimization and machine learning. In fact, our empirical studies, spanning quantum chemistry, quantum condensed matter, quantum machine learning, and noisy environments, have shown accelerations of more than 200x speedup in the overparameterized regime, 10x speedup in the smooth regime, and 3x speedup in the non-smooth regime. With QuACK, we offer a robust advancement that harnesses the advantage of gradient-based quantum optimization for practical benefits.

QuACK: Accelerating Gradient-Based Quantum Optimization with Koopman Operator Learning
Di Luo
Jiayu Shen Department of Physics. University of Illinois, Urbana- Chaaa-Chammpain Urbana, IL 61801, USA Illinois Quantum Information Science and Technology Center Illinois Center for Advanced Studies of the Universe j 1aayss@@ilinois. edu
Center for Theoretical Physics,
Massachusetts Institute of Technology.
Cambridge, MA 02139, USA Department of Physics, Harvard University, Cambridge, MA 02138, USA
The NSF AI Institute for Artificial
Intelligence and Fundamental Interactions diluo@mit.cm edu
Rumen Dangovski
Marin Soljačić Department of Physics,
Department of Electrical Engineering and Computer Science, Massachusetts Institute of Technology Cambridge, MA 02139, USA rumenrd@mit... edu
Massachusetts Institute of Technology Cambridge, MA 02139, USA jeljacic@mit...
Abstract
Quantum optimization, key application of quantum computing, has traditionally been stymied by the linearly increasing complexity of gradient calculations with an increasing number parameters. This work bridges the gap between Koopman operator theory, which has found utility in applications because it allows for linear representation of nonlinear dynamical systems, and natural gradient methods quantum optimization, leading to significant acceleration of gradient-based quan- tum optimization. We present Quantum-cirent circuit Alternating Controlled Koopman learning (QuACK), novel framework that leverages alternating algorithm for efficient prediction gradient dynamics on quantum computers. We demonstrate QuACK's 's remarkable ability accelerate gradient-based optimization across range of applications in quantum optimization and machine learning. In fact, our empirical studies, spanning quantum chemistry, quantum condensed matter, quan- tum machine learning, and noisy environments, have shown accelcrations of more than 200x speedup the overparameterized regime, 10x speedup in the smooth regime, and 3x speedup in the non-smooth regime. With QuACK, we offer robust advancement that harnesses the advantage gradient-based quantum optimization for practical benefits.
Introduction
The dawn of quantum computing has ushered in new era of technological advancement, presenting a paradigm shift how we approach complex computational problems. Central to these endeavors are Variational Quantum Algorithms (VQAs) [14], which are indispensable for configuring and optimizing quantum computers. These algorithms serve as the backbone of significant domains,
Corfirst authors
37th Conference on Neural Information Processing Systems (NcurIPS 2023).

---

including quantum optimization [54] and quantum machine learning (QML) [8]. VQAs have also influenced advances in various other quantum learning applications [17, 24, 24, 32, 45, 28, 43, 27, 67]
At the core of VQAs lies the challenge of effectively traversing and optimizing the high-dimensional parameter landscapes that define quantum systems. To solve this, there are two primary strategies: gradient-freee [72] and gradient-base
methods [38]. Gradient-free methods, while straightforward and widely used in practice, do not provide any guarantees of convergence, which often results in suboptimal solutions. On the other hand, gradient-based methods, such as those employed by the Variational Quantum Eigensolver (VQE) [59, 78), offer guarantees for convergence. This characteristic has facilitated their application across multitude of fields, such as high-energy physics [34, 65], condensed matter physics [83], quantum chemistry [58], and important optimization problems such as max-cut problem [19, 23).
More specifically, recent developments in overparameetrization theory show that gradient- based methods like gradient descent provide convergence guarantees in a variety of quantum optimization tasks [37, 44, 87]. New research indicates these methods surpass gradient-free techniques such as SPSA [72] in the context of differentiable analog quantum computers [38]. Notably, the quantum natural gradient, linked theoretically with imaginary time evolution, captures crucial geometric information, thereby enhancing quantum optimization [73].
Despite these advantages, the adoption of gradient- based methods in quantum systems is not without its obstacles. The computation of gradients in these hybrid quantum classical systems is notoriously rexource-intensivve and scales linearly with the number of parameters. This computational burden presents a significant hurdle, limiting the practical application of these methods on quantum com- puters, and thus, the full potential of quantum optimization and machine learning. Hence, we pose the question, "Can we accelerate prudient-based quantum optimization?" This is crucial to harness the theoretical advantages of convergence for practical quantum optimization tasks. In this work, we answer our question affirmatively by providing order-of-man -f-manitude speedups to VQAs. Namely, our contributions are as follows:
By perceiving the optimization trajectory in quantum optimization as a dynamical system, similarly to [15, 61] we bridge quantum natural gradient theory, overparameterization theory, and Koopman operator learning theory [36], which allows for a linear represenation of nonlinear dynamical systems and thus is useful in applications.
We propose Quantum-cireuit Alternating Controlled Koopman Operator Learning (QuACK), a new algorithm grounded on this theory. We scrutinize its spectral stability, convex problem convergence, complexity of speedup, and non-linear extensions using sliding window and neural network methodologies.
Through extensive experimentation in fields like quantum many-body physics, quantum chemistry, and quantum machine learning, we underscore QuACK's s superior performance, achieving speedups over 200x, 10x, 3x, and 2x-5.5x in overparameterized, smooth, non- smooth and noisy regimes respectively.
2 Related Work
Quantum Optimization Methods. Owing to prevailing experimental constraints, quantum opti- mization has frequently employed gradient-free methods such as SPSA, COBYLA, and Bayesian optimization [72, 70, 76], among others that alleviate the challenges inherent in quantum optimiza- tion [89, 25, 86). Regarding gradient-based methods, the quantum natural gradient [73] exhibits compelling geometric propertics, and conventional gradient methods such as SGD and Adam are applicable as well. Recent developments in overparameterization theory [37, 44, 87] have provided assurances for SGD's convergence in quantum optimization. We demonstrate an example where the gradient-based based methods find the minimum while the gradient-free method gets trapped in Appendix C. While meta- weta-learning techniques [81,33 33, 85] have been explored to accelerate optimization across var- ious tasks, focus in this work is on the acceleration of gradient-based quantum optimization, given the appealing theoretical properties of such methods. We emphasize, however, that our approach is complementary meta-learning and could be integrated as subroutine for potential enhancements.
Some additional lines of work are related to our study. You al. [88] analyze the convergence of quantum neural networks through the lens of the neural tangent kernel. Similarly, working through

---

Quanium oplimization and ML
b. Data acquisition
c. Koopman operator learning
d. Data prediction
Quantum computer
cost proportional Tigaranu
d(t)
cost independent of
anssta(()
quaaitum measurement CK
function ((O)
sma saress ((fe). (tm)
0it,)
T
0(4.1))
prodicted time series ( 1.... (fn roum)
embesdding
((4) - (((i)))
ciassical optimizer
((ta) (ble)a))
parameters chosen from optimal loss
((ta) = (tppe)
Egge arg min.
(((())
Figure 1: QuACK: Quantum-cireuit A Alternating Controlled Koopman Operator Learning. (a) Param- eterized quantum circuits process information; loss function evaluated via quantum measurements, Parameter updates for the quantum circuit are computed by a classical optimizer. (b) Optimization history forms a time series, the computational cost of which is proportional to the number parame- ters. (c) Koopman operator learning finds an embedding of data with approximately linear dynamics from time series in (b). (d) Koopman operator predicts parameter updates with computational cost independent of the number of parameters. Loss from predicted parameters is evaluated, and optimal parameters are used as starting point for the next iteration.
an effective quantum neural tangent kernel theory, Wang et al. [82] propose symmetric pruning to improve the loss landscape and the convergence of quantum neural networks. Finally, Garcia-Martin et al. [20] study the effect of noise on overparameterization in quantum neural networks.
Koopman Theory. The Koopman operator theory, originating from the 1930s, furnishes framework to understand dynamical systems [36, 80]. The theory has evolved, incorporating tools such as Dynamic Mode Decomposition (DMD) [68] (connected to Koopman mode decomposition [50, 66]) extended-DMD [84, 15, 61, 10, 3, 30, 79, 9], and machine learning approaches [48, 41, 4, 64). While there have been successful applications in neural network optimization [16, 77, 60] and quantum mechanics [22, 35], the linking of this theory with quantum natural gradient and overparameterization theory for optimization acceleration, contributions are built upon works on machine learning using Koopman operator theory [52, 53, 55, 71, 42].
have done, is novel knowledge. Ours and the above
3 Background
Variational Quantum Algorithm (VQA). For a quantum mechanical system with qubits, the key object that contains all the information of the system is called a wave function v. It is an lz-normalized complex-valued vector in the 2 -dimensional Hilbert space. A parameterized quantum cireuit encodes a wave function vho using of parameters O E Rr via an ansatz layer quantum circuit in a quantum computer, as shown in the top-left part of Figure 1. The number of parameters, Paraams- is typically chosen be polynomial in the number of qubits N, which scales much slower than the 2 -scaling of the dimension of & itself in the original Hilbert space.
Variational quantum eigensolver (VQE) aims to solve minimal energy wave function of a Hamiltonian with parameterized quantum circuit. A Hamiltonian H describes interactions in physical system, which mathematically is a Hermitian operator acting on the wave functions. The energy of a wave function is given by L(Φb
(v (H*). VQE utilizes this as a loss function to find the optimal 0- = arg ming ((O) arg ming (t'e) (Hre). Quantum machine learning follows a similar setup, aiming minimize C()) involved data with parameterized quantum circuits ve. which in QML are usually referred to as quantum neural networks.
To minimize the loss function, one can employ a gradient-based classical optimizer such as Adam, which requires calculating the gradient aC/a0, the quantum case, one usually has to explicitly evaluate the loss with perturbation in each direction i, for example, using the parameter-shiff rule [51, 69]: (C(0+ + x/2) [(0,-n/2)) 7/2))/2. This leads to a linear scaling of mparams computational cost, making quantum optimization significantly more expensive than classical backpropagation
3

---

which computational complexity is independent of mparams, while the required memory is still proportional pprrmms- It worth noting that the classical computational components involved in VQE, even including training saaral-network-basee algorithms in the following sections, typically are much cheaper than the quantum gradient cost given the scarcity of quantum resources in practice.
Quantum Natural Gradient. The quantum natural gradient method [73] generalizes the classical natural gradient method in classical machine learning [1] by extending the concept of probability to complex-valued wave functions. It is also theoretically connected imaginary time evolution [73]. In the context of parameter optimization, the natural gradient for updating the parameter 0 is governed by nonlinear differential equation 4. (t) = -nf VoC(((t), where denotes the scalar learning rate, and F' represents the quantum Fisher Information matrix defined Fij (Ore silee/00,/000 /00.000e//eeeeeee /0,)) (drhe/00) (b) /
zt.
Koopman Operator Learning. Consider dynamical system characterized by set of state variables x(t) E IR", governed by transition function ' such that art + = (t).. According the Koopman operator theory articulated by Koopman, a linear operator K. and function exist, satisfying (g(=((t)= = g (x)))))
g(x(t + 1)), where K. represents the Koopman operator. Generally, this operator can function in an infinite-dinn diiente-ddmessionall space. However, when K. is restricted to finite dimensional invariant subspace with R" - R",, the Koopman operator can be depicted as a Koopman matrix K Rmxm. Data acquired from the dynamics are needed to compute the Koopman operator [12, 11J. The standard Dynamic Mode Decomposition (DMD) approach assumes g to be the identity function, predicated on the notion that the underlying dynamics of x are approximately linear, i.e., T operates as linear function. The extended-DMD) method broadens this scope, utilizing additional feature functions such as polynomial and trigonometric functions as the basis functions for g. Further enhancing this approach, machine learning methods for the Koopman operator leverage neural networks as universal approximators for learning g [48].
4 QuACK Quantum-circuit Alternating Controlled Koopman Operator Learning
QuACK. Our QuACK algorithm, illustrated in Algorithm and Figure 1, employs quan- tum circuit vo with parameters 0 for quantum optimization QML tasks. In Panel (a) of Fig- ure I the loss function C(.) is stochastically eval- uated through quantum mcasurements, and classical optimizer updates the parameters. In gradient optimization steps, we obtain a time series of parameter up- Then in Panel (c) this series is utilized by the Koopman op- erator learning algorithm to find embedding for approximately linear dynamics. In Panel (d) this approach predicts the parameter updates for nDMD future gradient dynamics steps and cal- culates (ffm+1), ((m+2)),... (tmm+npxp)
Algorithm 1 QuACK
Input: Quantum circuit the, Loss function C(-), It- erations Niterrs Koopman operator learning parame- ters m (num. simulation. steps msim), 1DDMD (num. DMD steps).
Output: Optimal parameters 0* Initialize: ((a) randomly
Panel (b) following
for i to Raser - do Quantum optimization or QMI:: for l O
dates (tn), ((t,) )........... (tt..,
do Compute gradient (oL(O(t))) and update
0(4+) 0(12+1) using classical gradient-
based optimizer
Compute [(0(1++1))
end for
Koopman operator learning:
In each time step, the parameters are set directly in the quantum circuit for loss function eval- uation via quantum measurements. This pro- cedure has constant cost in terms of the num- ber of parameters, same as the forward eval- uation cost of the loss function. From the VDMD loss function values, we identify the low- est loss and the corresponding optimal time
Train Koopman operator KC and predict optimiza- tion trajectory
Optimal parameters selection: for l: + to m ADMD do
Compute (t((t))
end for
Determine lopt and set O(to) +- (l.pt) end for
In this work we will interchangibly use m and Rain to denote the same hyperparameter. For ease of notation, when indexing looping, and Asim when control for that parameter and plot dependencies.

---

topt = arg min StSt.. StSt MoDMD degradation in case of inaccurate DMD predictions. The algorithm iteratively alternates the simula- tion steps with the Koopman steps for Riter steps, similarly to [77]. To facillate the Koopman operator learning algorithm, we introduce DMD, Sliding Window DMD and neural DMD into QuACK as follows.
(t)(.). This step includes the last VQE iteration Em to prevent
DMD and Sliding Window DMD. Dynamic Mode Decomposition (DMD) employs linear fit for vector dynamics E R where ((2+11) = (t((t)). By concatenating 0 at m + consecutive times, we define (ta) = (t())
-.. 0ttmmm)mm )] We create data matrices (to) and (t1), the latter being the one-step evolution of the former. In approximately linear dynamics, K is constant for all 4g and hence (4)) R K ((p). The best fit occurs the Frobenius loss minimum, given by K O (t1 (too), where + is the Chore-Penrooee inverse.
When the dynamies of 0 is not linear, window and concatenate the steps to form an extended data matrix [18]
instead consider time-delay embedding with sliding
O(to)
((t)
((m)) (lmm+1)
O(L))
(
(0)(t)) (tt)))
Φ(t1)
((tm)]]
(I)
((ta)
((t++1)
((tm+d))
is generated by a sliding window of size + 1 at m + consecutive time steps. Each column of & is time-delay embedding for O and the different columns Φ in & are embeddings at different starting times. The time-delay embedding captures some nonlinearity in the dynamics of 0, with (ta+1)) ~ K $ (t(t)), where K E R=xn(d+1), The best is given by
K = arg mig [0(t++1) - K ( ((tu+))((((to))
K
During prediction, we start with (d+m))+)) K (pb(1+)) and update from (((m+1) 1) to (lmm+2) by removing the oldest data and adding new predicted data. This iterative prediction is performed via (fx++a+1) = K (ttx). Unlike the approach of Dylewsky et al. [18], we do not use an additional SVD before DMD, and our matrix K is non-square. We term this method Sliding Window DMD (SW-DMD), with standard DMD being a specific case when the sliding window size is (d = O). The dima- embedding is related Takens' theorem [75] with similar implementations in Hankel DMD [3] and streaming DMD [26, 21].
Neural DMD. To provide better approximation to the nonlinear dynamics, we ask whether the hard-coded sliding window transformation & can be a neural network. Thus, by simply reformulating & in Eq. 2 a neural network, we formulate a natural neural objective for Koopman operator learning as arg ming, [|O(t++1) K & (f(f)) where K E X.uut is linear Koopman operator and 4. (O(1)) is nonlinear neural embedding by a neural network $,, with parameters a. P. NN, & is a composition of the neural network architecture NN, and the sliding window embedding & from the previous section.
Drawing from the advancements in machine learning for DMD, we introduce three methods: MLP- DMD, CNN-DMD, and MLP-SW-DMI W-D... MLP-DMD uses a straightforward MLP architecture for + comprising two linear layers with ELU activation and a residual connection, shown in the Appendix. Unlike MLP-DMD, CNN-DMD incorporates information between simulation steps, treating these steps as the temporal dimension and parameters as the channel dimension of ID CNN encoder shown in the Appendix. To avoid look-ahead bias, we use causal masking of the CNN kernels, and the architecture includes two ID-CNN layers with bottleneck middle channel number of and ELU activation to prevent overfitting. MLP-SW SW--SW is similar to MLP-DMD but includes the time-delay embedding in the input, a feature we also add CNN-DMD. As a result, MLP-DMD and CNN-DMD extend the principles of DMD, whereas MLP-SW-DMI and CNN-DMD with time-delay embedding generalize from SW-DMD. More details are available in the Appendix.
Limitations. QuACK is currently only equipped with relatively simple neural network architecture while more advanced architectures like Transformer can be explored for future work. Even though QuACK reduces the number of necessary gradient steps largely and thus achieves speedup, training
5

---

of VQA with a few gradient steps is still required to obtain the data for Koopman operator learning. nsm for the training gradient steps in our design is hyperparameter (see ablation study Appendix), and we do not have a theoretical formula for it yet.
5 Theoretical Results
Connection to Quantum Nature Gradient. While there exists a Koopman embedding that can linearize given nonlinear dynamics, provide more insights between Koopman theory and gradient-based dynamics under quantum optimization. The dynamical equation from quantum natural gradients /d(tt/dt - VoC(O(t) is equivalent to (t) dt = -I' vo (t), where F is the quantum Fisher information matrix, and Pes represents projector onto the manifold of the parameterized quantum circuit. When the parameterized quantum circuit possesses full expressivity, covers the entire Hilbert space, resulting in (t) /dt = - (t) This is linear differential equation in the vector space of unnormalized wave functions. The normalized vhp from the parameterized quantum circuit together with additional normalization factor function (()) can serve an embedding to linearize the quantum natural gradient dynamics. For relative short time scale, the normalized the already provides good linearization which only differs from the exact dynamics by the normalization change in the short time scale. The special underlying structure of quantum natural gradient may make it casier to learn the approximate linear dynamics for Koopman operator learning.
Connection to Overparameterization Theory. Recent advancement on overparamettrization theory [37, 44, 87] finds that when the number of parameters the quantum circuit exceed certain limit, linear convergence of the variational quantum optimization under gradient descent guaranteed. You et al. [87] shows that the normalized vha from the parameterized quantum circuit in the overparatermization regime follows a dynamical equation which has a dominant part linear in vhe with additional perturbation terms. Similar to the quantum natural gradient, the overparameterizztion regime could provide an effective structure to simplify the Koopman operator learning with approximate linear dynamics.
5.1 Stability Analysis
We first note that the direct application of DMD without alternating the controlled scheme will lead to unstable or trivial performance in the asymptotic limit.
Theorem 5.1. Asymptotic DMD prediction for quantum optimization is trivial or unstable.
Proof. The asymptotic dynamics from DMD prediction is given by (TT) = K ( for T + oo. It follows that ((T) - w/th Um where wm and Um are the largest magnitude eigenvalue and the corresponding eigenvector of the Koopman operator K. If [m < 1, then ( will converge to zero, and the quantum eircuit will reach a trivial fixed state. If [Wmm
1, O(T) will keep oscillating or growing unbounded. For unitary gate (0) e :01' where P is Pauli string, (O) is periodic with respect to 0. The oscillation or unbounded growing behavior of (T") will lead to oscillation of the unitary gate in the asymptotic limit resulting in unstable performance.
The above issue is also found to exist in numerical results plotted in Appendix, indicating that the eigenvalues of the Koopman operators from quantum optimization dynamics can lead to trivial or unstable DMD prediction, which motivates us to develop QuACK. Indeed, our QuACK has controllable performances given by the following
Theorem 5.2. In each iteration of QuACK, the optimal parameters (topt) yield equivalent or lower loss than the m-step gradient-bart based optimizer.
Proof. From lopt arg minl, S1St (((()),, we have ((O()op)) S L(((Im)) where [(O(t..)) is the final loss from the m-step gradient- based optimizer.
As long as QuACK is able to capture certain dynamical modes that decrease the loss, then it will produce a lower loss even when the predicted dynamics does not exactly follow the same trend the m-step gradient descent updates. We also note that it is possible for QuACK to converge different

---

local minimum than the baseline gradient- based optimizer, but our experiments generally demonstrate that our QuACK achieves accuracy the same as or even better than the baseline with much faster convergence. Our procedure is robust against long-time prediction error and noise with much fewer gradient calculations, which can efficiently accelerate the gradient-based methods. Furthermore, our scheme has the following important implication, the proof of which we provide in Appendix.
Corollary 5.3. QuACK achieves superior performance over the asymptotic DMD prediction.
5.2 Complexity and Speedup Analysis
To achieve a certain target loss Ltarget near convergence, the traditional gradient-based optimizer as baseline takes T3 gradient steps. To achieve the same frarget: QuACK takes Tq.: TQ, + Tq2 steps where TQ.1 (2)).2) are the total numbers of QuACK training (prediction) steps. We denote the ratio between the computational costs of the baseline and QuACK s, which serves as the speedup ratio from QuACK. Our definition of speedup has some difference with the speedup defined in Ref. [16] although shares a similar spirit. gradient- based optimization, the computational costs of each step of QuACK training and prediction are different, with their ratio defined as f(p) where p := Aparams. In general, fp) (1()) since only QuACK training, not prediction, involves gradient steps.
Theorem 5.4. With baseline gradient-method. the speedup ratio is in the following range
S. S (P) + nDMD)
{p)) RDMD
where a : To In the limit of Niter > Do the upper bound can be achieved.
We present the proof in the Appendix, is a metric of the accuracy of Koopman prediction. Higher a means better prediction, and a perfect prediction has a 1. The exact form of [pp) depends on the details of the gradient method. For example, we have f (p) 2p + 1 for parameter-shift rules and f(p) ~ p² + P for quantum natural gradients [49]. If a is fixed, then the upper bound of s in Eq. 13 increases when p increases with an asymptote a afrssim nDMD)/ //aim/ naim p - cc. The upper bound in Eq. 13 implics s S (p where the equal sign is achieved in the limit NDDDD/ + 00. If a 1 one could in theory achieve f (p)-speedu least linear in Pparams-
In practice the variable a is influenced by Osim and IDMDD A decrease in a can occur when Asm diminishes or WDMD enlarges, prediction accuracy may drop if the optimization dynamics length for QuACK training is insufficient or the prediction length is too long. Moreover, estimating the gradient for each parameter requires a specific number of shots Tsshots on fixed quantum circuit. Quantum measurement precision usually follows the standard quantum limit ~ 1/ MShhts hence a finite Rhhots may result in noisy gradients for Koopman operator learning, influencing a. Intriguingly. when the prediction aligns with the pure VQA, QuACK's s loss might decrease faster than pure baseline VQA, leading >> 1 and a higher speedup. This could be due to dominant DMD spectrum modes with large eigenvalues aligning with the direction of fast convergence in the O-space.
6 Experiments
6.1 Experimental Setup
We adopt the Relative loss metric for benchmark, which is (C- Emin, full vQA)/ full VQA Lmin full vOA), where L is the current loss, and Linitial, full VQA and Lmin, full VQA are the initial and minimum loss of full VQA. We use pure VQE [59] and pure QML [63] as the baseline. We use ftarget at 1 1% relative loss for VQE and the target test accuracy (0.5% below maximum) for QML to compute the computational costs and the speedup 8 as a metric of the performance of QuACK. Our experiments are run with Qiskit [2]. Pytorch [57], Yao [47] (in Julia [7]), and Pennylane [6]. Details of the architectures and hyperparameters of our experiments are in Appendix. More ablation studies for hyperparameters are also in Appendix.
Quantum Ising Model. Quantum Ising model with a transverse field h has the Hamiltonian
H - E'" Ze 6 7441 - h MN X, where (T,, X,, Y, 7 are Pauli matrices for the i-th qubit. On the quantum circuit, we then use the RealAmplitudes ansatz and hardware-cfficien ansatz [31]
7

---

3,55
250
15
latraste dyuncics
Spoodup ratio
2000
Speedup rabio
Eveery
4.0
DMD prodlction (ouns)
DMD lasising (cuss)
150
10
-4.5
100
-5.0
50
0
200
400
600
800
1030
1500
2000
2500
10
15
20
Stops (prndien steps prodiction stepa)
Phearam
Ppproom
(a) Quantum natural gradients.
(b) Overparameteriiatton..
(c) Smooth optimization regimes.
Figure 2: Performance of our QuACK with the standard DMD in the following cases. (a) For quantum natural gradient, with short training (4 steps per piece) and long prediction (40 steps per piece). DMD accurately predicts the intrinsic dynamics of quantum optimization, and QuACK has 20.18x speedup. (b) In the overparameterization regime, QuACK has >200x speedup with 2-5 qubits. (c) In smooth optimization regimes, QuACK has > 10x speedup with 2-12 qubits.
Energy (Hartzee)
boand CMD (ORN))
-00
DHD (asn)
Tee acvunice
0.9
DAIn (urin)
-6
MLL I--I END tound
PITMI boan!
Etoogge
-11
MLP swt DND (ous)
sw-nAm
(acn)
0.8-
SW-DMD
MLLP DMD (ouns)
CNN TIsI (wir))
cre DMD (eans
0.7-
MLL.-W-DDA SW-DMD (vam)
CNX-DMD (oun:
Buadiue (QMLL)
0
100
200
300
50
100 Iterations
150
200
0
100
200
300
400
Iterations
Iterations
(a) LiH molecule.
(b) Quantum Ising model.
(c) Quantum machine learning.
Figure 3: Experimental results for (a) LiH molecule with 10 qubits using Adam (b) Quantum Ising model with 12 qubits using Adam (c) test accuracy of binary classification in QML. The solid piecewise eurves are true gradient steps, and the dashed lines connecting them indicate when the DMD prediction is applied to find ((ope) in our controlled scheme. Our QuACK with all the DMD methods bring acceleration, with maximum speedups (a) 4.63x (b) 3.24x (c) 4.38x.
which then define the and then L(0) = (we Hebe). We implement the VQE algorithm and QuACK for h 0.5 using gradient descent, quantum natural gradient, and Adam optimizers.
Quantum Chemistry. Quantum chemistry is of great interest as an application of quantum algorithms, and has Hamiltonian 76 = Σラ= hy with np polynomial in N, where P3 tensor products of Pauli matrices, and h, the associated real coefficients. The loss function of quantum chemistry is typically more complicated than the quantum Ising model. We explore the performance of QuACK by applying it VQE for the 10-qubit Hamiltonian of LiH molecule with interatomic distance 2.0 Á provided in Pennylane, with Adam and the RealAmplitudes ansatz.
Quantum Machine Learning. In addtion to VQE, we consider the task of binary classification on filtered MNIST dataset with samples labeled by digits "I" and "9". We use an interleaved scheme for QML, which shown to have generalization advantage [29, 13, 40. 63] and recently realized in experiment [62]. We use a 10-qubit quantum circuit with stochastic gradient descent for QMI. and QuACK, and layerwise partitioning [16] in O for neural DMD. Similar the target loss, we set the target test accuracy 0.5% below the maximum test accuracy to measure the closeness to the best test accuracy during the QML training, and use the ratios of cost between pure QML and QuACK achieving the target test accuracy as the speedup ratio.
6.2 Accurate Prediction for Quantum Natural Gradients by QuACK
In Figure 2a, we present the 5-qubit quantum Ising model results (learning rate 0.001) with the standard DMD method in the QuACK framework. We observe that the DMD prediction is almost perfect, i.e. a Rs 1. The speedup Figure 2a 20x close to 21x the theoretical speedup from the upper bound in Eq. 13 under = 1. This experiment shows (1) the success of DMD in predicting the dynamics (2) the power of QuACK of accelerating VQA (3) the precision of our complexity and speedup analysis in Sec. 5.2. We show 10-qubit results for all DMD methods in the Appendix.
8

---

(9)
Speedup
(VEP) bamn
Noise System
DMD
SW.
MLP.
MLP.
CNN-
Eueegg
THDD
Pishots
(ours)
DMD
DMD
SW-DMD
DMD
(ours)
(ours)
(ours)
(ours)
-10-
10-qubit
100
5.51x
5.54x
3.25x
3.23x
1.99x
1,000
3.20x
4.36x
2.38x
4.36x
2.54x
100
2000
shot noise
10,000
1.59x
3.49x
1.59x
2.41x
1.96x
(8]
Iterrations
5-qubit
100
1.50x
2.64x
1.83x
4.57x
1.47x
shot noise
1,000
1.39x
3.84x
1.45x
2.25x
1.95x
Foorgy
10,000
1.49x
3.43x
1.80x
2.00x
1.78x
S-qubit
100
2.44x
2.24x
2.43x
2.15x
2.34x
FakeLima
1,000
1.50x
2.61x
2.07x
2.41x
1.84x
10,000
1.48x
2.32x
1.93x
2.56x
1.92x
100
200
Iteeations
S-qubit 100
2.14x
2.51x
2.54x
2.91x
1.25x
Figure 4: Noisy quantum op-
FakeManila
1,000
1.49x
2.02x
1.90x
2.09x
1.89x
timization with nshots = 100.
10,000
1.95x
2.13x
2.13x
2.27x
1.82x
(a) 10-qubit shot noise sys-
Table I: Speedup ratios of our QuACK with all DMD methods for
tem (b) 5-qubit FakeManila
various noise systems.
6.3 More than 200x Speedup near the Overparametrization Regime by QuACK
As it used by the overparameteriiaaion theory in You al. [87], we use the 250-layer hardware- efficient ansatz [31] on the quantum Ising model with gradient descent, with numbers of qubits N 3, 4, 5 Teparams 1000, 1500, 2000, 2500, all in the regime of pppaams (2*) near the overparameterization regime [37]. In addition, we use a small learning rate 5e-6 so that the dynamics in the 0-space is approximately linear dynamics. We expect QuACK with the standard DMD to have good performance in this regime. In Figure 2b, for each Pparams. we randomly sample 10 initializations of 0 to calculate mean values and errorbars and obtain >200x speedup in all these cases. The great acceleration from our QuACK is an empirical validation and an application of the overparameterization theory for quantum optimization. On the other hand, the overparameterization regime is difficult for near-term quantum computers to realize due to the large number of parameters and optimization steps, and our QuACK makes its realization more feasible.
6.4 More than 10x Speedup Smooth Optimization Regimes by QuACK
For the quantum Ising model with gradient descent and 2-layer RealAmplitudes, rather than the overparameterization regime, we consider a different regime with lower Ppparms with learning rate 2e-3 that the optimization trajectory is smooth and the standard DMD is still expected to predict the dynamics accurately for a relatively long length of time. With the number of qubits N E [2, 12] (Pparams E [4, 24)) and 100 random samples for initialization of 0 for each Mparams: in Figure 2c, our QuACK achieves > >10x speedup in all these cases. This shows the potential of our methods for this regime with fewer parameters than overparameterization, which is more realistic near-term quantum hardware.
6.5 More than 3x Speedup in Non-smooth Optimization by QuACK
We further demonstrate speedup from QuACK the non-smooth optimization regimes with learning rate 0.01 for examples of quantum Ising model, quantum chemistry. and quantum machine learning with performance shown in Figure with numerical speedups in Appendix. Only the gradient steps are plotted. but the computational cost of QuACK prediction steps are also counted when computing speedup. All the DMD methods are applied to all the examples. Our QuACK with all the DMD methods accelerates the VQA, with maximum speedups (a) LiH molecule: 4.63x (b) quantum Ising model: 3.24x (c) QML: 4.38x. These applications are of broad interest across different fields and communities and show that our QuACK works for range of loss functions and tasks.

---

6.6 2x to 5.5x Speedup from Ablation the Robustness of QuACK to Noise
Near-term quantum computers are imperfect and have two types of noise: (1) shot noise from the probabilistic nature of quantum mechanics, which decreases as 1/ //t////suuae Mshotss (2) quantum noise due to the qubit and gate errors which cannot be removed by increasing Nshots- Therefore, we consider two categories of ablation studies (1) with shot noise only (2) with both shot noise and quantum noise. We apply our QuACK with all 5 DMD methods to 4 types of noise systems: 10-qubit and 5-qubit systems with only shot noise, Fakelima Lima, and FakeManila. The latter two are noise models provided by Qiskit to mimic 5-qubit IBM real quantum computers, Lima and Manila, which contain not only shots noise but also the muchine-speciffe quantum noise. We use the quantum Ising model with Adam and show generic dynamics in Figure 4 with statistical error from shots as error bands. The fluctuation and error from baseline VQE in Figure 4(a) 100-shot 10-qubit system are less than Figure 4(b) 100-shot FakeManila. Our QuACK works well in (a) up to 5.54x speedup and in (b) up to 2.44x speedup. In all examples, we obtain speedup and show them in Table 1, which demonstrate the robustness of our QuACK in realistic setups with generic noisy conditions. We have also implemented an experiment to accelerate VQE the real IBM quantum computer Lima with results in Appendix.
7 Conclusion
We developed QuACK, novel algorithm that accelerates quantum optimization. We derived QuACK from connecting quantum natural gradient theory, overparameterizztion theory, and Koopman op- erator learning theory. We rigorously tested QuACK's ' performance, robustmess, spectral stability, and complexity on both simulated and real quantum computers across variety of scenarios. No- tably, we observed orders of magnitude speedups with QuACK, achieving over 200 times faster in overparameterized regimes, 10 times in smooth regimes, and 3 times in non-smooth regimes. This research highlights the significant potential of Koopman operator theory for accelerating quantum optimization and lays the foundation for stronger connections between machine learning and quantum optimization. We elaborate more on the broader impact of our work in the Appendix.
Acknowledgement
The authors acknowledge helpful discussions with Hao He, Charles Roques- Carmes, Eleanor Crane, Nathan Wiebe, Zhuo Chen, Ryan Levy, Lucas Slattery, Bryan Clark, Weikang Li, Xiuzhe Luo, Patrick Draper, Aida El-Khadra, Andrew Lytle, Yu Ding, Ruslan Shaydulin, Yue Sun. DL., RD and MS acknowledge support from the NSF AI Institute for Artificial Intelligence and Fundamental Interactions (IAIFI). DL. is supported in part by the Co-Design Center for Quantum Advantage (C2QA). JS acknowledges support from the U.S. Department of Energy, Office of Science, Office of High Energy Physics Quant[SED program under an award for the Fermilab Theory Consortium "Intersections of QIS and Theoretical Particle Physics". This material is also in part based upon work supported by the Air Force Office of Scientific Research under the award number FA9550-21- 11-00-1----117777 We acknowledge the use of IBM Quantum services for this work. The views expressed are those of the authors, and do not reflect the official policy or position of IBM or the IBM Quantum team. In this paper we used ibmq_lima, which is one of the IBM Quantum Falcon Processors.
References
[1] Shun-Ichi Amari. Natural gradient works efficiently in learning. Neural computation, 10(2): 251-276, 1998.
[2] MD SAJID ANIS, Abby-Mitchell, Héctor Abrahamand, et al. Qiskit: An open-source frame- work for quantum computing, 2021.
[3] Hassan Arbabi and Igor Mezic. Ergodic theory, dynamic mode decomposition, and computation of spectral properties of the koopman operator. SIAM Journal on Applied Dynamical Systems, 16(4):209--1226, 2017.
[4] Omri Azencot, N Benjamin Erichson, Vanessa Lin, and Michael Mahoney. Forecasting se- quential data using consistent koopman autoencoders. International Conference on Machine Learning, pages 475-485. PMLR, 2020.
10

---

[5] George S. Barron and Christopher J. Wood. Measurement error mitigation for variational quantum algorithms, 2020. URL httpt:///aaiii prggabs//0100....
[6] Ville Bergholm, Josh Izaac, Maria Schuld, Christian Gogolin, M Sohaib Alam, Shahnawaz Ahmed, Juan Miguel Arrazola, Carsten Blank, Alain Delgado, Soran Jahangiri, et al. Pen- nylane: Automatic differentiation of hybrid muantum-classiee computations. arXiv preprint 1.Kiv:1811.04900 2018.
[7] Jeff Bezanson, Alan Edelman, Stefan Karpinski, and Viral B Shah. Julia: A fresh approach numerical computing. SIAM Review, 59(1))65-98, 2017. doi: 10.1137/141000671. URL https://epubs. siam. org/doi/10 1137/141000671.
[8] Jacob Biamonte, Peter Wittek, Nicola Pancotti, Patrick Rehentrost, Nathan Wiebe, and Seth Lloyd. Quantum machine learning. Nature, 549(767 (99(7671)1195-2222 2017.
[9] Bingni W Brunton, Lise A Johnson, Jeffrey G Ojemann, and J Nathan Kutz. Extracting spatial- temporal coherent patterns in large-scale neural recordings using dynamic mode decomposition. Journal of neuroscience methods, 258: 1-5, 2016.
[10] Steven L Brunton, Bingni W Brunton, Joshua L Proctor, Eurika Kaiser, and J Nathan Kutz. Chaos as an intermittently forced linear system. Nature communications, 8(1):1-9, 2017.
[11] Steven L Brunton, Marko Budišié, Eurika Kaiser, and J Nathan Kutz. Modern koopman theory for dynamical systems. arXiv preprint 2rXiv:2102.12086 2021.
[12] Marko Budisić, Ryan Mohr, and Igor Mezić. Applied koopmanism. Chaos: An Interdisciplinary Journal of Nonlinear Science, 22(4), 2012.
[13] Matthias C. Caro, Elies Gil-Fuster, Johannes Jakob Meyer, Jens Eisert, and Ryan Sweke. Encoding-dependent generalization bounds for parametrized quantum circuits. Quantum, 5: 582, November 2021. ISSN 2521-327X. doi: 10.223314--2011-1117753
URL https:
//doi.org/11
[14] 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):25 644, 2021.
[15] Felix Dietrich, Thomas N Thiem, and Ioannis G Kevrekidis. On the koopman operator of algorithms. SIAM Journal on Applied Dynamical Systems, 19(2):860-885, 2020.
[16] Akshunna S Dogra and William Redman. Optimizing neural networks via koopman operator theory. Advances in Neural Information Processing Systems, 33:2087-2097, 2020.
[17] Daoyi Dong, Chunlin Chen, Hanxiong Li, and Tzyh-Jong Tamn Quantum reinforcement learning. IEEE Transactions on Systems, Man, and Cybernetics, Part B (Cybernetics), 3807):20 2008.
[18) Daniel Dylewsky. Eurika Kaiser, Steven I. Brunton, and Nathan Kutz. Principal component trajectories for modeling spectrally continuous dynamics forced linear systems. Physical Review E, 105(1) (:013113,,, 2022.
[19] Edward Farhi, Jeffrey Goldstone, and Sam Gutmann. A quantum approximate optimization algorithm. arXiv preprint arXiv:1411.4028. 2014.
[20] Diego Gareía-Martin, Martin Larocca, and M Cerezo. Effects of noise on the overparametriza- tion of quantum neural networks. arXiv preprint arXiv:2302.05053 2023.
[21] Dimitrios Giannakis, Amelia Henriksen, Joel Tropp, and Rachel Ward. Learning to fore- cast dynamical systems from streaming data. SIAM Journal on Applied Dynamical Systems, 22(2):527-558, 2023. doi: 10.1137/21M144988XX URL https: /doi. org/10.1137 21M144983X.
[22] Andy Goldschmidt, E Kaiser, J L DuBois, L Brunton, and JN Kutz. Bilinear dynamic mode decomposition for quantum control. New Journal of Physics, 23(3):033055 mar 2021. doi: 10.1188//336-2223//bbbel URL https: //tp///oiii/ org/ htte:/00118888 10881201177/222020620
11

---

[23] Matthew P. Harrigan, Kevin J. Sung, Matthew Neeley, Kevin J. Satzinger, Frank Arute, Kunal Arya, Juan Atalaya, Joseph C. Bardin, Rami Barends, Sergio Boixo, Michael Broughton, Bob B. Buckley, David A. Buell, Brian Burkett, Nicholas Bushnell, Yu Chen, Zijun Chen, Ben Chiaro, Roberto Collins, William Courtney, Sean Demura, Andrew Dunsworth, Daniel Eppens, Austin Fowler, Brooks Foxen, Craig Gidney, Marissa Giustina, Rob Graff, Steve Habegger, Alan Ho, Sabrina Hong. Trent Huang. L. B. loffe, Sergei V. Isakov, Evan Jeffrey, Zhang Jiang, Cody Jones, Dvir Kafri, Kostyantyn Kechedzhi, Julian Kelly, Seon Kim, Paul V. Klimov, Alexander N. Korotkov, Fedor Kostritsa, David Landhuis, Pavel Laptev, Mike Lindmark, Martin Leib, Orion Martin, John M. Martinis, Jarrod R. McClean, Matt McEwen, Anthony Megrant, Xiao Mi, Masoud Mohseni, Wojciech Mruczkiewicz. Josh Mutus, Ofer Naaman, Charles Neill, Florian Neukart, Murphy Yuezhen Niu, Thomas E. O Brien, Bryan O'Gorman, Eric Ostby, Andre Petukhov, Harald Putterman, Chris Quintana, Pedram Roushan, Nicholas C. Rubin, Daniel Sank, Andrea Skolik, Vadim Smelyanskiy, Doug Strain, Michael Streif, Marco Szalay, Amit Vainsencher, Theodore White, Z. Jamie Yao, Ping Yeh, Adam Zaleman, Leo Zhou, Hartmut Neven, Dave Bacon, Erik Lucero, Edward Farhi, and Ryan Babbush. Quantum approximate optimization of non-planar graph problems on a planar superconducting processor. Nature Physics, 173))333--33, Mar 2021. ISSN 1745-2481. doi: 10.1038/<41167-020001111 001111...0//000
URL
[24] Vojtech Havličck, Antonio D. Córcoles, Kristan Temme, Aram W. Harrow, Abhinav Kandala, Jerry M. Chow, and Jay M. Gambetta. Supervised learning with quantum-enhance feature spaces. Nature, 567(7747):209-2) mar 2019. doi: 10. (..1038/41186--11-9999 https://doi.
URL
org/10. 100.100012111556001111 100---199-9-----0
[25] Mohsen Heidari, Ananth Grama, and Wojciech Szpankowski. Toward physically realizable quantum neural networks. In Proceedings of the AAAI Conference Artificial Intelligence. volume 36. pages 6900-690000 6909, 2022.
[26] Maziar S Hemati, Matthew O Williams, and Clarence W Rowley. Dynamic mode decomposition for large and streaming datasets. Physics of Fluids, 26(1 1), 2014.
[27] Hsin-Yuan Huang, Michael Broughton, Jordan Cotler, Sitan Chen, Jerry Li, Masoud Mohseni, Hartmut Neven, Ryan Babbush, Richard Kueng, John Preskill, and Jarrod R. McClean. Quantum advantage in learning from experiments. Science, 316(65998 10.1 1e11///cience.aann//
jun 2022. doi: URL htttps://dof 100 1226//2sccincceeeeecccccccccccee abn7
[28] Hsin- Yuan Huang, Richard Kueng, Giacomo Torlai, Victor V. Albert, and John Preskill. Provably efficient machine learning for quantum many-body problems. Science, 377(6613), sep 2022. doi: 1e122//ciince.abk3333. URL https : /ttp//i.orgg////// wtt.oo.orrro...11./222.... 11267,2Fsciinccc abk3333.
[29] Sofiene Jerbi, Lukas J. Fiderer, Hendrik Poulsen Nautrup, Jonas M. Kübler, Hans J. Briegel, and Vedran Dunjko. Quantum machine learning beyond kernel methods, 2021. URL https:
13162.
[30] Mason Kamb, Eurika Kaiser, Steven L Brunton, and J Nathan Kutz. Time-delay observables for koopman: Theory and applications. SIAM Journal on Applied Dynamical Systems, 19(2): 886-91 917, 2020.
[31] Abhinav Kandala, Antonio Mezzacapo, Kristan Temme, Maika Takita, Markus Brink, Jerry M Chow, and Jay M Gambetta. Hardware-efficient variational quantum eigensolver for small molecules and quantum magnets. nature, 549(7671):242-244) 2017.
[32] Iordanis Kerenidis, Jonas Landman, Alessandro Luongo, and Anupam Prakash. q-means: quantum algorithm for unsupervised machine learning. Advances in Neural Information Processing Systems, 32, 2019.
[33] Sami Khairy, Ruslan Shaydulin, Lukasz Cincio, Yuri Alexeev and Prasanna Balaprakash. Learn- ing to optimize variational quantum circuits solve combinatorial problems. In Proceedings of the AAAI conference on artificial intelligence, volume 34, pages 2367-2375, 2020.
[34] N. Klco, E. F. Dumitrescu, A. McCaskey, T. D. Morris, R. C. Pooser, M. Sanz, E. Solano, P. Lougovski, and M. J. Savage. Quantum-classical computation of schwinger model dynamics using quantum computers. Phys. Rev. A, 98:032331, Sep 2018. doi: 10. 103/PhysRevA.99 032331. URL https: //win//in../////////// aps wwwp///////oooooooooooo/ooooeoeo
doi / 10.. 1103/PhysRev....com 98. 032333..
12

---

[35] Stefan Klus, Feliks Nüske, and Sebastian Peitz. Koopman analysis of quantum systems, Journal of Physics A: Mathematical and Theoretical, 55(31)311402, jul 2022. doi: 10.1088/1731-8121/ ac7d22. URL ttttps://dog hrtg//00.066//175111111///121
[36] B. O. Koopman. Hamiltonian systems and transformation in hilbert space. Proceedings of the National Academy of Sciences, 17(5):315-318, 1931. doi: 10. 10.1073/pma..1755.355 URL
attps://vxe pnas. pwwp.org/pa..o.ppppppt.pp.pppp
org//oi httg/doi/abb/// haapi//abs///.0 www.1/0/../a.... 17.5331..
[37] Martin Larocca, Nathan Ju, Diego Garcia-Martín Patrick J Coles, and Marco Cerezo. Theory of overparametrization in quantum neural networks. arXiv preprint arXiv: 109. 1676, 2021.
[38] Jiaqi Leng, Yuxiang Peng, Yi-Ling Qiao, Ming Lin, and Xiaodi Wu. Differentiable analog quantum computing for optimization and control. arXiv preprint arXiv:2210. 15812, 2022.
[39] Hao Li, Zheng Xu, Gavin Taylor, Christoph Studer, and Tom Goldstein. Visualizing the loss landscape of neural nets. In S. Bengio, H. Wallach, H. Larochelle, K. Grauman, N. Cesa-Bianchi, and R. Garnett, editors, Advances in Neural Information Processing Systems, volume 31. Curran Associates, Inc., 2018. URL httpps::/pprccceeiingggeeee/ neurips........... secppape__filee wwwess/apee.../ pdf..
2018 (ttp:///AAA411b33336000066000000
[40] Weikang Li, Zhide Lu, and Dong-Ling Deng. Quantum Neural Network Classifiers: A Tutorial. SciPost Phys. Lect. Notes, 61, 2022. doi: 0e024446/sssosPPPPeseeeeeeessss URL https: //scipost.org 100.:2/46///aaaoottyyysccctttee
[41] Yunzhu Li, Hao He, Jiajun Wu, Dina Katabi, and Antonio Torralba. Learning compositional koopman operators for model-basee control. arXiv preprint 4rxiv:1910.08264, 2019.
[42] Zhen Liang, Changyuan Zhao, Wanwei Liu, Bai Xue, Wenjing Yang, and Zhengbin Pang. Credit assignment for trained neural networks based on koopman operator theory. arXiv preprint arXiv:2212.00998 2022.
[43] Junyu Liu, Francesco Tacchino, Jennifer R. Glick, Liang Jiang, and Antonio Mezzacapo. Representation learning via quantum neural tangent kernels. PRX Quantum, 3(3), aug 2022. doi: 10. 1003/prrquantuum..00008 030323.
URL https://dol /ttp::///oooooo/...//////// 111.//...103///ppuuaaaa
[44] Junyu Liu, Khadijeh Najafi, Kunal Sharma, Francesco Tacchino, Liang Jiang, and Antonio Mezzacapo. Analytic theory for the dynamics of wide quantum neural networks. Physical Review Letters, (30(15):15060)) 2023.
[45] Yunchao Liu, Srinivasan Arunachalam, and Kristan Temme. A rigorous and robust quantum speed-up in supervised machine learning. Nature Physics, 1799:1013-1117 jul 2021, doi: 10. (038/441567-001-012888
URL https::///ii..... http//di..og/////// otg/10..///o. 111..0111112-241177-001100000000
[46] Ilya Loshchilov and Frank Hutter. Sgdr: Stochastic gradient descent with warm restarts. arXiv preprint
2016.
[47] Xiu-Zhe Luo, Jin-Guo Liu, Pan Zhang, and Lei Wang. Yao.jl: Extensible, Efficient Framework for Quantum Algorithm Design. Quantum, 4:341, 2020. doi: 20-22331/--2220-0--1111 URL https: http::////uauuuuuuee
20- 11-001111111..1111111
[48] Bethany Lusch, J. Nathan Kutz, and Steven L. Brunton. Deep learning for universal linear embeddings of nonlinear dynamics. Nature Communications, 9(1,, nov 2018. doi: 10. 1038/ 141167-018-07210-0 URL httph::t///eec //doi. org/10.
[49] Sam McArdle, Tyson Jones, Suguru Endo, Ying Li, Simon Benjamin, and Xiao Yuan. Varia- tional ansatz-based quantum simulation of imaginary time evolution. npj Quantum Information, 5(1) 2019.
[50] Igor Mezic. Spectral properties of dynamical systems, model reduction and decomposi- tions. Nonlinear Dynamicx, 41(1):309-325, Aug 2005. ISSN 1573-269X. doi: 10. 10.1007/ 111071-005-2824 URL https: :/op:s:://oo /oiii org/ 10. 00000//811100--0--2822-44
13

---

[51] K. Mitarai, M. Negoro, M. Kitagawa, and K. Fujii. Quantum circuit learning. Phys. Rev. A, 98: 032309, Sep 2018. doi: 10. 110.//yyseee........ wt........0033399 URL https://link: aps org/doi/ 10. N0.1103/PhysRevA 98. 032309.
[52] Ryan Mohr and Igor Mezić. Koopman spectrum and stability of cascaded dynamical systems. The Koopman Operator Systems and Control: Concepts, Methodologies, and Applications. pages 99-129, 2020.
[53] Ryan Mohr, Maria Fonoberova, Zlatko Drmač, Iva Manojlović, and Igor Mezić. Predicting the critical number of layers for hierarchical support vector regression. Entropy, 23(1):37, 2020.
[54] Nikolaj Moll, Panagiotis Barkoutsos, Lev S Bishop, Jerry M Chow, Andrew Cross, Daniel J Egger, Stefan Filipp, Andreas Fuhrer, Jay M Gambetta, Marc Ganzhorn, Abhinav Kandala, Antonio Mezzacapo. Peter Müller, Walter Riess, Gian Salis, John Smolin, Ivano Tavemelli, and Kristan Temme. Quantum optimization using variational algorithms on near-term quantum devices. Quantum Science and Technology, 33):030503, jun 2018. doi: 00.1088/2058-9563 aab822. URL https: //doii///oiii org/ 10. 108.
[55] Ilan Naiman and Omri Azencot. A koopman approach to understanding sequence neural models. arXiv preprint arXiv:2102.07824, 2021.
[56] Yurii Nesterov. Introductory lectures on convex programming volume Basic course. Lecture notes, 3(4):5, 1998.
[57] Adam Paszke, Sam Gross, Francisco Massa, Adam Lerer, James Bradbury, Gregory Chanan, Trevor Killeen, Zeming Lin, Natalia Gimelshein, Luca Antiga, Alban Desmaison, Andreas Köpf, Edward Yang, 7ach Vitito, Martin Raison, Alykhan Tejani, Sasank Chilamkurthy, Benoit Steiner, Lu Fang, Junjie Bai, and Soumith Chintala. Pytorch: An imperative style, high-performance deep learning library, 2019. URL https //axxiv. org/abs/ org//bs/1911..0703..
[58] Alberto Peruzzo, Jarrod McClean, Peter Shadbolt, Man-Hong Yung, Xiao-Qi Zhou, Peter J. Love, Alán Aspuru-Guzik and Jeremy L. O'Brien. A variational eigenvalue solver on a photonic quantum processor. Nature Communications, 5(1), jul 2014. doi: 10. n0.1038/ncomms5213. URL
https://doi. http:///oo.oro11../. 10387/2ncoomm5521..
[59] Alberto Peruzzo, Jarrod McClean, Peter Shadbolt, Man-Hong Yung, Xiao- Qi Zhou, Peter J Love, Alán Aspuru-Guzik, and Jeremy I. O'brien. variational eigenvalue solver on a photonic quantum processor. Nature communications, 5(1):1-7, 2014.
[60] William T Redman, Maria Fonoberova, Ryan Mohr, Yannis Kevrekidis, and Igor Mezic. An operator theoretic view on pruning deep neural networks. In International Conference on Learning Representations, 2021.
[61] William T Redman, Maria Fonoberova, Ryan Mohr, Ioannis G Kevrekidis, and Igor Mezic. Algorithmic (semi-) conjugacy via koopman operator theory. In 2022 IEEE 61st Conference on Decision and Control (CDC), pages 6006 6016.601. IEEE. 2022.
[62] Wenhui Ren, Weikang Li, Shibo Xu, Ke Wang, Wenjie Jiang, Feitong Jin, Xuhao Zhu, Jiachen Chen, Zixuan Song, Pengfei Zhang, Hang Dong Xu Zhang, Jinfeng Deng, Yu Gao, Chuanyu Zhang, Yaozu Wu, Bing Zhang, Qiujiang Guo, Hekang Li, Zhen Wang. Jacob Biamonte, Chao Song, Dong-Ling Deng, and H. Wang. Experimental quantum adversarial learning with programmable superconducting qubits, 2022. URL //apiiv/////...////a org/ org/abs/ /2204. 2204.01738.
[63] Wenhui Ren, Weikang Li, Shibo Xu, Ke Wang, Wenjie Jiang, Feitong Jin, Xuhao Zhu, Jiachen Chen, Zixuan Song, Pengfei Zhang, et al. Experimental quantum adversarial learning with programmable superconducting qubits. arXiv preprint arXiv: 2022.
[64] Julian Rice, Wenwei Xu, and Andrew August. Analyzing koopman approaches to physics- informed machine learning for long-term sea-surface temperature forecasting. arXiv preprint axXiv:2010.00399, 2020.
14

---

[65] Enrico Rinaldi, Xizhi Han, Mohammad Hassan, Yuan Feng, Franco Nori, Michael McGuigan, and Masanori Hanada. Matrix model simulations using quantum computing, deep learning. and lattice monte carlo. PRX Quantum, 3:010324, Feb 2022. doi: 10. 1003/PXXQannuum.... URI. htt.h:tts:/// httpp:::///nk..eee aps. aps. http.///opooooooooooooooooooooo
www.1/////uuttuummmmmm 3.000324
[66] Clarence W Rowley, Igor Mezić, Shervin Bagheri, Philipp Schlatter, and Dan Henningson. Spectral analysis of nonlinear flows. Journal of fluid mechanics, 641:115-127, 2009.
[67] Manuel S. Rudolph, Ntwali Bashige Toussaint, Amara Katabarwa, Sonika Johri, Borja Per- opadre, and Alejandro Perdomo-Orii Generation of high-resolution handwritten digits with an ion-trap quantum computer. Phys. Rev. X, 12:031010, Jul 2022. doi: 10.1 103/PhysRevX. 12. 031010. URL https: //link aps opp..org/eee wwg//oi//aaooooooooooo 111./..11/.////ee///e/ 12. 12.031010.
[68] Peter J Schmid. Dynamic mode decomposition of numerical and experimental data. Journal of fluid mechanics, 656:5-28, 2010.
[69] Maria Schuld, Ville Bergholm, Christian Gogolin, Josh Izaac, and Nathan Killoran. Evaluating analytic gradients on quantum hardware. Phys. Rev. A, 99:032331, Mar 2019. doi: 10. 1 (0S/PhysRevA..9.055.
URL attps://link: aps owgg/oi////.ooooooooooooooooo 113//hyssevv..90
032331.
[70] Chris N Self, Kiran E Khosla, Alistair WR Smith, Frédéric Sauvage, Peter D Haynes, Johannes Knolle, Florian Mintert, and MS Kim. Variational quantum algorithm with information sharing. npj Quanium Information, 7(1):116, 2021.
[71] Petr Šimánek, Daniel Vašata, and Pavel Kordík. Learning to optimize with dynamic mode decomposition. In 2022 International Joint Conference on Neural Networks (IJCNN), pages 1-8. IEEE, 2022.
[72] James C Spall. An overview of the simultaneous perturbation method for efficient optimization. Johns Hopkins apl technical digest, 19(4):482-492, 1998.
[73] James Stokes, Josh Izaac, Nathan Killoran, and Giuseppe Carleo. Quantum Natural Gradient. Quantum, 4:269, May 2020. ISSN 2521-327X. doi: 10.2233 https://doi... org/ wttpg//....3/////eee 22331/ 22231/22020-05-25-2255
22222 20-20000---222225222-2-0 URL
[74] Ryan Sweke, Frederik Wilde, Johannes Meyer, Maria Schuld, Paul K. Faehrmann, Barthélémy Meynard-Piganeau, and Jens Eisert. Stochastic gradient descent for hybrid quantum-classical op- timization. Quantum, 4:314, August 2020. ISSN 2521-327X.
URL https://doi. org/oor//// 10. 22331 200---0--------
[75] Floris Takens. Detecting strange attractors in turbulence. In David Rand and Lai-Sang Young, editors, Dynamical Systems and Turbulence, Warwick 1980, pages 366-381, Berlin, Heidelberg, 1981. Springer Berlin Heidelberg. ISBN 978-3-540-38945-3
[76] Shiro Tamiya and Hayata Yamasaki. Stochastic gradient line bayesian optimization for efficient noise-robust optimization of parameterized quantum circuits. npj Quantum Information, 8(1); 90, 2022.
[77] Mauricio E. Tano, Gavin D. Portwood, and Jean C. Ragusa. Accelerating training in artificial neural networks with dynamic mode decomposition, 2020. URL https:// //arxiv./..ii////a orgg abs/ 2006. 2006.14371.
[78] Jules Tilly, Hongxiang Chen, Shuxiang Cao, Dario Picozzi, Kanav Setia, Ying Li, Edward Grant, Leonard Wossnig, Ivan Rungger, George H Booth, al. The variational quantum eigensolver: review of methods and best practices. Physics Reports, 986:1-128, 2022.
[79] Jonathan H Tu, Clarence W Rowley, Dirk M Luchtenburg, Steven I. Brunton, and J Nathan Kutz. On dynamic mode decomposition: Theory and applications. Journal of Computational Dynamics, 1(2):391-421, 2014.
[80] v. Neumann. Zur operatorenmethode der klassischen mechanik. Annals of Mathematics, 33(3):587-642, 1932. ISSN 0003486X. URL http: //ww. www.w..to....... http:/taaleeee9999
15

---

[81] Guillaume Verdon, Michael Broughton, Jarrod R McClean, Kevin J Sung. Ryan Babbush, Zhang Jiang, Hartmut Neven, and Masoud Mohseni. Learning learn with quantum neural networks via classical neural networks. arXiv preprint 1901. 2019.
[82] Xinbiao Wang, Junyu Liu, Tongliang Liu, Yong Luo, Yuxuan Du, and Dacheng Tao. Symmetric pruning in quantum neural networks. arXiv preprint arXiv:2208. 14057, 2022.
[83] Dave Wecker, Matthew B. Hastings, and Matthias Troyer. Progress towards practical quantum variational algorithms. Physical Review A, 92(4), oct 2015. doi: 10. 1011///yyyrreaa.22.422300..
URL httpss//doii org/ 10. 1108%22physreaa...... 92. 042303.
[84] Matthew O Williams, Ioannis G Kevrekidis, and Clarence W Rowley. A data-driven approxima- tion of the koopman operator: Extending dynamic mode decomposition. Journal of Nonlinear Science, 25:1307-1346, 2015.
[85] Max Wilson, Rachel Stromswold, Filip Wudarski, Stuart Hadfield, Norm M Tubman, and Eleanor G Rieffel. Optimizing quantum heuristics with meta-learning. Quantum Machine Intelligence, 3:1-14, 2021.
[86] Jiahao Yao, Haoya Li, Marin Bukov, Lin Lin, and Lexing Ying. Monte carlo tree search based hybrid optimization variational quantum circuits. Mathematical and Scientific Machine Learning, pages 49 64. PMLR, 2022.
[87] Xuchen You, Shouvanik Chakrabarti, and Xiaodi Wu. A convergence theory for parameterized variational quantum eigensolvers. arXiv preprint arXiv:2205. 12481, 2022.
[88] Xuchen You, Shouvanik Chakrabarti, Boyang Chen, and Xiaodi Wu. Analyzing conver- gence in quantum neural networks: Deviations from neural tangent kernels. arXiv preprint ar0iv:2303. /4844, 2023.
[89] Leo Zhou, Sheng- Tao Wang, Soonwon Choi, Hannes Pichler, and Mikhail D Lukin. Quantum approximate optimization algorithm: Performance, mechanism, and implementation on near- term devices. Physical Review X, 10(2):021077, 2020.
16

---

Appendix
The structure of our Appendix is follows. Appendix A gives an introduction to quantum mechanics and the overparamettrrizaton theory as preliminaries of our paper. Appendix B provides more details of our QuACK framework introduced in Sec. 4 of main text. Appendix D provides proofs of our theoretical results in Sec. 5 of main text. Appendix E discusses detailed information on Sec. Experiments of main text. Appendix F contains additional information.
A Preliminaries
A.1 Introduction to Quantum Mechanies for Quantum Computation
We introduce quantum mechanics for quantum computation in this section. In quantum mechanies, the basic element to describe the status of system is quantum state (or wave function) v/. A pure quantum state is a vector in a Hilbert space. We can also use the Dirac notation for quantum states (vb) and (eb) to denote the row and column vectors respectively. By convention, {v/ is the Hermitian conjugate (composition of complex conjugate and transpose) of [46).
In quantum system with single qubit, there are two orthonormal states (0) and [1), and generic quantum state is spanned under this basis as (&b) co|0) + [1] where co, Cj E C. Therefore, tb itself is in 2-dimensional Hilbert space as vb E C For quantum mechanical system with N qubits, the basis of quantum state contains tensor products (Kronecker products) of the single-qubit bases, i.e, (b1) @ (b2) @ .... 6 [bx), where by E (0, 1} (i = 0, 1, N). There are in total 2 basis vectors, and d is a linear combination of them with complex coefficents. Therefore, &b for an N -qqubit system is in a 2 -dimensional complex-valued Hilbert space C² For a normalized quantum state, we further require the constraint | where || ||2 the 12-norm.
For the --qubit system, the Hamiltonian 7- is a Hermitian 2 x 2 -matrix acting on the quantum state (wave function) th. The energy of & is given by [(e) {w) He)),,,, which is the inner product between {هb) (a row vector, the Hermitian conjugate of (x)) and (Hib) (matrix multiplication between
the matrix H and the column vector (ę9)).
Pauli matrices (including the identity matrix I by our convention) are the 2 x matrices
1 0 0 1 = 0
1
0
0 0 -1
x
Y
0 Z =
(4)
The Pauli matrices can act on single-qubit (2-dimensional) state through matrix multiplication. For the N N-qubit system, we need to specify which qubit the Pauli matrix is acting on by the subscript i for the i-th qubit. For example, X2 denotes the X Pauli matrix acting on the second qubit. To have complete form of a 2 x 2 -matrix acting on the --qubit system, we need tensor products of Pauli matrices, i.e., Pauli strings. For example, 11 & Zz @ Zy @ 14 is a 2 x 24- matrix acting
4-qubit system. Conventionally, without ambiguity, when writing a Pauli string matrix, we can omit the identity matrices, and it will be equivalent to write the above Pauli string matrix as Zz @ Z3 (which, an example, appears in the Hamiltonian of the quantum Ising model: N & Zi+1 h EN X.). Pauli string can serve as the basis of writing the Hamiltonian,
H. -- E which is manifested by format of the Hamiltonian used in quantum chemistry: H Ei h2P with np polynomial in N, where P3 are pauli strings, and hú are the associated real coefficients.
In quantum computation, we have quantum gates parametrized by common example is the single-qubit rotational gates (0), (0), Rz (0), 2 x 2-matrices defined as
Rx exp (- (0X cos (0/2)
ii (0/2) cos (0/2)
(5)
sin (0/2)
(0) = exp (-i0Y/2) = cos (0/2)
sin (0/2)
(6)
sin (0/2)
cos (0/2)
= Texp (-i0/2)
Rz (0) = exp (-i0Z/2)
(7)
0
exp (10/2)
17

---

where f E R is the rotational angle as the parameter of rotational gate. In quantum circuit, there can be number of rotational gates acting on different qubits, and the parameters them can be chosen independently. All these components of / then get combined into vector O E IR Pparame, Note that the space of is different from the space of tb.
The different qubits in the quantum circuit would still be disconnected with only single-qubit rotational gates. To connect the different qubits, the 2-qubit controlled gates, including controlled-X, controlled-Y, and controlled-Z, (with no parameter) are needed
0
0
0
CX
0
0
1
(8)
0
1
0
0
1
0
0
0 0 0
0
0
0
-i
CY
(9)
LO
i
0
0
0 -1
Z2
(10)
0
They are 2 2- -matricess that act on 2 qubits i, out of the N qubits.
RealAmplitudes ansatz. The RealAmplitudes ansatz is quantum circuit that can prepare quan- tum state with real amplitudes. The implementation of RealAmplitudes in Qiskit is a parameterized Ry-layer acting all the N qubits and then repetitions of an entanglement layer of CXX and parameterized -layer.. The number of reptitions denoted as "reps". The total number en- tanglement layers (with parameters) is reps, and the total number of parameterized Ry-layers is reps + 1. The total number of parameters is Uparams = N(reps + 1). The entanglement layers in experiment are chosen circular configuration.
Hardware-efficient ansatz. We use the hardware-efficient ansatz following the convention of You et al. [87]. In each building block, there are an Raylryer, an Ry-layer, and the CZ eZZeentnglemen layer at odd links and then even links (acting on the state in this deseribed order). Then there are in total repetitions of "depth" of such building blocks. In the end, there are 2N depth parameters.
A.2 Overparameterizzaton Theory
Recent development overparameterization theories has shown that VQA with gradient- optimization has convergence guarantee [37, 44, 87]. Since there are different assumptions behind different overparameterization theories, here we provide brief introduction the overparameteri- zation theory in You et al. [87]. and we refer the readers to the original paper for more details. The important insight of the overparameterization theory comes from that in large-nparams regime with proper learning rate, the dynamics of the wave function | (t)) from the parameterized quantum circuit described by the following equation
d (t)) - [H. (t) (t)( (t)) + (f((oo())).
(11)
dt
where H is the Hamiltonian VQE task, and is the commutator. The first term in the R.H.S. is the Riemannian gradient descent over the normalized wave function manifold with energy as the loss function and converges linearly the ground state. This is also similar to the case of the quantum natural gradient. The second term in the R.H.S. is a small perturbation function 8f of t (t)) (see detailed form You et al. [87]). It has been shown that in the overparameterization regime, the equation can still converge to the ground state under such perturbation. Similar to the argument in the quantum natural gradient case, the overparameterization theory provides an effective structure for Koopman learning with approximate linear dynamics.
18

---

B Details of Sec. 4 QuACK Quantum-cireuit Alternating Controlled Koopman Operator Learning
B.1 Futher details of Neural DMD
Resi dusi connectiio
K Koopman Linear
SW
paras
(Lo)
θ
(1 (1++1)
stop
Raim
larget
T
MLP(-SW)-DMD
b
channel dim. = (boftleneck)
Thaim
11-11
Causal CNN
Causal CNN
(d++ Moppss
NOI
CNN-DMD
Figure 5: Neural network architectures for our neural DMD approaches. The factor (d + 1) in the dimension (d 1)pprrssss is due to the sliding window embedding (a) MLP bottleneck architecture with MSE loss for training. (b) CNN bottleneck architecture that operates on simulations as temporal and parameters as channel dimensions.
The neural network architectures for our neural DMD, i.e., MLP-DMD, MLP-SW-DMD, and CNN- DMD, are shown in Figure 5. For the CNN-DMD, we use expansion ratio of 1 in the experiments.
Optimization. The parameters K and are trained jointly on arg min (fa++) K K&. (ft)))] from seratch with every new batch of optimization history by using the Adam optimizer for 30k steps with 9k steps of linear warmup from 0 to 0.001 and then cosine decay back to at step 30k. We use the MSE loss, which minimizes the Frobenius norm.
Activation Along with ELU, we also explored cosine, ReLU and tanh activations. We found ELU be the best, likely because: tanh suffers from vanishing gradients, ReLU biases to positive numbers (while input phases quantum circuit parameters 0 are unconstrained) and cosine is periodic.
The importance of learning rate scheduler. We train the neural network & from scratch every time we obtain optimization history training data. It is important that we have stable learning with well converging neural network every single Koopman operator fitting stage. For that purpose, we found it vital to use cosine-decag scheduler with linear warmup, which is typically useful in the computer vision literature [46]. Namely, for the first 9k steps of the neural network optimization, we linearly scale the learning rate from 0 to 0.001, and then use a cosine-decay from 0.001 to 0 until the final step at 30k. Sec. for quantum machine learning, we use 160k training steps for CNN to achieve better performance.
The importance of residual connections. In our work we use residual connection in order to make DMD special case of the neural DMD parameterization. The residual connection is indeed
19

---

very useful, as it is driven by the Koopman operator learning formulation. Namely, the residual connection makes it possible for the encoder to learn the identity. If the encoder becomes the identity, then MLP(-SW)-DDD or CNN-DMD become vanilla (SW-)DMID
The procedure for making predictions using neural DMD. Sec. provides the general ob- jective arg miggi,,... k.o [O(++1) K' (ett)))lee for training the neural-network DMD includ- ing MLP-DMD, CNN-DMD, and MLP-SW-DMB First, for MLP-DMD (and CNN-DMD with no sliding window), we take d = 0 with no sliding window, so the objective gets reduced to arg minn ([)(h) K (e())))()))ll
In the phase of training, the optimization history (to)), ((1), (Lm+1)) is first concatenated into (44)) and (t1) the same way as in SW- DMD using (tx)) (txx) ((tx+1) ... ((t++m)] In every column, (tt,) is one iteration ahead of (to) in the future direction. Then, in training, the operator &a = NN as a neural network architecture, acts only on ((a) not on (t,)) K is square Koopman matrix that denotes for- ward dynamical evolution from ((6)) directly to ((1). rather than from $ (ln) to &. ((1). Likewise, in the phase of inference for predicting the future of 0 beyond fm+ we apply the operator ) (tt)). without an explicit inversion of the K T. repeatedly using the evolution ((tx+1) = (K L. operator To. to bring back the original representation. Next, for HLLP-SW-DMD we need to put d back to the equations and make the operator .. = NN,, a T a composition of the neural network ar- chitecture NN,, and the sliding window embedding क. The Koopman operator K of MLP-SW-DMD has the same dimension as K of SW-DMD, which is non-square. The procedure of updating & (()))) by adding the latest data and removing the oldest data is the same in SW-DMD described in Sec. 4. The only difference between MLP-SW-DMD and SW-DMD is the additional neural network architecture NN, in MLP-SW-DMD, The only difference between MLP-SW-DMD and MLP-DMD is the additional sliding window embedding 4 in MLP-SW-DMD. The same relationship holds true for CNN-DMD between the cases of and d > 0.
B.2 The Alternating Controlled Scheme
Buselme (VQE)
Baseline (VQE))
Alternting DMD training (ours)
Alsomatinn DMD training (curs)
Alternating DMD prediction (ours)
Altomating DMD prediction (ours)
Evergy
Noa-allernating DMD training
Energy
-10-
-9-
Noa-alternating DMD prediction
-12-
-10-
100
150
0
100
200
300
Steps (gradicnt steps + prediction steps)
Steps (gradient steps + prediction steps)
(a) Quantum natural gradient results using alternating and non-alternating traditional DMD.
(b) Adam results using traditional DMD with the alter- nating scheme.
Figure 6: Motivating examples for the alternating scheme and nonlinear embeddings. The results are from the 10 10-qubit quantum Ising model. Solid and dashed parts indicate true gradient steps and prediction steps respectively. In the starting regime of (a) where the lines almost overlap, the first 10 steps are solid for the DMD lines. In (b), the red points mark the optimal parameters for each piece of DMD predictions. The next piece of VQE starts from the optimal parameters rather than the last parameters, is indicated by the red arrows, to guarantee the decrease of energy.
The Koopman operator theory is a powerful framework for understanding and predicting nonlinear dynamics through linear dynamics embedded into a higher dimensional space. By viewing parameter optimization on quantum computers as nonlinear dynamical evolution in the parameter space, we connect gradient dynamics in quantum optimization the Koopman operator theory. In particular, the quantum natural gradient helps to provide a effective structure of parameter embedding into a higher- dimensional space, related to imaginary-tine evolution. However, for quantum optimization, using the standard dynamic mode decomposition (DMD) that assumes linear dynamics in optimization directly has the following issues demonstrated Figure of the 10-qubit quantum Ising model with h 0.5 learning rate 0.01. (1) In Figure 6a. the case of natural gradient, although the dynamics is
20

---

COBYLA
Adaz)
EMD (cuma)
Energy
SELP- DEL-DDII (sur))
MLL--WW, DMI
CNN-DDID (purs)
50
100
150
200
Iterations
Figure 7: S-qubit shot noise, Rahots = 1,000. VQE with COBYLA is plotted in orange in addition to the baseline VQE with Adam and all the DMD methods our QuACK. The COBYLA gets trapped.
approximately linear (as we discuss main text), without using an alternating scheme, the DMD prediction only good up to about 50 steps and starts to differ from the baseline VQE. This issue is much mitigated by adopting our alternating scheme by rumning follow-up true gradient steps. (2) In Figure 6b, even with the alternating scheme, in the case of Adam where the dynamics less linear, the standard DMD method can start to diverge quickly. To mitigate this issue, we control our alternating scheme by starting the follow-up true gradient steps from the optimal parameters in prediction. In addition, we propose to use the better capture the nonlinearity of dynamics.
embedding and neural-networks to
From Theorem 5, the asymptotic behavior of DMD prediction for quantum optimization is trivial or unstable. This is manifested in Figure 6b, as the energy of DMD prediction diverges the prediction time increases.
C An Example Comparing Gradient-Based and Gradient-Free Methods
While gradient-basee methods and gradient-free methods are both applicable types of optimizers for VQAs, gradient-based methods gradient information and thus know better about the local geometry [39], especially with quantum Fisher information through quantum natural gradient. Particularly, the gradient- gradient-based method has been shown to converge for quantum optimization [74, 87].
In Figure 7, we show example of the quantum Ising model with shot noise. While the gradient- based VQE with Adam finds lower energy than COBYLA with rhobeg=1. O, as COBYLA gets trapped. The results of Adam and QuACK are from Figure 12c. Our QuACK further improve upon Adam.
D Proofs of Theoretical Results in Sec.
Corollary 5.3. QuACK achieves superior performance over the asymptotic DMD prediction.
Proof. As it is shown in Theorem 5.1, asymptotic DMD prediction could lead trivial or unstable solution. Since QuACK employs the alternating controlled scheme, Theorem. 5.2 shows that QuACK obtains the optimal prediction in each iteration. It implies that even the asymptotic prediction converges to trivial solution or oscillates, QuACK can take the best prediction among the sufficiently long DMD predictions achieve superior performance.
Corollary D.1. QuACK is guaranteed to converge for convex optimization on function f : IR. R that is convex and differentiable with gradient that is Lipschitz continuous of positive Lipschitz constant.
Proof. Since I has gradient that Lipschitz continuous with positive Lipschitz constant, there exists some L > 0 such that [x) f'(y)ll < L||z vll2. It has been shown that by choosing fixed
21

---

step size = 1/L, the gradient descent is guaranteed to converge [56]. Each gradient step update
from 2y. is guaranteed to have f(*++1) < f(xx) - 2 If (xx)) and after gradient steps from (0))
||ar(0) x
-fx)) -
(12)
2nn
where x" is the optimal solution. Since Theorem 5.2 shows that QuACK yields an equivalent or lower loss than n-step gradient descent and we discuss above that the convex function f with positive Lipschitz constant can converge from any 2:(0) with proper step size f), it follows that QuACK is guaranteed to converge in the same setup.
Theorem 5.4. With a baseline gradient- the speedup ratio s is in the following range
[())(Maim + RDMDD)
a S a f(p) RDMD
(13)
where a := T=/TTo. In the limit of Riter + 3o the upper bound can be achieved.
To achieve Learget, the baseline VQA takes To gradient steps, and QuACK takes To.: TQ.1 + Tq.2 steps, where TQ,1 (Tq.2) are the total numbers of QuACK training (prediction) steps. 8 is the speedup ratio from QuACK. p == Paparams is the number of parameters.
Proof. The total computational costs of the baseline and QuACK both contain two parts: classical computational cost and quantum computational cost. For the baseline gradient-basel based optimizer, the total computational cost is shots B, [ + cb. where Rchots is the number of quantum measurements per VQA example per gradient step per parameter, [B, is the batch size of VQA examples (e.g.. B,y1 is the number of training examples in the batch of QML, and is the number of terms in the Hamiltonian in VQE), g is the quantum computational cost per VQA example per shot per gradient step per parameter, and C is the total classical computational cost for the baseline, from processing the input and output of the quantum computer using classical computer. c depends on the details of the VQA task, and for the tasks feasible on near-term quantum computers, cb < y and thus can be neglected since the quantum resources are much more expensive than classical resources. (()) is the optimizer factor for per gradient step evaluation on a quantum computer. For example, we have f(p) = 2p + 1 for parameter-shif rules and f(p) ~ p² + p for quantum natural gradients. For QuACK, the total computational cost is Nsbota B2 (p))TT) + Ta + CQ. where cQ the total classical computational cost for QuACK, depending on the type of DMD method and the number of classical training steps for neural DMD, plus classical processing of the input and output of the quantum computer. Again, for near-term quantum computers, cQ & q for the same reason as c and thus can be neglected. The QuACK training term has the factor f(p), while the QuACK prediction term does not, because does not involve taking gradients. The speedup ratio by QuACK is then
q Nghots (p) +
② Nshoos BB (p) + To +cQ
Mshots (p)
9 Nahota
Bfllf())TQ. + T222
(14)
f(P)TB
f(P)Te.1 + To.
[Tp) + TQ22)
f(p)TQ.1 +T.2
When deriving Eq. 14, the common factor Mahots BBy in the numerator and denominator is exactly the same, so its cancellation is exact. Since QuACK training always occurs before QuACK prediction, whether Lrarget is achieved during QuACK training prediction, the general case is Tq. /Tq.2 2 nsim/ /sim/RDMD. IDMD. Therefore.
5.55 {p)(( RDMD) f(p) + RDDD
(15)
In the limit Rater + co, the location (measured in terms of the number of QuACK steps) of the last
QuACK step does not affect To./TQq. much and we have To./ -> Tsim/ IDMD, so the upper bound in Eq. 13 can be achieved.
D
22

---

E Detailed Information on Sec. 6 Experiments
E.1 Experimental Setup Details
We use the notation Th.s as the total number of pure VQA (baseline) gradient steps in the plots, and nsw the sliding-window size (equal to d + 1). Rittrr the number of repetitions of alternating VQA+DMD runs, which is chosen large enough to ensure convergence of the baseline VQA. When convergence is achieved, the performance of QuACK does not have a strong dependence on choice of
Vijter-
E.1.1
Quantum Ising Model Setup
boundary condition, such that and N + 1 1=1 2 1 E X;, we use the periodic
For the quantum Ising model Hamiltonian H = EE
identified.
AmplAtittss ansatz and reps=1 (2 layers, 2NV parameters) with To. 800, quantum natural gradient optimizer, learning rate 0.001. For the QuACK hyperparameters, we choose Asii = 4 and 7DDDD = 100 with Riter = 8. The random sampling of initialization of 0 is from uniform distribution in ( "tpraum
In Sec. 6.2 Quantum Natural Gradient, we use the Airuula--entanllen
In Sec. 6.3, we use the hardware-efficient ansatz with 250 layers (500N parameters) with Th. = 5000N, gradient descent optimizer, learning rate 5e-6. For the QuACK hyperparameters, we choose Assm and IDND = 1000 with Miter = 5N to ensure convergence.
In Sec. 6.4, we use the circular-enten entanglement RealAmplitudes ansatz and reps=1 (2 layers, 2NV parameters) with To. 1500, Adam optimizer, learning rate 2c-3. For the QuACK hyperparameters. we choose aaam 3 and nDMD = 60 with Rittrr / ( + RDMMD] = 96 to ensure convergence. Some examples have an earlier stop, which does not affect calculation of the speedup ratio since they has already achieve Liarget before 96 pieces of VQE+DMD.
In Sec. 6.5, model and reps=1 (2 layers, 2N 24 parameters) with Tb. 300 learning rate 0.01. For the QuACK hyperparameters, choose Aisi 5 and NDMD 40 with littr 12 to ensure convergence. We
the aircular-entagglemen RealAmplitudes ansatz for the 12-qubit quantum Ising
have the sliding-window size nsww = 3 for SW-DMD, MLP-SW-DMD, and CNN-DMD.
E.1.2 Quantum Chemistry Setup
A molecule of LiH, depicted in Figure 3a, consists of a lithium atom and hydrogen atom separated by distance. We use the quantum chemistry module from Pennylane [6] to obtain the 10-qubit Hamiltonian of LiH at interatmoic separation 2.0 with 5 active orbitals. We use the circular- entanglement Real Amplitudes ansatz and reps=1 (2 layers, 20 parameters). The optimizer Adam with the learning rate 0.01. We perform Th 1000 baseline VQE iterations. We choose Tisim ADMD = 40, Tliter = 12. The sliding-windee size is nsw = 3 for SW-DMD, MLP-SW-DMD, and
CNN-DMD.
E.1.3 QML Architecture and Training Details
In our QML example in Sec. 6, the quantum computer has = 10 qubits. The architecture is shown in Figure 8. For the MNIST binary classification task, each image is first downsampled to 16 x 16 pixels, and then used as an input æ E [o, 1 that is fed into an interleaved encoding quantum gate.. The parameters 0 also encoded in the interleaved encoding quantum gate. Then the quantum measurements are used as the output for computing the cross-entropy loss.
The interleaved encoding gate consists of 9 layers. Each layer has rotational layer and linear entanglement layer. On the rotational layer, each qubit has three rotational gates Rx Rz, Rx in a sequence. Therefore, each layer has 30 rotational angles, and the whole QML architecture has 270 rotational angles, i.e., Oparams = 270. Since each input example æ is 256-dimensional, we only use the first 256 rotational angles to encode the input data. The parameters 0 are also encoded in the rotational angles such that the angles are x 0.
Quantum measurements, as the last part of the quantum circuit, map the quantum output to the classical probability data. In each quantum measurement, each qubit the O-state or the 1-state, and the probability for the qubit to be in the 0-state is between 0 and 1. We regard this probability as
23

---

CrossEntropy
Loss
(0)
(0)
Interleaved
quantum measurement
encoding
(0)
(x + 0)
(0)
Figure 8: Quantum machine learning architecture with interleaved encoding of 10-qubit quantum circuit for a binary classification task MNIST.
the probablity for the image to be digit "I". We only use the probability on the 5th qubit (i = 5) as the output and compute the cross-entropy loss with the labels.
In the phase of training, all the training examples share the same but have different æ, and we optimize the final average loss with respect to 0 as
e arg min
((x train 0),
(16)
Turain
in the case of Ttrain training examples. The combination æ: + 0 is entered into the quantum circuit rotational angles, and we need to build Ptrain separate quantum circuits (which can be built either sequentially or parallel). The interleaved encoding gate whole can be viewed as a deep layer, and serve dual roles of encoding the classical data a and containing the machine learning parameters 0. the phase of inference, with the optimal parameter 0", we feed each test example arest into the quantum circuit as a combination pestt 0" and measure the output probability to compute the test accuracy.
We use 500 training examples and 500 test examples. During training, we use the stochastic gradient descent optimizer with the batch size 50 and learning rate 0.05. The full QML training has Ti, 400 iterations. We choose fiaim 10, RDMD 20, and new = 6 for SW-DMD and MLP-SW-DMD.
In neural DMD including MLP-DMD, ALP-SW-DMD CNN-DMD,
layerwise partitioning
that groups 0 by layers in the encoding gate. There are groups with group size 30. We perform neural DMD for each group, that the number of parameters in the neural networks for DMD is not too large. After predicting each group separately, we combine all groups of f to evaluate the loss and accuracy. In CNN-DMD for QMI, use 160k steps for sufficient CNN training. For the stability of CNN-DMD in presence of the layerwise partitioning, we choose new = for CNN-DMD.
E.2 Wallelock Time in Classical Simulations
We define the wallelock time the time of DMD learning plus the time of quantum optimization. The DMD learning on classical computers is indeed very efficient (for each piece, only milliseconds for DMD and SW-DMD, and less than minute for neural DMD), and thus it is not the bottleneck. The main bottleneck is the time of quantum optimization, and our QuACK is designed to speed up this. In our work, the quantum optimization is simulated by classical computers. The simulations on classical computer (a single CPU) take the time at orders from minutes to an hour depending on the details of the task and hyperparameters. As representative example, for the 12-qubit Ising model with Adam in Figure 3b of Sec. 6.5, the time costs of simulations (with the parameter- shift gradient updates explicitly to mimic the actual quantum optimization) are listed Table Thanks to the acceleration by our QuACK, we can see the benefit of having less wallclock time by our various DMD methods compared the baseline VQE. We note that these wallelock times are for classical simulations of quantum optimization. For actual quantum optimization, it is expected that
24

---

Method
Wallclock time (seconds)
VQE (baseline)
2866
DMD (ours)
646
SW-DMD (ours)
663
MLP-DMB (ours)
818
SW-MLP-DMML (ours)
849
ENN-DMD (ours)
828
Table 2: Wallclock time costs of simulations with the parameter-shift rule explicitly implemented on classical computer with single CPU. Our various QuACK methods are faster than the baseline because they use fewer gradient steps.
our approach can gain much more benefit, since the dominant cost is from each gradient step of quantum optimization. The wallclock time saved actual quantum computer will proportional to the speedup factor multiplying the actual time of each iteration in quantum optimization. This will help us save more resources since the actual quantum optimization time is more expensive than the classical simulations of the quantum optimization.
E.3 Speedup in Sec. 6.5
Speedup
MLP- SW-DMD
Task
DMD
SW-DMD
MLP-DMD
CNN-DMD
12-qubit Ising
3,43x
4.63x
2.04x
3,43x
2.32x
10-qubit LiH
2.31x
3.24x
1.82x
2.42x
1.16x
10-qubit QML
3.76x
4.38x
1.86x
4.11x
3.46x
Table 3: Speedup ratios for all DMD methods for various tasks under the condition of non-smooth optimization.
The speedup ratios in Sec. 6.5 for non-smooth optimization by QuACK from our QuACK with all the DMD methods are given in Table
E.4
Dynamies Prediction in the Quantum Natural Gradient, Overparameterization, and Smooth Optimizatoin Regimes
We show the dynamics prediction of the DMD prediction in our QuACK framework compared with the intrinsic dynamics of the baseline VQE in the cases of the quantum natural gradient, overparame- terization, and smooth optimization regimes, as a supplement the discussion in Sec. 6.2, 6.3, 6.4.
Quantum natural gradient. As supplement of Sec. 6.2, Figure 9, we show the prediction matching of the 10-qubit quantum Ising model (RealAmplitidues ansatz with reps 1) with transverse field h 0.5 using the quantum natural gradient with learning rate 0.01. the prediction from all the DMD methods in our QuACK framework is accurate, as they almost overlap with the intrinsic dynamics of energy from the baseline VQE (To 150). We use 7sin 10, uDMD = 20 with Nstte = 5. We choose new = 6 for SW-DMD, MLP-SW-DMID and CNN-DMD. For the neural DMD, to achieve good performance, we use 160k training steps for MLP-DMD, and 80k training steps for MLP-SW-DMD and CNN-DMD.
Overparameterization Regime. In Figure 10, we present examples used Sec. 6.3. The DMD prediction prediction matches the intrinsic dynamics of VQE, with short training (N-im = 4) and long prediction (DDMDD = 1000). Therefore, a great effect of >200x speedup can be achieved.
Smooth Optimization Regimes. In the smooth optimization regimes we consider, the optimization dynamics is not as linear the cases of the quantum natural gradient and overparameterizzatio. In
25

---

Intrinsic dynamics
DMD (owrs
SW-DMD (ours)
Energy
MLP-DMD (ows)
-9-
MLL-SW-DMA (ours)
CNN-DMD (ours)
-10-
50
100
150
Steps (gradient steps + prodiction steps)
Figure Quantum natural gradient for VQE of 10-qubit quantum Ising model. All the DMD methods using our QuACK framework provide accurate prediction for the intrinsic dynamics of energy of the VQE. For the various DMD methods, solid parts are VQE runs, and the dashed parts are DMD predictions.
Intrinsic dynamics
0-
Intrinsic dynamics
DMD training (ours)
DMD training (ous)
Energy
DMD prediction (ours)
Energy
-1
DMD prediction (ours)
-2-
-2
2500
5000
7500
10000
5000
10000
15000
Steps (gradient steps + prediction steps)
Steps (gradient steps + prediction steps)
(a) 2, n params 1000.
N paraams 1500.
Intrinsic dynamics
0
Intrinsic dynamics
DMD training (ours)
DMD training (ours)
Energy
Energy
DMD prediction (ours)
-2
DMD prodiction fours)
-2
-3-
5000
10000 15000 20000
10000
20000
Steps (gradient steps + prediction steps)
Steps (gradient steps + prediction steps)
(c) N 4, Paraams 2000.
(d) N Pararms 2500.
Figure 10: Prediction from DMD in our QuACK framework matches the intrinsic dynamics of energy in the overparameterizzatoon regime for VQE of the N-qubit quantum Ising model.
26

---

-1.4
-2.1
-3.0
lnriesie IKC prodkttio (vEo)
Elergy
-1.6
trahiing BMil profiction (son)
Energy
-2.0
UMI proditio (oen]
(wen))
Elergy
-3.5
-1.8
-2.8
-2.0
-3.0
-100
-2.2
-3.2
300
1000
1500
500
1000
1500
500
1000
1500
Stege (gradienn stege
prediction steqs)
Stege [gr (gradisent steps prediction stequ)
Steps
(gradien: stege prediction stepe)
(a)
2. Apparama
(b) N Rpparame
6.
(c) = 4, Apparas
8.
4.5
dynanees
4.0
BMT maining (won))
-5.0
(oan))
ruising (rom]
Energy
UMIl prodition (sem)
Energe
prodk (oon)
Energye
DMD prdistio (surs)
-1.5
-5.5
-5.0
-6.0
6.5
500
1000
1500
0
500
1000
1500
500
1000
1500
Stege (gradientt stepe prediction steps)
Stege
(gradiennt stege + predictioa stequ)
Steps (gradientt steps + prediction steps)
(d) N 5, Pparams
10.
(e)
6, aparams
12.
(f) N = 7, paramme
14.
latrictc dyassio
bestids dreansio
-1.0-
BMn maining (wen))
DMD miniii (cep)
DMID tousing (MaR))
Energy
Dall predetion (son)
Energe
DMD pridition (ear))
Energy
UMD postiction (oan))
-1.5
-5.0
-10-
500
1000
1500
5000 Steps (gradiect steps + prediction stepe)
1500
500
1000
1500
Stege [gr aitteet stege
prediction steps)
Stepe [graciinn steps prodlctioon stepss)
(g) N 8, Rpaaram
16.
(h) N 9, Rpparam 18.
ii) AN
10. Aparams = 20.
Bestak dbsessoo
lasttadc drassses pAm maiiing (oun)
miD nannng (oie)
Easrge
-9-
DSDD posticion (oan)
Ecerge
10-
BMl prodiitinn (oen))
-11-
-12
-12
500
1000
1500
1500
Stege [gradient steps prediction steps)
Stege (gradient steps + prediction steps)
(i) N 11, pparams 22.
(k) N 12, Rparame 24.
Figure 11: Prediction from DMD in our QuACK framework compared to the intrinsic dynamics of energy in the smooth optimization regime for VQE of the N-qubit quantum Ising model with Upparams = 2N.
addition, the dynamics from the Adam optimizer tends to be more complicated than the quantum natural gradient optimizer and the gradient descent. The above factors make challenges for the DMD prediction. In Figure 11, we present examples used in Sec. 6.4. The DMD prediction, with short training (Nsim = 3) and long prediction (NDMD = 60), still captures the trend of decrease of the loss (energy) and has good alignment in most cases. In some cases when the loss is almost already converged at a late optimization time with steps 2 500, , the rate of change of 0 is slow so that the DMD might overfit the flat dynamics and have divergence in its prediction. However, this is not problem for the practical thanks to the robustness of the alternating controlled scheme in our QuACK, manifestly explained in the example of Figure 6b. Therefore, great acceleration with >10x speedup can still be achieved. We also comment that intriguingly, in some examples of Figure 11, e.g., 11b. the loss from DMD in our QuACK might decrease faster than baseline VQE, which could lead to a > and a higher speedup, as we have mentioned in Sec. 5.2.
E.5 Experiments with Noise
In Sec. 6.6 and this section, we use the RealAmplitude ansatz with reps = (Mparams = 2N). The task VQE of the quantum Ising model with h = 0.5 initialized at random initialization (with a fixed random seed for comparing different cases with the same N). The optimizer is Adam with the
27

---

Montes (V0E
Soctee
USID (mun))
-8
3MHD (ORES)
DMD
Energge
ME DLSTT
Energe
Eneeyge
DATTY
MLL--W-
MIL--WW-n D-D coon))
-10-
CNN- (wap))
-10
-10
11
0
50
100
150
200
50
100
150
200
0
50
100
150
200
Inemations
Ineerations
Ineratiooss
(a) 10 10-qubit shot noise, Tishosa 100.
(b) 10-qubit shot noise, Oshota 1,000.
(c) 10-qubit shot noise, Tishota 10,000.
335
-3.
(oens)
Energy
SW-DMD (su))
MIL
Energy
-4.9
DAID
(Snn)
Energe
-4.0-
SW--DWI (san)
MLLP
MLP SW: DND (sen))
-4.5
M.P-EW DWD (ox))
-4.5
MIP--WW (GU))
CNN EXm (p0v))
CNC DAT (ver)
CNV BMT (see)
-5
-5.0
-5.0-
-5.5
0
50
100
150
200
0
30
100
150
200
50
100
150
200
Itecations
Iterations
Iserations
(d) 5-qubit shot noise, Aaahote
(e) 5-qubit shot noise, Tishots 1,000.
(f) 5-qubit shot noise, Tishots 10,000.
100.
-3.5
-3.5
DMD
Eneegy
XILENCEDD
BM-D
Energy
-4.0
ALLINEDD (oand)
59-000 (uea)
Eneegy
SM-DoI
IP SU IVD
P sur Twit (san))
SiI sy Twih (oen)
esea EAIT (oa))
-1.5
CSN DVD jari
-4.5
ESN DUD janr
-5.9
-5.0
-5
0
50
100
150
200
0
50
100
150
200
50
100
150
200
lterratooss
Iterations
Iserations
(g) 5 quuit FakeLima, Palhota 100.
(h) 5-qubit FakeLima, Nahoot 1,000.
(i) 5-qubit FakeLima, Naaoot 10,000.
Reaine (PQF)
Buntas (ViqE)
Bustas (1Q5)
(wex)
(ee))
-3.5
Enengy
MM-D pean)
Energy
Swatk fema
Mit DMD
Energy
-4.0
FMr bruh (am)
MLPAISD pant
XLLP- 5tt IND (aee
A22 det ED1D (wee)
CISAEDD (sand)
DMD (vea))
-4.5
BMD (aard
-5
-5.0
0
50
100
150
200
50
100
150
200
100
150
200
Iterations
Iterations
Iserations
(i) S-qubit FakeManila, Nahhts 100.
(k) 5-qubit FakeManila, Niboote
()) 5-qubit FakeManila, Nishots 10,000.
1,000.
Figure 12: Experiments with different noise systems at Tashots = 100, 1000, 10000. Optimization histories for energy of full VQE and various DMD methods with our QuACK are shown. Dashed lines indicate that the DMD methods are used to accelerate the optimization. The error bands are the statistical uncertainty of from finite-nghots quantum measurements.
learning rate 0.01. We have also applied measurement error mitigation [5] to reduce the effect of quantum noise.
In Figure 12 with statistical error from shots plotted error bands, we show the experiments with the acceleration effects by our QuACK framework using all the DMD methods with different noise systems (10-qubit and 5-qubit shots noise, FakeLima, and FakeManila) at Tishots = 100, 1000, 10000. The full baseline VQE has Th. = 200 iterations. We choose Nigi = 10 and RDMD = 20. SW-DMD, MLP-SW- DMD, and CNN-DMD use window size nsw = 6. The acceleration effects with numerical speedups are given in Table I of main text. There are more fluctuations in the small 7ishots cases, but our QuACK is still able to accelerate the VQE.
The spikes in the DMD results occur every Assim = 10 iterations at the beginning of every piece of VQE, and are more distinct when Rabots is smaller. This may be because it is harder to make
28

---

predictions of the VQE history when the parameter updates time series from measurement is more noisy. Despite the occasional spikes in energy, our QuACK with all the DMD methods still helps to get closer to the better parameters for optimization in later steps.
(cuma)
SW SW-DDID (ouns)
MILP PELP (oans)
Speedup ratio
4
MLLP-S HILF-SW-DXID (cxma)
UNN DNN-MDDD (mins)
3-
2-
10
Figure 13: Ablations of Rsim on the 12-qubit Ising model with Adam for all DMD methods.
Speedup ratio
3-
2-
1-
DND (suz))
(ouz) (sus)
(oun) MIPP DND (suz))
20
80
100
TDDDD
Figure 14: Ablations of ADMD on the 12-qubit Ising model with Adam for all DMD methods.
E.6 Ablation Study for asi and 7DMD
Figures 13 and 14, we show the ablation study nsim and NDMD all the DMD methods with QuACK framework. The experimental setup is the same the experiment in Sec. 6.5, 12-qubit Ising model with Adam (including having the same initial point), except for varying Naim- (For CNN-DMD, increase 7itter from 12 to 20 to ensure convergence.) With 7mm [4, 10] in Figure 13 and ADMD E [8, 100] in Figure 14, all the DMD methods have accelcration effects (>1x speedup), which shows that QuACK is robust in range of Asim In Sec. 6.5 for the quantum Ising model, we have used nsi = 5 and #DMD = 40. The choice of n.ii and RDMD will affect the speedup, and understanding the behavior from varying Nsin and RDMD needs future study.
E.7 Experiments on the Real IBM Quantum Computer Lima
In the current era, the practical cost using the real quantum resources is still very high (both in waiting time and actual expense), which makes implementing gradient-based optimizers on real quantum hardware an expensive task. However, we still try our best to perform an experiment on real IBM quantum computer Lima and demonstrate how our QuACK can accelerate optimization in complicated settings.
Given our limited access to real quantum hardware, gradient-basee optimization with quantum computer is too costly and time consuming. We use the gradient- free optimizer SPSA as an alternative, which updates the parameters by random perturbation. Before we dive in the data, We would like to point out that the gradient-free optimizer very different from gradient-based based optimizer and our main theoretical advantages in this work are for gradient-based quantum optimization. In addition, we find that the real quantum hardware also subject to fluctuation of day-to-day calibration which could affect the performance of our approach (it can be removed if one has direct timely access to
29

---

the quantum computer). Hence, the results in this section should not be directly compared to the experiments in our main text.
Baseline (VQE) SW-DMD (ours)
Baseline (VQE)
3.5-
SW-DMD (ouns)
-3.5
MIP-SW-DMD (ours)
MLP-SW-DMD (ours)
Energy
-1.0
Energy
-.0
-4.-
-4.5
-5.0
20
40
60
20
40
60
Iteraioons
Ittrations
(a) FakeLima with SPSA.
(b) Real Lima with SPSA.
Figure 15: For the 5-qubit quantum Ising model h. 0.5, SPSA on (a) FakeLimm and (b) the real quantum computer IBM Lima with Nshots 10,000. Optimization histories for energy of full VQE, SW-DMD, and ULP-SW-DMMD are shown. Dashed lines indicate that the DMD methods are used to accelerate the optimization. The error bands are the statistical uncertainty of from finite-nshots quantum measurements.
We use Ylshots = 10,000 for the 5-qubit Ising model at h = 0.5 on both Fakel .ima and real Lima. For our QuACK, we use SW-DMD and MLP-SW-DMD with nsw = 15, Alsi = 20, ADMD 20 due to our limited access to the real quantum hardware. We show the results in Figure 15b. Moreover, both the baseline VQE and our QuACK have more fluctuation on real Lima than FakeLima, which can be due to experimental instability in the real lab apparatus, such as day-to-day calibration. However, applying QuACK to this real physical case still help accelerate VQE, as SW-DMD and MLP-SW- DMD partly predict the dynamics and decrease the loss faster than the baseline. This is positive message as our approach can also be helpful for gradient- free optimization which our theorems are not designed for. Mcanwhile, would like to point out this is not the main focus of this paper because the gradient- based quantum optimization has been shown to have convergence guarantee and better than gradient-free methods [37, 44, 87, 38). In the coming few years when the quantum hardware become more suitable for gradient-based optimization, our QuACK will demonstrate more advantage for practical applications.
F
Additional Information
F.1
Ethics Statement
This work introduces the Quantum-circuit Alternating Controlled Koopman learning (QuACK), a novel algorithm enhancing the efficiency of quantum optimization and machine learning. As significant advancement in quantum computing, QuACK promises benefits across numerous scientific and technological upplications. However, the potential misuse of such technology, particularly in areas like quantum chemistry, could lead to unintended consequences. For example, the increased efficiency in quantum chemistry simulations could inadvertently facilitate the development of chemical weapons used irresponsibly.
F.2
Compute
All of our experiments for classically simulating quantum computation are performed on a single CPU. These includes all the experiments presented in the main text and the Appendix, except for the experiment run on the IBM quantum computer ibmq_limat which is one of the IBM Quantum Falcon Processors. The views expressed are those of the authors, and do not reflect the official policy or position of IBM or the IBM Quantum team.
30

---

F.3 Reproducibility
We have stated all of our hyperparameter choices for the experimental settings in the main text and in the appendix. We perform simulations of VQE using Qiskit [2], python framework for quantum computation, and Yao [47], a framework for quantum algorithms in Julia [7]. Our neural network code is based on Qiskit and Pytorch [57]. Our implementation of quantum machine learning is based
on Julia Yao. We use the quantum chemistry module from Pennylane [6] obtain the Hamiltonian
of the molecule. Our code is available at https: : /ttp/ggitit thub..b..... com CatooopmanQQAACK
F4 Broader Impact
The development and implementation of the our QuACK framework could be impactful the broader scientific and technological community. This approach to quantum optimization can drastically accelerate multitude of computations in quantum chemistry, quantum condensed matter, and quantum machine learning, which can lead to groundbreaking advancements in these fields.
For instance, in quantum chemistry, the rapid optimization enabled by QuACK could expedite the design new molecules and materials, potentially leading to the creation of novel drugs, eco- friendly fuels, and advanced materials with superior properties. In quantum condensed matter, faster computations could expedite our understanding of complex quantum systems, possibly catalyzing new insights in physics and material science.
In the realm of quantum machine learning, this acceleration could potentially revolutionize our ability to deal with large datasets and complex models, ultimately leading more accurate and efficient machine learning algorithms. This, in turn, could benefit broad range of sectors, from healthcare, where it could be used better diagnose and treat diseases, finance, where it could be used to model and predict market trends.
Moreover, the increased speed of quantum optimization could result in energy savings and reduced computing time, contributing to a more sustainable and efficient use of computational resources.
31


Reviews:
[{"review_id": "RnwxEbWS8R", "reviewer": "Reviewer_M6jg", "summary": "The paper presents an algorithm that  effectively \"extends\" $k$ gradients updates to $k'$ gradient updates by fitting a neural koopman operator. The additional cost is made worth it because the algorithm is derived in a quantum machine learning setting where quantum gradients are expensive and limited and classical operations are comparatively free and unlimited. The algorithm successfully speeds up Quantum Natural Gradient, in particular in the quantum overparametrzation regime (200x) but even in nonsmooth and noisy regimed it achieves 2x to 3x speedup. Convergence proofs for convex problems and some other theoretical results augment the derivation and empirical evaluation.", "questions": "- what is the distinction between previous \"neural koopman\" works (e.g. lusch et al) and this work? is it \"just\" that it is applied to QML learning dynamics?", "limitations": "I think limitations are well stated", "rating": 7, "confidence": 3, "soundness": 4, "presentation": 3, "contribution": 3, "strengths": "Originality: people don't use koopman operators enough, using them as a framework to perform a $m$-step extension of $k$ expensive gradient steps is  very clever and I might steal the idea for some of my own work post review period\nQuality: Argument is clear and sufficient analysis is done to sanity check and gain insight into the algorithm, but I would call this an empirical paper still, not in the least due to the training tricks required to make the neural koopman estimate work. For the empiricism, full marks, good ablations in the appendix, error bars where it matters. Bonus points for an attempt on real quantum experiments, even if the experiments are kind of tangential to the method presented (gradient free vs. gradient dynamics estimation)\nClarity:  well written, easy to understand\nSignificance: speaking as an ML person, I think this is a significant contribution to QML, in particular if we remain constraint by quantum operations\n\n\n", "weaknesses": "- what is the wallclock time of each method? this is a relatively crucial detail I am missing for context\n", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Strengths:\n\nOriginality: people don't use koopman operators enough, using them as a framework to perform a -step extension of  expensive gradient steps is very clever and I might steal the idea for some of my own work post review period Quality: Argument is clear and sufficient analysis is done to sanity check and gain insight into the algorithm, but I would call this an empirical paper still, not in the least due to the training tricks required to make the neural koopman estimate work. For the empiricism, full marks, good ablations in the appendix, error bars where it matters. Bonus points for an attempt on real quantum experiments, even if the experiments are kind of tangential to the method presented (gradient free vs. gradient dynamics estimation) Clarity: well written, easy to understand Significance: speaking as an ML person, I think this is a significant contribution to QML, in particular if we remain constraint by quantum operations\n\n**We thank the reviewer’s appreciation of our contributions.**\n\nWeaknesses:\nwhat is the wallclock time of each method? this is a relatively crucial detail I am missing for context\n\n**Thanks for the question. Here we define the wallclock time as the time of DMD learning + the time of quantum optimization. The DMD learning on classical computers is indeed very efficient (for each piece, only milliseconds for DMD and SW-DMD, and less than 1 minute for neural DMD) and thus it is not the bottleneck. The main bottleneck is the time of quantum optimization, and our QuACK is designed to speed up the time of quantum optimization. In our work, the quantum optimization is simulated by classical computers. The simulations on a classical computer (a single CPU) take the time at orders from minutes to an hour depending on the details of the task and hyperparameters. As a representative example, for the 12-qubit Ising model with Adam in Sec. 6.5 Figure 3(b) the time costs of simulations (with the parameter-shift gradient updates explicitly to mimic the actual quantum optimization) are**\n| Method      | Wallclock time |\n| ----------- | ----------- |\n| VQE (baseline)      |   2866 seconds    |\n|  DMD (ours)     | 646 seconds    |\n|  SW-DMD (ours)   |  663 seconds       |\n|  MLP-DMD (ours) | 818 seconds |\n| SW-MLP-DMD (ours) | 849 seconds |\n| CNN-DMD (ours) |  828 seconds   |\n\n**Thanks to the acceleration by our QuACK, we can see the benefit of having less wallclock time by our various DMD methods compared to the baseline VQE. We note that these wallclock times are for classical simulations of quantum optimization. For actual quantum optimization, it is expected that our approach can gain much more benefit, since the dominant cost is from each gradient step of quantum optimization. The wallclock time saved on an actual quantum computer will be proportional to the speedup factor shown in our paper multiplying the actual time of each iteration in quantum optimization. This will help us to save more resources since the actual quantum optimization time is more expensive than the classical simulations of the quantum optimization.**\n\n**We have included these details in the updated paper.**\n\nQuestions:\nwhat is the distinction between previous \"neural koopman\" works (e.g. lusch et al) and this work? is it \"just\" that it is applied to QML learning dynamics?\n\n**Thanks for the questions. While our neural DMD methods are inspired by the previous “neural koopman” works (e.g., lusch et al), there are certain features of our work. First, our work focuses on the acceleration of quantum optimization and QML, while the previous one is designed to learn classical PDEs. To achieve our goal, we need to analyze the quantum gradient optimization properties with the DMD approach, which builds connections among quantum imaginary time evolution, overparameterization theory, and complexity analysis. Furthermore, to achieve robust and efficient optimization, we develop an alternating control scheme to make sure our methods are always at least as good as the standard gradient-based method, which does not exist in the previous work.**"}, {"review_id": "vOlODk00jy", "reviewer": "Reviewer_kkUu", "summary": "The paper presents an innovative framework known as Quantum-circuit Alternating Controlled Koopman learning (QuACK), which effectively combines Koopman operator theory and natural gradient methods in quantum optimization. Through the utilization of an alternating algorithm, QuACK allows for the efficient prediction of gradient dynamics on quantum computers, resulting in a notable acceleration of variational quantum algorithms (VQAs). The authors provide empirical evidence showcasing the effectiveness of QuACK across diverse VQA tasks, including those involving noisy environments.\n\n\n\n\n", "questions": "The concerns listed in *Weakness* should be adequately addressed. Satisfactory responses to these points will further enhance the quality of the paper. ", "limitations": "The authors partially addressed the limitations of QuACK.  ", "rating": 6, "confidence": 5, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "The paper's strength lies in its contribution to accelerating the optimization of variational quantum algorithms (VQAs), which is crucial for leveraging the capabilities of modern quantum machines in practical problem-solving. The proposed QuACK addresses this challenge and presents intriguing findings. By incorporating Koopman operator theory and deep neural networks, QuACK offers noticeable speed improvements compared to conventional optimization methods like the parameter shift rule. The numerical results provided in the paper demonstrate the efficacy of QuACK.", "weaknesses": "The primary concern of the paper lies in the stability and robustness of QuACK. Algorithm 1 suggests that the performance of QuACK may heavily rely on the hyperparameters n_sim and n_DMD. Determining the appropriate values for these hyperparameters is an empirical process and may require additional hyperparameter optimization, introducing a potential computational burden. While the authors have conducted extensive numerical analysis, it remains unclear whether an improper setting of these hyperparameters could undermine the advancements of QuACK in optimizing modest-sized VQAs that aim to achieve quantum advantages, particularly in scenarios involving 100+ qubits.\n\nFurthermore, the issue of stability is exacerbated by QuACK's sensitivity to the system and shot noise. As demonstrated in the study by Du et al. (PRX Quantum 2.4, 2021: 040337), gradient-based methods can exhibit divergence under significant noise and low shot numbers. It remains uncertain whether QuACK demonstrates greater robustness compared to standard optimization strategies in such challenging scenarios. Addressing these stability and robustness concerns would augment the applicability and reliability of QuACK in practical quantum optimization tasks. A more in-depth discussion of these issues would be preferable.\n\nIn addition, there are some minor issues with the paper:\n\n- The font size in Figure 1 is too small, making it challenging to read.\n- The relation between n_sim and m is not clearly defined in the paper, and clarification is needed.\n- Corollary 5.4 could be removed since it is redundant given that the optimization of VQAs is generally non-convex.\n- The format of references does not adhere to the standard style in NeurIPS.\n- Several references are missing, including:\n   1. You, Xuchen, et al. arXiv:2303.14844.\n   2. García-Martín, D., Larocca, M., & Cerezo, M. arXiv:2302.05059.\n   3. Wang, Xinbiao, et al. arXiv:2208.14057.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Strengths:\nThe paper's strength lies in its contribution to accelerating the optimization of variational quantum algorithms (VQAs), which is crucial for leveraging the capabilities of modern quantum machines in practical problem-solving. The proposed QuACK addresses this challenge and presents intriguing findings. By incorporating Koopman operator theory and deep neural networks, QuACK offers noticeable speed improvements compared to conventional optimization methods like the parameter shift rule. The numerical results provided in the paper demonstrate the efficacy of QuACK.\n\n**We thank the Reviewer’s appreciation of our contributions.**\n\nWeaknesses:\nThe primary concern of the paper lies in the stability and robustness of QuACK. Algorithm 1 suggests that the performance of QuACK may heavily rely on the hyperparameters n_sim and n_DMD. Determining the appropriate values for these hyperparameters is an empirical process and may require additional hyperparameter optimization, introducing a potential computational burden. While the authors have conducted extensive numerical analysis, it remains unclear whether an improper setting of these hyperparameters could undermine the advancements of QuACK in optimizing modest-sized VQAs that aim to achieve quantum advantages, particularly in scenarios involving 100+ qubits.\n\n**We thank the Reviewer for the question. While n_sim and n_DMD are hyperparameters, we have certain intuition and rules of thumb for choice. In general, for smooth dynamics (such as the overparameterization regime), we need smaller n_sim, while for more complicated dynamics, larger n_sim is needed to capture the non-smooth dynamics. To gain a better understanding of the effects of n_sim, we have already performed an ablation study on n_sim in our supplementary materials. We have further performed an ablation study for n_DMD in Fig. 1 of our one-page pdf. The results show that our QuACK are robust to the change in n_sim and n_DMD, consistent with our intuition. For example, in the 12-qubit Ising model, n_DMD between 20-100 achieve good speedup. Meanwhile, as we mention in the Limitation part of our paper, more theoretical and algorithmic study of the hyperparameter choice will be an important future direction. For example, one can consider the online learning techniques in ML to adaptively update the hyperparameters for better performance. We have included the new results and discussions in the updated paper.**\n\nFurthermore, the issue of stability is exacerbated by QuACK's sensitivity to the system and shot noise. As demonstrated in the study by Du et al. (PRX Quantum 2.4, 2021: 040337), gradient-based methods can exhibit divergence under significant noise and low shot numbers. It remains uncertain whether QuACK demonstrates greater robustness compared to standard optimization strategies in such challenging scenarios. Addressing these stability and robustness concerns would augment the applicability and reliability of QuACK in practical quantum optimization tasks. A more in-depth discussion of these issues would be preferable.\n\n**Thanks for the comment. It is a good point to have understanding on the noise effects. While gradient-based methods may diverge under significant noise and low shot numbers, it is not clear if quantum optimization is useful in such situations since the quantum computers could just be too noisy to use. To understand the robustness of our approach under both quantum noise and shot noise, we have also performed ablation study in Section 6.6 with Table 1 and Figure 4. We find that our approach can still achieve 2x to 5.5x Speedup in different noisy regimes. Indeed, the alternating control scheme we developed is helpful to improve the robustness since it uses the optimal value for the next learning starting point, which reduces the noise fluctuation for a particular step. We have included more discussion on the topic in the updated paper.**\n\nIn addition, there are some minor issues with the paper:\n\nThe font size in Figure 1 is too small, making it challenging to read.\n\n**Thanks for the suggestion and we have increased the font size.**\n\nThe relation between n_sim and m is not clearly defined in the paper, and clarification is needed.\n\n**We thank the reviewer for pointing this out. For that purpose we update the paper in Algorithm 1 by adding the following specification of the hyperparameters: “Koopman operator learning parameters $m$ (num. simulation. steps $n_{\\mathrm{sim}})$, $n_{\\mathrm{DMD}}$ (num. DMD steps).”**\n\nCorollary 5.4 could be removed since it is redundant given that the optimization of VQAs is generally non-convex.\n\n**Thanks for the suggestion. It is true that VQA is generally non-convex and the original motivation is to show QuACK maintains nice properties for convex optimization as a theoretical result, in case readers are interested in.  We will be glad to follow the suggestion and move Corollary 5.4 to Appendix.**\n\nThe format of references does not adhere to the standard style in NeurIPS.\n\n**Thanks for the suggestions. We modified the format of references to enumerate with numbers.**\n\nSeveral references are missing, including:\nYou, Xuchen, et al. arXiv:2303.14844.\nGarcía-Martín, D., Larocca, M., & Cerezo, M. arXiv:2302.05059.\nWang, Xinbiao, et al. arXiv:2208.14057.\n\n**Thank you for the valuable suggestion for including these references. We included the following paragraph after the “Quantum Optimization Methods” paragraph in the Related Work Section:**\n\n***Some additional lines of work are related to our study. \\citet{you2023analyzing} analyzes the convergence of quantum neural networks through the lens of the neural tangent kernel. Similarly, working through an effective quantum NTK theory, \\citet{wang2022symmetric} proposes symmetric pruning to improve the loss landscape and the convergence of quantum neural networks. Finally, \\citet{garcia2023effects} studies the effect of noise on overparameterization in quantum neural networks.***\n"}, {"review_id": "bo1yFrGdX7", "reviewer": "Reviewer_sYsu", "summary": "This paper proposes QuACK, which leverages Koopman operator learning theory to accelerate gradient-based quantum optimization and machine learning. QuACK utilizes the sliding window DMD to enrich the embedding, and neural networks to learn and predict the nonlinear dynamics. Experiments on quantum Ising model, quantum chemistry and quantum machine learning show QuACK’s remarkable speedup and robustness. Also, theoretical analysis of its stability, convergence and complexity is provided.", "questions": "1. The parameter $n_{sim}$ seems not well-defined in the paper. What is the specific meaning of it in Algorithm 1?\n2. Have you compared QuACK with gradient-free methods like COBYLA?", "limitations": "Yes.", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "1. The proposed QuACK can significantly accelerate gradient-based quantum optimization by predicting the gradient dynamics, which may help deploy gradient-based quantum algorithms on NISQ devices.\n2. Extensive experiments on quantum Ising model, quantum chemistry and quantum machine learning are conducted. Besides, speedup is verified for quantum natural gradients, in overparameterized scenes, and on IBM quantum devices.\n3. Theoretical analysis of QuACK’s stability, convergence, complexity and speedup is provided.", "weaknesses": "1. $\\Theta(t_{d+1})\\approx K\\Phi(\\Theta(t_0))$ in page 5 seems to lack theoretical support, since the koopman operator is $Kg(x(t))=g(x(t+1))$, which is different from the given formula.\n2. Though gradient-based optimization with quantum computers can be costly and time consuming, an extra experiment on NISQ devices for gradient-based optimization is necessary for validating the feasibility of QuACK on realistic scenes.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Weaknesses:\nΘ(td+1)≈KΦ(Θ(t0)) in page 5 seems to lack theoretical support, since the koopman operator is Kg(x(t))=g(x(t+1), which is different from the given formula.\n\n**Thanks for the question. This is a good point to note. As the reviewer points out, this is different than the conventional Koopman operator notation. Indeed, here we take the perspective of ‘generalized operator’ by viewing K.𝜱 as one operator that transfers the state at time t to the state at time t+1. This formulation also generalizes the standard DMD where 𝜱 is the identity map while it can still be solved efficiently with 𝜱, particularly with the SW-DMD case we can still perform the SVD directly.**\n\nThough gradient-based optimization with quantum computers can be costly and time consuming, an extra experiment on NISQ devices for gradient-based optimization is necessary for validating the feasibility of QuACK on realistic scenes.\n\n**Thanks for the comment. Indeed, the current experiment on NISQ devices using gradient-based optimization is very costly. To provide a concrete example of quantum cost, the quantum computing service of Rigetti on Amazon (https://aws.amazon.com/braket/pricing/) for one VQE quantum optimization experiment of 160 params over 200 steps with 100 shots each can take: \\$ 160 * 200 * (0.3 + 100 * 0.00035) = \\$ 10720. While we are also very interested in performing gradient-based optimization on NISQ device, which will further demonstrate the benefit of our work on saving both computation and economic resources, we are not able to perform such experiments given our current budget and time and it could be an important direction for future work.**\n\nQuestions:\n1. The parameter n_sim seems not well-defined in the paper. What is the specific meaning of it in Algorithm 1?\n\n**We thank the reviewer for pointing out the unclearness of the definition of $n_\\mathrm{sim}$. $n_\\mathrm{sim} = m$ in Algorithm 1. We have now used “$n_\\mathrm{sim}$” to replace “$m$” in Algorithm 1 and the text near it.**\n\n2. Have you compared QuACK with gradient-free methods like COBYLA?\n\n**We thank the reviewer for raising this interesting point regarding gradient-free methods. While gradient-based methods and gradient-free methods are applicable types of optimizers for VQAs, gradient-based methods use gradient information and thus can know better about the local geometry [1], especially with quantum Fisher information through quantum natural gradient. Particularly, the gradient method has been shown to converge for quantum optimization [2, 3]. It is also known that other gradient-free methods such as SPSA do not perform well compared to gradient-based methods [4]. Given the nice convergent property of gradient-based optimization, it is meaningful to accelerate gradient-based methods. Hence, our paper focuses on improving upon gradient-based methods in variational quantum algorithms, instead of comparing with gradient-free methods.** \n\n**In Fig. 3 of our one-page pdf, we have included an example of shot-noise of the quantum Ising model to provide a concrete demonstration of the above point. While the gradient-based VQE with Adam finds a lower energy than COBYLA, as COBYLA gets trapped. Our methods further improve upon Adam.**\n\n[1] Li, Hao, Zheng Xu, Gavin Taylor, Christoph Studer, and Tom Goldstein. \"Visualizing the loss landscape of neural nets.\" Advances in neural information processing systems 31 (2018).\n[2] Ryan Sweke, Frederik Wilde, Johannes Meyer, Maria Schuld, Paul K. Faehrmann, Barthélémy Meynard-Piganeau, Jens Eisert. Stochastic gradient descent for hybrid quantum-classical optimization. Quantum 4, 314 (2020).\n[3] You, Xuchen, Shouvanik Chakrabarti, and Xiaodi Wu. \"A convergence theory for over-parameterized variational quantum eigensolvers.\" arXiv preprint arXiv:2205.12481 (2022).\n[4] Leng, Jiaqi, Yuxiang Peng, Yi-Ling Qiao, Ming Lin, and Xiaodi Wu. \"Differentiable analog quantum computing for optimization and control.\" Advances in Neural Information Processing Systems 35 (2022): 4707-4721.\n\n\n"}, {"review_id": "EmYXJEqZ6o", "reviewer": "Reviewer_ePBi", "summary": "This paper utilizes Koopman operator theory to accelerate the optimization of quantum circuits. Stability analysis is performed and the benefit of alternating between standard and Koopman optimization is discussed. A number of experiments are performed, across several different areas of interest to the quantum computing community, with Koopman optimization performing significantly faster than standard approaches. The effect of noise is studied, with QuACK again finding a benefit. ", "questions": "1. Why does the 4x speedup reported for Fig. 3 not match the qualitative increase in speed-up from the figure? \n\n2. Is it true that classical backpropagation is independent of $n_{params}$?\n\n3.  The speedup ratio of Fig. 2b and c seem to increase with the number of parameters. Is this expected? \n\n4. Does \"the a layerwise partitioning\" (line 299) refer to the layer Koopman partitioning of Dogra and Redman, 2020? \n", "limitations": "The authors do a sufficient job addressing their limitations in the Limitations subsection of Sec. 4. They also study several different examples, across multiple different subregions of quantum computing, as well as different noise condition, providing strong evidence for their claims that Koopman training accelerates quantum optimization. ", "rating": 7, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "1. This paper motivates the need for efficient, gradient based methods for optimizing quantum circuits. \n\n2. This paper shows, via a number of experiments, the potential of Koopman operator theory to accelerate training, over a number of different regimes. \n\n3. This paper tests multiple implementations for computing the Koopman spectra, including DMD, sliding DMD, and machine learning implementations. \n\n4. The Appendix contains many details on quantum computing and the architectures used (the availability of this information should be mentioned in the main text). ", "weaknesses": "1. While Theorem 5.1 is true, in the sense that any finite numerical implementation of Koopman mode decomposition will find eigenvalues that are not exactly equal to 1, that does not mean that the eigenvalues computed by DMD will not be very close to 1 (see Redman et al., 2021 Fig. 4 for example of eigenvalue being 1.000), and that the associated Koopman mode could be a good approximation to a true fixed point. \n\n2. Similarly, Theorem 5.2 and Corollary 5.4, while true, does not imply that QuACK will not lead the quantum circuit to converge to a different local minima than the gradient-based optimizer. This should be noted explicitly. \n\n3.  Fig. 3 shows that the Koopman based methods converge very quickly to the asymptotic energy and test accuracy - from just the plots alone it seems like the speed-up should be greater than the reported 4x.  Why is this the case? \n\n4. The Koopman learning section should be expanded to include mention of the Koopman mode decomposition (Mezic, 2005). Additionally, the need for data to computed the Koopman mode decomposition should be motivated in Sec. 3, before the QuACK algorithm (which needs data from the gradient based optimizer) is presented. The interested reader should be referred to more detailed discussion in Budisic  et al., 2012 and Brunton et al., 2022. Finally, it should be noted that the idea of time-delays is related to Taken's theorem, with the implementation presented in Eq. 1 being Hankel DMD (Arbabi and Mezic, 2017). The sliding window DMD method is similar to streaming DMD (Hermati et al., 2014; Giannakis et al., 2023). \n\n5. While this is, to my knowledge, the first approach of using Koopman operator theory to the study of quantum machine learning, it would be appropriate to cite more of the work on studying machine learning using Koopman operator theory (e.g., Mohr et al., 2020; Naiman and Azencot, 2021; Šimánek et al., 2022; Liang et al. 2022). Additionally, the previous work that has optimized neural networks using Koopman operator theory (Dogra and Redman, 2020; Tano et al., 2020) should be discussed in more detail (especially when presenting the speed-up $s$, which was defined similarly by Dogra and Redman, 2020, and when discussing the alternating strategy of Koopman training, which Tano et al. 2020 also utilized). Work using Koopman to study iterative algorithms (Dietrich et al., 2020; Redman et al., 2022) more generally should also be cited when mentioning that \"the optimization trajectory...is a dynamical system\" (line 52). Relatedly, the references with respect to Koopman operator theory need to be updated. Extended-DMD (EDMD) refers to a specific algorithm, developed by Williams et al. 2015. This was not referenced when EDMD was mentioned in the paper (line 80), and all other papers cited described extensions to DMD that are not EDMD. The connection between DMD and Koopman mode decomposition should be noted (Rowley et al., 2009). \n\n6. Is it true that classical backpropagation is independent of $n_{params}$? I think you mean that you don't need to do individual perturbations along the dimension of each parameter, but this needs to be clarified. \n\nMINOR COMMENTS:\n\n1. The speedup ratio of Fig. 2b and c seem to increase with the number of parameters. Is this expected? \n\n2. Describing Koopman as \"renowned for accelerating/predicting nonlinear dynamical systems\" (lines 4 and 54) is a little overgeneral. Perhaps, saying \"which has found utility in applications, as it allows for a linear representation of nonlinear dynamical systems,\" would be more specific and accurate. \n\n3. It is mentioned that the quantum natural gradient is linked to imaginary time in the Introduction, but this is not discussed in overview section of Quantum Natural Gradient in Sec. 3. \n\n4. There are a few minor typos: \n    i. The question \"How can we accelerate...\", which is not a yes/no question, is posed (line 48), to which you answer \"in the affirmative\". \n    ii. You list 3 speedups, but four conditions (lines 61, 62). \n    iii. \"of the system is called wave function\" (line 88)\n    iv. \"the a layerwise partitioning\" (line 299). Does this refer to the layer Koopman partitioning of Dogra and Redman, 2020? \n", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "This paper shows, via a number of experiments, ...\n\nThe Appendix contains many details on quantum computing and the architectures used (the availability of this information should be mentioned in the main text).\n\n**We thank the reviewer’s appreciation of our contributions.**\n\nWeaknesses:\nWhile Theorem 5.1 is true, ...\n\n**Thanks for the comment. It is a good point that for certain cases the Koopman mode could be a good approximation to a true fixed point, while for quantum optimization we notice that these could be more subtle. Many hardware-efficient quantum circuits do not have nice structures compared to certain well-designed neural networks like ResNet, and the parameters of quantum circuits are angles which could rotate periodically. In those cases, we find that the asymptotic DMD prediction is more likely to be trivial or unstable, which is the motivation of Theorem 5.1. We have included further discussion in the updated paper to elaborate this point.**\n\nSimilarly, Theorem 5.2 and Corollary 5.4, while true, ...\n\n**Thanks for the comment. We agree with the reviewer that for Theorem 5.2 it is possible for QuACK to converge to different local minima compared to gradient-based methods. For the convex problem setup in Corollary 5.4, there will be one global minima so that QuACK and gradient-based optimizer should converge to the same point. We have included this note in the updated paper.**\n\nFig. 3 shows that the Koopman based methods converge very quickly to the asymptotic energy and test accuracy - from just the plots alone it seems like the speed-up should be greater than the reported 4x. Why is this the case?\n\n**Thanks for the comment. Indeed, this is a plotting issue that appears to converge very quickly, which should be around 4x if we zoom in clearly. We include a zoomed-in plot in Fig. 2 of our one-page pdf.**\n\nThe Koopman learning section should be expanded to include ...\n\n**Thanks for the suggestions. We have improved the writing based on the suggestions and included the relevant references.** \n\nWhile this is, to my knowledge, the first approach of using Koopman operator theory to the study of quantum machine learning...\n\n**Thank you for suggestion these foundational works. We updated our manuscript as follows:**\n\n**- After the “Koopman Theory” paragraph in the “Related Work” Section, we continued with: Ours and the above contributions are built upon works on machine learning using Koopman operator theory\\citep{mohr2020koopman,mohr2020predicting,naiman2021koopman,vsimanek2022learning,liang2022credit}.**\n\n**- We added “Similar speed-up definition has been considered in\\citep{dogra2020optimizing}” as a footnote in line 256.**\n\n**- We added “The algorithm iteratively alternates the simulation steps with the Koopman steps for $n_\\mathrm{iter}$ steps, similarly to\\citep{tano2020accelerating}” in line 156.**\n\n**- We added “similarly to\\citep{dietrich2020koopman,redman2022algorithmic},” in line 52.**\n\n**- We added “(connected to Koopman mode decomposition\\citep{rowley2009spectral})” in line 79.**\n\nIs it true that classical backpropagation is independent of...\n\n**Thanks for the suggestion. The memory complexity of classical backpropagation still scales with the number of parameters but the computation complexity does not, which is the same as the forward propagation. It is correct because we do not need to do individual perturbations along the dimension of each parameter, thanks to automatic differentiation. We have made this clarification in the updated paper.** \n\nMINOR COMMENTS:\n\nThe speedup ratio of Fig. 2b and c seem to increase with the number of parameters. Is this expected?\n\n**Thanks for the question. This is expected according to Theorem 5.5. The upper bound in Eq. (3) for the speedup increases as the number of parameters $p$ increases, since $f(p)$ increases when $p$ increases.**\n\nDescribing Koopman as \"renowned for accelerating/predicting nonlinear dynamical systems\" (lines 4 and 54) is ...\n\n**Thanks for the suggestion. We have written the sentences based on the suggestion.**\n\nIt is mentioned that the quantum natural gradient...\n\n**Thanks for the suggestion. We have mentioned the connection in the beginning of Section 5 and in the updated version, we have added the discussion on the imaginary time evolution to the Quantum Natural Gradient in the overview section as well.**\n\nThere are a few minor typos: i. The question \"How can we accelerate...\", ...\n\n**Thanks for the suggestions. We have fixed the typos. The layer Koopman partition is inspired by Dogra and Redman, 2020, and here we partition the layers of parameters in the quantum circuit instead of the classical neural networks. We have corrected the typo and included more description of the layer Koopman partition in the updated paper.**\n\nQuestions:...\n\n**Thanks for the questions. We have addressed them above.**\n\n\n"}]

Author rebuttal:
**We thank the reviewers’ comments and suggestions. Reviewer M6jg acknowledges originality, clarity of our argument, “full marks” on our experiments, experiments on real hardware, and significance of the results. Reviewer kkUu acknowledges “intriguing findings” in approaching the limitations of crucial approaches to modern quantum machines in practical problem-solving, noticeable improvements in our experiments, and the efficacy of our framework. Reviewer sYsu acknowledges significant acceleration of our method, extensive experiments and theoretical analysis. Reviewer ePBi acknowledges the motivation, demonstration of promise, multiple implementations, and extensive ablations of our method.**

**Some questions and suggestions were posed regarding topics, including wallclock times (M6jg), robustness of our method (kkUu), theory alignment with known Koopman theory (sYsu), experiments on real hardware (sYsu), clarifications throughout the text (ePBi).**

**We have addressed all of them with additional experiment and discussion, presented in our individual responses. We easily incorporated all of our responses in our manuscript, and we described how we accomplished that in our individual responses to the reviewers.**

**Thus, we hope that the reviewers can consider raising their scores.**

Meta-review: The paper provides a new approach for quantum optimization that permits efficient evaluation of gradients. The approach particularly excels in the overparameterized regime which is particularly of interest for modern deep learning methods. The reviewers uniformly appreciated the originality and empirical effectiveness of the proposed approach, and are optimistic that the approach will inspire many followups in quantum optimization. There were some small concerns regarding hyperparameters and theoretical justifications, which were addressed adequately during the discussion phase. The AC would recommend including these details in the camera-ready version. Overall, there was broad consensus for accepting the paper.
Decision: Accept (spotlight)