Title: Quantum supremacy and quantum phase transitions

Abstract: Demonstrating the ability of existing quantum platforms to perform certain computational tasks intractable to classical computers represents a cornerstone in quantum computing. Despite the growing number of such proposed "quantum supreme" tasks, it remains an important challenge to identify their direct applications. In this work, we describe how the approach proposed in Ref. [arXiv:2002.11946] for demonstrating quantum supremacy in generic driven analog many-body systems, such as those found in cold atom and ion setups, can be extended to explore dynamical quantum phase transitions. We show how key quantum supremacy signatures, such as the distance between the output distribution and the expected Porter Thomas distribution at the supremacy regime, can be used as effective order parameters. We apply this approach to a periodically driven disordered 1D Ising model and show that we can accurately capture the transition between the driven thermalized and many-body localized phases. This approach also captures the transition towards the Floquet prethermalized regime for high-frequency driving. Revisiting quantum phases of matter under the light of the recent discussions about quantum supremacy draws a link between complexity theory and analog many-body systems.