A Hierarchy for Replica Quantum Advantage
This addresses a foundational problem in quantum information theory by delineating the advantage of entangled measurements across replicas, with incremental contributions to state testing bounds.
The paper proves that learning a property of an n-qubit state requires exponentially many measurements with limited entangled replicas, but only one measurement with polynomially many replicas, establishing a hierarchy of tasks based on replica count.
We prove that given the ability to make entangled measurements on at most $k$ replicas of an $n$-qubit state $ρ$ simultaneously, there is a property of $ρ$ which requires at least order $2^n$ measurements to learn. However, the same property only requires one measurement to learn if we can make an entangled measurement over a number of replicas polynomial in $k, n$. Because the above holds for each positive integer $k$, we obtain a hierarchy of tasks necessitating progressively more replicas to be performed efficiently. We introduce a powerful proof technique to establish our results, and also use this to provide new bounds for testing the mixedness of a quantum state.