Amplitude Ratios and Neural Network Quantum States

Vojtech Havlicek

IBM Quantum, IBM T.J. Watson Research Center

Find this paper interesting or want to discuss? Scite or leave a comment on SciRate.

Abstract

Neural Network Quantum States (NQS) represent quantum wavefunctions by artificial neural networks. Here we study the wavefunction access provided by NQS defined in [Science, 355, 6325, pp. 602-606 (2017)] and relate it to results from distribution testing. This leads to improved distribution testing algorithms for such NQS. It also motivates an independent definition of a wavefunction access model: the amplitude ratio access. We compare it to sample and sample and query access models, previously considered in the study of dequantization of quantum algorithms. First, we show that the amplitude ratio access is strictly stronger than sample access. Second, we argue that the amplitude ratio access is strictly weaker than sample and query access, but also show that it retains many of its simulation capabilities. Interestingly, we only show such separation under computational assumptions. Lastly, we use the connection to distribution testing algorithms to produce an NQS with just three nodes that does not encode a valid wavefunction and cannot be sampled from.

► BibTeX data

► References

[1] Scott Aaronsonand Alex Arkhipov ``The Computational Complexity of Linear Optics'' (2011).
https:/​/​doi.org/​10.1145/​1993636.1993682

[2] Clement Cannone Personal communication (2021).

[3] Clément L. Canonne, Dana Ron, and Rocco A. Servedio, ``Testing Probability Distributions using Conditional Samples'' SIAM Journal on Computing 44, 540–616 (2015).
https:/​/​doi.org/​10.1137/​130945508

[4] Clement L. Canonne, Xi Chen, Gautam Kamath, Amit Levi, and Erik Waingarten, ``Random Restrictions of High Dimensional Distributions and Uniformity Testing with Subcube Conditioning'' Proceedings of the Thirty-Second Annual ACM-SIAM Symposium on Discrete Algorithms 321–336 (2021).

[5] Giuseppe Carleo, Yusuke Nomura, and Masatoshi Imada, ``Constructing exact representations of quantum many-body systems with deep neural networks'' Nature Communications 9, 5322 (2018).
https:/​/​doi.org/​10.1038/​s41467-018-07520-3

[6] Giuseppe Carleoand Matthias Troyer ``Solving the quantum many-body problem with artificial neural networks'' Science 355, 602–606 (2017).
https:/​/​doi.org/​10.1126/​science.aag2302

[7] Sourav Chakraborty, Eldar Fischer, Yonatan Goldhirsh, and Arie Matsliah, ``On the Power of Conditional Samples in Distribution Testing'' Proceedings of the 4th Conference on Innovations in Theoretical Computer Science 561–580 (2013).
https:/​/​doi.org/​10.1145/​2422436.2422497

[8] Martin Dyer, Alan Frieze, and Ravi Kannan, ``A Random Polynomial-Time Algorithm for Approximating the Volume of Convex Bodies'' J. ACM 38, 1–17 (1991).
https:/​/​doi.org/​10.1145/​102782.102783

[9] Alan Frieze, Ravi Kannan, and Santosh Vempala, ``Fast Monte-Carlo Algorithms for Finding Low-Rank Approximations'' J. ACM 51, 1025–1041 (2004).
https:/​/​doi.org/​10.1145/​1039488.1039494

[10] Xun Gaoand Lu-Ming Duan ``Efficient representation of quantum many-body states with deep neural networks'' Nature Communications 8, 662 (2017).
https:/​/​doi.org/​10.1038/​s41467-017-00705-2

[11] Vojtech Havlicekand Sergii Strelchuk ``Quantum Schur Sampling Circuits can be Strongly Simulated'' Phys. Rev. Lett. 121, 060505 (2018).
https:/​/​doi.org/​10.1103/​PhysRevLett.121.060505

[12] Geoffrey E. Hinton ``Training Products of Experts by Minimizing Contrastive Divergence'' Neural Computation 14, 1771–1800 (2002).
https:/​/​doi.org/​10.1162/​089976602760128018

[13] Mark Huber ``Approximation algorithms for the normalizing constant of Gibbs distributions'' The Annals of Applied Probability 25 (2015).
https:/​/​doi.org/​10.1214/​14-aap1015

[14] Mark Jerrum ``Random Generation of Combinatorial Structures from a Uniform Distribution (Extended Abstract)'' Proceedings of the 12th Colloquium on Automata, Languages and Programming 290–299 (1985).

[15] Mark R. Jerrum, Leslie G. Valiant, and Vijay V. Vazirani, ``Random generation of combinatorial structures from a uniform distribution'' Theoretical Computer Science 43, 169–188 (1986).
https:/​/​doi.org/​10.1016/​0304-3975(86)90174-X
https:/​/​www.sciencedirect.com/​science/​article/​pii/​030439758690174X

[16] Bjarni Jónsson, Bela Bauer, and Giuseppe Carleo, ``Neural-network states for the classical simulation of quantum computing'' arXiv e-prints arXiv:1808.05232 (2018).
https:/​/​doi.org/​10.48550/​ARXIV.1808.05232
arXiv:1808.05232

[17] Richard M Karp, Michael Luby, and Neal Madras, ``Monte-Carlo approximation algorithms for enumeration problems'' Journal of Algorithms 10, 429–448 (1989).
https:/​/​doi.org/​10.1016/​0196-6774(89)90038-2
https:/​/​www.sciencedirect.com/​science/​article/​pii/​0196677489900382

[18] Matthieu Lerasle ``Lecture Notes: Selected topics on robust statistical learning theory'' arXiv e-prints arXiv:1908.10761 (2019).
https:/​/​doi.org/​10.48550/​ARXIV.1908.10761
arXiv:1908.10761

[19] Philip M. Longand Rocco A. Servedio ``Restricted Boltzmann Machines Are Hard to Approximately Evaluate or Simulate'' Proceedings of the 27th International Conference on International Conference on Machine Learning 703–710 (2010).

[20] James Martens, Arkadev Chattopadhya, Toni Pitassi, and Richard Zemel, ``On the Representational Efficiency of Restricted Boltzmann Machines'' Curran Associates, Inc. (2013).
http:/​/​papers.nips.cc/​paper/​5020-on-the-representational-efficiency-of-restricted-boltzmann-machines.pdf

[21] Matija Medvidovićand Giuseppe Carleo ``Classical variational simulation of the Quantum Approximate Optimization Algorithm'' npj Quantum Information 7, 101 (2021).
https:/​/​doi.org/​10.1038/​s41534-021-00440-z
arXiv:2009.01760

[22] Imdad S. B. Sardharwalla, Sergii Strelchuk, and Richard Jozsa, ``Quantum Conditional Query Complexity'' Quantum Info. Comput. 17, 541–567 (2017).

[23] P. Smolensky ``Information Processing in Dynamical Systems: Foundations of Harmony Theory'' MIT Press (1986).

[24] Daniel Štefankovič, Santosh Vempala, and Eric Vigoda, ``Adaptive Simulated Annealing: A near-Optimal Connection between Sampling and Counting'' J. ACM 56 (2009).
https:/​/​doi.org/​10.1145/​1516512.1516520

[25] Ewin Tang ``A Quantum-Inspired Classical Algorithm for Recommendation Systems'' Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing 217–228 (2019).
https:/​/​doi.org/​10.1145/​3313276.3316310

[26] L.G. Valiant ``The complexity of computing the permanent'' Theoretical Computer Science 8, 189–201 (1979).
https:/​/​doi.org/​10.1016/​0304-3975(79)90044-6
https:/​/​www.sciencedirect.com/​science/​article/​pii/​0304397579900446

[27] Maarten Van Den Nest ``Simulating Quantum Computers with Probabilistic Methods'' Quantum Info. Comput. 11, 784–812 (2011).

Cited by

[1] Alessandro Sinibaldi, Clemens Giuliani, Giuseppe Carleo, and Filippo Vicentini, "Unbiasing time-dependent Variational Monte Carlo by projected quantum evolution", Quantum 7, 1131 (2023).

[2] Sergey Bravyi, Giuseppe Carleo, David Gosset, and Yinchen Liu, "A rapidly mixing Markov chain from any gapped quantum many-body system", Quantum 7, 1173 (2023).

[3] Anna Dawid, Julian Arnold, Borja Requena, Alexander Gresch, Marcin Płodzień, Kaelan Donatella, Kim A. Nicoli, Paolo Stornati, Rouven Koch, Miriam Büttner, Robert Okuła, Gorka Muñoz-Gil, Rodrigo A. Vargas-Hernández, Alba Cervera-Lierta, Juan Carrasquilla, Vedran Dunjko, Marylou Gabrié, Patrick Huembeli, Evert van Nieuwenburg, Filippo Vicentini, Lei Wang, Sebastian J. Wetzel, Giuseppe Carleo, Eliška Greplová, Roman Krems, Florian Marquardt, Michał Tomza, Maciej Lewenstein, and Alexandre Dauphin, "Modern applications of machine learning in quantum sciences", arXiv:2204.04198, (2022).

The above citations are from Crossref's cited-by service (last updated successfully 2024-05-21 17:41:20) and SAO/NASA ADS (last updated successfully 2024-05-21 17:41:21). The list may be incomplete as not all publishers provide suitable and complete citation data.