1MIT Center for Theoretical Physics, 77 Massachusetts Avenue, Cambridge, MA 02139, USA
2Dahlem Centre for Complex Quantum Systems, Freie Universität Berlin, Arnimallee 14, 14195 Berlin, Germany
3MIT Department of Electrical Engineering and Computer Science, 77 Massachusetts Avenue, Cambridge, MA 02139, USA
4MIT Department of Mechanical Engineering, 77 Massachusetts Avenue, Cambridge, MA 02139, USA
5Turing Inc., Cambridge, MA 02139, USA
Find this paper interesting or want to discuss? Scite or leave a comment on SciRate.
Abstract
In light of recently proposed quantum algorithms that incorporate symmetries in the hope of quantum advantage, we show that with symmetries that are restrictive enough, classical algorithms can efficiently emulate their quantum counterparts given certain classical descriptions of the input. Specifically, we give classical algorithms that calculate ground states and time-evolved expectation values for permutation-invariant Hamiltonians specified in the symmetrized Pauli basis with runtimes polynomial in the system size. We use tensor-network methods to transform symmetry-equivariant operators to the block-diagonal Schur basis that is of polynomial size, and then perform exact matrix multiplication or diagonalization in this basis. These methods are adaptable to a wide range of input and output states including those prescribed in the Schur basis, as matrix product states, or as arbitrary quantum states when given the power to apply low depth circuits and single qubit measurements.
Featured image: Small groups of symmetry leave too large of an effective dimension for the problem to be tractable via quantum computation. On the contrary, very restrictive symmetries render a problem classically tractable. Between these two regions lies an area of promise where quantum computers may offer an advantage.
Popular summary
► BibTeX data
► References
[1] Hans Bethe. “Zur theorie der metalle”. Z. Phys. 71, 205–226 (1931).
https://doi.org/10.1007/BF01341708
[2] M. A. Levin and X.-G. Wen. “String-net condensation: A physical mechanism for topological phases”. Phys. Rev. B 71, 045110 (2005).
https://doi.org/10.1103/PhysRevB.71.045110
[3] A.A. Belavin, A.M. Polyakov, and A.B. Zamolodchikov. “Infinite conformal symmetry in two-dimensional quantum field theory”. Nucl. Phys. B 241, 333–380 (1984).
https://doi.org/10.1016/0550-3213(84)90052-X
[4] Louis Schatzki, Martin Larocca, Quynh T. Nguyen, Frederic Sauvage, and M. Cerezo. “Theoretical guarantees for permutation-equivariant quantum neural networks” (2022). arXiv:2210.09974.
arXiv:2210.09974
[5] Shouzhen Gu, Rolando D. Somma, and Burak Şahinoğlu. “Fast-forwarding quantum evolution”. Quantum 5, 577 (2021).
https://doi.org/10.22331/q-2021-11-15-577
[6] Roeland Wiersema, Cunlu Zhou, Yvette de Sereville, Juan Felipe Carrasquilla, Yong Baek Kim, and Henry Yuen. “Exploring entanglement and optimization within the Hamiltonian variational ansatz”. PRX Quantum 1, 020319 (2020).
https://doi.org/10.1103/PRXQuantum.1.020319
[7] Eric Ricardo Anschuetz. “Critical points in quantum generative models”. In International Conference on Learning Representations. (2022). url: https://openreview.net/forum?id=2f1z55GVQN.
https://openreview.net/forum?id=2f1z55GVQN
[8] Rolando Somma, Howard Barnum, Gerardo Ortiz, and Emanuel Knill. “Efficient solvability of Hamiltonians and limits on the power of some quantum computational models”. Phys. Rev. Lett. 97, 190501 (2006).
https://doi.org/10.1103/PhysRevLett.97.190501
[9] Robert Zeier and Thomas Schulte-Herbrüggen. “Symmetry principles in quantum systems theory”. J. Math. Phys. 52, 113510 (2011).
https://doi.org/10.1063/1.3657939
[10] Xuchen You, Shouvanik Chakrabarti, and Xiaodi Wu. “A convergence theory for over-parameterized variational quantum eigensolvers” (2022). arXiv:2205.12481.
arXiv:2205.12481
[11] Eric R. Anschuetz and Bobak T. Kiani. “Quantum variational algorithms are swamped with traps”. Nat. Commun. 13, 7760 (2022).
https://doi.org/10.1038/s41467-022-35364-5
[12] Grecia Castelazo, Quynh T. Nguyen, Giacomo De Palma, Dirk Englund, Seth Lloyd, and Bobak T. Kiani. “Quantum algorithms for group convolution, cross-correlation, and equivariant transformations”. Phys. Rev. A 106, 032402 (2022).
https://doi.org/10.1103/PhysRevA.106.032402
[13] Johannes Jakob Meyer, Marian Mularski, Elies Gil-Fuster, Antonio Anna Mele, Francesco Arzani, Alissa Wilms, and Jens Eisert. “Exploiting symmetry in variational quantum machine learning” (2022).
https://doi.org/10.1103/PRXQuantum.4.010328
[14] Martín Larocca, Frédéric Sauvage, Faris M. Sbahi, Guillaume Verdon, Patrick J. Coles, and M. Cerezo. “Group-invariant quantum machine learning”. PRX Quantum 3, 030341 (2022).
https://doi.org/10.1103/PRXQuantum.3.030341
[15] Michael Ragone, Paolo Braccia, Quynh T Nguyen, Louis Schatzki, Patrick J Coles, Frederic Sauvage, Martin Larocca, and M Cerezo. “Representation theory for geometric quantum machine learning” (2022). arXiv:2210.07980.
arXiv:2210.07980
[16] Michael M. Bronstein, Joan Bruna, Yann LeCun, Arthur Szlam, and Pierre Vandergheynst. “Geometric deep learning: Going beyond Euclidean data”. IEEE Signal Process. Mag. 34, 18–42 (2017).
https://doi.org/10.1109/MSP.2017.2693418
[17] Zonghan Wu, Shirui Pan, Fengwen Chen, Guodong Long, Chengqi Zhang, and Philip S. Yu. “A comprehensive survey on graph neural networks”. IEEE Trans. Neural Netw. Learn. Syst. 32, 4–24 (2021).
https://doi.org/10.1109/TNNLS.2020.2978386
[18] Taco Cohen and Max Welling. “Group equivariant convolutional networks”. In Maria Florina Balcan and Kilian Q. Weinberger, editors, Proceedings of The 33rd International Conference on Machine Learning. Volume 48 of Proceedings of Machine Learning Research, pages 2990–2999. New York, New York, USA (2016). PMLR. url: https://proceedings.mlr.press/v48/cohenc16.html.
https://proceedings.mlr.press/v48/cohenc16.html
[19] Peter J. Olver. “Classical invariant theory”. London Mathematical Society Student Texts. Cambridge University Press. Cambridge, UK (1999).
https://doi.org/10.1017/CBO9780511623660
[20] Bernd Sturmfels. “Algorithms in invariant theory”. Texts & Monographs in Symbolic Computation. Springer Vienna. Vienna, Austria (2008).
https://doi.org/10.1007/978-3-211-77417-5
[21] Ran Duan, Hongxun Wu, and Renfei Zhou. “Faster matrix multiplication via asymmetric hashing” (2022). arXiv:2210.10173.
arXiv:2210.10173
[22] James Demmel, Ioana Dumitriu, and Olga Holtz. “Fast linear algebra is stable”. Numer. Math. 108, 59–91 (2007).
https://doi.org/10.1007/s00211-007-0114-x
[23] Barbara M. Terhal and David P. DiVincenzo. “Classical simulation of noninteracting-fermion quantum circuits”. Phys. Rev. A 65, 032325 (2002).
https://doi.org/10.1103/PhysRevA.65.032325
[24] Nathan Shammah, Shahnawaz Ahmed, Neill Lambert, Simone De Liberato, and Franco Nori. “Open quantum systems with local and collective incoherent processes: Efficient numerical simulations using permutational invariance”. Phys. Rev. A 98, 063815 (2018).
https://doi.org/10.1103/PhysRevA.98.063815
[25] Guang Hao Low. “Classical shadows of fermions with particle number symmetry” (2022). arXiv:2208.08964.
arXiv:2208.08964
[26] Dave Bacon, Isaac L. Chuang, and Aram W. Harrow. “Efficient quantum circuits for Schur and Clebsch-Gordan transforms”. Phys. Rev. Lett. 97, 170502 (2006).
https://doi.org/10.1103/PhysRevLett.97.170502
[27] Dave Bacon, Isaac L. Chuang, and Aram W. Harrow. “The quantum Schur transform: I. efficient qudit circuits” (2006). arXiv:quant-ph/0601001.
arXiv:quant-ph/0601001
[28] William M. Kirby and Frederick W. Strauch. “A practical quantum algorithm for the Schur transform”. Quantum Info. Comput. 18, 721–742 (2018). url: https://dl.acm.org/doi/10.5555/3370214.3370215.
https://dl.acm.org/doi/10.5555/3370214.3370215
[29] Michael Gegg and Marten Richter. “Efficient and exact numerical approach for many multi-level systems in open system CQED”. New J. Phys. 18, 043037 (2016).
https://doi.org/10.1088/1367-2630/18/4/043037
[30] Hsin-Yuan Huang, Richard Kueng, and John Preskill. “Predicting many properties of a quantum system from very few measurements”. Nat. Phys. 16, 1050–1057 (2020).
https://doi.org/10.1038/s41567-020-0932-7
[31] Yunchao Liu, Srinivasan Arunachalam, and Kristan Temme. “A rigorous and robust quantum speed-up in supervised machine learning”. Nat. Phys. 17, 1013–1017 (2021).
https://doi.org/10.1038/s41567-021-01287-z
[32] Jarrod R McClean, Sergio Boixo, Vadim N Smelyanskiy, Ryan Babbush, and Hartmut Neven. “Barren plateaus in quantum neural network training landscapes”. Nat. Commun. 9, 4812 (2018).
https://doi.org/10.1038/s41467-018-07090-4
[33] Marco Cerezo, Akira Sone, Tyler Volkoff, Lukasz Cincio, and Patrick J Coles. “Cost function dependent barren plateaus in shallow parametrized quantum circuits”. Nat. Commun. 12, 1791–1802 (2021).
https://doi.org/10.1038/s41467-021-21728-w
[34] Carlos Ortiz Marrero, Mária Kieferová, and Nathan Wiebe. “Entanglement-induced barren plateaus”. PRX Quantum 2, 040316 (2021).
https://doi.org/10.1103/PRXQuantum.2.040316
[35] John Napp. “Quantifying the barren plateau phenomenon for a model of unstructured variational ansätze” (2022). arXiv:2203.06174.
arXiv:2203.06174
[36] Martin Larocca, Piotr Czarnik, Kunal Sharma, Gopikrishnan Muraleedharan, Patrick J. Coles, and M. Cerezo. “Diagnosing barren plateaus with tools from quantum optimal control”. Quantum 6, 824 (2022).
https://doi.org/10.22331/q-2022-09-29-824
[37] Martin Larocca, Nathan Ju, Diego García-Martín, Patrick J. Coles, and M. Cerezo. “Theory of overparametrization in quantum neural networks” (2021).
https://doi.org/10.1038/s43588-023-00467-6
[38] Bradley A. Chase and J. M. Geremia. “Collective processes of an ensemble of spin-$1/2$ particles”. Phys. Rev. A 78, 052101 (2008).
https://doi.org/10.1103/PhysRevA.78.052101
[39] Peter Kirton and Jonathan Keeling. “Superradiant and lasing states in driven-dissipative Dicke models”. New J. Phys. 20, 015009 (2018).
https://doi.org/10.1088/1367-2630/aaa11d
[40] Athreya Shankar, John Cooper, Justin G. Bohnet, John J. Bollinger, and Murray Holland. “Steady-state spin synchronization through the collective motion of trapped ions”. Phys. Rev. A 95, 033423 (2017).
https://doi.org/10.1103/PhysRevA.95.033423
[41] Ryszard Horodecki, Paweł Horodecki, Michał Horodecki, and Karol Horodecki. “Quantum entanglement”. Rev. Mod. Phys. 81, 865–942 (2009).
https://doi.org/10.1103/RevModPhys.81.865
[42] Zheshen Zhang and Quntao Zhuang. “Distributed quantum sensing”. Quantum Sci. Technol. 6, 043001 (2021).
https://doi.org/10.1088/2058-9565/abd4c3
[43] Robert Alicki, Sławomir Rudnicki, and Sławomir Sadowski. “Symmetry properties of product states for the system of N n‐level atoms”. J. Math. Phys. 29, 1158–1162 (1988).
https://doi.org/10.1063/1.527958
[44] Ryan O’Donnell and John Wright. “Learning and testing quantum states via probabilistic combinatorics and representation theory”. Curr. Dev. Math. 2021, 43–94 (2021).
https://doi.org/10.4310/CDM.2021.v2021.n1.a2
[45] Andrew M. Childs, Aram W. Harrow, and Paweł Wocjan. “Weak Fourier-Schur sampling, the hidden subgroup problem, and the quantum collision problem”. In Wolfgang Thomas and Pascal Weil, editors, STACS 2007. Pages 598–609. Berlin (2007). Springer Berlin Heidelberg.
https://doi.org/10.1007/978-3-540-70918-3_51
[46] Dorit Aharonov and Sandy Irani. “Hamiltonian complexity in the thermodynamic limit”. In Stefano Leonardi and Anupam Gupta, editors, Proceedings of the 54th Annual ACM SIGACT Symposium on Theory of Computing. Pages 750–763. STOC 2022New York (2022). Association for Computing Machinery.
https://doi.org/10.1145/3519935.3520067
[47] James D. Watson and Toby S. Cubitt. “Computational complexity of the ground state energy density problem”. In Stefano Leonardi and Anupam Gupta, editors, Proceedings of the 54th Annual ACM SIGACT Symposium on Theory of Computing. Pages 764–775. STOC 2022New York (2022). Association for Computing Machinery.
https://doi.org/10.1145/3519935.3520052
[48] Eric R. Anschuetz, Hong-Ye Hu, Jin-Long Huang, and Xun Gao. “Interpretable quantum advantage in neural sequence learning”. PRX Quantum 4, 020338 (2023).
https://doi.org/10.1103/PRXQuantum.4.020338
[49] Jin-Quan Chen, Jialun Ping, and Fan Wang. “Group representation theory for physicists”. World Scientific Publishing. Singapore (2002). 2nd edition.
https://doi.org/10.1142/5019
[50] OEIS Foundation Inc. “The On-Line Encyclopedia of Integer Sequences” (2022). Published electronically at http://oeis.org, Sequence A000292.
http://oeis.org
[51] William Fulton. “Young tableaux: With applications to representation theory and geometry”. London Mathematical Society Student Texts. Cambridge University Press. Cambridge, UK (1996).
https://doi.org/10.1017/CBO9780511626241
[52] Kenneth R Davidson. “C*-algebras by example”. Volume 6 of Fields Institute Monographs. American Mathematical Society. Ann Arbor, USA (1996). url: https://bookstore.ams.org/fim-6.
https://bookstore.ams.org/fim-6
[53] Giulio Racah. “Theory of complex spectra. II”. Phys. Rev. 62, 438–462 (1942).
https://doi.org/10.1103/PhysRev.62.438
[54] Vojtěch Havlíček and Sergii Strelchuk. “Quantum Schur sampling circuits can be strongly simulated”. Phys. Rev. Lett. 121, 060505 (2018).
https://doi.org/10.1103/PhysRevLett.121.060505
[55] R. H. Dicke. “Coherence in spontaneous radiation processes”. Phys. Rev. 93, 99–110 (1954).
https://doi.org/10.1103/PhysRev.93.99
[56] Andreas Bärtschi and Stephan Eidenbenz. “Deterministic preparation of Dicke states”. In Leszek Antoni Gąsieniec, Jesper Jansson, and Christos Levcopoulos, editors, Fundamentals of Computation Theory. Pages 126–139. Cham (2019). Springer International Publishing.
https://doi.org/10.1007/978-3-030-25027-0_9
[57] N. J. Vilenkin and A. U. Klimyk. “Representation of Lie groups and special functions”. Volume 3. Springer Dordrecht. Dordrecht, Netherlands (1992).
https://doi.org/10.1007/978-94-017-2885-0
Cited by
[1] Matthew L. Goh, Martin Larocca, Lukasz Cincio, M. Cerezo, and Frédéric Sauvage, “Lie-algebraic classical simulations for variational quantum computing”, arXiv:2308.01432, (2023).
[2] Caleb Rotello, Eric B. Jones, Peter Graf, and Eliot Kapit, “Automated detection of symmetry-protected subspaces in quantum simulations”, Physical Review Research 5 3, 033082 (2023).
[3] Tobias Haug and M. S. Kim, “Generalization with quantum geometry for learning unitaries”, arXiv:2303.13462, (2023).
[4] Jamie Heredge, Charles Hill, Lloyd Hollenberg, and Martin Sevior, “Permutation Invariant Encodings for Quantum Machine Learning with Point Cloud Data”, arXiv:2304.03601, (2023).
[5] Léo Monbroussou, Jonas Landman, Alex B. Grilo, Romain Kukla, and Elham Kashefi, “Trainability and Expressivity of Hamming-Weight Preserving Quantum Circuits for Machine Learning”, arXiv:2309.15547, (2023).
The above citations are from SAO/NASA ADS (last updated successfully 2023-11-28 11:44:12). The list may be incomplete as not all publishers provide suitable and complete citation data.
Could not fetch Crossref cited-by data during last attempt 2023-11-28 11:44:01: Could not fetch cited-by data for 10.22331/q-2023-11-28-1189 from Crossref. This is normal if the DOI was registered recently.
This Paper is published in Quantum under the Creative Commons Attribution 4.0 International (CC BY 4.0) license. Copyright remains with the original copyright holders such as the authors or their institutions.
- SEO Powered Content & PR Distribution. Get Amplified Today.
- PlatoData.Network Vertical Generative Ai. Empower Yourself. Access Here.
- PlatoAiStream. Web3 Intelligence. Knowledge Amplified. Access Here.
- PlatoESG. Carbon, CleanTech, Energy, Environment, Solar, Waste Management. Access Here.
- PlatoHealth. Biotech and Clinical Trials Intelligence. Access Here.
- Source: https://quantum-journal.org/papers/q-2023-11-28-1189/
