Built on

D. Hangleiter, I. Roth, D. Nagaj, and J. Eisert, Easing the Monte Carlo sign problem , Science Advances 6
Original
1906
Earlier work this paper cites.
Y. Bao, S. Choi, and E. Altman, Theory of the phase transition in random unitary circuits with measurements , Phys. Rev. B 101
Original
1908
Earlier work this paper cites.
C.-M. Jian, Y.-Z. You, R. Vasseur, and A. W. W. Ludwig, Measurement-induced criticality in random quantum circuits , Phys. Rev. B 101
Original
1908
Earlier work this paper cites.
F. Barahona, On the computational complexity of Ising spin glass models , J. Phys. A 15
1982
Earlier work this paper cites.
L. Stockmeyer, The complexity of approximate counting , in Proceedings of the fifteenth annual ACM symposium on Theory of computing - STOC ’83 , STOC ’83 (ACM Press, 1983)
1983
Earlier work this paper cites.
S. L. Braunstein, C. M. Caves, R. Jozsa, N. Linden, S. Popescu, and R. Schack, Separability of Very Noisy Mixed States and Implications for NMR Quantum Computing , Phys. Rev. Lett. 83
1999
Earlier work this paper cites.
J. Napp, R. L. L. Placa, A. M. Dalzell, F. G. S. L. Brandao, and A. W. Harrow, Efficient classical simulation of random shallow 2D quantum circuits , Phys. Rev. X 12
Original
2001
Earlier work this paper cites.
B. Collins, Moments and cumulants of polynomial random variables on unitary groups, the Itzykson-Zuber integral, and free probability , Int. Math. Res. Not. 17
2003
Earlier work this paper cites.
F. Verstraete and J. I. Cirac, Renormalization algorithms for Quantum-Many Body Systems in two and higher dimensions , (2004), cond-mat/0407066
2004
Earlier work this paper cites.
M. Ippoliti, M. J. Gullans, S. Gopalakrishnan, D. A. Huse, and V. Khemani, Entanglement Phase Transitions in Measurement-Only Dynamics , Phys. Rev. X 11
Original
2004
Earlier work this paper cites.
M. Troyer and U.-J. Wiese, Computational Complexity and Fundamental Limitations to Fermionic Quantum Monte Carlo Simulations , Phys. Rev. Lett. 94
2005
Earlier work this paper cites.
S. Aaronson, Quantum Computing, Postselection, and Probabilistic Polynomial-Time , Proc. R. Soc. Lond. A 461
2005
Earlier work this paper cites.
J. Kempe, A. Kitaev, and O. Regev, The Complexity of the Local Hamiltonian Problem , SIAM Journal of Computing 35
2006
Earlier work this paper cites.

Similar

P. Hayden, D. W. Leung, and A. Winter, Aspects of Generic Entanglement , Commun. Math. Phys. 265
2006
Cited alongside, same era.
J. Eisert, Computational Difficulty of Global Variations in the Density Matrix Renormalization Group , Phys. Rev. Lett. 97
2006
Cited alongside, same era.
N. Schuch, M. M. Wolf, F. Verstraete, and J. I. Cirac, The computational complexity of PEPS , Phys. Rev. Lett. 98
2007
Cited alongside, same era.
S. Bravyi, D. P. DiVincenzo, R. I. Oliveira, and B. M. Terhal, The Complexity of Stoquastic Local Hamiltonian Problems , Quant. Inf. Comput. 8
2008
Cited alongside, same era.
J. Jordan, R. Orus, G. Vidal, F. Verstraete, and J. I. Cirac, Classical simulation of infinite-size quantum lattice systems in two spatial dimensions , Phys. Rev. Lett. 101
2008
Cited alongside, same era.

Then

Z. Landau, U. Vazirani, and T. Vidick, A polynomial time algorithm for the ground state of one-dimensional gapped local Hamiltonians , Nature Phys. 11
Original
2015
Later among the works it cites.
P. Hayden, S. Nezami, X.-L. Qi, N. Thomas, M. Walter, and Z. Yang, Holographic duality from random tensor networks , Journal of High Energy Physics 2016
Original
2016
Later among the works it cites.
A. Barvinok, Computing the permanent of (some) complex matrices , Foundations of Computational Mathematics 16
Original
2016
Later among the works it cites.
F. Becca and S. Sorella, Quantum Monte Carlo Approaches for Correlated Systems (Cambridge University Press, 2017)
2017
Later among the works it cites.
L. Eldar and S. Mehraban, Approximating the permanent of a random matrix with vanishing mean , in 2018 IEEE 59th Annual Symposium on Foundations of Computer Science (FOCS) (IEEE, 2018) pp. 23–34, arXiv:1711.09457

Beyond the bibliography

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

Open on alphaXiv

alphaXiv is searching for related work…

Reading the bibliography…

2024

Sign problem in tensor network contraction

Chen, Jielun, Jiang, Jiaqing, Hangleiter, Dominik et al.

Understand

We investigate how the computational difficulty of contracting tensor networks depends on the sign structure of the tensor entries.

Using results from computational complexity, we observe that the approximate contraction of tensor networks with only positive entries has lower complexity.
This raises the question how this transition in computational complexity manifests itself in the hardness of different contraction schemes.
We pursue this question by studying random tensor networks with varying bias towards positive entries.

Built on

D. Hangleiter, I. Roth, D. Nagaj, and J. Eisert, Easing the Monte Carlo sign problem , Science Advances 6
Original
1906
Earlier work this paper cites.
Y. Bao, S. Choi, and E. Altman, Theory of the phase transition in random unitary circuits with measurements , Phys. Rev. B 101
Original
1908
Earlier work this paper cites.
C.-M. Jian, Y.-Z. You, R. Vasseur, and A. W. W. Ludwig, Measurement-induced criticality in random quantum circuits , Phys. Rev. B 101
Original
1908
Earlier work this paper cites.
F. Barahona, On the computational complexity of Ising spin glass models , J. Phys. A 15
1982
Earlier work this paper cites.
L. Stockmeyer, The complexity of approximate counting , in Proceedings of the fifteenth annual ACM symposium on Theory of computing - STOC ’83 , STOC ’83 (ACM Press, 1983)
1983
Earlier work this paper cites.
S. L. Braunstein, C. M. Caves, R. Jozsa, N. Linden, S. Popescu, and R. Schack, Separability of Very Noisy Mixed States and Implications for NMR Quantum Computing , Phys. Rev. Lett. 83
1999
Earlier work this paper cites.
J. Napp, R. L. L. Placa, A. M. Dalzell, F. G. S. L. Brandao, and A. W. Harrow, Efficient classical simulation of random shallow 2D quantum circuits , Phys. Rev. X 12
Original
2001
Earlier work this paper cites.
B. Collins, Moments and cumulants of polynomial random variables on unitary groups, the Itzykson-Zuber integral, and free probability , Int. Math. Res. Not. 17
2003
Earlier work this paper cites.
F. Verstraete and J. I. Cirac, Renormalization algorithms for Quantum-Many Body Systems in two and higher dimensions , (2004), cond-mat/0407066
2004
Earlier work this paper cites.
M. Ippoliti, M. J. Gullans, S. Gopalakrishnan, D. A. Huse, and V. Khemani, Entanglement Phase Transitions in Measurement-Only Dynamics , Phys. Rev. X 11
Original
2004
Earlier work this paper cites.
M. Troyer and U.-J. Wiese, Computational Complexity and Fundamental Limitations to Fermionic Quantum Monte Carlo Simulations , Phys. Rev. Lett. 94
2005
Earlier work this paper cites.
S. Aaronson, Quantum Computing, Postselection, and Probabilistic Polynomial-Time , Proc. R. Soc. Lond. A 461
2005
Earlier work this paper cites.
J. Kempe, A. Kitaev, and O. Regev, The Complexity of the Local Hamiltonian Problem , SIAM Journal of Computing 35
2006
Earlier work this paper cites.

Similar

P. Hayden, D. W. Leung, and A. Winter, Aspects of Generic Entanglement , Commun. Math. Phys. 265
2006
Cited alongside, same era.
J. Eisert, Computational Difficulty of Global Variations in the Density Matrix Renormalization Group , Phys. Rev. Lett. 97
2006
Cited alongside, same era.
N. Schuch, M. M. Wolf, F. Verstraete, and J. I. Cirac, The computational complexity of PEPS , Phys. Rev. Lett. 98
2007
Cited alongside, same era.
S. Bravyi, D. P. DiVincenzo, R. I. Oliveira, and B. M. Terhal, The Complexity of Stoquastic Local Hamiltonian Problems , Quant. Inf. Comput. 8
2008
Cited alongside, same era.
J. Jordan, R. Orus, G. Vidal, F. Verstraete, and J. I. Cirac, Classical simulation of infinite-size quantum lattice systems in two spatial dimensions , Phys. Rev. Lett. 101
2008
Cited alongside, same era.