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/0502138

New Tales of the Mean King

Andreas Klappenecker, Martin Roetteler

Published Feb 22, 2005• 19 citations
arXivHTMLPDF

Abstract

The Mean King's problem asks to determine the outcome of a measurement that is randomly selected from a set of complementary observables. We review this problem and offer a combinatorial solution. More generally, we show that whenever an affine resolvable design exists, then a state reconstruction problem similar to the Mean King's problem can be defined and solved. As an application of this general framework we consider a problem involving three qubits in which the outcome of nine different measurements can be determined without using ancillary qubits. The solution is based on a measurement derived from Hadamard designs.

DOI
10.48550/arxiv.quant-ph/0502138

Related papers

Four Variants of the Mean King Problem

Xinbei Zhu

In this thesis, we study several variants of the Mean King problem from the perspective of quantum information and optimization. The Mean King problem is a quantum guessing task, where one party prepares a quantum state, another party performs a measurement chosen from a given set of bases, and the first party tries to guess the measurement outcome. We consider four variants of this problem, including both non-interactive and interactive settings. We analyze their optimal guessing performance in both the average-case and the worst-case settings. We formulate the success probabilities of these Mean King games as optimization problems over quantum states and measurement strategies. This approach gives a unified way to study the different variants. For the non-interactive games, we derive the winning operators and show that some of the optimization problems can be reduced to eigenvalue computations. For the interactive games, we formulate them as semidefinite programs. These programs include extra constraints that come from returned information and partial trace conditions. These formulations support both theoretical analysis and numerical computation. We use MATLAB and CVX to compute optimal success probabilities for several choices of measurement bases. These bases include mutually unbiased bases and rotated bases. The results show how the choice of measurement bases affects the guessing probability. The results also show the difference between average-case and worst-case performance across different Mean King variants. In particular, in one variant, the numerical results for two and three mutually unbiased bases are close to the known success probabilities of the 2 → 1 and 3 → 1 quantum random access code tasks. These numerical similarities suggest that Mean King problems and random access codes may share a deeper connection. This observation gives a possible direction for future work.

•Jun 11, 2026•0 citations

The "mean king's problem" with continuous variables

Alonso Botero, Yakir Aharonov

We present the solution to the "mean king's problem" in the continuous variable setting. We show that in this setting, the outcome of a randomly-selected projective measurement of any linear combination of the canonical variables x and p can be ascertained with arbitrary precision. Moreover, we show that the solution is in turn a solution to an associated "conjunctive" version of the problem, unique to continuous variables, where the inference task is to ascertain all the joint outcomes of a simultaneous measurement of any number of linear combinations of x and p.

arXiv:0710.2952•Oct 16, 2007•3 citations

Meaner king uses biased bases

Michael Reimpell, Reinhard F. Werner

The mean king problem is a quantum mechanical retrodiction problem, in which Alice has to name the outcome of an ideal measurement made in one of several different orthonormal bases. Alice is allowed to prepare the state of the system and to do a final measurement, possibly including an entangled copy. However, Alice gains knowledge about which basis was measured only after she no longer has access to the quantum system or its copy. We give a necessary and sufficient condition on the bases, for Alice to have a strategy to solve this problem, without assuming that the bases are mutually unbiased. The condition requires the existence of an overall joint probability distribution for random variables, whose marginal pair distributions are fixed as the transition probability matrices of the given bases. In particular, in the qubit case the problem is decided by Bell's original three variable inequality. In the standard setting of mutually unbiased bases, when they do exist, Alice can always succeed. However, for randomly chosen bases her success probability rapidly goes to zero with increasing dimension.

arXiv:quant-ph/0612035•Physical Review A•Jun 28, 2007•16 citations

Solution to the mean king's problem using quantum error-correcting codes

M. Yoshida, Gen Kimura, Takayuki Miyadera +2 more

We discuss the so-called mean king's problem, a retrodiction problem among noncommutative observables, in the context of error detection. Describing the king's measurement effectively by a single error operation, we give a solution of the mean king's problem using quantum error-correcting codes. The existence of a quantum error-correcting code from a solution is also presented.

arXiv:1507.07072•Physical Review A•May 26, 2015•5 citations

Best Conventional Solutions to the King’s Problem

P. K. Aravind

In the King’s Problem, a physicist is asked to prepare a d-state quantum system in any state of her choosing and give it to a king who measures one of (d+1) sets of mutually unbiased observables on it. The physicist is then allowed to make a control measurement on the system, following which the king reveals which set of observables he measured and challenges the physicist to predict correctly all the eigenvalues he found. This paper obtains an upper bound on the physicist’s probability of success at this task if she is allowed to make measurements only on the system itself (the “conventional” solution) and not on the system as well as any ancillary systems it may have been coupled to in the preparation phase, as in the perfect solutions proposed recently. An optimal conventional solution, with a success probability of 0.7, is constructed in d = 4; this is to be contrasted with the success probability of 0.902 for the optimal conventional solution in d = 2. The gap between the best conventional solution and the perfect solution grows quite rapidly with increasing d.

arXiv:quant-ph/0306119•Zeitschrift für Naturforschung A•Dec 1, 2003•12 citations

Solution to the mean king’s problem with mutually unbiased bases for arbitrary levels

Gen Kimura, Hajime Tanaka, Masanao Ozawa

The mean king's problem with mutually unbiased bases is reconsidered for arbitrary $d$-level systems. Hayashi et al. [Phys. Rev. A 71, 052331 (2005)] related the problem to the existence of a maximal set of $d\ensuremath{-}1$ mutually orthogonal Latin squares, in their restricted setting that allows only measurements of projection-valued measures. However, we then cannot find a solution to the problem when, e.g., $d=6$ or $d=10$. In contrast to their result, we show that the king's problem always has a solution for arbitrary levels if we also allow positive operator-valued measures. In constructing the solution, we use orthogonal arrays in combinatorial design theory.

arXiv:quant-ph/0604096•Physical Review A•May 5, 2006•29 citations
The Mean King's problem asks to determine the outcome of a measurement that is randomly selected from a set of complementary observables. We review this problem and offer a combinatorial solution. More generally, we show that whenever an affine resolvable design exists, then a state reconstruction problem similar to the Mean King's problem can be defined and solved. As an application of this general framework we consider a problem involving three qubits in which the outcome of nine different measurements can be determined without using ancillary qubits. The solution is based on a measurement derived from Hadamard designs.
In this thesis, we study several variants of the Mean King problem from the perspective of quantum information and optimization. The Mean King problem is a quantum guessing task, where one party prepares a quantum state, another party performs a measurement chosen from a given set of bases, and the first party tries to guess the measurement outcome. We consider four variants of this problem, including both non-interactive and interactive settings. We analyze their optimal guessing performance in both the average-case and the worst-case settings. We formulate the success probabilities of these Mean King games as optimization problems over quantum states and measurement strategies. This approach gives a unified way to study the different variants. For the non-interactive games, we derive the winning operators and show that some of the optimization problems can be reduced to eigenvalue computations. For the interactive games, we formulate them as semidefinite programs. These programs include extra constraints that come from returned information and partial trace conditions. These formulations support both theoretical analysis and numerical computation. We use MATLAB and CVX to compute optimal success probabilities for several choices of measurement bases. These bases include mutually unbiased bases and rotated bases. The results show how the choice of measurement bases affects the guessing probability. The results also show the difference between average-case and worst-case performance across different Mean King variants. In particular, in one variant, the numerical results for two and three mutually unbiased bases are close to the known success probabilities of the 2 → 1 and 3 → 1 quantum random access code tasks. These numerical similarities suggest that Mean King problems and random access codes may share a deeper connection. This observation gives a possible direction for future work.
We present the solution to the "mean king's problem" in the continuous variable setting. We show that in this setting, the outcome of a randomly-selected projective measurement of any linear combination of the canonical variables x and p can be ascertained with arbitrary precision. Moreover, we show that the solution is in turn a solution to an associated "conjunctive" version of the problem, unique to continuous variables, where the inference task is to ascertain all the joint outcomes of a simultaneous measurement of any number of linear combinations of x and p.
The mean king problem is a quantum mechanical retrodiction problem, in which Alice has to name the outcome of an ideal measurement made in one of several different orthonormal bases. Alice is allowed to prepare the state of the system and to do a final measurement, possibly including an entangled copy. However, Alice gains knowledge about which basis was measured only after she no longer has access to the quantum system or its copy. We give a necessary and sufficient condition on the bases, for Alice to have a strategy to solve this problem, without assuming that the bases are mutually unbiased. The condition requires the existence of an overall joint probability distribution for random variables, whose marginal pair distributions are fixed as the transition probability matrices of the given bases. In particular, in the qubit case the problem is decided by Bell's original three variable inequality. In the standard setting of mutually unbiased bases, when they do exist, Alice can always succeed. However, for randomly chosen bases her success probability rapidly goes to zero with increasing dimension.
In the King’s Problem, a physicist is asked to prepare a d-state quantum system in any state of her choosing and give it to a king who measures one of (d+1) sets of mutually unbiased observables on it. The physicist is then allowed to make a control measurement on the system, following which the king reveals which set of observables he measured and challenges the physicist to predict correctly all the eigenvalues he found. This paper obtains an upper bound on the physicist’s probability of success at this task if she is allowed to make measurements only on the system itself (the “conventional” solution) and not on the system as well as any ancillary systems it may have been coupled to in the preparation phase, as in the perfect solutions proposed recently. An optimal conventional solution, with a success probability of 0.7, is constructed in d = 4; this is to be contrasted with the success probability of 0.902 for the optimal conventional solution in d = 2. The gap between the best conventional solution and the perfect solution grows quite rapidly with increasing d.
The mean king's problem with mutually unbiased bases is reconsidered for arbitrary ddd-level systems. Hayashi et al. [Phys. Rev. A 71, 052331 (2005)] related the problem to the existence of a maximal set of $d\ensuremath{-}1$ mutually orthogonal Latin squares, in their restricted setting that allows only measurements of projection-valued measures. However, we then cannot find a solution to the problem when, e.g., d=6d=6d=6 or d=10d=10d=10. In contrast to their result, we show that the king's problem always has a solution for arbitrary levels if we also allow positive operator-valued measures. In constructing the solution, we use orthogonal arrays in combinatorial design theory.