Algorithmic Cluster Expansions for Quantum Problems
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 probab...
| Main Authors: | , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
American Physical Society
2024-01-01
|
| Series: | PRX Quantum |
| Online Access: | http://doi.org/10.1103/PRXQuantum.5.010305 |
| _version_ | 1797353862612385792 |
|---|---|
| author | Ryan L. Mann Romy M. Minko |
| author_facet | Ryan L. Mann Romy M. Minko |
| author_sort | Ryan L. Mann |
| collection | DOAJ |
| description | 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. |
| first_indexed | 2024-03-08T13:37:07Z |
| format | Article |
| id | doaj.art-2dd171b696a24583a5f6dca4a527f5ec |
| institution | Directory Open Access Journal |
| issn | 2691-3399 |
| language | English |
| last_indexed | 2024-03-08T13:37:07Z |
| publishDate | 2024-01-01 |
| publisher | American Physical Society |
| record_format | Article |
| series | PRX Quantum |
| spelling | doaj.art-2dd171b696a24583a5f6dca4a527f5ec2024-01-16T15:49:36ZengAmerican Physical SocietyPRX Quantum2691-33992024-01-015101030510.1103/PRXQuantum.5.010305Algorithmic Cluster Expansions for Quantum ProblemsRyan L. MannRomy M. MinkoWe 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.http://doi.org/10.1103/PRXQuantum.5.010305 |
| spellingShingle | Ryan L. Mann Romy M. Minko Algorithmic Cluster Expansions for Quantum Problems PRX Quantum |
| title | Algorithmic Cluster Expansions for Quantum Problems |
| title_full | Algorithmic Cluster Expansions for Quantum Problems |
| title_fullStr | Algorithmic Cluster Expansions for Quantum Problems |
| title_full_unstemmed | Algorithmic Cluster Expansions for Quantum Problems |
| title_short | Algorithmic Cluster Expansions for Quantum Problems |
| title_sort | algorithmic cluster expansions for quantum problems |
| url | http://doi.org/10.1103/PRXQuantum.5.010305 |
| work_keys_str_mv | AT ryanlmann algorithmicclusterexpansionsforquantumproblems AT romymminko algorithmicclusterexpansionsforquantumproblems |