.png){kind=icon}
.png){kind=icon}
Return
Algorithmic Cluster Expansions for Quantum Problems
.png){kind=icon}
OA
AI
DOI：10.1103/PRXQuantum.5.010305.png)
.png){kind=icon}
Original request for help.png){kind=icon}
Share.png){kind=icon}
Save
Abstract
En 中文
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 KoteckATIN SMALL LETTER Y WITH ACUTE 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.
Keywords:
APPROXIMATION ALGORITHMS
PARTITION-FUNCTIONS
COMPLEXITY
Journal
P
IF:
11
Papers:
919
Citations:
9.0K