Algorithm for Preparing Thermal Gibbs States Pawel Wocjan University of Central Florida July 25, 2010 Pawel Wocjan University of Central Florida Algorithm for Preparing Thermal Gibbs States Related work This work is based on Sampling from the Thermal Quantum Gibbs State and Evaluating Partition Functions with a Quantum Computer with David Poulin, Phys. Rev. Lett. 103, 220502 (2009) Algorithm for Preparing Thermal States – Detailed Analysis with C.-F. Chiang, Proc. NATO ARW “Quantum Cryptography and Computing: Theory and Implementation, Gdansk, Poland, 9-12 September 2009 This work has been supported by the National Science Foundation grants CCF-0726771 and CCF-0746600 Pawel Wocjan University of Central Florida Algorithm for Preparing Thermal Gibbs States Definitions Let H be a Hamiltonian with spectral decomposition D Ea |ψa ψa | H= a=1 The partition function Zβ at inverse temperature β is D e −βEa Zβ := a=1 The thermal state ρβ at inverse temperature β is D ρβ := a=1 e −βEa |ψa ψa | Zβ Pawel Wocjan University of Central Florida Algorithm for Preparing Thermal Gibbs States Thermalizing quantum systems Given H, β, and , prepare a quantum state ρ˜β with ρβ − ρ˜β Pawel Wocjan University of Central Florida tr ≤ Algorithm for Preparing Thermal Gibbs States Methods Metropolis Sampling Quantized Metropolis Sampling Somma, Boixo, Barnum, and Knill, PRL 101,130504 W. and Abeyesinghe, PRA 78, 032311 Method based on Amplitude Amplification (this presentation) Quantum Metropolis Sampling (David Poulin’s presentation) Pawel Wocjan University of Central Florida Algorithm for Preparing Thermal Gibbs States Classical Hamiltonians Let Ω be a set whose elements x correspond the states of some classical system Let E : Ω → [0, 1] denote the energy function, assigning to each state x its energy E (x) Let H= E (x)|x x| x∈Ω Thermalizing such classical systems is easier because H is diagonal in the computational basis {|x }x∈Ω Pawel Wocjan University of Central Florida Algorithm for Preparing Thermal Gibbs States Metropolis sampling Given such classical Hamiltonian H, we can always construct a Markov chain P whose limiting distribution is equal to ρβ The spectral gap δ determines how fast we can approach the Boltzmann distribution The run time scales like 1/δ In general, it is not possible to determine (or bound) the spectral gap ⇒ heuristics There are important cases where it can be shown that the gap is large Pawel Wocjan University of Central Florida Algorithm for Preparing Thermal Gibbs States Quantized Metropolis algorithm Given such classical Hamiltonian H, there is a “quantized” Metropolis algorithm preparing a state |ϕ˜β with |ϕβ − |ϕ˜β ≤ where |ϕβ is a “quantized” version of the Boltzmann distribution |ϕβ := x∈Ω The run times scales like e −βEx |x Zβ 1/δ Pawel Wocjan University of Central Florida Algorithm for Preparing Thermal Gibbs States Structure of our method Prepare the state 1 √ D |x ⊗ |Ex ⊗ |0 x∈Ω Apply a controlled rotation to obtain the state 1 |Ψ = √ D √ |x ⊗ |Ex ⊗ e −βEx |0 + 1 − e −βEx |1 x∈Ω Pawel Wocjan University of Central Florida Algorithm for Preparing Thermal Gibbs States Structure of our method Measure in the basis |0 , |1 If we obtain |0 ⇒ the post-measurement state is |Π0 |Ψ Π0 |Ψ = x∈Ω e −βEx |x ⊗ |Ex ⊗ |0 Zβ where Π0 = I ⊗ |0 0| Using amplitude amplification, we can achieve an expected run time D 1 = Π0 |Ψ Zβ Pawel Wocjan University of Central Florida Algorithm for Preparing Thermal Gibbs States Generalization to quantum Hamiltonians Let H be an arbitrary quantum Hamiltonian with spectral decomposition D Ea |ψa ψa | H= Ea ∈ [0, 1/2] a=1 There are two difficulties: we cannot change between the computational basis |a and the eigenvector basis |ψa of H we do not know the energies Ea Both difficulties can be overcome with quantum phase estimation ⇒ we can extend the previous method to quantum Hamiltonians Pawel Wocjan University of Central Florida Algorithm for Preparing Thermal Gibbs States Error sources Given H, β, and , our quantum algorithm prepares ρ˜β ρβ − ρ˜β tr ≤ The errors come from two sources: ρβ − ρ˜β tr ≤ ρ − ρsim tr + ρsim − ρfail tr ρsim due to imperfect simulation of exp(2πiH) ρ˜β = ρfail due to nonzero failure probability and limited precision of quantum phase estimation Pawel Wocjan University of Central Florida Algorithm for Preparing Thermal Gibbs States Imperfect simulation of Hamiltonians Assume that H is sparse and let U = exp(2πiH) Using techniques for simulating Hamiltonian time evolutions, we can implement Usim with U − Usim ≤ sim The cost scales like poly(log D, 1/ sim , s) where s indicates the sparseness of H Pawel Wocjan University of Central Florida Algorithm for Preparing Thermal Gibbs States Technical results Matrix logarithm is Lipschitz continuous: U − Usim ≤ sim ⇒ there is a Hamiltonian Hsim with H − Hsim ≤ O( sim ) Thermal states are H¨older continuous: H − Hsim ≤ O( sim ) ⇒ the corresponding thermal states satisfy ρ − ρsim tr Pawel Wocjan University of Central Florida ≤ O( β sim ) Algorithm for Preparing Thermal Gibbs States Structure of our method Start with the maximally entangled state 1 |Φ := √ D D |a ⊗ |a a=1 Run phase estimation of Usim on first part of |Φ and record eigenphase in the energy register Apply the controlled rotation R = √ RE = −βE √ e 1 − e −βE E |E E | ⊗ RE √ − √1 − e −βE e −βE Use amplitude amplification to increase overlap with |0 component Pawel Wocjan University of Central Florida Algorithm for Preparing Thermal Gibbs States Invariance of maximally entangled state Let |Φ := 1 √ D D |a ⊗ |a a=1 D V |ψa a| := a=1 ¯ , we have Due to invariance of |Φ under V ⊗ V 1 |Φ = √ D Pawel Wocjan University of Central Florida D |ψa ⊗ |ψ¯a a=1 Algorithm for Preparing Thermal Gibbs States Correspondance between energy levels and eigenphases Recall that U = exp(2πiH) We have (U ⊗ ID )|ψa ⊗ |ψ¯a (U ⊗ ID )|Φ = e 2πiEa |ψa ⊗ |ψ¯a = 1 √ D D e 2πiEa |ψa ⊗ |ψ¯a a=1 The energy levels Ea of H correspond bijectively to the eigenphases Ea of U ⇒ Apply quantum phase estimation to approximate the energy levels Pawel Wocjan University of Central Florida Algorithm for Preparing Thermal Gibbs States Intuition – perfect quantum phase estimation If perfect quantum phase estimation were possible (infinite precion and zero probability of failure), we could prepare the state 1 |Ψ = √ D D |ψa ⊗ |ψ¯a ⊗ |Ea ⊗ √ e −βEa |0 + 1 − e −βEa |1 a=1 ⇒ Using amplitude amplification just as in the case of classical Hamiltonians, we could obtain a purification of the thermal state Pawel Wocjan University of Central Florida Algorithm for Preparing Thermal Gibbs States Imperfect quantum phase estimation We use quantum phase estimation that invokes the controlled Usim operation O((1/ prec ) log(1/ fail )) times ⇒ We transform |Φ to the state 1 √ D D |ψa ⊗ |ψ¯a ⊗ ca− |Ea− + ca+ |Ea+ Ea+ − Ea ≤ prec , |ca+ |2 + |ca− |2 ≥ 1 − |ξ 2 ≤ + |ξ a=1 Ea − Ea− ≤ prec fail fail Pawel Wocjan University of Central Florida Algorithm for Preparing Thermal Gibbs States Controlled rotation After quantum phase estimation, we apply the rotation controlled ˜ by the value in the energy register to prepare the state |Ψ 1 √ D D |ψa ⊗|ψ¯a ⊗ca± |Ea± ⊗ ± ± e −βEa |0 + 1 − e −βEa |1 +|ξ˜ a=1 Pawel Wocjan University of Central Florida Algorithm for Preparing Thermal Gibbs States Amplitude amplification We apply amplitude amplification to obtain |β˜ := ˜ Π0 |Ψ ˜ Π0 |Ψ The required number of iterations is ˜ 1/ Π0 |Ψ The desired approximate thermal state is ˜ ρ˜β = TrA¯ (|β˜ β|) where we trace out over the ancilla, the energy register and the register holding |ψ¯a Pawel Wocjan University of Central Florida Algorithm for Preparing Thermal Gibbs States Error analysis The approximate thermal state ρ˜β is close to the perfect ρβ provided that simulation and phase estimation are accurate enough Given H, β, and , our quantum algorithm makes it possible to prepare ρ˜β ρβ − ρ˜β tr ≤ The expected run time is D β 1 · · log + β Zβ Pawel Wocjan University of Central Florida Algorithm for Preparing Thermal Gibbs States
- Library Home /
- Search Collections /
- Open Collections /
- Browse Collections /
- Canadian Summer School on Quantum Information (CSSQI) (10th : 2010) /
- Quantum algorithm for preparing thermal Gibbs states
Open Collections
Canadian Summer School on Quantum Information (CSSQI) (10th : 2010)
Quantum algorithm for preparing thermal Gibbs states Wocjan, Pawel Jul 25, 2010
Page Metadata
Item Metadata
Title | Quantum algorithm for preparing thermal Gibbs states |
Creator |
Wocjan, Pawel |
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 |
Date Issued | 2010-07-25 |
Description | We present a quantum algorithm for preparing thermal Gibbs states of interacting quantum systems. This algorithm is based on Grover’s technique for quantum state engineering, and its running time is dominated by the factor sqrt{D/Z}, where D and Z_beta denote the dimension of the quantum system and its partition function at inverse temperature beta, respectively. We discuss the differences between this algorithm and quantum Metropolis sampling (see the presentation by David Poulin) and outline the analysis of the errors that arise due to imperfect simulation of Hamiltonian time evolutions and limited performance of phase estimation (finite accuracy and nonzero probability of failure). |
Genre |
Presentation |
Type |
Text Sound 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.0103167 |
URI | http://hdl.handle.net/2429/30076 |
Affiliation |
Non UBC |
Peer Review Status | Reviewed |
Scholarly Level | Faculty |
Rights URI | http://creativecommons.org/licenses/by-nc-nd/4.0/ |
AggregatedSourceRepository | DSpace |
Download
- Media
- 59370-Wocjan-ThermGibbsPrepAnalysis.pdf [ 191.46kB ]
- 59370-WS Jul 25 Pawel.mp4 [ 97.91MB ]
- Metadata
- JSON: 59370-1.0103167.json
- JSON-LD: 59370-1.0103167-ld.json
- RDF/XML (Pretty): 59370-1.0103167-rdf.xml
- RDF/JSON: 59370-1.0103167-rdf.json
- Turtle: 59370-1.0103167-turtle.txt
- N-Triples: 59370-1.0103167-rdf-ntriples.txt
- Original Record: 59370-1.0103167-source.json
- Full Text
- 59370-1.0103167-fulltext.txt
- Citation
- 59370-1.0103167.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:
http://iiif.library.ubc.ca/presentation/dsp.59370.1-0103167/manifest