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(β) = 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

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:
https://iiif.library.ubc.ca/presentation/dsp.59370.1-0103161/manifest

Comment

Related Items