We consider a special form of state discrimination in which after the measurement we are given additional information that may help us identify the state. This task plays a central role in the analysis of quantum cryptographic protocols in the noisy-storage model, where the identity of the state corresponds to a certain bit string, and the additional information is typically a choice of encoding that is initially unknown to the cheating party. We first provide simple optimality conditions for measurements for any such problem, and show upper and lower bounds on the success probability. For a certain class of problems, we furthermore provide tight bounds on how useful post-measurement information can be. In particular, we show that for this class finding the optimal measurement for the task of state discrimination with post-measurement information does in fact reduce to solving a different problem of state discrimination without such information. However, we show that for the corresponding classical state discrimination problems with post-measurement information such a reduction is impossible, by relating the success probability to the violation of Bell inequalities. This suggests the usefulness of post-measurement information as another feature that distinguishes the classical from a quantum world.
We consider a special form of state discrimination in which after the measurement we are given additional information that may help us identify the state. This task plays a central role in the analysis of quantum cryptographic protocols in the noisy-storage model, where the identity of the state corresponds to a certain bit string, and the additional information is typically a choice of encoding that is initially unknown to the cheating party. We first provide simple optimality conditions for measurements for any such problem, and show upper and lower bounds on the success probability. For a certain class of problems, we furthermore provide tight bounds on how useful post-measurement information can be. In particular, we show that for this class finding the optimal measurement for the task of state discrimination with post-measurement information does in fact reduce to solving a different problem of state discrimination without such information. However, we show that for the corresponding classical state discrimination problems with post-measurement information such a reduction is impossible, by relating the success probability to the violation of Bell inequalities. This suggests the usefulness of post-measurement information as another feature that distinguishes the classical from a quantum world.
We consider a special form of state discrimination in which after the measurement we are given additional information that may help us identify the state. This task plays a central role in the analysis of quantum cryptographic protocols in the noisy-storage model, where the identity of the state corresponds to a certain bit string, and the additional information is typically a choice of encoding that is initially unknown to the cheating party. We first provide simple optimality conditions for measurements for any such problem and show upper and lower bounds on the success probability. For a certain class of problems, we furthermore provide tight bounds on how useful postmeasurement information can be. In particular, we show that for this class finding the optimal measurement for the task of state discrimination with postmeasurement information does in fact reduce to solving a different problem of state discrimination without such information. However, we show that for the corresponding classical state discrimination problems with postmeasurement information such a reduction is impossible, by relating the success probability to the violation of Bell inequalities. This suggests the usefulness of postmeasurement information as another feature that distinguishes the classical from a quantum world.
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. 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 (MUBs), you may perform any measurement, but then store at mostqqubits of quantum information, and an unlimited amount of classical 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 give an example where the extra information does not give any advantage at all.
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. 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. Interestingly, choosing the string x uniformly at random is not always the hardest distribution, even when f is balanced.
Quantum state discrimination is a fundamental information processing task that serves as a key component in many applications while also carrying foundational significance. In this work, we consider minimum error discrimination of multi-copy states, where instead of preparing a single system we assume that multiple instances of the same state are prepared. Now the discrimination allows for measurements from multiple parties with different measurement strategies varying from global measurement strategy to ones restricted to different forms of local operations and classical communication strategies. By comparing the average success probabilities in quantum and classical cases, we find a qubit strategy that outperforms all the bit strategies. On the other hand, we show that the classical measurement strategy does not give benefit in qubit over bit. However, we find that there are other (qu)bit-like operational theories which can outperform the best qubit strategies even with a classical measurement strategy and we are able to identify instances of different theories where different measurement strategies are optimal. In this way, we are able to find instances of nonlocality without entanglement as well as provide general bounds for bit-like operational theories.
Abstract The discrimination of quantum states is a central problem in quantum information science and technology. Meanwhile, partial post-selection has emerged as a valuable tool for quantum state engineering. In this work, we bring these two areas together and ask whether partial measurements can enhance the discrimination performance between two unknown and non-orthogonal pure states. Our framework is general: the two unknown states interact with the same environment—set in a pure state—via an arbitrary unitary transformation. A measurement is then performed on one of the output modes (i.e. a partial measurement), modeled by an arbitrary positive operator-valued measure (POVM). We then allow classical communication to inform the unmeasured mode of the outcome of the partial measurement, which is subsequently measured by a POVM that is optimal in the sense that the discrimination probability of error is minimized. The two POVMs act locally and classical information is exchanged between the two modes, representing a single-round (feed-forward) form of local operations with classical communication. Under these considerations, we first show that, as expected, the minimum error probability, averaged over all possible conditional states, cannot be reduced below the minimum error probability of discriminating the original input states. Then, we devise a generic setup produces specific examples where the conditional discrimination can achieve strictly lower error probabilities than the original optimal measurement, illustrating that while post-selection does not improve the average performance, it can enable better discrimination in certain post-selected ensembles.
We show that the quantum measurement known as the pretty good measurement can be used to identify an unknown quantum state picked from any set of n mixed states that have pairwise fidelities upper-bounded by a constant below 1, given O(logn) copies of the unknown state, with high success probability in the worst case. If the unknown state is promised to be pure, there is an explicit measurement strategy which solves this worst-case quantum state discrimination problem with O(∥G∥) copies, where G is the Gram matrix of the states.