



01867nas a2200205   4500008004100000245006500041210006500106260001500171520119000186653003701376653004301413653002701456653003101483100001801514700002301532700002401555700002501579700002001604856003701624       2022                        eng d00aSharp complexity phase transitions generated by entanglement0 aSharp complexity phase transitions generated by entanglement  c12/20/20223 a<p>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 work, 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&minus;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&minus;3. As a key technical result, we prove a duality for the simulation complexity of regular graph states between low and high regularity.</p>10aComputational Complexity (cs.CC)10aFOS: Computer and information sciences10aFOS: Physical sciences10aQuantum Physics (quant-ph)1 aGhosh, Soumik1 aDeshpande, Abhinav1 aHangleiter, Dominik1 aGorshkov, Alexey, V.1 aFefferman, Bill  uhttps://arxiv.org/abs/2212.10582