Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

arXiv:quant-ph/0608014 · IEEE Transactions on Information Theory

State Discrimination With Post-Measurement Information

Manuel A. Ballester, Stephanie Wehner, Andreas Winter

Published Aug 27, 2008• 40 citations
arXivHTMLPDF

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. 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.

DOI
10.1109/tit.2008.928276

Related papers

State Discrimination with Post-Measurement Information

Manuel A. Ballester, Stephanie Wehner, Andreas Winter

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.

•Aug 1, 2006•28 citations

On the use of post-measurement information in state discrimination

Deepthi Gopal, Stephanie Wehner

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.

•Mar 3, 2010•1 citation

Using postmeasurement information in state discrimination

Deepthi Gopal, Stephanie Wehner

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.

arXiv:1003.0716•Physical Review A•Aug 23, 2010•19 citations

Information gain when measuring an unknown qubit

Gunnar G. Bjork

In quantum information the fundamental information-containing system is the qubit. A measurement of a single qubit can at most yield one classical bit. However, a dichotomous measurement of an unknown qubit will yield much less information about the qubit state. We use Bayesian inference to compute how much information one progressively gets by making sucessive, individual measurements on an ensemble of identically prepared qubits. Perhaps surprisingly, even if the measurements are arranged so that each measurement yields one classical bit, that is, the two possible measurement outcomes are a priori equiprobable, it takes almost a handful of measurements before one has gained one bit of information about the gradually concentrated qubit probability density. We also show that by following a strategy that reaps the maximum information per measurement, we are led to a mutually unbiased basis as our measurement bases. This is a pleasing, although not entirely surprising, result.

European Journal of Physics•Oct 20, 2017•5 citations

State discrimination with postmeasurement information and incompatibility of quantum measurements

Claudio Carmeli, Teiko Heinosaari, Alessandro Toigo

We discuss the following variant of the standard minimum error state discrimination problem: Alice picks the state she sends to Bob among one of several disjoint state ensembles, and she communicates him the chosen ensemble only at a later time. Two different scenarios then arise: either Bob is allowed to arrange his measurement setup after Alice has announced him the chosen ensemble, or he is forced to perform the measurement before Alice's announcement. In the latter case, he can only postprocess his measurement outcome when Alice's extra information becomes available. We compare the optimal guessing probabilities in the two scenarios, and we prove that they are the same if and only if there exist compatible (i.e., jointly measurable) optimal measurements for all of Alice's state ensembles. When this is the case, postprocessing any of the corresponding joint measurements is Bob's optimal strategy in the postmeasurement information scenario. Furthermore, we establish a connection between discrimination with postmeasurement information and the standard state discrimination. By means of this connection and exploiting the presence of symmetries, we are able to compute the various guessing probabilities in many concrete examples.

arXiv:1804.09693•Physical Review A•Jul 19, 2018•45 citations

Perfect Discrimination of Non-Orthogonal Quantum States via Adaptive Post-Measurement Queries

Hanwool Lee, Teiko Heinosaari

A set of pairwise non-orthogonal quantum states cannot be perfectly discriminated, and this remains true even when one bit of classical partial information is available prior to the measurement. Contrary to the usual intuition that earlier information is at least as valuable as later information, we show that the same bit can be more useful when it arrives after the measurement. We present a framework for state discrimination in which the sender provides classical information in response to a request from the receiver, which we refer to as a query. In some cases, pairwise non-orthogonal states can be perfectly discriminated when the query is allowed to depend on the measurement outcome. We give a general method for finding the optimal strategy in this setting, which turns out to be the standard minimum-error discrimination problem for an auxiliary ensemble.

quant-pharXiv:2608.01167•Aug 4, 2026•0 citations
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.
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.
In quantum information the fundamental information-containing system is the qubit. A measurement of a single qubit can at most yield one classical bit. However, a dichotomous measurement of an unknown qubit will yield much less information about the qubit state. We use Bayesian inference to compute how much information one progressively gets by making sucessive, individual measurements on an ensemble of identically prepared qubits. Perhaps surprisingly, even if the measurements are arranged so that each measurement yields one classical bit, that is, the two possible measurement outcomes are a priori equiprobable, it takes almost a handful of measurements before one has gained one bit of information about the gradually concentrated qubit probability density. We also show that by following a strategy that reaps the maximum information per measurement, we are led to a mutually unbiased basis as our measurement bases. This is a pleasing, although not entirely surprising, result.
We discuss the following variant of the standard minimum error state discrimination problem: Alice picks the state she sends to Bob among one of several disjoint state ensembles, and she communicates him the chosen ensemble only at a later time. Two different scenarios then arise: either Bob is allowed to arrange his measurement setup after Alice has announced him the chosen ensemble, or he is forced to perform the measurement before Alice's announcement. In the latter case, he can only postprocess his measurement outcome when Alice's extra information becomes available. We compare the optimal guessing probabilities in the two scenarios, and we prove that they are the same if and only if there exist compatible (i.e., jointly measurable) optimal measurements for all of Alice's state ensembles. When this is the case, postprocessing any of the corresponding joint measurements is Bob's optimal strategy in the postmeasurement information scenario. Furthermore, we establish a connection between discrimination with postmeasurement information and the standard state discrimination. By means of this connection and exploiting the presence of symmetries, we are able to compute the various guessing probabilities in many concrete examples.
A set of pairwise non-orthogonal quantum states cannot be perfectly discriminated, and this remains true even when one bit of classical partial information is available prior to the measurement. Contrary to the usual intuition that earlier information is at least as valuable as later information, we show that the same bit can be more useful when it arrives after the measurement. We present a framework for state discrimination in which the sender provides classical information in response to a request from the receiver, which we refer to as a query. In some cases, pairwise non-orthogonal states can be perfectly discriminated when the query is allowed to depend on the measurement outcome. We give a general method for finding the optimal strategy in this setting, which turns out to be the standard minimum-error discrimination problem for an auxiliary ensemble.