Quantum Adiabatic Optimization vs. Quantum Monte Carlo
This content delves into the comparison between Quantum Adiabatic Optimization and Quantum Monte Carlo methods in quantum computing, discussing their approaches, algorithms, potential applications, and theoretical possibilities. It explores the concepts of adiabatic theorem, simulated annealing, stoquastic Hamiltonians, and possibilities for adiabatic optimization, shedding light on the potential of quantum computing in optimization tasks.
Download Presentation
Please find below an Image/Link to download the presentation.
The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author.If you encounter any issues during the download, it is possible that the publisher has removed the file from their server.
You are allowed to download the files provided on this website for personal or commercial use, subject to the condition that they are used lawfully. All files are the property of their respective owners.
The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author.
E N D
Presentation Transcript
Quantum Adiabatic Optimization vs Quantum Monte Carlo Aram Harrow (MIT) joint work with Elizabeth Crosson (Caltech) arXiv:1 601.03030 to appear FOCS 201 6 MSR Faculty Summit 201 6.7.15
adiabatic algorithm [Farhi, Goldstone, Gutmann, Sipser 00] Problem: Given f:{0,1}n Z, minimize f(z). Approach: apply H(s) = (1-s) HX + s Hf equiv: H(s) = (1-s) (hypercube Laplacian) + s diag(f) Adiabatic theorem: Running for time poly(1 / mins[ 1(s)- 0(s)]) guarantees that we will end in the ground state of H1. Not discussed in this talk: noisy dynamics non-stoquastic Hamiltonians
QAO vs simulated annealing (SA) Farhi Goldstone Gutmann q-ph/0201013 Simulated annealing: Given state x repeatedly Choose random neighbor y With probability min(1, exp((f(x)-f(y))/T) replace x with y. Otherwise do nothing. Gradually lower T Problems where QAO is exponentially faster than SA z1 QMC succeeds (maybe) QMC succeeds energy z2 bush of implications z3 zn Hamming weight Which problem features make QAO outperform classical?
possibilities for adiabatic optimization pessimistic: There is a classical simulator that runs in time poly(time required by the adiabatic algorithm). Grover exhibits quadratic separation. evidence in favor: QMC (for stoquastic Hamiltonians). optimistic: Stoquastic adiabatic evolution is universal for quantum computing. Would imply collapse of PH & approx counting = exact counting . (Proof uses QMC + post-selection.) Nothing rules out fast adiabatic algorithms for factoring or 3SAT. intermediate: Exponential speedups (i.e. no simulation) but weaker than general-purpose QC. Oracle speedup for mostly adiabatic evolution (NSK 1 2) evidence in favor: QMC sometimes takes exponential time
quantum Monte Carlo (QMC) stoquastic Hamiltonians: Hxy 0 for x y. implies is entrywise nonnegative | 0 0| = lim is too. aside: H gapped p(z)= z| 0 2 has high conductance can estimate by sampling from
What is Hcl? e.g. 1-D transverse Ising model: H = i Zi Zi+1 - i Xi 2-D classical ferromagnetic Ising model Vertical bonds: ferromagnetic energy ln( L/ ), i.e. disagree prob /L. L n Horizontal bonds: = HD / L n
standard part of QMC 1. Use local moves (Glauber or Metropolis) to generate samples from (z1, ..., zL). Run-time/accuracy tradeoff unknown in general. 2. Use sampling-to-counting equivalence to estimate Z or O =tr[O e- H]/Z. Problem reduces to bounding mixing time (equiv. gap) of a classical Markov chain.
The Markov chain n 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 0 0 1 1 0 1 1 0 0 1 1 1 1 1 1 1 1 0 1 1 0 jump L ... z2 z1 1 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 weight(z) = exp(- (E(z1) + ... + E(zL)) / L) ( /L)# vertical jumps 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 rapidly mixing?
can QMC simulate adiabatic evolution? Only if gap 1/poly(n). since we need 1/gap for e- H |gs gs| and / # of imaginary time steps Only if we follow the adiabatic path. Otherwise would solve NP-complete problems. Technically useful as a warm start and to avoid unphysical/unlikely configurations. Even then there may be topological obstructions [Hastings-Freedman 13]
[see also J SIBMTN 1 603.01 293] the path measure random walk z1,...,zL on hypercube {0,1}n conditioned to return (zL+1 = z1) alternatively can use open boundary conditions. typically n total jumps Suppose that f(z) depends only on Hamming weight |z|. look only at Hamming weight: {0,1}n -> {0,1, ,n}. take n-> and {0,1, ,n} [0,1]. Brownian motion, or with closed B.C., Brownian bridge 1 with local Z fields -> Brownian motion with drift Ornstein-Uhlenbeckbridge dx(t) = ( -x(t)) dt + dB(t) = drift, = mean, = diffusion 0.9 imaginary time 0.8 0.7 0.6 0.5 0.4 0.3 0.2 0.1 Hamming weight 0 -8 -6 -4 -2 0 2 4 6
local times of Brownian motion Local time: Lx(t) = amount of time Brownian motion B(t) spends at point x. L vy s theorem: {L0(t): t 0} and {S(t): t 0} have the same distribution, where S(t) = sup0 s t B(s). In fact, (S-B, S) =d (|B|, L0) Additionally, S =d |B|.
local times of Brownian motion Local time: Lx(t) = amount of time Brownian motion B([0,t]) spends at point x. L vy s theorem: (S-B, S) =d (|B|, L0) Proof: consider discrete r walk: W(n) = X(1) + ... + X(n) with X(t) = 1. Let M(n) = max(W(0), ..., W(n)). M = # of times M-W remains at 0 d L0 figure adapted from Brownian Motion by M rters and Peres. Y(t) = M(t)-W(t) d |W(t)|
FGG 02 R 04 KC 15 BvD 16 JSIBMTN 16 Hamming weight + spike f(|z|) 1 width na exp(-na+(b-1)/2) height b n1 /2-a-b 0.5 height nb (1 ) 0 0 0.5 |z| width a 0 n
QMC and tunnelling spike (width na, height nb) 1 ST = normalized spike time d |N(0, na-1 /2)| imaginary time 0.9 0.8 0.7 0.6 proof using either L vy s thm or quantum-classical correspondence. 0.5 0.4 0.3 0.2 0.1 0 -8 -6 -4 -2 0 2 4 6 Hamming weight Feynman-Kac thm: Pr[path | spike] = exp(- ST nb) Pr[path | no spike] if a+b<1 /2 then typical paths don t notice the spike.
instantons on the cheap spike a<1 /2 2a+b<1 cf JSIBMTN 16 (width na, height nb) 1 imaginary time 0.9 0.8 0.7 steps to traverse spike n2a 0.6 0.5 0.4 min ST = n2a/ n 0.3 0.2 0.1 Feynman-Kac prob reduced by exp(-n2a+b-1) 0 -8 -6 -4 -2 0 2 4 6 Hamming weight 2a+b 1 is the theshold to cross the spike once.
canonical paths Given Markov chain P(x,y) with stationary distribution (x) and Q(x,y) = P(x,y) (y) = Q(y,x). TFAE: P has a 1/poly(n) gap between the top two eigenvalues conductance The conductance is 1/poly(n). = minS Q(S, Sc) / (S) (Sc) For any x,y there exists a path xy from x -> y routing (x) (y) units of flow such that each edge e has load poly(n) Q(e). ( canonical paths/flows ) Heuristics analyze some plausible cut. Proofs analyze all cuts or construct paths. canonical paths
open questions multidimensional / non-bit-symmetric tunneling. The a+b<1 /2 approach generalizes to whenever The unperturbed problem has good canonical paths. The perturbation is small relative to the gap. What about the 2a+b < 1 scenario? Quantum state geometry vs QMC geometry. Ground states of gapped Hamiltonian have high conductance. When does this imply that paths in QMC do too? Poly-time simulation of AQC or exponential separation?
1-d canonical path x1,1 x1,2 x1,3 x1,4 x1,5 x1,6 x2.1 x2,2 x2,3 x2,4 x2,5 x2,6 x3,1 x3,2 x3,3 x3,4 x3,5 x3,6 x4,1 x4,2 x4,3 x4,4 x4,5 x4,6 y1,1 y1,2 y1,3 y1,4 y1,5 y1,6 y2.1 y2,2 y2,3 y2,4 x2,5 x2,6 x3,1 x3,2 x3,3 x3,4 x3,5 x3,6 x4,1 x4,2 x4,3 x4,4 x4,5 x4,6 energy penalty: 2 new jumps 1 term from HD (L bonds each with weight 1 /L.) ... y1,1 y1,2 y1,3 y1,4 y1,5 y1,6 y2.1 y2,2 y2,3 y2,4 y2,5 y2,6 y3,1 y3,2 y3,3 y3,4 y3,5 y3,6 y4,1 y4,2 y4,3 y4,4 y4,5 y4,6 y1,1 x1,2 x1,3 x1,4 x1,5 x1,6 x2.1 x2,2 x2,3 x2,4 x2,5 x2,6 x3,1 x3,2 x3,3 x3,4 x3,5 x3,6 x4,1 x4,2 x4,3 x4,4 x4,5 x4,6 ...
QMC on the spike energy E (z) = |z| + n 1|z|=n/4 Hamming weight Quantum gap 1-n -1/2for <1/2 [Reichardt] or n -1/2for >1/2. We show QMC works when <1/2. relate to spikeless Hamiltonian E(z) = |z| (z1,1, ..., zn,L) = 0(z1,1, ..., z1,L) ... 0(zn,1, ..., zn,L) n decoupled 1-D Ising models. (z) = C (z) exp(-n [# |zi| = n/4] / L)
