betaFeedback

WorksPhysics and Astronomy

Quantum Stochastic Gradient Descent in its continuous-time limit based on the Wigner formulation of Open Quantum Systems

Abstract

The main ideas behind a research plan to use the Wigner formulation as a bridge between classical and quantum probabilistic algorithms are presented, focusing on a particular case: the Quantum analog of Stochastic Gradient Descent in its continuous-time limit based on the Wigner formulation of Open Quantum Systems.

Introduction

The Wigner formalism of quantum mechanics presents a completely quantum mechanical phase space description, at the cost of losing the non-negativity of probability density functions from which observables will be calculated through integrals over space. The Wigner picture is very intuitive, as it presents itself as a quantum extension of typical classical statistical mechanics descriptions of probability distributions in phase space linked to Boltzmann equations and other families of kinetic equations as well. This Wigner quantum analog of a classical probability density function over phase space shows the similarities but also stresses the differences between the quantum and classical worlds (sometimes behaving as a false cognate if taken naively without care or physical intuition). This intuitive physical picture of the Wigner function renders itself helpful in the study of open quantum systems. Under the assumption of a Markovian noise, the density matrix picture for these quantum subsystems perturbed by their environment is given by the Lindblad master equation, which has the main drawback that the operators representing the noise effect coming from the environment are somehow obscure and hard to interpret in a physically intuitive way even though their math structure is well understood from the operator algebra point of view. On the other hand, the completely equivalent Wigner-Fokker-Planck equation (in continuous variables under the assumption that a phase space description is possible) is a more amenable and physically intuitive mathematical model. Under the assumption of continuous variables, the density matrix description of Markovian open quantum systems under a Lindblad master equation is completely equivalent to the phase-space formulation of open quantum systems via a Wigner-Fokker-Planck equation, since one can obtain the Wigner quasi-probability density function as the Fourier transform of the density matrix in convenient coordinates (and revert back from the Wigner function to the density matrix expressed in a position basis via an inverse Fourier transform). If one assumes that the potential is harmonic as in V=x2/2V=x^2/2, the Wigner-Fokker-Planck equation takes the form (taking units such that ℏ=1=m\hbar=1=m)

wt+p⋅wx−x⋅wp=∇⋅(D∇w)+γ∇p⋅(wp)(1)w_t+p\cdot w_x-x\cdot w_p=\nabla\cdot(D\nabla w)+\gamma\nabla_p\cdot(wp) \tag*{(1)}

where DD is the diffusion matrix representing part of the noise process introduced by the environment, and γ\gamma is a friction coefficient for the other term introducing noise. Though this benchmark problem is already very useful since a good amount of the potentials that physicists use to model phenomena are linear combinations of harmonic potentials, one could ask the question on how to use a Wigner picture for more general non-harmonic potentials. The Wigner-Fokker-Planck equation for an arbitrary potential VV is given by

wt+p⋅wx+Θ[V](w)=∇⋅(D∇w)+γ∇p⋅(wp),Θ[V](w)=−iℏ(2π)d∫R2dδV(x,η)w(x,p′)eiη⋅(p−p′) dp′ dη(2)\begin{aligned} w_t+p\cdot w_x+\Theta[V](w)&=\nabla\cdot(D\nabla w)+\gamma\nabla_p\cdot(wp),\\ \Theta[V](w)&=\frac{-i}{\hbar(2\pi)^d}\int_{\mathbb{R}^{2d}}\delta V(x,\eta)w(x,p')e^{i\eta\cdot(p-p')}\,dp'\,d\eta \tag*{(2)} \end{aligned}

where δV(x,η)=V(x+η2)−V(x−η2)\delta V(x,\eta)=V\left(x+\frac{\eta}{2}\right)-V\left(x-\frac{\eta}{2}\right). The right-hand-side terms have a clear interpretation as first a diffusion operator and then a friction term (that can be treated as a transport). In the left hand side, there is quantum transport over the phase space, with the pseudo-differential (integral) operator Θ[V](w)\Theta[V](w). This operator is the result of the Fourier-transform of the commutator [ρ^,V^][\hat{\rho},\hat{V}] in the Lindblad picture for density matrices ρ^\hat{\rho}. As we have mentioned above, the relation between the density matrix operator ρ^\hat{\rho} in its position representation and the Wigner function is given by a Fourier transform in convenient coordinates, given below,

w(x,p,t)=1ℏ(2π)d∫R2dρ(x+y,x−y)e−iy⋅p/ℏ dyρ(x,y)=⟨x+y∣ρ^∣x−y⟩.(3)\begin{aligned} w(x,p,t)&=\frac{1}{\hbar(2\pi)^d}\int_{\mathbb{R}^{2d}}\rho(x+y,x-y)e^{-iy\cdot p/\hbar}\,dy\\ \rho(x,y)&=\langle x+y|\hat{\rho}|x-y\rangle. \tag*{(3)} \end{aligned}

Stochastic Gradient Descent

We focus on the study of stochastic gradient descent by means of their continuous time limit (Su, Wibisono, Jordan, Shi). Following (Liu, Su, Li), if f:Rd→Rdf:\mathbb{R}^{d} \to\mathbb{R}^{d} is the objective function constructed with all data, and the Stochastic Gradient Descent (SGD) algorithm is given by

xk+1=xk−s∇~f(xk)x_{k+1}=x_k-s\widetilde{\nabla}f(x_k)

where ss is the learning rate and ∇~f\widetilde{\nabla}f is the estimated gradient (obtained from a mini-batch), then one can model SGD by the following iteration,

xk+1=xk−s∇f(xk)−sξkx_{k+1}=x_k-s\nabla f(x_k)-s\xi_k

where ξk\xi_k is a given noise that obeys a normal distribution, as in the so-called “unadjusted Langevin dynamics”. Taking the continuous time limit one obtains a stochastic differential equation (SDE) that includes the learning rate ss as a parameter, which models the discrete SGD algorithm. This SDE is

dx=−∇f(x)dt+sdW,dx=-\nabla f(x)dt+\sqrt{s}dW,

with WW a Brownian motion.

There is a direct analogy with open quantum systems via this SDE. In the case where the environment introduces Markovian noise, the SDE version of the Wigner-Fokker-Planck model of open quantum systems is given by an SDE modeling the evolution of the Wigner quasi-distribution w(x,p,t)w(x,p,t). Taking units such that ℏ=1=m\hbar=1=m, if we consider α\alpha the quantum transport over the subsystem, σ\sigma the standard deviation related to the noise, 2σdW=2DdtN(0,1)2\sigma dW=2Ddt\mathcal{N}(0,1) where N(0,1)\mathcal{N}(0,1) is a normal distribution with mean zero and variance 1, and DD the diffusion matrix representing part of the noise introduced by the environment. The other part of the noise is given by a friction term which is included in the quantum transport. Namely, the friction term is γ∇p⋅(wp)\gamma\nabla_p\cdot(wp), where γ\gamma is the friction coefficient and pp is the momentum variable. The full transport term (including both pure quantum transport and the friction term representing noise but added to the transport term) is

α(x,p,t)=∇⋅(w(p,−x−γp)).\alpha(x,p,t)=\nabla\cdot(w(p,-x-\gamma p)).

From a particle viewpoint, where z=(x,p)z=(x,p) represents the location in phase space of particle points to be sampled from a Wigner quasi-PDF, following D’Ariano et al., one can represent the motion of phase-space points according to the following model,

dzi=Q[zi(t)]dt+E[zi(t)]dz_i=Q[z_i(t)]dt+E[z_i(t)]

with i∈{1,N}i\in\{1,N\} an index representing the studied particle from the sample, Q[z(t)]=(p,−x−γp)Q[z(t)]=(p,-x-\gamma p) being the quantum transport, and EE being a zero average Gaussian random variable, whose variance is DdtDdt. The closest expression as a stochastic gradient for our SDE related to open quantum systems is via the Hamiltonian+gradient flow as in

dzi=[J∇iH(z)−∇i(γp2/2)]dt+E[zi(t)],i∈{1,⋯ ,N}dz_i = [J\nabla_i H(z) - \nabla_i(\gamma p^2/2)]dt + E[z_i(t)], \quad i \in\{1,\cdots,N\}

where part of the flow is indeed gradient (the friction one) but the other part is related to a Hamiltonian flow where the gradient is multiplied by the symplectic matrix JJ. Our problem has, regarding transport, both a symplectic flow structure (due to the Hamiltonian) and a gradient flow structure too (due to the friction term), which combined with the diffusion due to the environment noise, has a dynamics almost similar to the SGD counterpart (becoming more similar to a gradient flow as the friction term dominates in the limit γ→∞\gamma\to\infty). To fully express our problem then, we have then that

d(xi,pi)=[J∇i(p2+x22)−γ∇i(p22)]dt+E[xi(t),pi(t)],i∈{1,⋯ ,N}d(x_i,p_i) = [J\nabla_i\left(\frac{p^2+x^2}{2}\right) - \gamma\nabla_i\left(\frac{p^2}{2}\right)]dt + E[x_i(t),p_i(t)], \quad i \in\{1,\cdots,N\}

Our point: the Hamiltonian flow (for the case of the harmonic oscillator dynamics) plus a dominant gradient-flow (in the case where the friction dominates by making the damping coefficient γ→∞\gamma\to\infty) and diffusion terms (the last two due to subsystem-environment interaction) is almost equivalent to the continuous limit of Stochastic Gradient Descent (when friction dominates Hamiltonian transport), and therefore their behaviors (and performances) are similar (the similarity becoming stronger as friction dominates more the Hamiltonian transport). Since the numerics of SGD is similar to the Physics of open quantum systems, we would expect variations of SGD to a good numerical model available for mimicking quantum problems where the hamiltonian transport is subjected to environment noise represented in both transport due to friction and diffusion connected to random walks happening continuously in time.

Conjecture 1. For minimization problems that can be formulated as quantum transport perturbed by Markovian noise, then SGD must a good candidate for a numerical method available, since it’s reproducing exactly the problem it’s trying to solve.

Advantages of an SGD formulation as an open quantum system rather than a closed quantum dynamics

A closed quantum system description has the drawback that their evolution is unitary, so a Quantum Tunneling Walk (QTW) will not formally converge. This is not the behavior observed for SGD, whose dynamics is quite similar to an open quantum system: gradient-related transport plus noise, and convergence to a steady state solution (as proven for the benchmark problem of a harmonic potential). So an open quantum system dynamics does have truly a mixing time as exponential decay towards the steady state solution, for example in the case of a harmonic potential, where it has been proved by Sparber et al [6].

Wigner-Fokker-Planck: harmonic case in arbitrary dimension, decay rate, mixing time

In classical machine learning, it is known [1],[2],[3],[8] that the continuous-time limit of gradient descent methods such as the Stochastic Gradient Descent (SGD) algorithm can be modeled by differential equations. For SGD, whose Stochastic Differential Equation (SDE) approximation is

dx=−∇f(x)dt+sdW,dx=-\nabla f(x)dt+\sqrt{s}dW,

with WW a standard Brownian motion, the Fokker–Planck equation for the SGD pdf ρSGD\rho_{\mathrm{SGD}},

∂tρSGD=∇⋅(ρSGD∇f)+s2∇2ρSGD,\partial_t\rho_{\mathrm{SGD}}=\nabla\cdot(\rho_{\mathrm{SGD}}\nabla f)+\frac{s}{2}\nabla^2\rho_{\mathrm{SGD}},

is the respective continuous-time limit equivalent [14],[12],[13].

Quantum extensions of SGD have been proposed attempting to obtain a quantum advantage. Work in [14] explores quantum speedups for nonconvex optimization problems introducing a quantum tunneling walk (QTW) algorithm for nonconvex problems where local minima are "approximately global". This is obtained by analogy between classical Fokker-Planck and the Schroedinger equation as the quantum equivalent under certain periodicity conditions. They report quantum speedup over classical stochastic gradient descents (SGD) when the barriers between different local minima are high but thin and flat minima.

However, it is physically clear that the quantum version of the equation representing the SDE version of SGD should be Wigner-Fokker-Planck, which for the case of a harmonic potential V(x)=ω02x2/2V(x)=\omega_0^2x^2/2 takes the form

∂tw=−∇⋅(wJ∇H)+γ∇p⋅(w∇pp22)+∇⋅(D∇w),J=(0Id−Id0),(4)\partial_t w=-\nabla\cdot(wJ\nabla H)+\gamma\nabla_p\cdot\left(w\nabla_p\frac{p^2}{2}\right)+\nabla\cdot(D\nabla w),\qquad J=\begin{pmatrix}0&I_d\\-I_d&0\end{pmatrix}, \tag*{(4)}

with the Hamiltonian H=T(p)+V(x)=p22m+ω02x22H=T(p)+V(x)=\frac{p^2}{2m}+\frac{\omega_0^2x^2}{2} representing the (kinetic plus potential) energy, JJ the symplectic matrix, dd the dimension of the physical space, the diffusion matrix DD and friction coefficient γ\gamma, because the open quantum system model represented above is the quantum version of the system studied by the classical Fokker-Planck representing an SGD, particularly when the gradient term associated to friction dominates the Hamiltonian transport. Wigner-Fokker-Planck is completely equivalent to the dynamics of a noisy quantum transport system whose SDE form is

d(x,p)=(J∇H−∇pγp22)dt+E(D),(5)d(x,p)=\left(J\nabla H-\nabla_p\frac{\gamma p^2}{2}\right)dt+E(D), \tag*{(5)}

where xx is the position and pp the momentum in quantum phase space, and EE is a random variable sampled from a Gaussian distribution with covariance matrix 2Ddt2Ddt (dt≈Δtdt\approx\Delta t discretized). We illustrate in Figure 1 below the dynamics of the Wigner-Fokker-Planck model for an open quantum system as the balance between quantum transport (made of both a Hamiltonian flow and gradient transport) and diffusive noise.

Image not extracted

Figure 1. A Wigner distribution is shown, where quantum transport & diffusion mechanisms over a point are highlighted. This process is the continuous quantum limit of Stochastic Gradient Descent.

There are previous studies of the harmonic benchmark for WFP [6], whose results can be used. In particular, Sparber et al. prove in [6] the existence of a steady-state solution w∞(x,p)w_{\infty}(x,p) for this benchmark problem, providing its analytical form, and it also gives the exponential decay rate of any well-posed initial condition towards this analytical steady state for the harmonic case. Namely, [6] finds that

∥w(t,⋅)−w∞∥p≤Cexp⁡(−κt),C>0, t>0,\lVert w(t,\cdot)-w_{\infty}\rVert_p \le C \exp(-\kappa t), \qquad C>0,\ t>0,

with 1≤p≤21 \le p \le2 depending on the relative entropy (logarithmic or quadratic), and that the respective decay rate is the smallest eigenvalue of the Hessian of the quadratic polynomial AA such that w∞∝exp⁡(−A(x,p))w_{\infty} \propto\exp(-A(x,p)) (the Wigner steady state for this problem is a Gaussian state), so that

Hess⁡A≥κI2d,(Hess⁡A)ij=∂ij2A,i,j=1,⋯ ,2d.\operatorname{Hess} A \ge\kappa I_{2d}, \qquad(\operatorname{Hess} A)_{ij} = \partial_{ij}^{2} A,\quad i,j=1,\cdots,2d.

This exponential decay rate is advantageous for interpreting WFP as a quantum extension of SGD because it will provide the respective mixing time of a quantum SGD algorithm based on the WFP equation. Most importantly, nothing precludes interpreting WFP not only on physical dimensions such that d=1,2,3d=1,2,3, but actually for d≫1d \gg1 as is typically the case for Machine Learning, in which the problem is of high dimensionality given the amount of data for the problem. Our result is that, for WFP in a high dimension d≫1d \gg1, the decay rate providing the mixing time for the related quantum SGD algorithm in the benchmark case of a harmonic potential is simply the smallest of only 2 possible roots (with high algebraic multiplicity) of the characteristic polynomial, which although of degree 2d2d, as we mentioned has only 2 possibly different roots of multiplicity dd.

Our preliminary result indicates that the decay rate towards the steady state in WFP (and therefore the mixing time in its quantum version of SGD) does not depend on the dimension dd of the problem for the harmonic potential benchmark problem, as it should be since this doesn’t happen either in the classical SGD optimization for a quadratic function (such as the parabola representing a harmonic potential). Namely, the decay rate does not slow down as the quantum space dimension d≫1d \gg1 increases for this benchmark case of a harmonic potential.

Preliminary Calculations

We show the preliminary calculations for high dimensions d≫1d \gg1. We consider x∈Rdx \in\mathbb{R}^{d}, p∈Rdp \in\mathbb{R}^{d}, so (x,p)∈R2d(x,p) \in\mathbb{R}^{2d}, and therefore the diffusion matrix is the block matrix

References

  1. [1]Su, W., Boyd, S., and Candes, E. J. A differential equation for modeling nesterov’s accelerated gradient method: theory and insights. J. Mach. Learn. Res. 17, 1 (jan 2016), 5312–5354.
  2. [2]Wibisono, A., Wilson, A. C., and Jordan, M. I. A variational perspective on accelerated methods in optimization. Proceedings of the National Academy of Sciences 113, 47 (2016), E7351–E7358.DOI
  3. [3]JORDAN, M. I. DYNAMICAL, SYMPLECTIC AND STOCHASTIC PERSPECTIVES ON GRADIENT-BASED OPTIMIZATION. World Scientific, 2018, pp. 523–549.DOI
  4. [6]Sparber, C., Carrillo, J., Dolbeault, J., and Markowich, P. On the long-time behavior of the quantum fokker-planck equation. Monatshefte fur Mathematik 141, 3 (Mar. 2004), 237–257.
  5. [8]Shi, B., Du, S. S., Jordan, M. I., and Su, W. J. Understanding the acceleration phenomenon via high-resolution differential equations, 2018.
  6. [12]Bhatnagar, S., Prasad, H., Prashanth, L. (2013). Stochastic Approximation Algorithms. In: Stochastic Recursive Algorithms for Optimization. Lecture Notes in Control and Information Sciences, vol 434. Springer, London. https://doi.org/10.1007/978-1-4471-4285-0_3
  7. [13]On the Validity of Modeling SGD with Stochastic Differential Equations (SDEs) Zhiyuan Li, Sadhika Malladi, Sanjeev Arora. NeurIPS 2021 Posterarxiv.org/abs/2102.12470
  8. [14]On Quantum Speedups for Nonconvex Optimization via Quantum Tunneling Walks. Yizhou Liu, Weijie J. Su, and Tongyang Li. Quantum 7, 1030 (2023).DOI

Paper details

vlnc:W_det8k558
Version
v1 · latest
Published
Fresh — added to the Hub within the last 30 days
Added
License
CC BY 4.0
Usage

views · 0

downloads · 0

A view counts once per browser per day, a download each time the PDF is requested.

  • Physics and Astronomy

Not recorded for this paper

View statement
Looking for related papers…
Contents