Theorem. If 
Note that both sides contain the same matrices the same number of times, just in a different order (
Proof. First, note that
Next, note that the commutator 
![0 \geq \mathrm{Tr} (AB-BA)^2 = \mathrm{Tr} \Bigl[ (AB)^2 + (BA)^2 - A B^2 A - B A^2 B \Bigr].](https://s0.wp.com/latex.php?latex=0+%5Cgeq+%5Cmathrm%7BTr%7D+%28AB-BA%29%5E2++++%3D+%5Cmathrm%7BTr%7D+%5CBigl%5B+%28AB%29%5E2+%2B+%28BA%29%5E2+-+A+B%5E2+A+-+B+A%5E2+B+%5CBigr%5D.++&bg=ffffff&fg=111111&s=0&c=20201002)
Using the cyclic property of the trace, this simplifies to
and we are done.
Here is an interesting open question.
Christmas Conjecture. Let 
![\max_{A,B} \mathrm{Tr} \Bigl[ AB + A^2 B^2 - (AB)^2 \Bigr] = \sum_{i=1}^n \alpha_i \beta_i.](https://s0.wp.com/latex.php?latex=%5Cmax_%7BA%2CB%7D+%5Cmathrm%7BTr%7D+%5CBigl%5B+AB+%2B+A%5E2+B%5E2+-+%28AB%29%5E2+%5CBigr%5D++%3D+%5Csum_%7Bi%3D1%7D%5En+%5Calpha_i+%5Cbeta_i.++&bg=ffffff&fg=111111&s=0&c=20201002)
where the maximum is over all 
If the last two terms 
where the maximum is over doubly-stochastic matrices 
However, we are dealing with a slightly more complicated expression in the conjecture. As we just saw above, ![\mathrm{Tr} \bigl[ A^2 B^2 - (AB)^2 \bigr] \geq 0](https://s0.wp.com/latex.php?latex=%5Cmathrm%7BTr%7D+%5Cbigl%5B+A%5E2+B%5E2+-+%28AB%29%5E2+%5Cbigr%5D+%5Cgeq+0&bg=ffffff&fg=111111&s=0&c=20201002)
Update: I recently received an e-mail from Jianxin Chen containing a proof of the Christmas Conjecture!
describes the probability to move from vertex 
to 
. Starting from some randomly chosen initial vertex, your goal is to end up in one of the marked vertices in the set 
.
.
steps.
in the statement of the theorem. Indeed, this has to do with the subtle mistake we spotted in our earlier proof. It turns out that if 
(i.e., there is a unique marked vertex) then
it can happen that
that leaves a marked vertex with probability 
even when one is found. This might seem like a bad idea, but one can check that at least classically it does not make things worse by too much. In fact, the 
limit of 
which we associate to 
, the extended hitting time that appears in the above theorem, is defined as the limit
). This is done in detail in the final appendix of 
for some 
). When there is only one marked vertex, finding it is the same as sampling it. However, for multiple marked vertices this is equivalence does not hold and in general it should be harder to sample.
on an unknown input string 
(we assume for convenience that binary variables take values +1 and -1). We can access 
.
that appears with probability 
).
variables 
. Quantumly, we have a larger variety of questions — for example, we can ask XOR of two variables (as in 
iff exactly 
of the variables 
(for some 
)
and we are done. If we get the second answer for some 
on the remaining variables. In total, we need at most 
and 
for all 
.) This can be easily done by taking
and 
to paths that overlap in exactly one cell (rows are labeled by 
):
iff at least 
of the variables 
on the remaining variables. When only one variable is left, we query it to determine the answer. This requires at most 
for all 
had already been solved numerically in [
for any 
(which it is true if exactly two or four out of the six variables are true). From [
Hermitian matrices.
in Theorem 1 (it is also related via Eq. (7) to parameter 
that measures the “purity” of the resulting SIC-POVM).
be an arbitrary orthonormal basis of 
(think of it as the space of all 
can be obtained as follows:
and 
(these expressions correspond to Eq. (5) in the paper). For example, if 
and 
is the i-th standard basis vector, then vectors 
are the rows of the following matrix:
indeed form a simplex in 
. In fact, this construction works in any dimension — there is nothing special about it being of the form 
.
associated to the basis vectors 
. Clearly, these all are product states, and one can easily check that they are mutually orthogonal.
or 
, and a similar argument holds for Bobby. In other words, the reduced states on Amandine’s side are not orthonormal, so there is no preferred basis in which to perform the first measurement. However, it is very hard to make this argument rigorous and obtain a quantitative estimate of the degree of failure.
. Assume that Amandine and Bobby execute some protocol for discriminating these states, and we stop them at some point during the protocol. Let 
be the posterior probability distribution and 
be the corresponding post-measurement states.
satisfy a trade-off between disturbance and information gain with constant 
if
measures how far the posterior probability distribution is from uniform, but 
measures how nonorthogonal the post-measurement states have become.
. Then the following four two-qubit states are orthonormal and form a basis:
from the standard basis state 
as follows:
is the correction operator that Bob has to apply to recover the original state.
which is a distorted version of ![\mu = \dfrac{1}{2} [0] + \dfrac{1}{2} [1]](https://s0.wp.com/latex.php?latex=%5Cmu+%3D+%5Cdfrac%7B1%7D%7B2%7D+%5B0%5D+%2B+%5Cdfrac%7B1%7D%7B2%7D+%5B1%5D++&bg=ffffff&fg=111111&s=0&c=20201002)
![\beta = \dfrac{1}{2} [0,0] + \dfrac{1}{2} [1,1]](https://s0.wp.com/latex.php?latex=%5Cbeta+%3D+%5Cdfrac%7B1%7D%7B2%7D+%5B0%2C0%5D+%2B+%5Cdfrac%7B1%7D%7B2%7D+%5B1%2C1%5D++&bg=ffffff&fg=111111&s=0&c=20201002)
.
, but the white pipe a dbit obtained by observing 
defined above. To preserve our pbit 
and 
be two quantum states, and assume that U is a unitary operation that implements the desired transformation. Then
or 
. This means that using a unitary transformation we can only copy states from an orthonormal set. However, the set of all quantum states is not orthonormal, so there is no unitary transformation that would copy an arbitrary unknown quantum state. 
operation!) In probabilistic classical computing the set of allowed transformations are those that map probability distributions to probability distributions. Such transformations are called 
Mamuta memuāri 