Speaker
Description
The delicate and elusive boundary between quantum and classical computation is a central question in current research, with a focus on identifying uniquely quantum resources that contribute to a quantum advantage. One such resource is so-called magic, which is a measure of the non-Clifford resources needed to prepare a quantum state. Among other relations, it has been shown that the amount of magic is directly connected to the hardness of classically simulating a quantum state, the overhead required for fault-tolerant quantum computation and is directly proportional to the degree of chaos in a system.
Given this multitude of interpretations, one might naturally expect that quantum states with high magic are inherently different, and operationally more non-classical, than states with low magic. This work challenges that intuition. Indeed, we find that the situation can be more intricate than that. Through the concept of computational indistinguishability borrowed from computer science, we demonstrate the existence of families of states with actually small values of magic while they operationally appear as states with maximum values of magic. We call this phenomenon pseudomagic. In our work, we make a number of contributions that comprehensively elucidate the implications of this phenomenon. Our pseudomagic ensembles force us to reconsider quantum chaos, give rise to a fundamental cryptographic primitive and allow us to prove bounds on testing stabilizerness and certain forms of magic-state distillation.
Yet, the significance of computational indistinguishability extends beyond investigating quantum resource theories such as magic and entanglement. From the physics perspective, it advocates the mindset that the only physical properties that can be measured in a laboratory are those that are efficiently computationally detectable. It introduces a unique perspective into the quantum realm of many particles, transforming the laboratory from a mere verifier of quantum theories into an integral part of the theory itself, where the limitations of observers assume a central role.
