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(β) = 1Z e −βH . The ground state of H, i.e. ρG(∞). Physically relevance: thermal equilibrium at temperature 1β . Output 〈X (t)Y 〉 = Tr{Xe−iHtYeiHtρ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(β) = 1Z e −βH . The ground state of H, i.e. ρG(∞). Physically relevance: thermal equilibrium at temperature 1β . Output 〈X (t)Y 〉 = Tr{Xe−iHtYeiHtρ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(β) = 1Z e −βH . The ground state of H, i.e. ρG(∞). Physically relevance: thermal equilibrium at temperature 1β . Output 〈X (t)Y 〉 = Tr{Xe−iHtYeiHtρ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(β) = 1Z e −βH . The ground state of H, i.e. ρG(∞). Physically relevance: thermal equilibrium at temperature 1β . Output 〈X (t)Y 〉 = Tr{Xe−iHtYeiHtρ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−iHtYeiHtρ} 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−iHtYeiHtρ} 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−iHtYeiHtρ} 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 exp(−it ∑ k hk ) = [∏ k exp(−ihk/N) ]N +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 exp(−it ∑ k hk ) = [∏ k exp(−ihk/N) ]N +O( 1 N2 ) e = -iHt U A # 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 exp(−it ∑ k hk ) = [∏ k exp(−ihk/N) ]N +O( 1 N2 ) e = -iHt U A # 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 exp(−it ∑ k hk ) = [∏ k exp(−ihk/N) ]N +O( 1 N2 ) e = -iHt U A # 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? Use Markov Chain Monte Carlo to sample from pG(x) = 1Z e −βE(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. 3 Accept / reject new configuration with wxy = min{1,eβ(E(x)−E(y))}: 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? Use Markov Chain Monte Carlo to sample from pG(x) = 1Z e −βE(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. 3 Accept / reject new configuration with wxy = min{1,eβ(E(x)−E(y))}: 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? Use Markov Chain Monte Carlo to sample from pG(x) = 1Z e −βE(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. 3 Accept / reject new configuration with wxy = min{1,eβ(E(x)−E(y))}: 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? Use Markov Chain Monte Carlo to sample from pG(x) = 1Z e −βE(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. 3 Accept / reject new configuration with wxy = min{1,eβ(E(x)−E(y))}: 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? Use Markov Chain Monte Carlo to sample from pG(x) = 1Z e −βE(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. 3 Accept / reject new configuration with wxy = min{1,eβ(E(x)−E(y))}: 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? Use Markov Chain Monte Carlo to sample from pG(x) = 1Z e −βE(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. 3 Accept / reject new configuration with wxy = min{1,eβ(E(x)−E(y))}: 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? Use Markov Chain Monte Carlo to sample from pG(x) = 1Z e −βE(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. 3 Accept / reject new configuration with wxy = min{1,eβ(E(x)−E(y))}: 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 x0 P(x1|x0)−−−−−→ x1 P(x2|x1)−−−−−→ x2 . . . xn−1 P(xn|xn−1)−−−−−−→ xn Detailed balance condition The distribution pG(x) = 1Z e −βH(x) 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 x0 P(x1|x0)−−−−−→ x1 P(x2|x1)−−−−−→ x2 . . . xn−1 P(xn|xn−1)−−−−−−→ xn Detailed balance condition The distribution pG(x) = 1Z e −βH(x) 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 x0 P(x1|x0)−−−−−→ x1 P(x2|x1)−−−−−→ x2 . . . xn−1 P(xn|xn−1)−−−−−−→ xn ∼ 1Z e −βH(xn) Detailed balance condition The distribution pG(x) = 1Z e −βH(x) 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 x0 P(x1|x0)−−−−−→ x1 P(x2|x1)−−−−−→ x2 . . . xn−1 P(xn|xn−1)−−−−−−→ xn ∼ 1Z e −βH(xn) Detailed balance condition The distribution pG(x) = 1Z e −βH(x) 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 x0 P(x1|x0)−−−−−→ x1 P(x2|x1)−−−−−→ x2 . . . xn−1 P(xn|xn−1)−−−−−−→ xn ∼ 1Z e −βH(xn) Detailed balance condition The distribution pG(x) = 1Z e −βH(x) 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 En(ρ0)→ 1Z e−βH 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 En(ρ0)→ 1Z e−βH 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 En(ρ0)→ 1Z e−βH 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 En(ρ0)→ 1Z e−βH 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 En(ρ0)→ 1Z e−βH 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: |0〉 ∑ i αi|ψi〉 ∑ i αi|ψi〉 ⊗ |Ei〉 H F e−iHr 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: |0〉 ∑ i αi|ψi〉 ∑ i αi|ψi〉 ⊗ |Ei〉 H F e−iHr 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: |0〉 ∑ i αi|ψi〉 ∑ i αi|ψi〉 ⊗ |Ei〉 H F e−iHr 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 C x y David Poulin (Sherbrooke) Quantum Metropolis QAMF@UBC’10 20 / 27 Quantum Metropolis Importance of local moves E C x y David Poulin (Sherbrooke) 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 Use QPE to prepare an initial random energy eigenstate ψi . 2 Apply a local random unitary transformation C: C : |ψi〉 → ∑ j c ij |ψj〉 Ei ∼ Ej 3 Use QPE to collapse onto a new energy eigenstate ψj and learn the associated energy Ej : QPE : ∑ j c ij |ψj〉 → ∑ j c ij |ψj〉 ⊗ |Ej〉 |c ij |2−−→ |ψj〉 ⊗ |Ej〉 4 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 Use QPE to prepare an initial random energy eigenstate ψi . 2 Apply a local random unitary transformation C: C : |ψi〉 → ∑ j c ij |ψj〉 Ei ∼ Ej 3 Use QPE to collapse onto a new energy eigenstate ψj and learn the associated energy Ej : QPE : ∑ j c ij |ψj〉 → ∑ j c ij |ψj〉 ⊗ |Ej〉 |c ij |2−−→ |ψj〉 ⊗ |Ej〉 4 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 Use QPE to prepare an initial random energy eigenstate ψi . 2 Apply a local random unitary transformation C: C : |ψi〉 → ∑ j c ij |ψj〉 Ei ∼ Ej 3 Use QPE to collapse onto a new energy eigenstate ψj and learn the associated energy Ej : QPE : ∑ j c ij |ψj〉 → ∑ j c ij |ψj〉 ⊗ |Ej〉 |c ij |2−−→ |ψj〉 ⊗ |Ej〉 4 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 Use QPE to prepare an initial random energy eigenstate ψi . 2 Apply a local random unitary transformation C: C : |ψi〉 → ∑ j c ij |ψj〉 Ei ∼ Ej 3 Use QPE to collapse onto a new energy eigenstate ψj and learn the associated energy Ej : QPE : ∑ j c ij |ψj〉 → ∑ j c ij |ψj〉 ⊗ |Ej〉 |c ij |2−−→ |ψj〉 ⊗ |Ej〉 4 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 Use QPE to prepare an initial random energy eigenstate ψi . 2 Apply a local random unitary transformation C: C : |ψi〉 → ∑ j c ij |ψj〉 Ei ∼ Ej 3 Use QPE to collapse onto a new energy eigenstate ψj and learn the associated energy Ej : QPE : ∑ j c ij |ψj〉 → ∑ j c ij |ψj〉 ⊗ |Ej〉 |c ij |2−−→ |ψj〉 ⊗ |Ej〉 4 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 c ij |ψj〉 ⊗ |Ej〉 → ∑ j c ij |ψ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 c ij |ψj〉 ⊗ |Ej〉 → ∑ j c ij |ψ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 c ij |ψj〉 ⊗ |Ej〉 → ∑ j c ij |ψ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 c ij |ψj〉 ⊗ |Ej〉 → ∑ j c ij |ψ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 c ij |ψj〉 ⊗ |Ej〉 → ∑ j c ij |ψ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 c ij |ψj〉 ⊗ |Ej〉 → ∑ j c ij |ψ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〉 |ψ⊥〉 = √ 1− q|φQ〉 − √ q|φ⊥Q〉 |φQ〉 = √ q|ψ〉+ √ 1− q|ψ⊥〉 |φ⊥Q〉 = √ 1− 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〉 |ψ⊥〉 = √ 1− q|φQ〉 − √ q|φ⊥Q〉 |φQ〉 = √ q|ψ〉+ √ 1− q|ψ⊥〉 |φ⊥Q〉 = √ 1− 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〉 |ψ⊥〉 = √ 1− q|φQ〉 − √ q|φ⊥Q〉 |φQ〉 = √ q|ψ〉+ √ 1− q|ψ⊥〉 |φ⊥Q〉 = √ 1− 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〉 |ψ⊥〉 = √ 1− q|φQ〉 − √ q|φ⊥Q〉 |φQ〉 = √ q|ψ〉+ √ 1− q|ψ⊥〉 |φ⊥Q〉 = √ 1− 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〉 |ψ⊥〉 = √ 1− q|φQ〉 − √ q|φ⊥Q〉 |φQ〉 = √ q|ψ〉+ √ 1− q|ψ⊥〉 |φ⊥Q〉 = √ 1− 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〉 |ψ⊥〉 = √ 1− q|φQ〉 − √ q|φ⊥Q〉 |φQ〉 = √ q|ψ〉+ √ 1− q|ψ⊥〉 |φ⊥Q〉 = √ 1− 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〉 |ψ⊥〉 = √ 1− q|φQ〉 − √ q|φ⊥Q〉 |φQ〉 = √ q|ψ〉+ √ 1− q|ψ⊥〉 |φ⊥Q〉 = √ 1− 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|ψ⊥〉 |φ⊥Q〉 = √ 1− q|ψ〉 − √q|ψ⊥〉 Repeat m times, probability of failure is ∼ p−m. We can reject the update→ quantum Metropolis step E . Quantum detailed balance √ pmpn〈ψi |E(|ψm〉〈ψn|)|ψj〉 = √ pipj〈ψm|E(|ψi〉〈ψj |)|ψn〉 Hence ρG = ∑ j 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|ψ⊥〉 |φ⊥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 √ pmpn〈ψi |E(|ψm〉〈ψn|)|ψj〉 = √ pipj〈ψm|E(|ψi〉〈ψj |)|ψn〉 Hence ρG = ∑ j 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|ψ⊥〉 |φ⊥Q〉 = √ 1− q|ψ〉 − √q|ψ⊥〉 |ψ⊥〉|φ⊥Q〉 |ψ〉Done P 1-q q Repeat m times, probability of failure is ∼ p−m. We can reject the update→ quantum Metropolis step E . Quantum detailed balance √ pmpn〈ψi |E(|ψm〉〈ψn|)|ψj〉 = √ pipj〈ψm|E(|ψi〉〈ψj |)|ψn〉 Hence ρG = ∑ j 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|ψ⊥〉 |φ⊥Q〉 = √ 1− q|ψ〉 − √q|ψ⊥〉 |ψ⊥〉|φ⊥Q〉 |ψ〉 |φQ〉 |φ⊥Q〉 Done QP 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 √ pmpn〈ψi |E(|ψm〉〈ψn|)|ψj〉 = √ pipj〈ψm|E(|ψi〉〈ψj |)|ψn〉 Hence ρG = ∑ j 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|ψ⊥〉 |φ⊥Q〉 = √ 1− q|ψ〉 − √q|ψ⊥〉 |ψ⊥〉|φ⊥Q〉 |ψ〉 |φQ〉 |ψ⊥〉|φ⊥Q〉 |ψ〉Done Done QP P 1-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 √ pmpn〈ψi |E(|ψm〉〈ψn|)|ψj〉 = √ pipj〈ψm|E(|ψi〉〈ψj |)|ψn〉 Hence ρG = ∑ j 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|ψ⊥〉 |φ⊥Q〉 = √ 1− q|ψ〉 − √q|ψ⊥〉 |ψ⊥〉|φ⊥Q〉 |ψ〉 |φQ〉 |ψ⊥〉|φ⊥Q〉 |ψ〉 |φQ〉 |φ⊥Q〉 Done Done Q QP P 1-q 1-q 1-q 1-q 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 √ pmpn〈ψi |E(|ψm〉〈ψn|)|ψj〉 = √ pipj〈ψm|E(|ψi〉〈ψj |)|ψn〉 Hence ρG = ∑ j 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|ψ⊥〉 |φ⊥Q〉 = √ 1− q|ψ〉 − √q|ψ⊥〉 |ψ⊥〉|φ⊥Q〉 |ψ〉 |φQ〉 |ψ⊥〉|φ⊥Q〉 |ψ〉 |φQ〉 |φ⊥Q〉 Done Done Q QP P 1-q 1-q 1-q 1-q q q q q q |ψ⊥〉 |ψ〉Done P 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 √ pmpn〈ψi |E(|ψm〉〈ψn|)|ψj〉 = √ pipj〈ψm|E(|ψi〉〈ψj |)|ψn〉 Hence ρG = ∑ j 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|ψ⊥〉 |φ⊥Q〉 = √ 1− q|ψ〉 − √q|ψ⊥〉 |ψ⊥〉|φ⊥Q〉 |ψ〉 |φQ〉 |ψ⊥〉|φ⊥Q〉 |ψ〉 |φQ〉 |φ⊥Q〉 Done Done Q QP P 1-q 1-q 1-q 1-q q q q q q |ψ⊥〉 |ψ〉 |φQ〉 |φ⊥Q〉 Done QP 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 √ pmpn〈ψi |E(|ψm〉〈ψn|)|ψj〉 = √ pipj〈ψm|E(|ψi〉〈ψj |)|ψn〉 Hence ρG = ∑ j 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|ψ⊥〉 |φ⊥Q〉 = √ 1− q|ψ〉 − √q|ψ⊥〉 |ψ⊥〉|φ⊥Q〉 |ψ〉 |φQ〉 |ψ⊥〉|φ⊥Q〉 |ψ〉 |φQ〉 |φ⊥Q〉 Done Done Q QP P 1-q 1-q 1-q 1-q q q q q q |ψ⊥〉 |ψ〉 |φQ〉 |φ⊥Q〉 Done QP 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 √ pmpn〈ψi |E(|ψm〉〈ψn|)|ψj〉 = √ pipj〈ψm|E(|ψi〉〈ψj |)|ψn〉 Hence ρG = ∑ j 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|ψ⊥〉 |φ⊥Q〉 = √ 1− q|ψ〉 − √q|ψ⊥〉 |ψ⊥〉|φ⊥Q〉 |ψ〉 |φQ〉 |ψ⊥〉|φ⊥Q〉 |ψ〉 |φQ〉 |φ⊥Q〉 Done Done Q QP P 1-q 1-q 1-q 1-q q q q q q |ψ⊥〉 |ψ〉 |φQ〉 |φ⊥Q〉 Done QP 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 √ pmpn〈ψi |E(|ψm〉〈ψn|)|ψj〉 = √ pipj〈ψm|E(|ψi〉〈ψj |)|ψn〉 Hence ρG = ∑ j 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|ψ⊥〉 |φ⊥Q〉 = √ 1− q|ψ〉 − √q|ψ⊥〉 |ψ⊥〉|φ⊥Q〉 |ψ〉 |φQ〉 |ψ⊥〉|φ⊥Q〉 |ψ〉 |φQ〉 |φ⊥Q〉 Done Done Q QP P 1-q 1-q 1-q 1-q q q q q q |ψ⊥〉 |ψ〉 |φQ〉 |φ⊥Q〉 Done QP 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 √ pmpn〈ψi |E(|ψm〉〈ψn|)|ψj〉 = √ pipj〈ψm|E(|ψi〉〈ψj |)|ψn〉 Hence ρG = ∑ j 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 H = ∑ k σxkσ x k+1+σ y kσ y k+1+gσ z k The local moves Ck = k−1⊗ j=1 σzj σxk 200 400 600 800 1000 100 200 300 400 500 600 700 g = 3 2 g = 1 2 g = 0 g = - 1 2/ / / David Poulin (Sherbrooke) Quantum Metropolis 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
- Library Home /
- Search Collections /
- Open Collections /
- Browse Collections /
- Canadian Summer School on Quantum Information (CSSQI) (10th : 2010) /
- Quantum Metropolis sampling: an algorithm to simulate...
Open Collections
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
Page Metadata
Item Metadata
Title | Quantum Metropolis sampling: an algorithm to simulate thermal systems with a quantum computer |
Creator |
Poulin, David |
Contributor | University of British Columbia. Department of Physics and Astronomy Workshop on Quantum Algorithms, Computational Models and Foundations of Quantum Mechanics Pacific Institute for the Mathematical Sciences Summer School on Quantum Information (10th : 2010 : Vancouver, B.C.) |
Date Issued | 2010-07-24 |
Description | The original motivation to build a quantum computer came from Feynman who envisaged a machine capable of simulating generic quantum mechanical systems, a task that is intractable for classical computers. Such a machine would have tremendous applications in all physical sciences, including condensed matter physics, chemistry, and high energy physics. Part of Feynman's challenge was met by Lloyd who showed how to approximately decompose the time-evolution operator of interacting quantum particles into a short sequence of elementary gates, suitable for operation on a quantum computer. However, this left open the more fundamental problem of how to simulate the equilibrium and static properties of quantum systems. This requires the preparation of ground and Gibb's states on a quantum computer. For classical systems, this problem is solved by the ubiquitous Metropolis algorithm, a method that basically acquired a monopoly for the simulation of interacting particles. In this talk, I will demonstrate that the corresponding quantum problem can be solved by a quantum Metropolis algorithm. This validates the quantum computer as a universal simulator, and proves that the so-called sign ! problem occurring in quantum Monte Carlo methods can be resolved with a quantum computer. |
Subject |
Quantum algorithm Quantum many-body physics Quantum simulation Markov Chain Monte Carlo |
Genre |
Presentation |
Type |
Text Still Image Moving Image |
Language | eng |
Date Available | 2016-11-22 |
Provider | Vancouver : University of British Columbia Library |
Rights | Attribution-NonCommercial-NoDerivatives 4.0 International |
DOI | 10.14288/1.0103161 |
URI | http://hdl.handle.net/2429/30073 |
Affiliation |
Non UBC |
Peer Review Status | Unreviewed |
Scholarly Level | Faculty |
Rights URI | http://creativecommons.org/licenses/by-nc-nd/4.0/ |
AggregatedSourceRepository | DSpace |
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
Cite
Citation Scheme:
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>
Our image viewer uses the IIIF 2.0 standard.
To load this item in other compatible viewers, use this url:
https://iiif.library.ubc.ca/presentation/dsp.59370.1-0103161/manifest