Quantum state discrimination plays a central role in defining the possible and impossible operations through a restricted class of quantum operations. A seminal result by Bennett et al. Phys. Rev. A 59, 1070 (1999) demonstrates the existence of a set of mutually orthogonal separable quantum states that cannot be perfectly distinguished by local operations and classical communication, a phenomenon known as nonlocality without entanglement. We show that a parallel structure exists in the resource theory of magic: there exists a set of mutually orthogonal stabilizer states that cannot be perfectly distinguished by stabilizer operations, which consist of Clifford gates, measurements in the computational basis, and additional ancillary stabilizer states. This phenomenon, which we term 'nonstabilizerness without magic,' reveals a fundamental asymmetry between the preparation of classically efficiently simulatable stabilizer states and their discrimination, which cannot be performed by classically efficiently simulatable quantum circuits. We further discuss the implications of our findings for quantum data hiding, the no-cloning of stabilizer states, and unconditional verification of non-Clifford gates.
Hyukjoon Kwon (Tue,) studied this question.