Canadian Summer School on Quantum Information (CSSQI) (10th : 2010)

Quantum Metropolis sampling: an algorithm to simulate thermal systems with a quantum computer Poulin, David Jul 24, 2010

Your browser doesn't seem to have a PDF viewer, please download the PDF to view this item.

Item Metadata

Download

Media
59370-PoulinUBC2010.pdf [ 2.71MB ]
59370-WS Jul 24 Poulin.mp4 [ 143.07MB ]
Metadata
JSON: 59370-1.0103161.json
JSON-LD: 59370-1.0103161-ld.json
RDF/XML (Pretty): 59370-1.0103161-rdf.xml
RDF/JSON: 59370-1.0103161-rdf.json
Turtle: 59370-1.0103161-turtle.txt
N-Triples: 59370-1.0103161-rdf-ntriples.txt
Original Record: 59370-1.0103161-source.json
Full Text
59370-1.0103161-fulltext.txt
Citation
59370-1.0103161.ris

Full Text

Quantum Metropolis Sampling David Poulin Département de Physique Université de Sherbrooke Joint work with: K. Temme, T. Osborne, K. Vollbrecht, and F. Verstraete  Workshop on quantum Algorithms, Computational Models, and Foundations of Quantum Mechanics University of British Columbia, Vancouver July 2010  David Poulin (Sherbrooke)  Quantum Metropolis  QAMF@UBC’10  1 / 27  Next’s year Canadian Quantum Information Summer School and Student Conference June 6th to 17th 2011 Jouvence, Parc National du Mont Orford (near Sherbrooke Qc)  David Poulin (Sherbrooke)  Quantum Metropolis  QAMF@UBC’10  2 / 27  Motivation  Outline  1  Motivation  2  Quantum simulators  3  Metropolis algorithm  4  Quantum Metropolis  David Poulin (Sherbrooke)  Quantum Metropolis  QAMF@UBC’10  3 / 27  Motivation  What are computers used for?  From talk by F. Verstraete, from a talk by S. Aaronson, from a talk by A. Aspuru-Guzik David Poulin (Sherbrooke)  Quantum Metropolis  QAMF@UBC’10  4 / 27  Motivation  What are they computing?  Inputs A local Hamiltonian H =  k  hk :  hk = O(1). hk acts on a few particles, i.e. hk = I ⊗ I ⊗ A ⊗ I ⊗ I ⊗ B ⊗ I ⊗ I.  An efficiently specifiable state ρ, e.g.  The Gibbs state ρG (β) = Z1 e−βH . The ground state of H, i.e. ρG (∞). Physically relevance: thermal equilibrium at temperature  1 β.  Output X (t)Y = Tr{Xe−iHt YeiHt ρG (β)} for one-body operators X and Y .  David Poulin (Sherbrooke)  Quantum Metropolis  QAMF@UBC’10  5 / 27  Motivation  What are they computing?  Inputs A local Hamiltonian H =  k  hk :  hk = O(1). hk acts on a few particles, i.e. hk = I ⊗ I ⊗ A ⊗ I ⊗ I ⊗ B ⊗ I ⊗ I.  An efficiently specifiable state ρ, e.g.  The Gibbs state ρG (β) = Z1 e−βH . The ground state of H, i.e. ρG (∞). Physically relevance: thermal equilibrium at temperature  1 β.  Output X (t)Y = Tr{Xe−iHt YeiHt ρG (β)} for one-body operators X and Y .  David Poulin (Sherbrooke)  Quantum Metropolis  QAMF@UBC’10  5 / 27  Motivation  What are they computing?  Inputs A local Hamiltonian H =  k  hk :  hk = O(1). hk acts on a few particles, i.e. hk = I ⊗ I ⊗ A ⊗ I ⊗ I ⊗ B ⊗ I ⊗ I.  An efficiently specifiable state ρ, e.g.  The Gibbs state ρG (β) = Z1 e−βH . The ground state of H, i.e. ρG (∞). Physically relevance: thermal equilibrium at temperature  1 β.  Output X (t)Y = Tr{Xe−iHt YeiHt ρG (β)} for one-body operators X and Y .  David Poulin (Sherbrooke)  Quantum Metropolis  QAMF@UBC’10  5 / 27  Motivation  What are they computing?  Inputs A local Hamiltonian H =  k  hk :  hk = O(1). hk acts on a few particles, i.e. hk = I ⊗ I ⊗ A ⊗ I ⊗ I ⊗ B ⊗ I ⊗ I.  An efficiently specifiable state ρ, e.g.  The Gibbs state ρG (β) = Z1 e−βH . The ground state of H, i.e. ρG (∞). Physically relevance: thermal equilibrium at temperature  1 β.  Output X (t)Y = Tr{Xe−iHt YeiHt ρG (β)} for one-body operators X and Y .  David Poulin (Sherbrooke)  Quantum Metropolis  QAMF@UBC’10  5 / 27  Motivation  Why is this complicated?  Tr{Xe−iHt YeiHt ρ}  Matrix multiplication in vector space H of dimension exponential with the number of particles. ρ is not specified in a useful format: E.g., ρ ∝ e−βH . Computing its matrix elements ρij is hard.  David Poulin (Sherbrooke)  Quantum Metropolis  QAMF@UBC’10  6 / 27  Motivation  Why is this complicated?  Tr{Xe−iHt YeiHt ρ}  Matrix multiplication in vector space H of dimension exponential with the number of particles. ρ is not specified in a useful format: E.g., ρ ∝ e−βH . Computing its matrix elements ρij is hard.  David Poulin (Sherbrooke)  Quantum Metropolis  QAMF@UBC’10  6 / 27  Motivation  Why is this complicated?  Tr{Xe−iHt YeiHt ρ}  Matrix multiplication in vector space H of dimension exponential with the number of particles. ρ is not specified in a useful format: E.g., ρ ∝ e−βH . Computing its matrix elements ρij is hard.  David Poulin (Sherbrooke)  Quantum Metropolis  QAMF@UBC’10  6 / 27  Motivation  Some partial solutions Weakly interacting particles: H = H0 + V . Perturbation theory Hartree-Fock Density functional theory etc.  Weakly entangled particles/one dimension Renormalization methods (NRG, DMRG, MPS, PEPES). Other variational methods (Laughlin state, Moore-Read).  Unfrustrated bosonic systems Quantum Monte Carlo e−βH ∼ (I − H) ⊗ (I − H) ⊗ . . .  The interesting physics appears to lie outside the scope covered by these methods. Standard model for elementary particle masses Hubbard model for superconductivity Coulomb force for molecular binding energies David Poulin (Sherbrooke)  Quantum Metropolis  QAMF@UBC’10  7 / 27  Motivation  Some partial solutions Weakly interacting particles: H = H0 + V . Perturbation theory Hartree-Fock Density functional theory etc.  Weakly entangled particles/one dimension Renormalization methods (NRG, DMRG, MPS, PEPES). Other variational methods (Laughlin state, Moore-Read).  Unfrustrated bosonic systems Quantum Monte Carlo e−βH ∼ (I − H) ⊗ (I − H) ⊗ . . .  The interesting physics appears to lie outside the scope covered by these methods. Standard model for elementary particle masses Hubbard model for superconductivity Coulomb force for molecular binding energies David Poulin (Sherbrooke)  Quantum Metropolis  QAMF@UBC’10  7 / 27  Motivation  Some partial solutions Weakly interacting particles: H = H0 + V . Perturbation theory Hartree-Fock Density functional theory etc.  Weakly entangled particles/one dimension Renormalization methods (NRG, DMRG, MPS, PEPES). Other variational methods (Laughlin state, Moore-Read).  Unfrustrated bosonic systems Quantum Monte Carlo e−βH ∼ (I − H) ⊗ (I − H) ⊗ . . .  The interesting physics appears to lie outside the scope covered by these methods. Standard model for elementary particle masses Hubbard model for superconductivity Coulomb force for molecular binding energies David Poulin (Sherbrooke)  Quantum Metropolis  QAMF@UBC’10  7 / 27  Motivation  Some partial solutions Weakly interacting particles: H = H0 + V . Perturbation theory Hartree-Fock Density functional theory etc.  Weakly entangled particles/one dimension Renormalization methods (NRG, DMRG, MPS, PEPES). Other variational methods (Laughlin state, Moore-Read).  Unfrustrated bosonic systems Quantum Monte Carlo e−βH ∼ (I − H) ⊗ (I − H) ⊗ . . .  The interesting physics appears to lie outside the scope covered by these methods. Standard model for elementary particle masses Hubbard model for superconductivity Coulomb force for molecular binding energies David Poulin (Sherbrooke)  Quantum Metropolis  QAMF@UBC’10  7 / 27  Quantum simulators  Outline  1  Motivation  2  Quantum simulators  3  Metropolis algorithm  4  Quantum Metropolis  David Poulin (Sherbrooke)  Quantum Metropolis  QAMF@UBC’10  8 / 27  Quantum simulators  Original motivation  David Poulin (Sherbrooke)  Quantum Metropolis  QAMF@UBC’10  9 / 27  Quantum simulators  Original motivation  David Poulin (Sherbrooke)  Quantum Metropolis  QAMF@UBC’10  9 / 27  Quantum simulators  Solving the dynamics Lloyd’s idea, ’96 N  exp(−it  exp(−ihk /N)  hk ) = k  k  + O(  1 ) N2  So we can integrate Schrödinger’s equation, solve ρ˙ = −i[H, ρ]. How do we specify the initial conditions ρG (β)? David Poulin (Sherbrooke)  Quantum Metropolis  QAMF@UBC’10  10 / 27  Quantum simulators  Solving the dynamics Lloyd’s idea, ’96 N  exp(−it  exp(−ihk /N)  hk ) = k  k  + O(  1 ) N2  A  e-iHt =  U # of gates = poly(n,t,ε-1)  So we can integrate Schrödinger’s equation, solve ρ˙ = −i[H, ρ]. How do we specify the initial conditions ρG (β)? David Poulin (Sherbrooke)  Quantum Metropolis  QAMF@UBC’10  10 / 27  Quantum simulators  Solving the dynamics Lloyd’s idea, ’96 N  exp(−it  exp(−ihk /N)  hk ) = k  k  + O(  1 ) N2  A  e-iHt =  U # of gates = poly(n,t,ε-1)  So we can integrate Schrödinger’s equation, solve ρ˙ = −i[H, ρ]. How do we specify the initial conditions ρG (β)? David Poulin (Sherbrooke)  Quantum Metropolis  QAMF@UBC’10  10 / 27  Quantum simulators  Solving the dynamics Lloyd’s idea, ’96 N  exp(−it  exp(−ihk /N)  hk ) = k  k  + O(  1 ) N2  A  e-iHt =  U # of gates = poly(n,t,ε-1)  So we can integrate Schrödinger’s equation, solve ρ˙ = −i[H, ρ]. How do we specify the initial conditions ρG (β)? David Poulin (Sherbrooke)  Quantum Metropolis  QAMF@UBC’10  10 / 27  Quantum simulators  Approaches to ρG (β)  Simulate evolution of "system+bath" and Metropolis-like. Conditions for thermalization not reproduced (poorly understood).  Use adiabatic evolution H(t) = (1 − t/T )H0 + t/THhard Must avoid quantum phase transition. Limited to ground state.  Use Grover-like algorithm to search ground state. Slow. David Poulin (Sherbrooke)  Quantum Metropolis  QAMF@UBC’10  11 / 27  Quantum simulators  Approaches to ρG (β)  Simulate evolution of "system+bath" and Metropolis-like. Conditions for thermalization not reproduced (poorly understood).  Use adiabatic evolution H(t) = (1 − t/T )H0 + t/THhard Must avoid quantum phase transition. Limited to ground state.  Use Grover-like algorithm to search ground state. Slow. David Poulin (Sherbrooke)  Quantum Metropolis  QAMF@UBC’10  11 / 27  Quantum simulators  Approaches to ρG (β)  Simulate evolution of "system+bath" and Metropolis-like. Conditions for thermalization not reproduced (poorly understood).  Use adiabatic evolution H(t) = (1 − t/T )H0 + t/THhard Must avoid quantum phase transition. Limited to ground state.  Use Grover-like algorithm to search ground state. Slow. David Poulin (Sherbrooke)  Quantum Metropolis  QAMF@UBC’10  11 / 27  Quantum simulators  Approaches to ρG (β)  Simulate evolution of "system+bath" and Metropolis-like. Conditions for thermalization not reproduced (poorly understood).  Use adiabatic evolution H(t) = (1 − t/T )H0 + t/THhard Must avoid quantum phase transition. Limited to ground state.  Use Grover-like algorithm to search ground state. Slow. David Poulin (Sherbrooke)  Quantum Metropolis  QAMF@UBC’10  11 / 27  Quantum simulators  Approaches to ρG (β)  Simulate evolution of "system+bath" and Metropolis-like. Conditions for thermalization not reproduced (poorly understood).  Use adiabatic evolution H(t) = (1 − t/T )H0 + t/THhard Must avoid quantum phase transition. Limited to ground state.  Use Grover-like algorithm to search ground state. Slow. David Poulin (Sherbrooke)  Quantum Metropolis  QAMF@UBC’10  11 / 27  Quantum simulators  Approaches to ρG (β)  Simulate evolution of "system+bath" and Metropolis-like. Conditions for thermalization not reproduced (poorly understood).  Use adiabatic evolution H(t) = (1 − t/T )H0 + t/THhard Must avoid quantum phase transition. Limited to ground state.  Use Grover-like algorithm to search ground state. Slow. David Poulin (Sherbrooke)  Quantum Metropolis  QAMF@UBC’10  11 / 27  Metropolis algorithm  Outline  1  Motivation  2  Quantum simulators  3  Metropolis algorithm  4  Quantum Metropolis  David Poulin (Sherbrooke)  Quantum Metropolis  QAMF@UBC’10  12 / 27  Metropolis algorithm  How is this problem solved for classical systems? 1 −βE(x) Ze  Use Markov Chain Monte Carlo to sample from pG (x) =  The Metropolis algorithm 1  Start from a random configuration x of energy E(x).  2  Generate a new configuration y by changing x at a few locations. Accept / reject new configuration with wxy = min{1, eβ(E(x)−E(y )) }:  3  Accept x ← y with probability wxy . Reject x ← x with probability 1 − wxy .  4  Return to 2.  David Poulin (Sherbrooke)  Quantum Metropolis  QAMF@UBC’10  13 / 27  Metropolis algorithm  How is this problem solved for classical systems? 1 −βE(x) Ze  Use Markov Chain Monte Carlo to sample from pG (x) =  The Metropolis algorithm 1  Start from a random configuration x of energy E(x).  2  Generate a new configuration y by changing x at a few locations. Accept / reject new configuration with wxy = min{1, eβ(E(x)−E(y )) }:  3  Accept x ← y with probability wxy . Reject x ← x with probability 1 − wxy .  4  Return to 2.  David Poulin (Sherbrooke)  Quantum Metropolis  QAMF@UBC’10  13 / 27  Metropolis algorithm  How is this problem solved for classical systems? 1 −βE(x) Ze  Use Markov Chain Monte Carlo to sample from pG (x) =  The Metropolis algorithm 1  Start from a random configuration x of energy E(x).  2  Generate a new configuration y by changing x at a few locations. Accept / reject new configuration with wxy = min{1, eβ(E(x)−E(y )) }:  3  Accept x ← y with probability wxy . Reject x ← x with probability 1 − wxy .  4  Return to 2.  David Poulin (Sherbrooke)  Quantum Metropolis  QAMF@UBC’10  13 / 27  Metropolis algorithm  How is this problem solved for classical systems? 1 −βE(x) Ze  Use Markov Chain Monte Carlo to sample from pG (x) =  The Metropolis algorithm 1  Start from a random configuration x of energy E(x).  2  Generate a new configuration y by changing x at a few locations. Accept / reject new configuration with wxy = min{1, eβ(E(x)−E(y )) }:  3  Accept x ← y with probability wxy . Reject x ← x with probability 1 − wxy .  4  Return to 2.  David Poulin (Sherbrooke)  Quantum Metropolis  QAMF@UBC’10  13 / 27  Metropolis algorithm  How is this problem solved for classical systems? 1 −βE(x) Ze  Use Markov Chain Monte Carlo to sample from pG (x) =  The Metropolis algorithm 1  Start from a random configuration x of energy E(x).  2  Generate a new configuration y by changing x at a few locations. Accept / reject new configuration with wxy = min{1, eβ(E(x)−E(y )) }:  3  Accept x ← y with probability wxy . Reject x ← x with probability 1 − wxy .  4  Return to 2.  David Poulin (Sherbrooke)  Quantum Metropolis  QAMF@UBC’10  13 / 27  Metropolis algorithm  How is this problem solved for classical systems? 1 −βE(x) Ze  Use Markov Chain Monte Carlo to sample from pG (x) =  The Metropolis algorithm 1  Start from a random configuration x of energy E(x).  2  Generate a new configuration y by changing x at a few locations. Accept / reject new configuration with wxy = min{1, eβ(E(x)−E(y )) }:  3  Accept x ← y with probability wxy . Reject x ← x with probability 1 − wxy .  4  Return to 2.  David Poulin (Sherbrooke)  Quantum Metropolis  QAMF@UBC’10  13 / 27  Metropolis algorithm  How is this problem solved for classical systems? 1 −βE(x) Ze  Use Markov Chain Monte Carlo to sample from pG (x) =  The Metropolis algorithm 1  Start from a random configuration x of energy E(x).  2  Generate a new configuration y by changing x at a few locations. Accept / reject new configuration with wxy = min{1, eβ(E(x)−E(y )) }:  3  Accept x ← y with probability wxy . Reject x ← x with probability 1 − wxy .  4  Return to 2.  David Poulin (Sherbrooke)  Quantum Metropolis  QAMF@UBC’10  13 / 27  Metropolis algorithm  Markov chain P(x1 |x0 )  P(xn |xn−1 )  P(x2 |x1 )  x0 −−−−−→ x1 −−−−−→ x2 . . . xn−1 −−−−−−→ xn Detailed balance condition The distribution pG (x) =  1 −βH(x) Ze  obeys the condition  pG (x)P(y |x) = pG (y )P(x|y ) so it is the fixed point of the Markov chain P(x|y ). Convergence rate The convergence rate is given by the inverse spectral gap ∆−1 of the stochastic matrix P(x|y ): n ∈ O(∆−1 ). ∆−1 appears to scale polynomially for problems of interest. David Poulin (Sherbrooke)  Quantum Metropolis  QAMF@UBC’10  14 / 27  Metropolis algorithm  Markov chain P(x1 |x0 )  P(xn |xn−1 )  P(x2 |x1 )  x0 −−−−−→ x1 −−−−−→ x2 . . . xn−1 −−−−−−→ xn Detailed balance condition The distribution pG (x) =  1 −βH(x) Ze  obeys the condition  pG (x)P(y |x) = pG (y )P(x|y ) so it is the fixed point of the Markov chain P(x|y ). Convergence rate The convergence rate is given by the inverse spectral gap ∆−1 of the stochastic matrix P(x|y ): n ∈ O(∆−1 ). ∆−1 appears to scale polynomially for problems of interest. David Poulin (Sherbrooke)  Quantum Metropolis  QAMF@UBC’10  14 / 27  Metropolis algorithm  Markov chain P(x1 |x0 )  P(xn |xn−1 )  P(x2 |x1 )  x0 −−−−−→ x1 −−−−−→ x2 . . . xn−1 −−−−−−→ xn ∼  1 −βH(xn ) e Z  Detailed balance condition The distribution pG (x) =  1 −βH(x) Ze  obeys the condition  pG (x)P(y |x) = pG (y )P(x|y ) so it is the fixed point of the Markov chain P(x|y ). Convergence rate The convergence rate is given by the inverse spectral gap ∆−1 of the stochastic matrix P(x|y ): n ∈ O(∆−1 ). ∆−1 appears to scale polynomially for problems of interest. David Poulin (Sherbrooke)  Quantum Metropolis  QAMF@UBC’10  14 / 27  Metropolis algorithm  Markov chain P(x1 |x0 )  P(xn |xn−1 )  P(x2 |x1 )  x0 −−−−−→ x1 −−−−−→ x2 . . . xn−1 −−−−−−→ xn ∼  1 −βH(xn ) e Z  Detailed balance condition The distribution pG (x) =  1 −βH(x) Ze  obeys the condition  pG (x)P(y |x) = pG (y )P(x|y ) so it is the fixed point of the Markov chain P(x|y ). Convergence rate The convergence rate is given by the inverse spectral gap ∆−1 of the stochastic matrix P(x|y ): n ∈ O(∆−1 ). ∆−1 appears to scale polynomially for problems of interest. David Poulin (Sherbrooke)  Quantum Metropolis  QAMF@UBC’10  14 / 27  Metropolis algorithm  Markov chain P(x1 |x0 )  P(xn |xn−1 )  P(x2 |x1 )  x0 −−−−−→ x1 −−−−−→ x2 . . . xn−1 −−−−−−→ xn ∼  1 −βH(xn ) e Z  Detailed balance condition The distribution pG (x) =  1 −βH(x) Ze  obeys the condition  pG (x)P(y |x) = pG (y )P(x|y ) so it is the fixed point of the Markov chain P(x|y ). Convergence rate The convergence rate is given by the inverse spectral gap ∆−1 of the stochastic matrix P(x|y ): n ∈ O(∆−1 ). ∆−1 appears to scale polynomially for problems of interest. David Poulin (Sherbrooke)  Quantum Metropolis  QAMF@UBC’10  14 / 27  Quantum Metropolis  Outline  1  Motivation  2  Quantum simulators  3  Metropolis algorithm  4  Quantum Metropolis  David Poulin (Sherbrooke)  Quantum Metropolis  QAMF@UBC’10  15 / 27  Quantum Metropolis  Can’t we do the same with quantum systems?  Objective CPTP map E such that E n (ρ0 ) →  1 −βH Ze  for large enough n.  Straightforward generalization of Metropolis 1  Start from a random energy eigenstate ψi of energy Ei .  2  Generate a new "nearby" energy eigenstate ψj of energy Ej .  3  Accept / reject new configuration with wij = min{1, eβ(Ei −Ej ) }: Accept x ← y with probability wij . Reject x ← x with probability 1 − wij .  4  Return to 2.  David Poulin (Sherbrooke)  Quantum Metropolis  QAMF@UBC’10  16 / 27  Quantum Metropolis  Can’t we do the same with quantum systems?  Objective CPTP map E such that E n (ρ0 ) →  1 −βH Ze  for large enough n.  Straightforward generalization of Metropolis 1  Start from a random energy eigenstate ψi of energy Ei .  2  Generate a new "nearby" energy eigenstate ψj of energy Ej .  3  Accept / reject new configuration with wij = min{1, eβ(Ei −Ej ) }: Accept x ← y with probability wij . Reject x ← x with probability 1 − wij .  4  Return to 2.  David Poulin (Sherbrooke)  Quantum Metropolis  QAMF@UBC’10  16 / 27  Quantum Metropolis  Can’t we do the same with quantum systems?  Objective CPTP map E such that E n (ρ0 ) →  1 −βH Ze  for large enough n.  Straightforward generalization of Metropolis 1  Start from a random energy eigenstate ψi of energy Ei .  2  Generate a new "nearby" energy eigenstate ψj of energy Ej .  3  Accept / reject new configuration with wij = min{1, eβ(Ei −Ej ) }: Accept x ← y with probability wij . Reject x ← x with probability 1 − wij .  4  Return to 2.  David Poulin (Sherbrooke)  Quantum Metropolis  QAMF@UBC’10  16 / 27  Quantum Metropolis  Can’t we do the same with quantum systems?  Objective CPTP map E such that E n (ρ0 ) →  1 −βH Ze  for large enough n.  Straightforward generalization of Metropolis 1  Start from a random energy eigenstate ψi of energy Ei .  2  Generate a new "nearby" energy eigenstate ψj of energy Ej .  3  Accept / reject new configuration with wij = min{1, eβ(Ei −Ej ) }: Accept x ← y with probability wij . Reject x ← x with probability 1 − wij .  4  Return to 2.  David Poulin (Sherbrooke)  Quantum Metropolis  QAMF@UBC’10  16 / 27  Quantum Metropolis  Can’t we do the same with quantum systems?  Objective CPTP map E such that E n (ρ0 ) →  1 −βH Ze  for large enough n.  Straightforward generalization of Metropolis 1  Start from a random energy eigenstate ψi of energy Ei .  2  Generate a new "nearby" energy eigenstate ψj of energy Ej .  3  Accept / reject new configuration with wij = min{1, eβ(Ei −Ej ) }: Accept x ← y with probability wij . Reject x ← x with probability 1 − wij .  4  Return to 2.  David Poulin (Sherbrooke)  Quantum Metropolis  QAMF@UBC’10  16 / 27  Quantum Metropolis  Problems We don’t know what the energy eigenstates ψi are. Use quantum phase estimation.  David Poulin (Sherbrooke)  Quantum Metropolis  QAMF@UBC’10  17 / 27  Quantum Metropolis  Problems We don’t know what the energy eigenstates ψi are. Use quantum phase estimation.  David Poulin (Sherbrooke)  Quantum Metropolis  QAMF@UBC’10  17 / 27  Quantum Metropolis  Quantum phase estimation The ability to simulate the dynamics generated by H can be used to construct an efficient circuit to (approximately) measure the energy:  i  e−iHr  αi |ψi |0  H  F  i  αi |ψi ⊗ |Ei  Can use to prepare a random energy eigenstate. Can use to measure the energy of a given eigenstate.  David Poulin (Sherbrooke)  Quantum Metropolis  QAMF@UBC’10  18 / 27  Quantum Metropolis  Quantum phase estimation The ability to simulate the dynamics generated by H can be used to construct an efficient circuit to (approximately) measure the energy:  i  e−iHr  αi |ψi |0  H  F  i  αi |ψi ⊗ |Ei  Can use to prepare a random energy eigenstate. Can use to measure the energy of a given eigenstate.  David Poulin (Sherbrooke)  Quantum Metropolis  QAMF@UBC’10  18 / 27  Quantum Metropolis  Quantum phase estimation The ability to simulate the dynamics generated by H can be used to construct an efficient circuit to (approximately) measure the energy:  i  e−iHr  αi |ψi |0  H  F  i  αi |ψi ⊗ |Ei  Can use to prepare a random energy eigenstate. Can use to measure the energy of a given eigenstate.  David Poulin (Sherbrooke)  Quantum Metropolis  QAMF@UBC’10  18 / 27  Quantum Metropolis  Problems We don’t know what the energy eigenstates ψi are. Use quantum phase estimation.  How do we jump to a "nearby" energy eigenstate? Importance of local moves If classical configurations x and y differ only at a few positions, then E(x) ≈ E(y ) for any local Hamiltonian H.  David Poulin (Sherbrooke)  Quantum Metropolis  QAMF@UBC’10  19 / 27  Quantum Metropolis  Problems We don’t know what the energy eigenstates ψi are. Use quantum phase estimation.  How do we jump to a "nearby" energy eigenstate? Importance of local moves If classical configurations x and y differ only at a few positions, then E(x) ≈ E(y ) for any local Hamiltonian H.  David Poulin (Sherbrooke)  Quantum Metropolis  QAMF@UBC’10  19 / 27  Quantum Metropolis  Problems We don’t know what the energy eigenstates ψi are. Use quantum phase estimation.  How do we jump to a "nearby" energy eigenstate? Importance of local moves If classical configurations x and y differ only at a few positions, then E(x) ≈ E(y ) for any local Hamiltonian H.  David Poulin (Sherbrooke)  Quantum Metropolis  QAMF@UBC’10  19 / 27  Quantum Metropolis  Problems We don’t know what the energy eigenstates ψi are. Use quantum phase estimation.  How do we jump to a "nearby" energy eigenstate? Importance of local moves If classical configurations x and y differ only at a few positions, then E(x) ≈ E(y ) for any local Hamiltonian H.  David Poulin (Sherbrooke)  Quantum Metropolis  QAMF@UBC’10  19 / 27  Quantum Metropolis  Importance of local moves  E  David Poulin (Sherbrooke)  Cyx  Quantum Metropolis  QAMF@UBC’10  20 / 27  Quantum Metropolis  Importance of local moves  E  David Poulin (Sherbrooke)  Cyx  Quantum Metropolis  QAMF@UBC’10  20 / 27  Quantum Metropolis  Problems We don’t know what the energy eigenstates ψi are. Use quantum phase estimation.  How do we jump to a "nearby" energy eigenstate? Importance of local moves If classical configurations x and y differ only at a few positions, then E(x) ≈ E(y ) for any local Hamiltonian H. This ensures that the local move has a good chance of being accepted. This was a failure in one of the approach of Terhal and DiVincenzo. Use random local unitary transformation.  Measure new state’s energy → irreversible process: how to reject? Classically, we keep a copy of x before going to y : cloning. Use measurement that reveals less information. David Poulin (Sherbrooke)  Quantum Metropolis  QAMF@UBC’10  21 / 27  Quantum Metropolis  Problems We don’t know what the energy eigenstates ψi are. Use quantum phase estimation.  How do we jump to a "nearby" energy eigenstate? Importance of local moves If classical configurations x and y differ only at a few positions, then E(x) ≈ E(y ) for any local Hamiltonian H. This ensures that the local move has a good chance of being accepted. This was a failure in one of the approach of Terhal and DiVincenzo. Use random local unitary transformation.  Measure new state’s energy → irreversible process: how to reject? Classically, we keep a copy of x before going to y : cloning. Use measurement that reveals less information. David Poulin (Sherbrooke)  Quantum Metropolis  QAMF@UBC’10  21 / 27  Quantum Metropolis  Problems We don’t know what the energy eigenstates ψi are. Use quantum phase estimation.  How do we jump to a "nearby" energy eigenstate? Importance of local moves If classical configurations x and y differ only at a few positions, then E(x) ≈ E(y ) for any local Hamiltonian H. This ensures that the local move has a good chance of being accepted. This was a failure in one of the approach of Terhal and DiVincenzo. Use random local unitary transformation.  Measure new state’s energy → irreversible process: how to reject? Classically, we keep a copy of x before going to y : cloning. Use measurement that reveals less information. David Poulin (Sherbrooke)  Quantum Metropolis  QAMF@UBC’10  21 / 27  Quantum Metropolis  Problems We don’t know what the energy eigenstates ψi are. Use quantum phase estimation.  How do we jump to a "nearby" energy eigenstate? Importance of local moves If classical configurations x and y differ only at a few positions, then E(x) ≈ E(y ) for any local Hamiltonian H. This ensures that the local move has a good chance of being accepted. This was a failure in one of the approach of Terhal and DiVincenzo. Use random local unitary transformation.  Measure new state’s energy → irreversible process: how to reject? Classically, we keep a copy of x before going to y : cloning. Use measurement that reveals less information. David Poulin (Sherbrooke)  Quantum Metropolis  QAMF@UBC’10  21 / 27  Quantum Metropolis  Problems We don’t know what the energy eigenstates ψi are. Use quantum phase estimation.  How do we jump to a "nearby" energy eigenstate? Importance of local moves If classical configurations x and y differ only at a few positions, then E(x) ≈ E(y ) for any local Hamiltonian H. This ensures that the local move has a good chance of being accepted. This was a failure in one of the approach of Terhal and DiVincenzo. Use random local unitary transformation.  Measure new state’s energy → irreversible process: how to reject? Classically, we keep a copy of x before going to y : cloning. Use measurement that reveals less information. David Poulin (Sherbrooke)  Quantum Metropolis  QAMF@UBC’10  21 / 27  Quantum Metropolis  Problems We don’t know what the energy eigenstates ψi are. Use quantum phase estimation.  How do we jump to a "nearby" energy eigenstate? Importance of local moves If classical configurations x and y differ only at a few positions, then E(x) ≈ E(y ) for any local Hamiltonian H. This ensures that the local move has a good chance of being accepted. This was a failure in one of the approach of Terhal and DiVincenzo. Use random local unitary transformation.  Measure new state’s energy → irreversible process: how to reject? Classically, we keep a copy of x before going to y : cloning. Use measurement that reveals less information. David Poulin (Sherbrooke)  Quantum Metropolis  QAMF@UBC’10  21 / 27  Quantum Metropolis  Problems We don’t know what the energy eigenstates ψi are. Use quantum phase estimation.  How do we jump to a "nearby" energy eigenstate? Importance of local moves If classical configurations x and y differ only at a few positions, then E(x) ≈ E(y ) for any local Hamiltonian H. This ensures that the local move has a good chance of being accepted. This was a failure in one of the approach of Terhal and DiVincenzo. Use random local unitary transformation.  Measure new state’s energy → irreversible process: how to reject? Classically, we keep a copy of x before going to y : cloning. Use measurement that reveals less information. David Poulin (Sherbrooke)  Quantum Metropolis  QAMF@UBC’10  21 / 27  Quantum Metropolis  Not quite there yet... 1 2  Use QPE to prepare an initial random energy eigenstate ψi . Apply a local random unitary transformation C: C : |ψi →  3  Ei ∼ Ej  Use QPE to collapse onto a new energy eigenstate ψj and learn the associated energy Ej : QPE : j  4  j  cji |ψj  cji |ψj →  |cji |2  j  cji |ψj ⊗ |Ej −−→ |ψj ⊗ |Ej  Compute wij = min{1, eβ(Ei −Ej ) }  With probability wij , go to step 2. With probability 1 − wij , return computer to state ψi and fo to step 3.  David Poulin (Sherbrooke)  Quantum Metropolis  QAMF@UBC’10  22 / 27  Quantum Metropolis  Not quite there yet... 1 2  Use QPE to prepare an initial random energy eigenstate ψi . Apply a local random unitary transformation C: C : |ψi →  3  Ei ∼ Ej  Use QPE to collapse onto a new energy eigenstate ψj and learn the associated energy Ej : QPE : j  4  j  cji |ψj  cji |ψj →  |cji |2  j  cji |ψj ⊗ |Ej −−→ |ψj ⊗ |Ej  Compute wij = min{1, eβ(Ei −Ej ) }  With probability wij , go to step 2. With probability 1 − wij , return computer to state ψi and fo to step 3.  David Poulin (Sherbrooke)  Quantum Metropolis  QAMF@UBC’10  22 / 27  Quantum Metropolis  Not quite there yet... 1 2  Use QPE to prepare an initial random energy eigenstate ψi . Apply a local random unitary transformation C: C : |ψi →  3  Ei ∼ Ej  Use QPE to collapse onto a new energy eigenstate ψj and learn the associated energy Ej : QPE : j  4  j  cji |ψj  cji |ψj →  |cji |2  j  cji |ψj ⊗ |Ej −−→ |ψj ⊗ |Ej  Compute wij = min{1, eβ(Ei −Ej ) }  With probability wij , go to step 2. With probability 1 − wij , return computer to state ψi and fo to step 3.  David Poulin (Sherbrooke)  Quantum Metropolis  QAMF@UBC’10  22 / 27  Quantum Metropolis  Not quite there yet... 1 2  Use QPE to prepare an initial random energy eigenstate ψi . Apply a local random unitary transformation C: C : |ψi →  3  Ei ∼ Ej  Use QPE to collapse onto a new energy eigenstate ψj and learn the associated energy Ej : QPE : j  4  j  cji |ψj  cji |ψj →  |cji |2  j  cji |ψj ⊗ |Ej −−→ |ψj ⊗ |Ej  Compute wij = min{1, eβ(Ei −Ej ) }  With probability wij , go to step 2. With probability 1 − wij , return computer to state ψi and fo to step 3.  David Poulin (Sherbrooke)  Quantum Metropolis  QAMF@UBC’10  22 / 27  Quantum Metropolis  Not quite there yet... 1 2  Use QPE to prepare an initial random energy eigenstate ψi . Apply a local random unitary transformation C: C : |ψi →  3  Ei ∼ Ej  Use QPE to collapse onto a new energy eigenstate ψj and learn the associated energy Ej : QPE : j  4  j  cji |ψj  cji |ψj →  |cji |2  j  cji |ψj ⊗ |Ej −−→ |ψj ⊗ |Ej  Compute wij = min{1, eβ(Ei −Ej ) }  With probability wij , go to step 2. With probability 1 − wij , return computer to state ψi and fo to step 3.  David Poulin (Sherbrooke)  Quantum Metropolis  QAMF@UBC’10  22 / 27  Quantum Metropolis  Coherent Metropolis move We combine steps 3&4 coherently (Ei is known):  j  cji |ψj ⊗ |Ej →  j  cji |ψj ⊗ |Ej ⊗ (  wij |0 +  1 − wij |1 )  Measure last qubit: If the outcome is 0, measure the "energy register" to learn Ej and return to step 2. If the outcome is 1, go back to state ψi . This is already better because only one bit of information was learned–accepr/reject–so less damage was made to the state. We can use QPE to determine if we are back in state ψi . David Poulin (Sherbrooke)  Quantum Metropolis  QAMF@UBC’10  23 / 27  Quantum Metropolis  Coherent Metropolis move We combine steps 3&4 coherently (Ei is known):  j  cji |ψj ⊗ |Ej →  j  cji |ψj ⊗ |Ej ⊗ (  wij |0 +  1 − wij |1 )  Measure last qubit: If the outcome is 0, measure the "energy register" to learn Ej and return to step 2. If the outcome is 1, go back to state ψi . This is already better because only one bit of information was learned–accepr/reject–so less damage was made to the state. We can use QPE to determine if we are back in state ψi . David Poulin (Sherbrooke)  Quantum Metropolis  QAMF@UBC’10  23 / 27  Quantum Metropolis  Coherent Metropolis move We combine steps 3&4 coherently (Ei is known):  j  cji |ψj ⊗ |Ej →  j  cji |ψj ⊗ |Ej ⊗ (  wij |0 +  1 − wij |1 )  Measure last qubit: If the outcome is 0, measure the "energy register" to learn Ej and return to step 2. If the outcome is 1, go back to state ψi . This is already better because only one bit of information was learned–accepr/reject–so less damage was made to the state. We can use QPE to determine if we are back in state ψi . David Poulin (Sherbrooke)  Quantum Metropolis  QAMF@UBC’10  23 / 27  Quantum Metropolis  Coherent Metropolis move We combine steps 3&4 coherently (Ei is known):  j  cji |ψj ⊗ |Ej →  j  cji |ψj ⊗ |Ej ⊗ (  wij |0 +  1 − wij |1 )  Measure last qubit: If the outcome is 0, measure the "energy register" to learn Ej and return to step 2. If the outcome is 1, go back to state ψi . This is already better because only one bit of information was learned–accepr/reject–so less damage was made to the state. We can use QPE to determine if we are back in state ψi . David Poulin (Sherbrooke)  Quantum Metropolis  QAMF@UBC’10  23 / 27  Quantum Metropolis  Coherent Metropolis move We combine steps 3&4 coherently (Ei is known):  j  cji |ψj ⊗ |Ej →  j  cji |ψj ⊗ |Ej ⊗ (  wij |0 +  1 − wij |1 )  Measure last qubit: If the outcome is 0, measure the "energy register" to learn Ej and return to step 2. If the outcome is 1, go back to state ψi . This is already better because only one bit of information was learned–accepr/reject–so less damage was made to the state. We can use QPE to determine if we are back in state ψi . David Poulin (Sherbrooke)  Quantum Metropolis  QAMF@UBC’10  23 / 27  Quantum Metropolis  Coherent Metropolis move We combine steps 3&4 coherently (Ei is known):  j  cji |ψj ⊗ |Ej →  j  cji |ψj ⊗ |Ej ⊗ (  wij |0 +  1 − wij |1 )  Measure last qubit: If the outcome is 0, measure the "energy register" to learn Ej and return to step 2. If the outcome is 1, go back to state ψi . This is already better because only one bit of information was learned–accepr/reject–so less damage was made to the state. We can use QPE to determine if we are back in state ψi . David Poulin (Sherbrooke)  Quantum Metropolis  QAMF@UBC’10  23 / 27  Quantum Metropolis  Undoing binary measurement, Marriott & Watrous ’05 Ingredients Initial state |ψ .  Circuit for measurement P = {P, P ⊥ } with P = |ψ ψ|. Circuit for a different measurement Q = {Q, Q ⊥ }. Goal Starting from Q ⊥ |ψ , go back to |ψ . Solution Iterate P and Q measurements until outcome P is obtained. √ |ψ = (Q + Q ⊥ )|ψ |φQ = q|ψ + 1 − q|ψ ⊥ √ √ = q|φQ + 1 − q|φ⊥ |φ⊥ = 1 − q|ψ − q|ψ ⊥ Q Q √ |ψ ⊥ = 1 − q|φQ − q|φ⊥ Q David Poulin (Sherbrooke)  Quantum Metropolis  QAMF@UBC’10  24 / 27  Quantum Metropolis  Undoing binary measurement, Marriott & Watrous ’05 Ingredients Initial state |ψ .  Circuit for measurement P = {P, P ⊥ } with P = |ψ ψ|. Circuit for a different measurement Q = {Q, Q ⊥ }. Goal Starting from Q ⊥ |ψ , go back to |ψ . Solution Iterate P and Q measurements until outcome P is obtained. √ |ψ = (Q + Q ⊥ )|ψ |φQ = q|ψ + 1 − q|ψ ⊥ √ √ = q|φQ + 1 − q|φ⊥ |φ⊥ = 1 − q|ψ − q|ψ ⊥ Q Q √ |ψ ⊥ = 1 − q|φQ − q|φ⊥ Q David Poulin (Sherbrooke)  Quantum Metropolis  QAMF@UBC’10  24 / 27  Quantum Metropolis  Undoing binary measurement, Marriott & Watrous ’05 Ingredients Initial state |ψ .  Circuit for measurement P = {P, P ⊥ } with P = |ψ ψ|. Circuit for a different measurement Q = {Q, Q ⊥ }. Goal Starting from Q ⊥ |ψ , go back to |ψ . Solution Iterate P and Q measurements until outcome P is obtained. √ |ψ = (Q + Q ⊥ )|ψ |φQ = q|ψ + 1 − q|ψ ⊥ √ √ = q|φQ + 1 − q|φ⊥ |φ⊥ = 1 − q|ψ − q|ψ ⊥ Q Q √ |ψ ⊥ = 1 − q|φQ − q|φ⊥ Q David Poulin (Sherbrooke)  Quantum Metropolis  QAMF@UBC’10  24 / 27  Quantum Metropolis  Undoing binary measurement, Marriott & Watrous ’05 Ingredients Initial state |ψ .  Circuit for measurement P = {P, P ⊥ } with P = |ψ ψ|. Circuit for a different measurement Q = {Q, Q ⊥ }. Goal Starting from Q ⊥ |ψ , go back to |ψ . Solution Iterate P and Q measurements until outcome P is obtained. √ |ψ = (Q + Q ⊥ )|ψ |φQ = q|ψ + 1 − q|ψ ⊥ √ √ = q|φQ + 1 − q|φ⊥ |φ⊥ = 1 − q|ψ − q|ψ ⊥ Q Q √ |ψ ⊥ = 1 − q|φQ − q|φ⊥ Q David Poulin (Sherbrooke)  Quantum Metropolis  QAMF@UBC’10  24 / 27  Quantum Metropolis  Undoing binary measurement, Marriott & Watrous ’05 Ingredients Initial state |ψ .  Circuit for measurement P = {P, P ⊥ } with P = |ψ ψ|. Circuit for a different measurement Q = {Q, Q ⊥ }. Goal Starting from Q ⊥ |ψ , go back to |ψ . Solution Iterate P and Q measurements until outcome P is obtained. √ |ψ = (Q + Q ⊥ )|ψ |φQ = q|ψ + 1 − q|ψ ⊥ √ √ = q|φQ + 1 − q|φ⊥ |φ⊥ = 1 − q|ψ − q|ψ ⊥ Q Q √ |ψ ⊥ = 1 − q|φQ − q|φ⊥ Q David Poulin (Sherbrooke)  Quantum Metropolis  QAMF@UBC’10  24 / 27  Quantum Metropolis  Undoing binary measurement, Marriott & Watrous ’05 Ingredients Initial state |ψ .  Circuit for measurement P = {P, P ⊥ } with P = |ψ ψ|. Circuit for a different measurement Q = {Q, Q ⊥ }. Goal Starting from Q ⊥ |ψ , go back to |ψ . Solution Iterate P and Q measurements until outcome P is obtained. √ |ψ = (Q + Q ⊥ )|ψ |φQ = q|ψ + 1 − q|ψ ⊥ √ √ = q|φQ + 1 − q|φ⊥ |φ⊥ = 1 − q|ψ − q|ψ ⊥ Q Q √ |ψ ⊥ = 1 − q|φQ − q|φ⊥ Q David Poulin (Sherbrooke)  Quantum Metropolis  QAMF@UBC’10  24 / 27  Quantum Metropolis  Undoing binary measurement, Marriott & Watrous ’05 Ingredients Initial state |ψ .  Circuit for measurement P = {P, P ⊥ } with P = |ψ ψ|. Circuit for a different measurement Q = {Q, Q ⊥ }. Goal Starting from Q ⊥ |ψ , go back to |ψ . Solution Iterate P and Q measurements until outcome P is obtained. √ |ψ = (Q + Q ⊥ )|ψ |φQ = q|ψ + 1 − q|ψ ⊥ √ √ = q|φQ + 1 − q|φ⊥ |φ⊥ = 1 − q|ψ − q|ψ ⊥ Q Q √ |ψ ⊥ = 1 − q|φQ − q|φ⊥ Q David Poulin (Sherbrooke)  Quantum Metropolis  QAMF@UBC’10  24 / 27  Quantum Metropolis  Undoing binary measurement, Marriott & Watrous ’05 |ψ  |ψ ⊥  =  √  =  q|φQ + 1 − q|φQ  1 − q|φ⊥ Q √ ⊥ − q|φQ  |φQ  |φ⊥ Q  = =  √  1 − q|ψ ⊥ √ 1 − q|ψ − q|ψ ⊥  q|ψ +  Repeat m times, probability of failure is ∼ p−m . We can reject the update → quantum Metropolis step E. Quantum detailed balance √ pm pn ψi |E(|ψm ψn |)|ψj = Hence ρG =  j  pi pj ψm |E(|ψi ψj |)|ψn  pj |ψj ψj | is the fixed point, pj ∝ e−βEj .  David Poulin (Sherbrooke)  Quantum Metropolis  QAMF@UBC’10  25 / 27  Quantum Metropolis  Undoing binary measurement, Marriott & Watrous ’05 |ψ  |ψ ⊥  =  √  =  q|φQ + 1 − q|φQ  1 − q|φ⊥ Q √ ⊥ − q|φQ  |φQ  |φ⊥ Q  = =  √  1 − q|ψ ⊥ √ 1 − q|ψ − q|ψ ⊥  q|ψ +  |φ⊥ Q Repeat m times, probability of failure is ∼ p−m . We can reject the update → quantum Metropolis step E. Quantum detailed balance √ pm pn ψi |E(|ψm ψn |)|ψj = Hence ρG =  j  pi pj ψm |E(|ψi ψj |)|ψn  pj |ψj ψj | is the fixed point, pj ∝ e−βEj .  David Poulin (Sherbrooke)  Quantum Metropolis  QAMF@UBC’10  25 / 27  Quantum Metropolis  Undoing binary measurement, Marriott & Watrous ’05 |ψ  |ψ ⊥  =  q|φQ + 1 − q|φQ  =  P 1-q  |φ⊥ Q  √  q  |ψ  1 − q|φ⊥ Q √ ⊥ − q|φQ  |φQ  |φ⊥ Q  = =  √  1 − q|ψ ⊥ √ 1 − q|ψ − q|ψ ⊥  q|ψ +  Done  |ψ ⊥  Repeat m times, probability of failure is ∼ p−m . We can reject the update → quantum Metropolis step E. Quantum detailed balance √ pm pn ψi |E(|ψm ψn |)|ψj = Hence ρG =  j  pi pj ψm |E(|ψi ψj |)|ψn  pj |ψj ψj | is the fixed point, pj ∝ e−βEj .  David Poulin (Sherbrooke)  Quantum Metropolis  QAMF@UBC’10  25 / 27  Quantum Metropolis  Undoing binary measurement, Marriott & Watrous ’05 |ψ  |ψ ⊥  =  q|φQ + 1 − q|φQ  =  P 1-q  |φ⊥ Q  √  q  Q  |ψ |ψ  Done 1-q  ⊥  q  1 − q|φ⊥ Q √ ⊥ − q|φQ  |φQ  |φ⊥ Q  = =  √  1 − q|ψ ⊥ √ 1 − q|ψ − q|ψ ⊥  q|ψ +  |φQ |φ⊥ Q  Repeat m times, probability of failure is ∼ p−m . We can reject the update → quantum Metropolis step E. Quantum detailed balance √ pm pn ψi |E(|ψm ψn |)|ψj = Hence ρG =  j  pi pj ψm |E(|ψi ψj |)|ψn  pj |ψj ψj | is the fixed point, pj ∝ e−βEj .  David Poulin (Sherbrooke)  Quantum Metropolis  QAMF@UBC’10  25 / 27  Quantum Metropolis  Undoing binary measurement, Marriott & Watrous ’05 |ψ  |ψ ⊥  =  q|φQ + 1 − q|φQ  =  P 1-q  |φ⊥ Q  √  q  Q  |ψ |ψ  Done 1-q  ⊥  q  1 − q|φ⊥ Q √ ⊥ − q|φQ  |φQ |φ⊥ Q  P  q  1-q q  |φQ  |φ⊥ Q  |ψ  = =  √  1 − q|ψ ⊥ √ 1 − q|ψ − q|ψ ⊥  q|ψ +  Done  |ψ ⊥  Repeat m times, probability of failure is ∼ p−m . We can reject the update → quantum Metropolis step E. Quantum detailed balance √ pm pn ψi |E(|ψm ψn |)|ψj = Hence ρG =  j  pi pj ψm |E(|ψi ψj |)|ψn  pj |ψj ψj | is the fixed point, pj ∝ e−βEj .  David Poulin (Sherbrooke)  Quantum Metropolis  QAMF@UBC’10  25 / 27  Quantum Metropolis  Undoing binary measurement, Marriott & Watrous ’05 |ψ  |ψ ⊥  =  q|φQ + 1 − q|φQ  =  P 1-q  |φ⊥ Q  √  q  Q  |ψ |ψ  Done 1-q  ⊥  q  1 − q|φ⊥ Q √ ⊥ − q|φQ  |φQ |φ⊥ Q  P  q  1-q q  |φQ  |φ⊥ Q  |ψ |ψ  ⊥  Q  Done 1-q q  = =  √  1 − q|ψ ⊥ √ 1 − q|ψ − q|ψ ⊥  q|ψ +  |φQ |φ⊥ Q  Repeat m times, probability of failure is ∼ p−m . We can reject the update → quantum Metropolis step E. Quantum detailed balance √ pm pn ψi |E(|ψm ψn |)|ψj = Hence ρG =  j  pi pj ψm |E(|ψi ψj |)|ψn  pj |ψj ψj | is the fixed point, pj ∝ e−βEj .  David Poulin (Sherbrooke)  Quantum Metropolis  QAMF@UBC’10  25 / 27  Quantum Metropolis  Undoing binary measurement, Marriott & Watrous ’05 |ψ  |ψ ⊥  =  q|φQ + 1 − q|φQ  =  P 1-q  |φ⊥ Q  √  q  Q  |ψ |ψ  Done 1-q  ⊥  q  1 − q|φ⊥ Q √ ⊥ − q|φQ  |φQ |φ⊥ Q  P  q  1-q q  |φQ  |φ⊥ Q  |ψ |ψ ⊥  Q  Done 1-q q  = =  |φQ |φ⊥ Q  √  1 − q|ψ ⊥ √ 1 − q|ψ − q|ψ ⊥  q|ψ +  P  q  1-q q  |ψ  Done  |ψ ⊥  Repeat m times, probability of failure is ∼ p−m . We can reject the update → quantum Metropolis step E. Quantum detailed balance √ pm pn ψi |E(|ψm ψn |)|ψj = Hence ρG =  j  pi pj ψm |E(|ψi ψj |)|ψn  pj |ψj ψj | is the fixed point, pj ∝ e−βEj .  David Poulin (Sherbrooke)  Quantum Metropolis  QAMF@UBC’10  25 / 27  Quantum Metropolis  Undoing binary measurement, Marriott & Watrous ’05 |ψ  |ψ ⊥  =  q|φQ + 1 − q|φQ  =  P 1-q  |φ⊥ Q  √  q  Q  |ψ |ψ  Done 1-q  ⊥  q  1 − q|φ⊥ Q √ ⊥ − q|φQ  |φQ |φ⊥ Q  P  q  1-q q  |φQ  |φ⊥ Q  |ψ |ψ  ⊥  Q  Done 1-q q  = =  |φQ |φ⊥ Q  √  1 − q|ψ ⊥ √ 1 − q|ψ − q|ψ ⊥  q|ψ +  P  q  1-q q  |ψ |ψ  Q  Done  ⊥  1-q q  |φQ |φ⊥ Q  Repeat m times, probability of failure is ∼ p−m . We can reject the update → quantum Metropolis step E. Quantum detailed balance √ pm pn ψi |E(|ψm ψn |)|ψj = Hence ρG =  j  pi pj ψm |E(|ψi ψj |)|ψn  pj |ψj ψj | is the fixed point, pj ∝ e−βEj .  David Poulin (Sherbrooke)  Quantum Metropolis  QAMF@UBC’10  25 / 27  Quantum Metropolis  Undoing binary measurement, Marriott & Watrous ’05 |ψ  |ψ ⊥  =  q|φQ + 1 − q|φQ  =  P 1-q  |φ⊥ Q  √  q  Q  |ψ |ψ  Done 1-q  ⊥  q  1 − q|φ⊥ Q √ ⊥ − q|φQ  |φQ |φ⊥ Q  P  q  1-q q  |φQ  |φ⊥ Q  |ψ |ψ  ⊥  Q  Done 1-q q  = =  |φQ |φ⊥ Q  √  1 − q|ψ ⊥ √ 1 − q|ψ − q|ψ ⊥  q|ψ +  P  q  1-q q  |ψ |ψ  Q  Done  ⊥  1-q q  |φQ |φ⊥ Q  Repeat m times, probability of failure is ∼ p−m . We can reject the update → quantum Metropolis step E. Quantum detailed balance √ pm pn ψi |E(|ψm ψn |)|ψj = Hence ρG =  j  pi pj ψm |E(|ψi ψj |)|ψn  pj |ψj ψj | is the fixed point, pj ∝ e−βEj .  David Poulin (Sherbrooke)  Quantum Metropolis  QAMF@UBC’10  25 / 27  Quantum Metropolis  Undoing binary measurement, Marriott & Watrous ’05 |ψ  |ψ ⊥  =  q|φQ + 1 − q|φQ  =  P 1-q  |φ⊥ Q  √  q  Q  |ψ |ψ  Done 1-q  ⊥  q  1 − q|φ⊥ Q √ ⊥ − q|φQ  |φQ |φ⊥ Q  P  q  1-q q  |φQ  |φ⊥ Q  |ψ |ψ  ⊥  Q  Done 1-q q  = =  |φQ |φ⊥ Q  √  1 − q|ψ ⊥ √ 1 − q|ψ − q|ψ ⊥  q|ψ +  P  q  1-q q  |ψ |ψ  Q  Done  ⊥  1-q q  |φQ |φ⊥ Q  Repeat m times, probability of failure is ∼ p−m . We can reject the update → quantum Metropolis step E. Quantum detailed balance √ pm pn ψi |E(|ψm ψn |)|ψj = Hence ρG =  j  pi pj ψm |E(|ψi ψj |)|ψn  pj |ψj ψj | is the fixed point, pj ∝ e−βEj .  David Poulin (Sherbrooke)  Quantum Metropolis  QAMF@UBC’10  25 / 27  Quantum Metropolis  Undoing binary measurement, Marriott & Watrous ’05 |ψ  |ψ ⊥  =  q|φQ + 1 − q|φQ  =  P 1-q  |φ⊥ Q  √  q  Q  |ψ |ψ  Done 1-q  ⊥  q  1 − q|φ⊥ Q √ ⊥ − q|φQ  |φQ |φ⊥ Q  P  q  1-q q  |φQ  |φ⊥ Q  |ψ |ψ  ⊥  Q  Done 1-q q  = =  |φQ |φ⊥ Q  √  1 − q|ψ ⊥ √ 1 − q|ψ − q|ψ ⊥  q|ψ +  P  q  1-q q  |ψ |ψ  Q  Done  ⊥  1-q q  |φQ |φ⊥ Q  Repeat m times, probability of failure is ∼ p−m . We can reject the update → quantum Metropolis step E. Quantum detailed balance √ pm pn ψi |E(|ψm ψn |)|ψj = Hence ρG =  j  pi pj ψm |E(|ψi ψj |)|ψn  pj |ψj ψj | is the fixed point, pj ∝ e−βEj .  David Poulin (Sherbrooke)  Quantum Metropolis  QAMF@UBC’10  25 / 27  Quantum Metropolis  Inverse gap for XY model at T = 0 The model  The local moves     k −1  σkx σkx +1 +σky σky +1 +gσkz  H= k  700 600 500 400  Ck =   j=1  σjz  σkx  g = - 1/ 2 g=0 g = 1/ 2 g = 3/ 2  300 200 100 200  David Poulin (Sherbrooke)  400  600  Quantum Metropolis  800  1000  QAMF@UBC’10  26 / 27  Conclusion  Quantum simulations could be the central task for quantum computers. They require initializing the quantum computer in physically relevant state. The classical problem is solved by the Metropolis algorithm. Rapidly mixing Markov chain to sample from Gibbs distribution. Cleaver unphysical moves can be much faster than "system+bath" simulation.  We have shown how to leverage the full power of the Metropolis algorithm to the quantum setting. Brings a solution to the initialization problem. Validates the quantum computer as a universal simulator.  Markov chain Monte Carlo is the starting point of many classical algorithms. New quantum algorithms? Dissipation driven algorithm: inherently robust... David Poulin (Sherbrooke)  Quantum Metropolis  QAMF@UBC’10  27 / 27  Conclusion  Quantum simulations could be the central task for quantum computers. They require initializing the quantum computer in physically relevant state. The classical problem is solved by the Metropolis algorithm. Rapidly mixing Markov chain to sample from Gibbs distribution. Cleaver unphysical moves can be much faster than "system+bath" simulation.  We have shown how to leverage the full power of the Metropolis algorithm to the quantum setting. Brings a solution to the initialization problem. Validates the quantum computer as a universal simulator.  Markov chain Monte Carlo is the starting point of many classical algorithms. New quantum algorithms? Dissipation driven algorithm: inherently robust... David Poulin (Sherbrooke)  Quantum Metropolis  QAMF@UBC’10  27 / 27  Conclusion  Quantum simulations could be the central task for quantum computers. They require initializing the quantum computer in physically relevant state. The classical problem is solved by the Metropolis algorithm. Rapidly mixing Markov chain to sample from Gibbs distribution. Cleaver unphysical moves can be much faster than "system+bath" simulation.  We have shown how to leverage the full power of the Metropolis algorithm to the quantum setting. Brings a solution to the initialization problem. Validates the quantum computer as a universal simulator.  Markov chain Monte Carlo is the starting point of many classical algorithms. New quantum algorithms? Dissipation driven algorithm: inherently robust... David Poulin (Sherbrooke)  Quantum Metropolis  QAMF@UBC’10  27 / 27  Conclusion  Quantum simulations could be the central task for quantum computers. They require initializing the quantum computer in physically relevant state. The classical problem is solved by the Metropolis algorithm. Rapidly mixing Markov chain to sample from Gibbs distribution. Cleaver unphysical moves can be much faster than "system+bath" simulation.  We have shown how to leverage the full power of the Metropolis algorithm to the quantum setting. Brings a solution to the initialization problem. Validates the quantum computer as a universal simulator.  Markov chain Monte Carlo is the starting point of many classical algorithms. New quantum algorithms? Dissipation driven algorithm: inherently robust... David Poulin (Sherbrooke)  Quantum Metropolis  QAMF@UBC’10  27 / 27  Conclusion  Quantum simulations could be the central task for quantum computers. They require initializing the quantum computer in physically relevant state. The classical problem is solved by the Metropolis algorithm. Rapidly mixing Markov chain to sample from Gibbs distribution. Cleaver unphysical moves can be much faster than "system+bath" simulation.  We have shown how to leverage the full power of the Metropolis algorithm to the quantum setting. Brings a solution to the initialization problem. Validates the quantum computer as a universal simulator.  Markov chain Monte Carlo is the starting point of many classical algorithms. New quantum algorithms? Dissipation driven algorithm: inherently robust... David Poulin (Sherbrooke)  Quantum Metropolis  QAMF@UBC’10  27 / 27  

Cite

Citation Scheme:

        

Citations by CSL (citeproc-js)

Usage Statistics

Share

Embed

Customize your widget with the following options, then copy and paste the code below into the HTML of your page to embed this item in your website.
                        
                            <div id="ubcOpenCollectionsWidgetDisplay">
                            <script id="ubcOpenCollectionsWidget"
                            src="{[{embed.src}]}"
                            data-item="{[{embed.item}]}"
                            data-collection="{[{embed.collection}]}"
                            data-metadata="{[{embed.showMetadata}]}"
                            data-width="{[{embed.width}]}"
                            async >
                            </script>
                            </div>
                        
                    
IIIF logo Our image viewer uses the IIIF 2.0 standard. To load this item in other compatible viewers, use this url:
http://iiif.library.ubc.ca/presentation/dsp.59370.1-0103161/manifest

Comment

Related Items