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

Quantum algorithm for preparing thermal Gibbs states Wocjan, Pawel Jul 25, 2010

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

Item Metadata

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

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  

Cite

Citation Scheme:

        

Citations by CSL (citeproc-js)

Usage Statistics

Share

Embed

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

Comment

Related Items