Markov chain Monte Carlo algorithms have important applications in counting problems and in machine learning problems, settings that involve estimating quantities that are difficult to compute exactly. How much can quantum computers speed up classical Markov chain algorithms? In this work we consider the problem of speeding up simulated annealing algorithms, where the stationary distributions of the Markov chains are Gibbs distributions at temperatures specified according to an annealing schedule.
We construct a quantum algorithm that both adaptively constructs an annealing schedule and quantum samples at each temperature. Our adaptive annealing schedule roughly matches the length of the best classical adaptive annealing schedules and improves on nonadaptive temperature schedules by roughly a quadratic factor. Our dependence on the Markov chain gap matches other quantum algorithms and is quadratically better than what classical Markov chains achieve. Our algorithm is the first to combine both of these quadratic improvements. Like other quantum walk algorithms, it also improves on classical algorithms by producing “qsamples” instead of classical samples. This means preparing quantum states whose amplitudes are the square roots of the target probability distribution.
In constructing the annealing schedule we make use of amplitude estimation, and we introduce a method for making amplitude estimation nondestructive at almost no additional cost, a result that may have independent interest. Finally we demonstrate how this quantum simulated annealing algorithm can be applied to the problems of estimating partition functions and Bayesian inference.
more »
« less
Quantum eigenstates from classical Gibbs distributions
We discuss how the language of wave functions (state vectors) andassociated non-commuting Hermitian operators naturally emerges fromclassical mechanics by applying the inverse Wigner-Weyl transform to thephase space probability distribution and observables. In this language,the Schr"odinger equation follows from the Liouville equation, with \hbar ℏ now a free parameter. Classical stationary distributions can berepresented as sums over stationary states with discrete (quantized)energies, where these states directly correspond to quantum eigenstates.Interestingly, it is now classical mechanics which allows for apparentnegative probabilities to occupy eigenstates, dual to the negativeprobabilities in Wigner’s quasiprobability distribution. These negativeprobabilities are shown to disappear when allowing sufficientuncertainty in the classical distributions. We show that thiscorrespondence is particularly pronounced for canonical Gibbs ensembles,where classical eigenstates satisfy an integral eigenvalue equation thatreduces to the Schr"odinger equation in a saddle-pointapproximation controlled by the inverse temperature. We illustrate thiscorrespondence by showing that some paradigmatic examples such astunneling, band structures, Berry phases, Landau levels, levelstatistics and quantum eigenstates in chaotic potentials can bereproduced to a surprising precision from a classical Gibbs ensemble,without any reference to quantum mechanics and with all parameters(including \hbar ℏ )on the order of unity.
more »
« less
- Award ID(s):
- 1813499
- NSF-PAR ID:
- 10293278
- Date Published:
- Journal Name:
- SciPost Physics
- Volume:
- 10
- Issue:
- 1
- ISSN:
- 2542-4653
- Format(s):
- Medium: X
- Sponsoring Org:
- National Science Foundation
More Like this
-
-
We consider a toy model for emergence of chaos in a quantum many-body short-range-interacting system: two one-dimensional hard-core particles in a box, with a small mass defect as a perturbation over an integrable system, the latter represented by two equal mass particles.To that system, we apply a quantum generalization of Chirikov's criterion for the onset of chaos, i.e. the criterion of overlapping resonances.There, classical nonlinear resonances translate almost automatically to the quantum language. Quantum mechanics intervenes at a later stage: the resonances occupying less than one Hamiltonian eigenstate are excluded from the chaos criterion. Resonances appear as contiguous patches of low purity unperturbed eigenstates, separated by the groups of undestroyed states-the quantum analogues of the classical KAM tori.more » « less
-
We give two new quantum algorithms for solving semidefinite programs (SDPs) providing quantum speed-ups. We consider SDP instances with m constraint matrices, each of dimension n, rank at most r, and sparsity s. The first algorithm assumes an input model where one is given access to an oracle to the entries of the matrices at unit cost. We show that it has run time O~(s^2 (sqrt{m} epsilon^{-10} + sqrt{n} epsilon^{-12})), with epsilon the error of the solution. This gives an optimal dependence in terms of m, n and quadratic improvement over previous quantum algorithms (when m ~~ n). The second algorithm assumes a fully quantum input model in which the input matrices are given as quantum states. We show that its run time is O~(sqrt{m}+poly(r))*poly(log m,log n,B,epsilon^{-1}), with B an upper bound on the trace-norm of all input matrices. In particular the complexity depends only polylogarithmically in n and polynomially in r. We apply the second SDP solver to learn a good description of a quantum state with respect to a set of measurements: Given m measurements and a supply of copies of an unknown state rho with rank at most r, we show we can find in time sqrt{m}*poly(log m,log n,r,epsilon^{-1}) a description of the state as a quantum circuit preparing a density matrix which has the same expectation values as rho on the m measurements, up to error epsilon. The density matrix obtained is an approximation to the maximum entropy state consistent with the measurement data considered in Jaynes' principle from statistical mechanics. As in previous work, we obtain our algorithm by "quantizing" classical SDP solvers based on the matrix multiplicative weight update method. One of our main technical contributions is a quantum Gibbs state sampler for low-rank Hamiltonians, given quantum states encoding these Hamiltonians, with a poly-logarithmic dependence on its dimension, which is based on ideas developed in quantum principal component analysis. We also develop a "fast" quantum OR lemma with a quadratic improvement in gate complexity over the construction of Harrow et al. [Harrow et al., 2017]. We believe both techniques might be of independent interest.more » « less
-
Andrews, David L. ; Galvez, Enrique J. ; Rubinsztein-Dunlop, Halina (Ed.)The similarity between the 2D Helmholtz equation in elliptical coordinates and the Schr¨odinger equation for the simple mechanical pendulum inspires us to use light to mimic this quantum system. When optical beams are prepared in Mathieu modes, their intensity in the Fourier plane is proportional to the quantum mechanical probability for the pendulum. Previous works have produced a two-dimensional pendulum beam that oscillates as a function of time through the superpositions of Mathieu modes with phases proportional to pendulum energies. Here we create a three-dimensional pendulum wavepacket made of a superposition of Helical Mathieu-Gaussian modes, prepared in such a way that the components of the wave-vectors along the propagation direction are proportional to the pendulum energies. The resulting pattern oscillates or rotates as it propagates, in 3D, with the propagation coordinate playing the role of time. We obtained several different propagating beam patterns for the unbound-rotor and the bound-swinging pendulum cases. We measured the beam intensity as a function of the propagation distance. The integrated beam intensity along elliptical angles plays the role of quantum pendulum probabilities. Our measurements are in excellent agreement with numerical simulations.more » « less
-
null (Ed.)Path integral quantum Monte Carlo (PIMC) is a method for estimating thermal equilibrium properties of stoquastic quantum spin systems by sampling from a classical Gibbs distribution using Markov chain Monte Carlo. The PIMC method has been widely used to study the physics of materials and for simulated quantum annealing, but these successful applications are rarely accompanied by formal proofs that the Markov chains underlying PIMC rapidly converge to the desired equilibrium distribution.In this work we analyze the mixing time of PIMC for 1D stoquastic Hamiltonians, including disordered transverse Ising models (TIM) with long-range algebraically decaying interactions as well as disordered XY spin chains with nearest-neighbor interactions. By bounding the convergence time to the equilibrium distribution we rigorously justify the use of PIMC to approximate partition functions and expectations of observables for these models at inverse temperatures that scale at most logarithmically with the number of qubits.The mixing time analysis is based on the canonical paths method applied to the single-site Metropolis Markov chain for the Gibbs distribution of 2D classical spin models with couplings related to the interactions in the quantum Hamiltonian. Since the system has strongly nonisotropic couplings that grow with system size, it does not fall into the known cases where 2D classical spin models are known to mix rapidly.more » « less
- Free Publicly Accessible Full Text
-
Accepted Manuscript1.0
- Journal Article:
- https://doi.org/10.21468/SciPostPhys.10.1.014
