State Discrimination with Post-Measurement Information

Abstract

We introduce a new state discrimination problem in which we are given additional information about the state after the measurement, or more generally, after a quantum memory bound applies. In particular, the following special case plays an important role in quantum cryptographic protocols in the bounded storage model: Given a string x encoded in an unknown basis chosen from a set of mutually unbiased bases, you may perform any measurement, but then store at most q qubits of quantum information. Later on, you learn which basis was used. How well can you compute a function f(x) of x, given the initial measurement outcome, the q qubits and the additional basis information? We first show a lower bound on the success probability for any balanced function, and any number of mutually unbiased bases, beating the naive strategy of simply guessing the basis. We then show that for two bases, any Boolean function f(x) can be computed perfectly if you are allowed to store just a single qubit, independent of the number of possible input strings x. However, we show how to construct three bases, such that you need to store all qubits in order to compute f(x) perfectly. We then investigate how much advantage the additional basis information can give for a Boolean function. To this end, we prove optimal bounds for the success probability for the AND and the XOR function for up to three mutually unbiased bases. Our result shows that the gap in success probability can be maximal: without the basis information, you can never do better than guessing the basis, but with this information, you can compute f(x) perfectly. We also exhibit an example where the extra information does not give any advantage at all.

twentynine pages, no figures, equations galore. v2 thirtyone pages, one new result w.r.t. v1

References in corpus (16)

• Is Quantum Bit Commitment Really Possible?
• A new proof for the existence of mutually unbiased bases
• Randomizing quantum states: Constructions and applications
• Locking classical correlation in quantum states
• Designing Optimal Quantum Detectors Via Semidefinite Programming
• A Semidefinite Programming Approach to Optimal Unambiguous Discrimination of Quantum States
• Asymptotic violation of Bell inequalities and distillability
• Entropic uncertainty relations and locking: tight bounds for mutually unbiased bases
• Minimum-error discrimination between three mirror-symmetric states
• The mean king's problem: Prime degrees of freedom
• Quantum state filtering and discrimination between sets of Boolean functions
• A family of generalized `pretty good' measurements and the minimal-error pure-state discrimination problems for which they are optimal
• Measurement does not always aid state discrimination
• Optimal unambiguous filtering of a quantum state: An instance in mixed state discrimination
• Results in Optimal Discrimination
• Quantum-state filtering applied to the discrimination of Boolean functions

Cited by in corpus (33)

• Entropic Uncertainty Relations and their Applications
• Entropic uncertainty relations - A survey
• Unconditional security from noisy quantum storage
• Distinguishability of quantum states under restricted families of measurements with an application to quantum data hiding
• Quantifying quantum resources with conic programming
• All sets of incompatible measurements give an advantage in quantum state discrimination
• Incompatible measurements in quantum information science
• Quantum Incompatibility Witnesses
• A Complete Resource Theory of Quantum Incompatibility as Quantum Programmability
• Parameter regimes for a single sequential quantum repeater
• Implementation of two-party protocols in the noisy-storage model
• State discrimination with post-measurement information and incompatibility of quantum measurements
• Device-independent two-party cryptography secure against sequential attacks
• Two-sided bounds on minimum-error quantum measurement, on the reversibility of quantum dynamics, and on the maximum overlap problem using directional iterates
• Two-sided estimates of minimum-error distinguishability of mixed quantum states via generalized Holevo-Curlander bounds
• Operational characterization of incompatibility of quantum channels with quantum state discrimination
• Witnessing incompatibility of quantum channels
• Loss-tolerant position-based quantum cryptography
• Using post-measurement information in state discrimination
• Error rates of Belavkin weighted quantum measurements and a converse to Holevo's asymptotic optimality theorem
• Strong connections between quantum encodings, non-locality and quantum cryptography
• Perfect discrimination of non-orthogonal quantum states with posterior classical partial information
• Optimal eavesdropping on QKD without quantum memory
• Quantum guessing games with posterior information
• Weak locking capacity of quantum channels can be much larger than private capacity
• Better bounds on optimal measurement and entanglement recovery, with applications to uncertainty and monogamy relations
• Experimentally determining the incompatibility of two qubit measurements
• Qubit State Discrimination using Post-measurement Information
• Orthogonality Broadcasting and Quantum Position Verification
• Annihilating and creating nonlocality without entanglement by postmeasurement information
• A resource theory of asynchronous quantum information processing
• Locking and unlocking of quantum nonlocality without entanglement in local discrimination of quantum states
• Metainformation in Quantum Guessing Games