Complexity Phase Transitions Generated by Entanglement

Creators: Ghosh, Soumik; Deshpande, Abhinav; Hangleiter, Dominik; Gorshkov, Alexey V.; Fefferman, Bill

Abstract

Entanglement is one of the physical properties of quantum systems responsible for the computational hardness of simulating quantum systems. But while the runtime of specific algorithms, notably tensor network algorithms, explicitly depends on the amount of entanglement in the system, it is unknown whether this connection runs deeper and entanglement can also cause inherent, algorithm-independent complexity. In this Letter, we quantitatively connect the entanglement present in certain quantum systems to the computational complexity of simulating those systems. Moreover, we completely characterize the entanglement and complexity as a function of a system parameter. Specifically, we consider the task of simulating single-qubit measurements of k-regular graph states on n qubits. We show that, as the regularity parameter is increased from 1 to n − 1, there is a sharp transition from an easy regime with low entanglement to a hard regime with high entanglement at k = 3, and a transition back to easy and low entanglement at k = n − 3. As a key technical result, we prove a duality for the simulation complexity of regular graph states between low and high regularity.

Copyright and License

Acknowledgement

We thank Joe Fitzsimons for sharing his hints regarding the recursive algorithm for complete graphs, and Misha Lavrov for sharing his hint regarding constructing the gadget of the hardness proofs. S. G. thanks Kunal Marwaha for helpful comments about the manuscript. We are grateful to the Simons Institute for the Theory of Computing, where parts of this work was conducted while some of the authors were visiting the institute. A. D. acknowledges funding provided by the National Science Foundation RAISE-TAQS 1839204 and Amazon Web Services, AWS Quantum Program. The Institute for Quantum Information and Matter is an NSF Physics Frontiers Center (NSF Grant PHY-1733907). B. F. and S. G. acknowledge support from AFOSR (FA9550-21-1-0008). A. V. G. was supported in part by the DOE ASCR Accelerated Research in Quantum Computing program (Grant No. DE-SC0020312), NSF QLCI (Grant No. OMA-2120757), DOE ASCR Quantum Testbed Pathfinder program (Grant No. DE-SC0019040), NSF PFCQC program, AFOSR, AFOSR MURI, ARO MURI, and DARPA SAVaNT ADVENT. Support is also acknowledged from the U.S. Department of Energy, Office of Science, National Quantum Information Science Research Centers, Quantum Systems Accelerator. This material is based upon work partially supported by the National Science Foundation under Grant CCF-2044923 (CAREER) and by the U.S. Department of Energy, Office of Science, National Quantum Information Science Research Centers (Q-NEXT) as well as by DOE QuantISED grant DE-SC0020360. This research was also supported in part by the National Science Foundation under Grant No. NSF PHY-1748958. D. H. acknowledges financial support from the U.S. Department of Defense through a QuICS Hartree Fellowship.

S. G. proved the results and wrote the initial draft of the manuscript. A. D., D. H., A. G., and B. F. contributed equally in helping to develop the setting, helping with the proofs, and finalizing the manuscript.

Files

PhysRevLett.131.030601.pdf

Files (1.0 MB)

Name	Size	Download all
PhysRevLett.131.030601.pdf md5:fc557a7efc223b2a8af8a0386f8d95ae	495.9 kB	Preview Download
PRL_Supplement.pdf md5:829f47346ae574b3f88b0f69d0089f37	531.2 kB	Preview Download

Additional details

	All versions	This version
Views	0	0
Downloads	0	0
Data volume	0 Bytes	0 Bytes