A simple lower bound for the complexity of estimating partition functions on a quantum computer
<|reference_start|>A simple lower bound for the complexity of estimating partition functions on a quantum computer: 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.<|reference_end|>
@article{chen2024a,
    title={A simple lower bound for the complexity of estimating partition
  functions on a quantum computer},
    author={Zherui Chen, Giacomo Nannicini},
    journal={arXiv preprint arXiv:2404.02414},
    year={2024},
    archivePrefix={arXiv},
    eprint={2404.02414},
    primaryClass={quant-ph cs.CC cs.DS math.ST stat.TH}
}