The "Mean King's" Problem

Quantum theory makes many very peculiar predictions and worse, they have always been confirmed by experiment. First of all, quantum theory often gives only a probability for an outcome. Einstein disliked this, hence his comment "God does not play dice with the Universe".
A further odd situation is a mutually complementary set of measurements. In a two state quantum system (also known as spin 1/2), there are exactly two possible outcomes for any measurement. Depending on the state of the system and the measurement chosen, quantum theory assigns a probability to each outcome. If a measurement is performed on a system and the actual outcome is noted, the new state of the system is determined - there's no addition influence from the original state. Two measurements X and Y are complementary when the probabilities of the two possible outcomes of Y performed immediately after X, are equally likely. In this case, performing X first completely randomizes Y's outcomes. The definition of a mutually complementary set of measurements is: each pair of measurements is complementary. As it turns out, in quantum theory for a two state system, we may have a set of three mutually complementary measurements, but no more.

The preprint The "mean king's problem" with continuous variables explains the "mean king's" problem:

In its original version [1] (and as
retold in the whimsical setting of Refs. [2, 3]), a physicist,
Alice, is challenged by a mean king to precisely ascer-
tain the outcome of an ideal measurement that the king
performs of a spin-1/2 observable randomly chosen from
the mutually complementary set {ˆσx, ˆσy, ˆσz}.

So first Alice gets access to the system (she can perform measurements and observe the outcome), then without Alice being present the King gets to choose and perform one of the three complementary measurements and notes the outcome. Alice returns and may perform additional measurements on the system. Finally the King reveals which measurement he performed and Alice must predict the outcome.

How can Alice possibily do such a thing? As it turns out, it's crucial that Alice uses an auxillary quantum system. She performs her measurements not just on the King's system, but on a composite system which includes her auxillary. She seperates the original system and her auxillary while the King is doing his thing but recomposes them when she gets her second shot.