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

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

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

Notice for Google Chrome users:
If you are having trouble viewing or searching the PDF with Google Chrome, please download it here instead.

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 H = D∑ a=1 Ea|ψa〉〈ψa| The partition function Zβ at inverse temperature β is Zβ := D∑ a=1 e−βEa The thermal state ρβ at inverse temperature β is ρβ := D∑ a=1 e−βEa Zβ |ψa〉〈ψa| Pawel Wocjan University of Central Florida Algorithm for Preparing Thermal Gibbs States Thermalizing quantum systems Given H, β, and , prepare a quantum state ρ̃β with ‖ρβ − ρ̃β‖tr ≤  Pawel Wocjan University of Central Florida 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 = ∑ x∈Ω E (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∈Ω √ e−βEx Zβ |x〉 The run times scales like √ 1/δ Pawel Wocjan University of Central Florida Algorithm for Preparing Thermal Gibbs States Structure of our method Prepare the state 1√ D ∑ x∈Ω |x〉 ⊗ |Ex〉 ⊗ |0〉 Apply a controlled rotation to obtain the state |Ψ〉 = 1√ D ∑ x∈Ω |x〉 ⊗ |Ex〉 ⊗ (√ e−βEx |0〉+ √ 1− e−βEx |1〉 ) 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 Zβ |x〉 ⊗ |Ex〉 ⊗ |0〉 where Π0 = I ⊗ |0〉〈0| Using amplitude amplification, we can achieve an expected run time 1 ‖Π0|Ψ〉‖ = √ D 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 H = D∑ a=1 Ea|ψa〉〈ψa| Ea ∈ [0, 1/2] 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(2piiH) ρ̃β = ρ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(2piiH) Using techniques for simulating Hamiltonian time evolutions, we can implement Usim with ‖U − Usim‖ ≤ sim The cost scales like poly(logD, 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ölder continuous: ‖H − Hsim‖ ≤ O(sim) ⇒ the corresponding thermal states satisfy ‖ρ− ρsim‖tr ≤ O( √ βsim) Pawel Wocjan University of Central Florida Algorithm for Preparing Thermal Gibbs States Structure of our method Start with the maximally entangled state |Φ〉 := 1√ D D∑ a=1 |a〉 ⊗ |a〉 Run phase estimation of Usim on first part of |Φ〉 and record eigenphase in the energy register Apply the controlled rotation R = ∑ E |E 〉〈E | ⊗ RE RE = ( √ e−βE −√1− e−βE√ 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=1 |a〉 ⊗ |a〉 V := D∑ a=1 |ψa〉〈a| Due to invariance of |Φ〉 under V ⊗ V̄ , we have |Φ〉 = 1√ D D∑ a=1 |ψa〉 ⊗ |ψ̄a〉 Pawel Wocjan University of Central Florida Algorithm for Preparing Thermal Gibbs States Correspondance between energy levels and eigenphases Recall that U = exp(2piiH) We have (U ⊗ ID)|ψa〉 ⊗ |ψ̄a〉 = e2piiEa |ψa〉 ⊗ |ψ̄a〉 (U ⊗ ID)|Φ〉 = 1√ D D∑ a=1 e2piiEa |ψa〉 ⊗ |ψ̄a〉 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=1 |ψa〉 ⊗ |ψ̄a〉 ⊗ |Ea〉 ⊗ (√ e−βEa |0〉+ √ 1− e−βEa |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=1 |ψa〉 ⊗ |ψ̄a〉 ⊗ ( c−a |E−a 〉+ c+a |E+a 〉 ) + |ξ〉 E+a − Ea ≤ prec, Ea − E−a ≤ prec |c+a |2 + |c−a |2 ≥ 1− fail ‖|ξ〉‖2 ≤ 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=1 |ψa〉⊗|ψ̄a〉⊗c±a |E±a 〉⊗ (√ e−βE±a |0〉+ √ 1− e−βE±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 ρ̃β = TrĀ(|β̃〉〈β̃|) 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 Zβ · β  · ( log 1  + β ) 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}]}"
                            data-media="{[{embed.selectedMedia}]}"
                            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-0103167/manifest

Comment

Related Items