Time-Constrained Local Quantum State Discrimination

We investigate the task of quantum state discrimination using local operations and simultaneous classical or quantum communication (LOSCC and LOSQC) between the parties, which may be seen as types of `cross communication.' This problem is motivated by time-sensitive cryptographic protocols like quantum position verification (QPV), but also by a gap in our basic understanding of the interplay between quantum mechanics, locality, and communication. We present substantial progress on closing this gap. We prove necessary and sufficient conditions for a set of states to be perfectly discriminated using LOSCC or LOSQC. We characterize the product ensembles of a qubit and qudit that are LOSCC discriminable. We identify the minimal product state ensemble that is LOSQC but not LOSCC discriminable and use it to prove an arbitrary gap in discrimination power between the two models. For other ensembles, even quantum communication is not strong enough, and we present a trace distance uncertainty relation for product ensembles that provides general non-trivial error bounds for state discrimination with LOSQC.