A simple lower bound for the complexity of estimating partition functions on a quantum computer
| Title: | A simple lower bound for the complexity of estimating partition functions on a quantum computer |
|---|---|
| Authors: | Chen, Zherui, Nannicini, Giacomo |
| Publication Year: | 2024 |
| Collection: | Computer Science Mathematics Quantum Physics Statistics |
| Subject Terms: | Quantum Physics, Computer Science - Computational Complexity, Computer Science - Data Structures and Algorithms, Mathematics - Statistics Theory |
| More Details: | We study the complexity of estimating the partition function $\mathsf{Z}(\beta)=\sum_{x\in\chi} e^{-\beta H(x)}$ for a Gibbs distribution characterized by the Hamiltonian $H(x)$. We provide a simple and natural lower bound for quantum algorithms that solve this task by relying on reflections through the coherent encoding of Gibbs states. Our primary contribution is a $\varOmega(1/\epsilon)$ lower bound for the number of reflections needed to estimate the partition function with a quantum algorithm. The proof is based on a reduction from the problem of estimating the Hamming weight of an unknown binary string. Comment: 11 pages, we added a reference [HK20] to a recent classical lower bound in the sampling model |
| Document Type: | Working Paper |
| Access URL: | http://arxiv.org/abs/2404.02414 |
| Accession Number: | edsarx.2404.02414 |
| Database: | arXiv |
| FullText | Text: Availability: 0 CustomLinks: – Url: http://arxiv.org/abs/2404.02414 Name: EDS - Arxiv Category: fullText Text: View this record from Arxiv MouseOverText: View this record from Arxiv – Url: https://resolver.ebsco.com/c/xy5jbn/result?sid=EBSCO:edsarx&genre=article&issn=&ISBN=&volume=&issue=&date=20240402&spage=&pages=&title=A simple lower bound for the complexity of estimating partition functions on a quantum computer&atitle=A%20simple%20lower%20bound%20for%20the%20complexity%20of%20estimating%20partition%20functions%20on%20a%20quantum%20computer&aulast=Chen%2C%20Zherui&id=DOI: Name: Full Text Finder (for New FTF UI) (s8985755) Category: fullText Text: Find It @ SCU Libraries MouseOverText: Find It @ SCU Libraries |
|---|---|
| Header | DbId: edsarx DbLabel: arXiv An: edsarx.2404.02414 RelevancyScore: 1085 AccessLevel: 3 PubType: Report PubTypeId: report PreciseRelevancyScore: 1085.41735839844 |
| IllustrationInfo | |
| Items | – Name: Title Label: Title Group: Ti Data: A simple lower bound for the complexity of estimating partition functions on a quantum computer – Name: Author Label: Authors Group: Au Data: <searchLink fieldCode="AR" term="%22Chen%2C+Zherui%22">Chen, Zherui</searchLink><br /><searchLink fieldCode="AR" term="%22Nannicini%2C+Giacomo%22">Nannicini, Giacomo</searchLink> – Name: DatePubCY Label: Publication Year Group: Date Data: 2024 – Name: Subset Label: Collection Group: HoldingsInfo Data: Computer Science<br />Mathematics<br />Quantum Physics<br />Statistics – Name: Subject Label: Subject Terms Group: Su Data: <searchLink fieldCode="DE" term="%22Quantum+Physics%22">Quantum Physics</searchLink><br /><searchLink fieldCode="DE" term="%22Computer+Science+-+Computational+Complexity%22">Computer Science - Computational Complexity</searchLink><br /><searchLink fieldCode="DE" term="%22Computer+Science+-+Data+Structures+and+Algorithms%22">Computer Science - Data Structures and Algorithms</searchLink><br /><searchLink fieldCode="DE" term="%22Mathematics+-+Statistics+Theory%22">Mathematics - Statistics Theory</searchLink> – Name: Abstract Label: Description Group: Ab Data: We study the complexity of estimating the partition function $\mathsf{Z}(\beta)=\sum_{x\in\chi} e^{-\beta H(x)}$ for a Gibbs distribution characterized by the Hamiltonian $H(x)$. We provide a simple and natural lower bound for quantum algorithms that solve this task by relying on reflections through the coherent encoding of Gibbs states. Our primary contribution is a $\varOmega(1/\epsilon)$ lower bound for the number of reflections needed to estimate the partition function with a quantum algorithm. The proof is based on a reduction from the problem of estimating the Hamming weight of an unknown binary string.<br />Comment: 11 pages, we added a reference [HK20] to a recent classical lower bound in the sampling model – Name: TypeDocument Label: Document Type Group: TypDoc Data: Working Paper – Name: URL Label: Access URL Group: URL Data: <link linkTarget="URL" linkTerm="http://arxiv.org/abs/2404.02414" linkWindow="_blank">http://arxiv.org/abs/2404.02414</link> – Name: AN Label: Accession Number Group: ID Data: edsarx.2404.02414 |
| PLink | https://login.libproxy.scu.edu/login?url=https://search.ebscohost.com/login.aspx?direct=true&site=eds-live&scope=site&db=edsarx&AN=edsarx.2404.02414 |
| RecordInfo | BibRecord: BibEntity: Subjects: – SubjectFull: Quantum Physics Type: general – SubjectFull: Computer Science - Computational Complexity Type: general – SubjectFull: Computer Science - Data Structures and Algorithms Type: general – SubjectFull: Mathematics - Statistics Theory Type: general Titles: – TitleFull: A simple lower bound for the complexity of estimating partition functions on a quantum computer Type: main BibRelationships: HasContributorRelationships: – PersonEntity: Name: NameFull: Chen, Zherui – PersonEntity: Name: NameFull: Nannicini, Giacomo IsPartOfRelationships: – BibEntity: Dates: – D: 02 M: 04 Type: published Y: 2024 |
| ResultId | 1 |