Fetching the paper…

Reading the bibliography…

2020

Efficient Algorithms for Approximating Quantum Partition Functions

Mann, Ryan L., Helmuth, Tyler

Original
PDF
Post on X

Understand

We establish a polynomial-time approximation algorithm for partition functions of quantum spin models at high temperature.

Our algorithm is based on the quantum cluster expansion of Neto\v{c}n\'y and Redig and the cluster expansion approach to designing algorithms due to Helmuth, Perkins, and Regts.
Similar results have previously been obtained by related methods, and our main contribution is a simple and slightly sharper analysis for the case of pairwise interactions on bounded-degree graphs.

Efficient Algorithms for Approximating Quantum Partition Functions · Around

Built on

Z. Chen, A. Galanis, L. A. Goldberg, W. Perkins, J. Stewart, and E. Vigoda, in Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2019) (Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik, 2019) arXiv:1901.06653
Original
1901
Earlier work this paper cites.
C. Liao, J. Lin, P. Lu, and Z. Mao, in Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2019) (Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik, 2019) arXiv:1903.07531
Original
1903
Earlier work this paper cites.
S. Bravyi, D. Gosset, and R. Movassagh, arXiv e-prints (2019), arXiv:1909.11485
Original
1909
Earlier work this paper cites.
C. Borgs, J. Chayes, T. Helmuth, W. Perkins, and P. Tetali, in Proceedings of the 52nd Annual ACM SIGACT Symposium on Theory of Computing (ACM, 2020) pp. 738–751, arXiv:1909.09298
Original
1909
Earlier work this paper cites.
A. W. Harrow, S. Mehraban, and M. Soleimanifar, in Proceedings of the 52nd Annual ACM SIGACT Symposium on Theory of Computing (ACM, 2020) pp. 378–386, arXiv:1910.09071
Original
1910
Earlier work this paper cites.
T. Kuwahara, K. Kato, and F. G. Brandão, Physical Review Letters 124
Original
1910
Earlier work this paper cites.
J. Mayer and M. Mayer, Statistical Mechanics (John Wiley & Sons, Inc., 1940)
1940
Earlier work this paper cites.
H. J. Ryser, Combinatorial Mathematics , Vol. 14 (Mathematical Association of America, 1963)
1963
Earlier work this paper cites.
Y. M. Park, Journal of Statistical Physics 27
1982
Earlier work this paper cites.
R. Kotecký and D. Preiss, Communications in Mathematical Physics 103
1986
Earlier work this paper cites.
M. Jerrum and A. Sinclair, SIAM Journal on Computing 22
1993
Earlier work this paper cites.

Similar

C. Borgs, R. Kotecký, and D. Ueltschi, Communications in Mathematical Physics 181
1996
Cited alongside, same era.
D. Ueltschi, Discontinuous Phase Transitions in Quantum Lattice Systems , Ph.D. thesis, Verlag nicht ermittelbar (1998)
1998
Cited alongside, same era.
E. Crosson and S. Slezak, arXiv e-prints (2020), arXiv:2002.02232
Original
2002
Cited alongside, same era.
C. Carlson, E. Davies, and A. Kolla, arXiv e-prints (2020), arXiv:2003.01154
Original
2003
Cited alongside, same era.
K. Netočný and F. Redig, Journal of Statistical Physics 117
2004
Cited alongside, same era.

Then

S. Bravyi, Quantum Information and Computation 15
Original
2015
Later among the works it cites.
A. Galanis, D. Štefankovič, and E. Vigoda, Combinatorics, Probability and Computing 25
Original
2016
Later among the works it cites.
A. Barvinok, Combinatorics and Complexity of Partition Functions , Vol. 274 (Springer, 2016)
2016
Later among the works it cites.
L. A. Goldberg and H. Guo, Computational Complexity 26
Original
2017
Later among the works it cites.
V. Patel and G. Regts, SIAM Journal on Computing 46
Original
2017
Later among the works it cites.

Beyond the bibliography

alphaXiv searches the wider corpus for related work and actual follow-ups.

Open on alphaXiv

alphaXiv is searching for related work…

D. Weitz, in Proceedings of the Thirty-Eighth Annual ACM Symposium on Theory of Computing (ACM, 2006) pp. 140–149

2006

Cited alongside, same era.

A. Björklund, T. Husfeldt, P. Kaski, and M. Koivisto, in 49th Annual IEEE Symposium on Foundations of Computer Science (IEEE, 2008) pp. 677–686, arXiv:0711.2585

2008

Cited alongside, same era.

S. Arora and B. Barak, Computational Complexity: A Modern Approach (Cambridge University Press, 2009)

2009

Cited alongside, same era.

M. J. Bremner, R. Jozsa, and D. J. Shepherd, in Proceedings of the Royal Society of London A: Mathematical, Physical and Engineering Sciences (The Royal Society, 2010) p. rspa20100301, arXiv:1005.1407

2010

Cited alongside, same era.

A. Sly and N. Sun, in 53rd Annual IEEE Symposium on Foundations of Computer Science (FOCS) (IEEE, 2012) pp. 361–369, arXiv:1203.2602

2012

Cited alongside, same era.

C. Borgs, J. Chayes, J. Kahn, and L. Lovász, Random Structures & Algorithms 42

2013

Cited alongside, same era.

S. Friedli and Y. Velenik, Statistical Mechanics of Lattice Systems: A Concrete Mathematical Introduction (Cambridge University Press, 2017)

2017

Later among the works it cites.

R. L. Mann and M. J. Bremner, Quantum 3

2019

Later among the works it cites.

J. Liu, A. Sinclair, and P. Srivastava, Journal of Statistical Physics 174

2019

Later among the works it cites.

M. Jenssen, P. Keevash, and W. Perkins, in Proceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms (SIAM, 2019) pp. 2235–2247, arXiv:1807.04804

2019

Later among the works it cites.

T. Helmuth, W. Perkins, and G. Regts, Probability Theory and Related Fields 176

2020

Closest in time.