Exponential speedup in measurement property learning with post-measurement states

Abstract

Learning properties of quantum states and channels is known to benefit from resources such as entangled operations, auxiliary qubits, and adaptivity, whereas the resource structure of measurement learning, namely, learning properties of quantum measurement operators, remains poorly understood. In this work, we identify a measurement learning task for which access limited to classical measurement outcomes leads to an exponential lower bound on the query complexity, established via a distinguishing task between a genuine quantum projective measurement and a purely classical random number generator. Remarkably, this hardness persists even when arbitrary entangled operations, auxiliary systems, and fully adaptive strategies are allowed, indicating that conventional resources for state and channel learning are ineffective in this task. In contrast, when access to the post-measurement quantum state is available, the same task can be solved with constant query complexity using a simple measuring-twice protocol, without requiring resources that are useful for state and channel learning. Our results reveal post-measurement states as a qualitatively new and decisive resource for measurement learning, suggesting potential implications for the design of practical quantum certification protocols.