Abstract
We establish a general framework for developing approximation algorithms for a class of counting problems. Our framework is based on the cluster expansion of the abstract polymer model formalism of Kotecký and Preiss. We apply our framework to obtain efficient algorithms for (1) approximating probability amplitudes of a class of quantum circuits close to the identity, (2) approximating expectation values of a class of quantum circuits with operators close to the identity, (3) approximating partition functions of a class of quantum spin systems at high temperature, and (4) approximating thermal expectation values of a class of quantum spin systems at high temperature with positive-semidefinite operators. Further, we obtain hardness of approximation results for approximating probability amplitudes of quantum circuits and partition functions of quantum spin systems. This establishes a computational complexity transition for these problems and shows that our algorithmic conditions are optimal under complexity-theoretic assumptions. Finally, we show that our algorithmic condition is almost optimal for expectation values and optimal for thermal expectation values in the sense of zero freeness.
- Received 6 July 2023
- Revised 15 October 2023
- Accepted 1 December 2023
DOI:https://doi.org/10.1103/PRXQuantum.5.010305
Published by the American Physical Society under the terms of the Creative Commons Attribution 4.0 International license. Further distribution of this work must maintain attribution to the author(s) and the published article's title, journal citation, and DOI.
Published by the American Physical Society
Physics Subject Headings (PhySH)
Popular Summary
The classification of the computational complexity of quantum problems is a crucial aspect of quantum information science, essential for understanding the capabilities and limitations of quantum computing. Our research focuses on the exploration of specific conditions under which quantum problems can be efficiently approximated using classical computational techniques. This not only enhances our understanding of quantum computing but opens new possibilities for its application.
We establish a general framework for developing approximating algorithms for quantum problems based on the cluster expansion. We apply this framework to obtain efficient approximation algorithms under certain algorithmic conditions for probability amplitudes, expectation values, partition functions, and thermal expectation values. Further, we obtain hardness of approximation results for probability amplitudes and partition functions, establishing a computational complexity transition and demonstrating the optimality of our algorithmic conditions under complexity-theoretic assumptions.
Our work offers a deeper understanding of the computational complexity of quantum problems, offering new insights into the tractability and intractability of these problems. This has significant implications for quantum computing, indicating that some problems are more suited to classical approximation than previously believed.
