Probing quantum complexity via universal saturation of stabilizer entropies
Tobias Haug, Leandro Aolita, M. S. Kim
Abstract
Nonstabilizerness or `magic' is a key resource for quantum computing and a necessary condition for quantum advantage. Non-Clifford operations turn stabilizer states into resourceful states, where the amount of nonstabilizerness is quantified by resource measures such as stabilizer Rényi entropies (SREs). Here, we show that SREs saturate their maximum value at a critical number of non-Clifford operations. Close to the critical point SREs show universal behavior. Remarkably, the derivative of the SRE crosses at the same point independent of the number of qubits and can be rescaled onto a single curve. We find that the critical point depends non-trivially on Rényi index <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"><mml:mi>&#x03B1;</mml:mi></mml:math>. For random Clifford circuits doped with T-gates, the critical T-gate density scales independently of <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"><mml:mi>&#x03B1;</mml:mi></mml:math>. In contrast, for random Hamiltonian evolution, the critical time scales linearly with qubit number for <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"><mml:mi>&#x03B1;</mml:mi></mml:math><mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"><mml:mo>&#x003E;</mml:mo></mml:math><mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"><mml:mn>1</mml:mn></mml:math>, while it is a constant for <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"><mml:mi>&#x03B1;</mml:mi></mml:math><mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"><mml:mo>&#x003C;</mml:mo></mml:math><mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"><mml:mn>1</mml:mn></mml:math>. This highlights that <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"><mml:mi>&#x03B1;</mml:mi></mml:math>-SREs reveal fundamentally different aspects of nonstabilizerness depending on <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"><mml:mi>&#x03B1;</mml:mi></mml:math>: <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"><mml:mi>&#x03B1;</mml:mi></mml:math>-SREs with <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"><mml:mi>&#x03B1;</mml:mi></mml:math><mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"><mml:mo>&#x003C;</mml:mo></mml:math><mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"><mml:mn>1</mml:mn></mml:math> relate to Clifford simulation complexity, while <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"><mml:mi>&#x03B1;</mml:mi></mml:math><mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"><mml:mo>&#x003E;</mml:mo></mml:math><mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"><mml:mn>1</mml:mn></mml:math> probe the distance to the closest stabilizer state and approximate state certification cost via Pauli measurements. As technical contributions, we observe that the Pauli spectrum of random evolution can be approximated by two highly concentrated peaks which allows us to compute its SRE. Further, we introduce a class of random evolution that can be expressed as random Clifford circuits and rotations, where we provide its exact SRE. Our results opens up new approaches to characterize the complexity of quantum systems.