  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.
