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 |
| Description not available. |