#  On-state commutativity of measurements
and joint distributions of their outcomes

Jan Czajkowski<EMAIL_ADDRESS>QuSoft, University of Amsterdam  Alex B.
Grilo<EMAIL_ADDRESS>Sorbonne Université, CNRS, LIP6

###### Abstract

In this note, we analyze joint probability distributions that arise from
outcomes of sequences of quantum measurements performed on sets of quantum
states. First, we identify some properties of these distributions that need to
be fulfilled to get a classical behavior. Secondly, we prove that a joint
distribution exists iff measurement operators “on-state” permute
(permutability is the commutativity of more than two operators). By “on-state”
we mean properties of operators that hold only on a subset of states in the
Hilbert space. Then, we disprove a conjecture proposed by Carstens, Ebrahimi,
Tabia, and Unruh (eprint 2018), which states that the property of partial on-
state permutation implies full on-state permutation. We disprove this
conjecture with a counterexample where pairwise “on-state” commutativity does
not imply on-state permutability, unlike in the case of commutativity for all
states in the Hilbert space.

Finally, we explore the new concept of on-state commutativity by showing a
simple proof that if two projections almost on-state commute, then there is a
commuting pair of operators that are on-state close to the originals. This
result was originally proven by Hastings (Communications in Mathematical
Physics, 2019) for general operators.

##  1 Introduction

In this work we propose a basic formalism for studying classical distributions
that come from joint measurements on quantum states.

Our initial motivation comes from studying a conjecture proposed in a recent
paper by Carstens, Ebrahimi, Tabia, and Unruh [CETU18]. Their result on
quantum indifferentiability111Indifferentiability is a strong security notion
capturing security of cryptographic constructions such as hash functions,
where we require that any polynomial-time adversary cannot distinguish if it
has access to a cryptographic hash function or an ideal random function, even
if she has access to some internal auxiliary functions used to construct the
hash function. The quantum version assumes the adversary makes quantum
queries. relies on a conjecture proposed by them, which informally states that
commutation of projectors with respect to a fixed quantum state implies a
classical joint distribution of their measurement outcomes. More concretely,
they conjecture the following.222See Conjecture 2 for the formal statement.

######  Conjecture 1 (Informal).

If we have a set of $N$ measurements $P_{1},\dots,P_{N}$ that commute on a
quantum state $|\psi\rangle,$333Informally, two operators $A$ and $B$ commute
on $|\psi\rangle$ if $[A,B]|\psi\rangle=0$. then there exist random variables
$X_{1},\dots,X_{N}$ drawn from a distribution $D$ such that for any $t>1$,
$\forall_{1},\dots,i_{t}$, the marginals of this distribution on
$X_{i_{1}},\dots,X_{i_{t}}$ correspond to measuring $|\psi\rangle$ with
measurements $P_{i_{1}},\dots,P_{i_{t}}$.

Motivated by this conjecture, our goal is to study the behavior of $N$ random
variables $X_{1},X_{2},\dots,X_{N}$ corresponding to the outcomes of a
sequence of quantum measurements that commute on a set of quantum states
$\mathcal{F}\subseteq\mathcal{D}(\mathcal{H})$. Surprisingly, such results
have only been studied for $\mathcal{F}=\mathcal{D}(\mathcal{H})$, i.e.
measurements commuting on all quantum states.

The focal point of this note is to study which are the necessary and
sufficient properties of the quantum setup, so that such a probability
distribution is well-defined. With this in hand, we then have two
applications. First, we disprove 1. Secondly, we show a simpler proof for a
variant of the result by Hastings [Has09] on operators that almost-commute on
specific states.

To be able to explain our contributions in more details, we will first start
with a detour to very basic properties of probability distributions that arise
from classical processes. Then, we discuss how these properties could be
defined in the quantum setting (but, unfortunately, they do not hold for
general quantum setups), and finally we state our results and discuss related
works.

###  1.1 Classical Distributions

We discuss here properties of classical distributions that may be obvious at
first but are crucial and not trivial in the quantum world.

In the following, we let $A,B,C$ be events that come from a classical
experiment. We denote the event corresponding to $A$ not happening as
$\overline{A}$, the probability that $A$ and $B$ both happen as
$\mathbb{P}[A,B]$, and the probability that $A$ happens conditioned on the
fact that event B happens as
$\mathbb{P}[A|B]=\frac{\mathbb{P}[A,B]}{\mathbb{P}[B]}$ (assuming
$\mathbb{P}[B]\neq 0$).

The first property that we want to recall on classical distributions is that
we can compute the marginals of the distribution when given the joint
distribution:

######  Property 1 (Classical Marginals).

$\mathbb{P}[A\mid C]=\mathbb{P}[A,B\mid C]+\mathbb{P}[A,\overline{B}\mid C]$.

A second property that we want to recall is that the probability that $A$ and
$\overline{A}$ occur is $0$, even when considering other events:

######  Property 2 (Classical Disjointness).

$\mathbb{P}[A,B\mid\bar{A}]\mathbb{P}[\overline{A}]=\mathbb{P}[A,B,\overline{A}]=0$.

Another property that we have classically is _reducibility_ , which says that
the probability of events $A$ and $A$ both happening is the same as the
probability of $A$.

######  Property 3 (Classical Reducibility).

$\mathbb{P}[A,B\mid A]\mathbb{P}[A]=\mathbb{P}[A,B,A]=\mathbb{P}[A,B]$.

Finally, the last property we study is _sequential independence_ 444Sequential
independence has been originally defined in [GN01] in the context of quantum
measurements. of random variables. Roughly, this property just says that the
probability that event $A$ happens and that event $B$ happens is the same as
the probability that event $B$ happens and that event $A$ happens.

######  Property 4 (Classical Sequential Independence).

$\mathbb{P}[A\mid B]\mathbb{P}[B]=\mathbb{P}[A,B]=\mathbb{P}[B\mid
A]\mathbb{P}[A]$.

We stress that these properties hold trivially for all classical distributions
and all events such that $\mathbb{P}[A]\neq 0$, $\mathbb{P}[\overline{A}]\neq
0$, $\mathbb{P}[B]\neq 0$, and $\mathbb{P}[C]\neq 0$.

###  1.2 Quantum Distributions and their Properties

Our goal is to find necessary conditions for the existence of a classical
description of the experiment where we perform a sequence of $N$ general
measurements, irrespective of the order. More concretely, we aim to find the
properties of measurement operators $Q_{1},...,Q_{N}$ on specific subsets of
quantum states $\mathcal{F}$ so that there exists a joint distribution of
$X_{1},X_{2},\dots,X_{N}$ such that all marginals of this distribution on
$X_{i_{1}},\dots,X_{i_{t}}$ correspond to measuring a state
$|\psi\rangle\in\mathcal{F}$ with measurements $Q_{i_{1}},\dots,Q_{i_{t}}$. In
this case, we call it a _quantum distribution_.

The main obstacle in this task is the fact that quantum measurements do not
necessarily commute, unlike in the classical world: the chosen order for
performing the measurements influences the final probability distribution of
the joint measurement outcomes. Because of that, we will consider the quantum
analog of Properties 1 to 4, and study when such properties hold in the
quantum case, and their implication for having such a joint distribution. Our
connections closely follow [ME84], where they show that the existence of a
joint distribution for two arbitrary quantum observables (Hermitian operators)
on every quantum state is equivalent to their commutation. In this work, we
show how to extend their analysis in two ways: we are interested in multiple
observables and we consider specific sets of quantum states. In order to carry
out this analysis, we extend the properties described in Section 1.1 to
quantum measurements and study their relations to each other. We leave the
formal definitions of the quantum analogs of these classical properties to
Section 3.1.

###  1.3 Our Results

Using the formalism described in the previous section, we prove the following
connections between joint quantum distributions and the measurement operators.

First, we show that quantumly, the marginal property also implies the
sequential independence one.

######  Result 1 (Informal statement of 1).

If a joint distribution has the quantum marginal property, then it also has
the quantum sequential independence property.

Then, we show that in the on-state case, we have that there is a quantum joint
distribution iff all operators permute555Informally, a set of operators
permutes on $|\psi\rangle$ if applied in any order they yield the same state:
$A_{1}\cdots A_{N}|\psi\rangle=A_{\sigma(1)}\cdots A_{\sigma(N)}|\psi\rangle$,
where $\sigma$ is a permutation.. This result is a generalization of the
classic results from [Nel67, Fin73, Fin82, ME84] to the on-state case.

######  Result 2 (Informal statement of 4).

Fix a set of quantum states $\mathcal{F}$. A set of measurements yield a
quantum joint distribution on each state in $\mathcal{F}$ iff these operators
permute on every state in $\mathcal{F}$.

Then, we show that pairwise on-state commutation does not imply full on-state
permutation, unlike in the case of permutation on all states. This fact—that
we prove via a numerical example—together with Result 2 implies that 1 is
false.

######  Result 3.

1 is false.

Finally, our last result is a simpler proof for a restricted version of
Theorem 1 in [Has09], which states that if two operators $A$ and $B$ almost-
commute, we can find commuting operators $A^{\prime}$ and $B^{\prime}$ that
are close to $A$ and $B$, respectively. In our case, we consider on-state
commutation instead of the regular one, and unlike in [Has09], our proof works
only for projectors.

######  Result 4 (Making almost commuting projectors commute).

Given any two projectors $P_{1}$ and $P_{2}$ and a state $|\psi\rangle$ we
have that if $\left\|(P_{1}P_{2}-P_{2}P_{1})|\psi\rangle\right\|=\epsilon$
then there is a projector $P_{2}^{\prime}$ that is close to the original
projector on the state
$\left\|(P_{2}^{\prime}-P_{2})|\psi\rangle\right\|\leq\sqrt{2}\epsilon$ and
$[P_{1},P_{2}^{\prime}]=0$.

###  1.4 Related Work

A prominent result in the literature is that a joint distribution for a set of
measurements exists iff all the operators pairwise commute. Different versions
of this result were previously proven: In [Nel67] the author considers the
case of continuous variables and $N$ observables. A similar result but without
specifying the Hilbert space is achieved with different mathematical tools in
[Fin82]. In the specific case where we have only two observables, we mention
three works; In [Fin73] and [ME84] the authors prove the classic problem in a
way similar to each other, but using different mathematical tools. All but the
first work mentioned here focus on the joint distribution as a functional from
the space of states. An approach using $*$-algebras was presented by Hans
Maassen in [Maa06, Maa10].

The authors of [GN02] analyze the case of general measurements but prove that
the measurement operators pairwise commute iff the square-root operators
permute (Corollaries 3 and 6 in [GN02]), in the sense of our Definition 3 (for
all states in $\mathcal{H}$). In general the problem of conditional
probabilities in Quantum Mechanics was discussed by Cassinelli and Zanghi in
[CZ83].

The related problems of incompatible devices measurement and joint
measurability of quantum effects are covered in [HMZ16] and [BN18]
respectively.

In [Lin97, FR96] the authors prove that for any two Hermitian matrices if
their commutator has small norm, then there are operators close to the
originals that fully commute. In [Has09] Hastings proves how close the new
operators are in terms of the norm of the commutator.

### Organization

In Section 2, we provide some preliminaries. Then in Section 3, we discuss
quantum distributions and their properties. Finally, in Section 4, we discuss
the almost-commuting case.

### Acknowledgements

JC thanks Dominique Unruh and Christian Schaffner for helpful discussions. JC
was supported by a NWO VIDI grant (Project No. 639.022.519). Most of this work
was done while AG was affiliated to CWI and QuSoft.

##  2 Preliminaries

###  2.1 Notation

In this work, we are going to use calligraphic letters
($\mathcal{S},\mathcal{R},...$) to denote sets. We denote
$[N]:=\\{1,2,\dots,N\\}$. For $\mathcal{S}\subseteq[N]$, we denote by
$\mathcal{S}(i)$ the $i$-th element of the set $\mathcal{S}$ in ascending
order. For some fixed sets $\mathcal{X}_{1},...,\mathcal{X}_{N}$, we denote by
$\vec{x}$ an element of $\mathcal{X}_{1}\times\cdots\mathcal{X}_{N}$ and for
$\mathcal{S}\subseteq[N]$ we have
$\vec{x}_{\mathcal{S}}:=(x_{\mathcal{S}(1)},\dots,x_{\mathcal{S}(|\mathcal{S}|)})$.
We denote the set of all $t$-element permutations by $\Sigma_{t}$. For some
complex number $c=a+b\textnormal{i}$, we define $\mathfrak{Re}(c)=a$ as its
real part.

###  2.2 Quantum Measurements

We briefly review some concepts in quantum computation/information and we
refer to [NC11] for an more detailed introduction to these topics.

Quantum states are represented by positive semi-definite operators with unit
trace, i.e., $\rho\succeq 0,\textnormal{Tr}(\rho)=1$. We denote the set of all
density operators on some Hilbert space $\mathcal{H}$ by
$\mathcal{D}(\mathcal{H})$.

To describe general measurements, we use the notion of Positive Operator
Valued Measure (POVM). The only requirement of POVMs is that they consist of
positive operators and sum up to the identity operator. More formally, a POVM
with set of outcomes $\mathcal{X}$ is described by a set of operators
$\mathcal{M}=\\{Q^{x}\\}_{x\in\mathcal{X}}$, where $\forall
x\in\mathcal{X}:Q^{x}\succeq 0$, and
$\sum_{x\in\mathcal{X}}Q^{x}=\mathbbm{1}$.

We denote the probability of getting the outcome $x$ when measuring $\rho$
with the measurement $\mathcal{M}$ by
$\mathbb{P}[x\leftarrow\mathcal{M}(\rho)]:=\textnormal{Tr}(Q^{x}\rho)$. To
describe the post-measurement state, we can write down operators of
$\mathcal{M}$ as products of linear operators on $\mathcal{H}$ (denoted by
$\mathcal{L}(\mathcal{H})$), $Q^{x}=A^{x\dagger}A^{x}$, where
$A^{x}\in\mathcal{L}(\mathcal{H})$ (such a decomposition is always possible
since $Q^{x}\succeq 0$). The post-measurement state when the outcome of
$\mathcal{M}$ on $\rho$ is $x$ is given by

$\rho_{x}:=\frac{A^{x}\rho A^{x\dagger}}{\textnormal{Tr}(Q^{x}\rho)}.$ (1)

The operator $A^{x}$ is called the _square root_ of $Q^{x}$.

##  3 Quantum Distributions

In this section, we study the description of the statistics of outcomes
derived from a sequence of measurements. Our approach is to consider the
quantum version of the classical properties described in Section 1.1. Since
quantum measurements do not commute in general, these quantum properties do
not always hold. We then study the connection between properties of the
measurements and the properties of their outcome distribution.

The structure of our proofs follows [ME84], where they show that for two
Hermitian observables there is a joint distribution for the outcomes of their
joint measurement iff they commute. We stress that the result in [ME84] only
works for measurements that commute on every quantum state and our result
extends it to the case of joint distributions defined on a limited set of
states.

In the following, we denote the observables with $Q$ and their square-roots
with $R$. In Section 3.1, we define the quantum analogues of the classical
properties of distributions defined in Section 1.1. Then, in Section 3.2, we
state and prove the main result of this section, where we show a connection
between existence of a distribution and permutability—a generalization of
commutativity—of the corresponding measurement operators.

###  3.1 Quantum Distributions

We analyse a functional from the set of density operators and finite sets of
$N$ random variables $X_{1},X_{2},\dots,X_{N}$ to reals
$\mathbf{W}_{[N]}:\mathcal{D}(\mathcal{H})\times(\mathcal{X}_{1}\times\cdots\times\mathcal{X}_{N})\to[0,1]$.
We define this functional666Note that the superscript of
$\mathbf{W}^{\rho}_{[N]}(\vec{x})$ denotes the first input to the functional,
so we have $\mathbf{W}_{[N]}(\rho,\vec{x})$. as

$\mathbf{W}_{[N]}^{\rho}(\vec{x}):=\textnormal{Tr}\left(Q_{[N]}^{\vec{x}}\rho\right),$
(2)

where $Q_{[N]}^{\vec{x}}$ is a positive semidefinite operator corresponding to
the outcome $\vec{x}\in\mathcal{X}_{1}\times\cdots\times\mathcal{X}_{N}$. The
subscript $[N]$ of $\mathbf{W}$ denotes the set of indices of random variables
that the distribution is defined on. This definition is similar to the one
proposed by [ME84].

The starting point of our discussion is that every random variable $X_{i}$
corresponds to the measurement $\mathcal{M}_{i}=\\{Q_{i}^{x_{i}}\\}$. So we
have to keep in mind that these operators are fixed throughout this note.

Given the definition of $\mathbf{W}$, we can state conditions so that it can
be seen as a joint quantum distribution:

  * •

Normalization: $\sum_{\vec{x}}Q^{\vec{x}}_{[N]}=\mathbbm{1}$, which implies
that for all
$\rho\in\mathcal{D}(\mathcal{H}),\;\sum_{\vec{x}}\mathbf{W}^{\rho}(\vec{x})=1$.

  * •

Linearity: for every
$\vec{x}\in\mathcal{X}_{1}\times\cdots\times\mathcal{X}_{N}$,
$\rho_{1},\rho_{2}\in\mathcal{D}(\mathcal{H})$ and
$\lambda_{1},\lambda_{2}\in[0,1]$, we have that

$\mathbf{W}^{\lambda_{1}\rho_{1}+\lambda_{2}\rho_{2}}_{[N]}(\vec{x})=\lambda_{1}\mathbf{W}^{\rho_{1}}_{[N]}(\vec{x})+\lambda_{2}\mathbf{W}^{\rho_{2}}_{[N]}(\vec{x}).$

  * •

Non-negativity: for every
$\vec{x}\in\mathcal{X}_{1}\times\cdots\times\mathcal{X}_{N}$ and
$\rho\in\mathcal{D}(\mathcal{H})$, we have
$\mathbf{W}^{\rho}_{[N]}(\vec{x})\geq 0$.

We describe the quantum analogues of the properties described in Section 1.1.

#### Marginals.

We start with a sequence of general measurements (i.e. POVMs):
$\\{\mathcal{M}_{i}\\}_{i\in[N]}$, where
$\mathcal{M}_{i}:=\\{Q_{i}^{x}\\}_{x\in\mathcal{X}_{i}}$ for all $i$ and all
$Q_{i}^{x}\succeq 0$ and $\sum_{x\in\mathcal{X}_{i}}Q^{x}_{i}=\mathbbm{1}$.
Moreover, for $\mathcal{S}\subseteq[N]$ we define $Q^{\vec{y}}_{\mathcal{S}}$
to be measurement operators where
$\vec{y}\in\mathcal{X}_{\mathcal{S}(1)}\times\cdots\times\mathcal{X}_{\mathcal{S}(|\mathcal{S}|)}$.

Given $Q^{\vec{y}}_{\mathcal{S}}$ and their corresponding square-roots
$R^{\vec{y}}_{\mathcal{S}}$ and $\rho$, we have that if
$\textnormal{Tr}\left(R^{\vec{y}}_{\mathcal{S}}\rho
R^{\vec{y}\dagger}_{\mathcal{S}}\right)\neq 0$, then we define the conditional
distribution for any sequence $\vec{x}$ as

$\mathbf{W}_{[N]}^{\rho}(\vec{x}\mid\vec{y}):=\mathbf{W}_{[N]}^{R^{\vec{y}}_{\mathcal{S}}\rho
R^{\vec{y}\dagger}_{\mathcal{S}}}(\vec{x})/\textnormal{Tr}R^{\vec{y}}_{\mathcal{S}}\rho
R^{\vec{y}\dagger}_{\mathcal{S}}.$ (3)

For all those measurements, for a set
$\mathcal{F}\subseteq\mathcal{D}(\mathcal{H})$, and for
$\mathcal{U}\subseteq[N]$, we define the “orbit” of the post-measurement
states. For any $\mathcal{T}\subseteq[N]$ of size $t$, we take $s\leq t$ sets
$\mathcal{S}_{1},...,\mathcal{S}_{s}$ that are a partition of $\mathcal{T}$.
We then consider the post-measurement states generated by sequences of
measurements corresponding to $\mathcal{S}_{i}$:

$\displaystyle\mathcal{G}_{\mathcal{U}}(\mathcal{F}):=\left\\{R^{\vec{y}_{s}}_{\mathcal{S}_{s}}\cdots
R^{\vec{y}_{1}}_{\mathcal{S}_{1}}\psi
R^{\vec{y}_{1}\dagger}_{\mathcal{S}_{1}}\cdots
R^{\vec{y}_{s}\dagger}_{\mathcal{S}_{s}}/\textnormal{Tr}\left(R^{\vec{y}_{s}}_{\mathcal{S}_{s}}\cdots
R^{\vec{y}_{1}}_{\mathcal{S}_{1}}\psi
R^{\vec{y}_{1}\dagger}_{\mathcal{S}_{1}}\cdots
R^{\vec{y}_{s}\dagger}_{\mathcal{S}_{s}}\right):\psi\in\mathcal{F},\mathcal{T}\subseteq\mathcal{U},\right.$
$\displaystyle\left.s\leq\left|\mathcal{T}\right|,\;\mathcal{S}_{1},...,\mathcal{S}_{s}\subseteq\mathcal{T},\bigcup_{i=1}^{s}\mathcal{S}_{i}=\mathcal{T},\forall
i\neq
j\,\mathcal{S}_{i}\cap\mathcal{S}_{j}=\emptyset,\vec{y}_{i}\in\mathcal{X}_{\mathcal{S}_{i}(1)}\times\cdots\times\mathcal{X}_{\mathcal{S}_{i}(|\mathcal{S}_{i}|)}\right\\},$
(4)

where $R^{\vec{y}_{i}}_{\mathcal{S}_{i}}$ are the square-root operators of
$Q^{\vec{y}_{i}}_{\mathcal{S}_{i}}=R^{\vec{y}_{i}\dagger}_{\mathcal{S}_{i}}R^{\vec{y}_{i}}_{\mathcal{S}_{i}}$.
The subscript of $\mathcal{G}$ denotes the set we take the subsets of, usually
it is $[N]$ but later we also consider $[N]\setminus\mathcal{S}$ for some
$\mathcal{S}$.

With our quantum marginals property, we require that the operator we get after
we sum over a subset of variables is still a valid measurement operator.

######  Property 5 (Quantum Marginals).

We say that the joint distribution $\mathbf{W}$ has the _quantum marginals
property on set $\mathcal{F}$_ if for every $\mathcal{S}\subseteq[N]$, there
is a measurement
$\mathcal{M}_{\mathcal{S}}=\\{Q^{\vec{y}}\\}_{\vec{y}\in(\mathcal{X}_{i})_{i\in\mathcal{S}}}$
such that for every value
$\vec{x}\in\mathcal{X}_{1}\times\mathcal{X}_{2}\times\cdots\times\mathcal{X}_{N}$,
denoting $\vec{x}:=(x_{1},x_{2},\dots,x_{N})$ and for every density operator
$\rho\in\mathcal{G}_{[N]}(\mathcal{F})$ defined as in Equation (3.1) we have
that

$\displaystyle\mathbf{W}^{\rho}_{\mathcal{S}}(\vec{x}_{\mathcal{S}}):=\textnormal{Tr}\left(Q^{\vec{x}_{\mathcal{S}}}_{\mathcal{S}}\rho\right)=\sum_{x_{i}\in\mathcal{X}_{i},i\in[N]\setminus\mathcal{S}}\mathbf{W}^{\rho}_{[N]}(\vec{x}).$
(5)

Additionally for $|\mathcal{S}|=1$ the operators $Q^{x_{i}}_{i}$ are the
operators from $\mathcal{M}_{i}$.

#### Disjointness.

It follows from the definition of POVMs that the quantum measurement operators
need not be orthogonal, and this implies that the disjointness property
(Property 2 does not hold in generality quantumly.

Disjointness is a property that concerns a post-measurement state of a set
$\mathcal{S}$ of variables. To ensure the existence of a measurement operator
corresponding to $\mathcal{S}$, we need to assume Property 5.

######  Property 6 (Quantum Disjointness).

Let $\mathbf{W}$ be a joint distribution for which Property 5 holds. We say
that $\mathbf{W}$ has the _quantum disjointness property on set $\mathcal{F}$_
if for every subset $\mathcal{S}\subseteq[N]$, for every density operator
$\rho\in\mathcal{G}_{[N]\setminus\mathcal{S}}(\mathcal{F})$, and for every
value
$\vec{x}\in\mathcal{X}_{1}\times\mathcal{X}_{2}\times\cdots\times\mathcal{X}_{N}$
and $\vec{y}\in\prod_{i\in\mathcal{S}}\mathcal{X}_{i}$, we have that if
$\vec{y}\neq\vec{x}_{\mathcal{S}}$, then

$\displaystyle\mathbf{W}^{\rho}_{[N]}(\vec{x}\mid\vec{y})\mathbf{W}^{\rho}_{[N]}(\vec{y})=\textnormal{Tr}\left(Q^{\vec{x}}_{[N]}R^{\vec{y}}_{\mathcal{S}}\rho
R^{\vec{y}\dagger}_{\mathcal{S}}\right)=0.$ (6)

#### Reducibility.

Reducibility (Property 3) is a similar property to disjointness but with the
key difference that we condition on the same event:

######  Property 7 (Quantum Reducibility).

Let $\mathbf{W}$ be a joint distribution for which Property 5 holds. We say
that $\mathbf{W}$ has the _quantum reducibility property on set $\mathcal{F}$_
if for every subset $\mathcal{S}\subset[N]$, every density operator
$\rho\in\mathcal{G}_{[N]\setminus\mathcal{S}}(\mathcal{F})$, and value
$\vec{x}\in\mathcal{X}_{1}\times\mathcal{X}_{2}\times\cdots\times\mathcal{X}_{N}$,
we have that

$\displaystyle\mathbf{W}^{\rho}_{[N]}(\vec{x}\mid\vec{x}_{\mathcal{S}})\mathbf{W}^{\rho}_{[N]}(\vec{x}_{\mathcal{S}})=\textnormal{Tr}\left(Q^{\vec{x}}_{[N]}R^{\vec{x}_{\mathcal{S}}}_{\mathcal{S}}\rho
R^{\vec{x}_{\mathcal{S}}\dagger}_{\mathcal{S}}\right)=\textnormal{Tr}\left(Q^{\vec{x}}_{[N]}\rho\right).$
(7)

new line

Note that the last two properties together allow us to conclude that the
operators are (morally) _on-state projections_ : Property 6 plays the role of
different projectors being orthogonal and Property 7 that projecting twice to
the same space does not change the resulting state.

More concretely, we say that the $R_{i}$’s are on-state projectors on
$\psi\in\mathcal{F}$ if for all $\mathcal{S}\subseteq[N]$, all
$\vec{x}\in\mathcal{X}_{1}\times\cdots\times\mathcal{X}_{N}$, all
$\vec{y}\in\prod_{i\in\mathcal{S}}\mathcal{X}_{i}$, and for
$R_{\mathcal{S}}^{\vec{y}}:=R^{y_{1}}_{\mathcal{S}(1)}R^{y_{2}}_{\mathcal{S}(2)}\cdots
R^{y_{t}}_{\mathcal{S}(t)}$ and
$Q_{\mathcal{S}}^{\vec{y}}:=R_{\mathcal{S}}^{\vec{y}\dagger}R_{\mathcal{S}}^{\vec{y}}$
(similarly for $[N]$), we have

$\displaystyle\textnormal{Tr}\left(R^{\vec{y}\dagger}_{\mathcal{S}}Q^{\vec{x}}_{[N]}R^{\vec{y}}_{\mathcal{S}}\psi\right)=\delta_{\vec{y},\vec{x}_{\mathcal{S}}}\textnormal{Tr}\left(Q^{\vec{x}}_{[N]}\psi\right).$
(8)

#### Sequential Independence

As previously discussed, the notion of time order in the quantum setting is
much more delicate as the probabilistic events no longer commute. Let us go
back to the example of the simple sequence $(A,B)$ from Section 1.1 but now
consider $A$ and $B$ as quantum observables measured on the state $\rho$. Let
us assume for simplicity that $A$ and $B$ are projections. The probability of
measuring $a$ with $A$ is $\textnormal{Tr}\left(A\rho\right)$ and the state
after this measurement is $\rho_{a}:=\frac{A\rho
A}{\textnormal{Tr}\left(A\rho\right)}$ so the probability of measuring the
sequence $(a,b)$ equals

$\mathbb{P}[b\leftarrow B(\rho_{a})]\mathbb{P}[a\leftarrow
A(\rho)]=\textnormal{Tr}\left(B\frac{A\rho
A}{\textnormal{Tr}(A\rho)}\right)\textnormal{Tr}\left(A\rho\right)=\textnormal{Tr}\left(ABA\rho\right).$
(9)

On the other hand the probability of measuring the sequence $(b,a)$ equals
$\textnormal{Tr}\left(BAB\rho\right)$ which is in general different than
Equation (9). This simple example shows that sequential independence is not
attained by all quantum joint probabilities. More formally, the notion of
sequential independence from [GN02] for quantum joint probabilities can be
stated as follows.

######  Property 8 (Quantum Sequential Independence).

Let $\mathbf{W}$ be a joint distribution for which Property 5 holds. We say
that $\mathbf{W}$ has the _quantum sequential independence property on set
$\mathcal{F}$_ if for every density operator $\psi\in\mathcal{F}$, for any
$\mathcal{T}\subseteq[N]$ of size $t$, for all $s\leq t$, partition
$\mathcal{S}_{1},...,\mathcal{S}_{s}$ of $\mathcal{T}$, permutation
$\sigma\in\Sigma_{s}$, and
$\vec{x}\in\mathcal{X}_{1}\times\mathcal{X}_{2}\times\cdots\times\mathcal{X}_{N}$
such that $\vec{x}:=(x_{1},x_{2},\dots,x_{N})$ and
$\vec{y}_{i}:=\left(x_{\mathcal{S}_{i}(1)},x_{\mathcal{S}_{i}(2)},\dots,x_{\mathcal{S}_{i}(\left|\mathcal{S}_{i}\right|)}\right)$,
we have that

Tr
$\displaystyle\left(Q^{\vec{y}_{s}}_{\mathcal{S}_{s}}R^{\vec{y}_{s-1}}_{\mathcal{S}_{s-1}}\cdots
R^{\vec{y}_{1}}_{\mathcal{S}_{1}}\psi
R^{\vec{y}_{1}\dagger}_{\mathcal{S}_{1}}R^{\vec{y}_{2}\dagger}_{\mathcal{S}_{2}}\cdots
R^{\vec{y}_{s-1}\dagger}_{\mathcal{S}_{s-1}}\right)$
$\displaystyle=\textnormal{Tr}\left(Q^{\vec{y}_{\sigma(s)}}_{\mathcal{S}_{\sigma(s)}}R^{\vec{y}_{\sigma(s-1)}}_{\mathcal{S}_{\sigma(s-1)}}\cdots
R^{\vec{y}_{\sigma(1)}}_{\mathcal{S}_{\sigma(1)}}\psi
R^{\vec{y}_{\sigma(1)}\dagger}_{\mathcal{S}_{\sigma(1)}}R^{\vec{y}_{\sigma(2)}\dagger}_{\mathcal{S}_{\sigma(2)}}\cdots
R^{\vec{y}_{\sigma(s-1)}\dagger}_{\mathcal{S}_{\sigma(s-1)}}\right).$ (10)

######  Theorem 1 (Marginals imply Sequential Independence).

If a joint distribution $\mathbf{W}$ has Property 5, 6, and 7, then it also
has Property 8.

###### Proof.

First note that Properties 5, 6, and 7 directly imply Equation (8).

We now prove the statement for two sets of indices and then argue how to
extend it for $s$ sets. In our restricted case, we have that

$\displaystyle\textnormal{Tr}\left(Q^{\vec{y}_{1}}_{\mathcal{S}_{1}}R^{\vec{y}_{2}}_{\mathcal{S}_{2}}\psi
R^{\vec{y}_{2}\dagger}_{\mathcal{S}_{2}}\right)=\textnormal{Tr}\left(\sum_{\vec{y}^{\prime}}Q^{\vec{y}^{\prime}}_{\mathcal{S}_{1}\cup\mathcal{S}_{2}}R^{\vec{y}_{2}}_{\mathcal{S}_{2}}\psi
R^{\vec{y}_{2}\dagger}_{\mathcal{S}_{2}}\right)$ (11)
$\displaystyle=\textnormal{Tr}\left(Q^{\vec{y}}_{\mathcal{S}_{1}\cup\mathcal{S}_{2}}R^{\vec{y}_{2}}_{\mathcal{S}_{2}}\psi
R^{\vec{y}_{2}\dagger}_{\mathcal{S}_{2}}\right)$ (12)
$\displaystyle=\textnormal{Tr}\left(Q^{\vec{y}}_{\mathcal{S}_{1}\cup\mathcal{S}_{2}}\psi\right),$
(13)

where the first equality comes from the marginals property, the second
equality comes from the disjointness property if we take $\vec{y}$ that agrees
with $\vec{y}_{2}$ on $\mathcal{S}_{2}$, and the last equality comes from the
reducibility property.

The above derivation can be repeated for any other two sets
$\mathcal{S}^{\prime}_{1}$ and $\mathcal{S}^{\prime}_{2}$ such that
$\mathcal{S}^{\prime}_{1}\cup\mathcal{S}^{\prime}_{2}=\mathcal{S}_{1}\cup\mathcal{S}_{2}$.
Any pair like this will yield
$\textnormal{Tr}\left(Q^{\vec{y}}_{\mathcal{S}_{1}\cup\mathcal{S}_{2}}\psi\right)$
that equals
$\textnormal{Tr}\left(Q^{\vec{y}}_{\mathcal{S}^{\prime}_{1}\cup\mathcal{S}^{\prime}_{2}}\psi\right)$
for all other sets $\mathcal{S}^{\prime}_{1}$ and $\mathcal{S}^{\prime}_{2}$,
hence we have proven Property 8 for any two subsets.

In general, we prove a slightly stronger statement than Property 8. We prove
that not only different sequences give the same probabilities but also that
these probabilities equal
$\textnormal{Tr}\left(Q^{\vec{y}}_{\mathcal{T}}\psi\right)$ for some operator
$Q^{\vec{y}}_{\mathcal{T}}$.

The general case holds by taking
$\rho\in\mathcal{G}_{[N]\setminus\mathcal{S}_{s}}(\mathcal{F})$ instead of
$\psi$ and use it in the above calculation. To prove Property 8 for any $s$
sets we consider $\rho=R^{\vec{y}_{s-1}}_{\mathcal{S}_{s-1}}\cdots
R^{\vec{y}_{1}}_{\mathcal{S}_{1}}\psi
R^{\vec{y}_{1}\dagger}_{\mathcal{S}_{1}}R^{\vec{y}_{2}\dagger}_{\mathcal{S}_{2}}\cdots
R^{\vec{y}_{s-1}\dagger}_{\mathcal{S}_{s-1}}$ and
$\textnormal{Tr}\left(Q^{\vec{y}_{s}}_{\mathcal{S}_{s}}\rho\right)$. We shave
off operators from $\rho$ one by one using Equation (13). After $s$ steps we
have that
$\textnormal{Tr}\left(Q^{\vec{y}_{s}}_{\mathcal{S}_{s}}\rho\right)=\textnormal{Tr}\left(Q^{\vec{x}_{\mathcal{T}}}_{\mathcal{T}}\psi\right)$.
Again, repeating this procedure for a different $\rho^{\prime}$ with sets that
sum to the same $\mathcal{T}$ yields the claimed result. ∎

###  3.2 Joint Distributions and Permutability

In this section, we state the definition of a joint distribution that
describes a sequence of quantum measurements done on states from a small set.
We also define a generalization of commutativity and prove that a joint
distribution exists if and only if the measurement operators are permutable.

######  Definition 2 (Quantum Joint Distribution On State).

A joint distribution of $N$ random variables $X_{1},\dots,X_{N}$ that describe
outcomes of general quantum measurements of states $\psi\in\mathcal{F}$ is
defined as a positive, normalized, and linear functional

$\displaystyle\mathbf{W}_{[N]}:\mathcal{D}(\mathcal{H})\times(\mathcal{X}_{1}\times\mathcal{X}_{2}\times\cdots\times\mathcal{X}_{N})\to[0,1],$
(14)

for which

  1. (1)

Quantum Marginals on states in $\mathcal{F}$, Property 5, holds,

  2. (2)

Quantum Disjointness on states in $\mathcal{F}$, Property 6, holds,

  3. (3)

Quantum Reducibility on states in $\mathcal{F}$, Property 7, holds,

  4. (4)

Quantum Sequential Independence on states in $\mathcal{F}$, Property 8, holds.

Next we show the connection between the existence of joint distributions and
requirements on the measurement operators. But first let us define the notion
of on-state permutability.

######  Definition 3 (On-state permutator, (fully) permutable operators).

For any $s$ operators $R_{i}$ and a permutation of the $s$-element set
$\sigma\in\Sigma_{s}$ the permutator on $\psi$ is defined as

$\displaystyle[R_{1},$ $\displaystyle R_{2},\dots,R_{s}]_{\psi}(\sigma):=$
$\displaystyle\textnormal{Tr}\left(R_{s}R_{s-1}\cdots R_{1}\psi
R^{\dagger}_{1}R^{\dagger}_{2}\cdots
R^{\dagger}_{s}\right)-\textnormal{Tr}\left(R_{\sigma(s)}R_{\sigma(s-1)}\cdots
R_{\sigma(1)}\psi R^{\dagger}_{\sigma(1)}R^{\dagger}_{\sigma(2)}\cdots
R^{\dagger}_{\sigma(s)}\right).$ (15)

We say that the operators $R_{1},\dots,R_{s}$ are _permutable_ if
$[R_{1},\dots,R_{s}]_{\psi}(\sigma)=0$ for all $\sigma\in\Sigma_{s}$.
Moreover, we call a set of measurements $\\{\mathcal{M}_{i}\\}_{i}$ _fully
permutable on $\mathcal{F}$_ if all square-root operators $R^{\vec{y}}_{i}$ of
these measurements $\mathcal{M}_{i}$ permute on $\psi\in\mathcal{F}$ for all
$\sigma\in\Sigma_{s}$.

Now we state the theorem connecting existence of joint distributions with
permutability of the measurement operators. This statement extends Theorem
$3.2$ of [ME84], where they prove that if the joint distribution satisfies the
marginals property (they use the name “nondisturbance”), then the operators
pairwise commute.

######  Theorem 4 (Quantum Joint Distribution and Permutability).

There is a quantum joint distribution on states $\psi\in\mathcal{F}$
describing measurement outcomes of $N$ observables $X_{1},\dots,X_{N}$ if and
only if all square roots $R^{x}_{i}$ of $Q^{x}_{i}$ operators of measurements
$\mathcal{M}_{i}$ permute on $\psi\in\mathcal{F}$ and are on-state projectors
according to Equation (8).

###### Proof.

$(\Rightarrow)$ Permutability follows from Property 8 for $N$ single-element
sets $\mathcal{S}_{i}=\\{i\\}$. Being on-state projectors (Equation (8))
follows from Property 6 and Property 7.

$(\Leftarrow)$ The other direction of the proof follows by setting the
measurement operators to
$Q_{\mathcal{S}}^{\vec{y}}:=R^{y_{t}\dagger}_{\mathcal{S}(t)}R^{y_{t-1}\dagger}_{\mathcal{S}(t-1)}\cdots
R^{y_{1}\dagger}_{\mathcal{S}(1)}R^{y_{1}}_{\mathcal{S}(1)}R^{y_{2}}_{\mathcal{S}(2)}\cdots
R^{y_{t}}_{\mathcal{S}(t)}$, for every set $\mathcal{S}\subseteq[N]$ with
$|\mathcal{S}|=t$. Similarly we define
$R_{\mathcal{S}}^{\vec{y}}:=R^{y_{1}}_{\mathcal{S}(1)}R^{y_{2}}_{\mathcal{S}(2)}\cdots
R^{y_{t}}_{\mathcal{S}(t)}$.

The marginals property follows from the fact that
$\sum_{x_{i}\in\mathcal{X}_{i}}Q_{i}^{x_{i}}=\mathbbm{1}$:

$\displaystyle\sum_{x_{i}\in\mathcal{X}_{i},i\in[N]\setminus\mathcal{S}}\textnormal{Tr}\left(Q^{x_{i_{i}}}_{i_{1}}R^{\vec{y}}_{[N]\setminus\\{i_{1}\\}}\rho
R^{\vec{y}\dagger}_{[N]\setminus\\{i_{1}\\}}\right)$
$\displaystyle=\sum_{x_{i}\in\mathcal{X}_{i},i\in[N]\setminus(\mathcal{S}\cup\\{i_{1}\\})}\textnormal{Tr}\left(Q^{x_{i_{2}}}_{i_{2}}R^{\vec{y}}_{[N]\setminus\\{i_{1},i_{2}\\}}\rho
R^{\vec{y}\dagger}_{[N]\setminus\\{i_{1},i_{2}\\}}\right)=\cdots=\textnormal{Tr}\left(Q^{\vec{y}}_{\mathcal{S}}\rho\right).$
(16)

Properties 6 and 7 are natural consequences of Equation (8). The only
difference between the properties and on-state projections is the set
$\mathcal{G}_{[N]\setminus\mathcal{S}}(\mathcal{F})$ versus just
$\mathcal{F}$. Nonetheless, with our definition of
$R_{\mathcal{S}}^{\vec{y}}$, Equation (8) implies disjointness and
reducibility.

In Theorem 1 we have already proved that marginals together with disjointness
and reducibility imply sequential independence, which concludes our proof. ∎

###  3.3 Pairwise on-state commutation does not imply full commutation

We now investigate whether full permutability is the weakest assumption we can
have for joint distributions to exist.

When we consider this question for the full Hilbert space
$\mathcal{F}=\mathcal{D}(\mathcal{H})$, this problem has been considered by a
number of works in the literature [Nel67, Fin73, Fin82, ME84] and it is well-
known that it suffices for the measurement operators to pairwise commute,
i.e., pairwise commutation on all possible quantum states implies
permutability of the operators.

Our goal in this section is to consider the case where
$\mathcal{F}\subsetneq\mathcal{D}(\mathcal{H})$. In particular, in [CETU18],
in order to connect perfect quantum indifferentiability to classical
indifferentiability with stateless simulators777 Roughly, we say that $A$ is
classical (quantum) indifferentiable from $B$ iff we can map classical (resp.
quantum) attacks on $A$ to classical (resp. quantum) attacks on $B$ using
simulators. Moreover, we say that the simulator is stateless if it does not
store any internal state. , they rely on the following conjecture.

######  Conjecture 2 (Conjecture 2 from [CETU18]).

Consider $N$ binary measurements described by projectors $P_{1},\dots,P_{N}$,
and a quantum state $|\Psi\rangle$.

Assume that any $t$ out of the $N$ measurements permute on state
$|\Psi\rangle$. That is, for any $I$ with $|I|=t$, if
$P^{\prime}_{1},\dots,P^{\prime}_{t}$ and
$P^{\prime\prime}_{1},\dots,P^{\prime\prime}_{t}$ are the projectors
$\\{P_{i}\\}_{i\in I}$ (possibly in different order), then
$P^{\prime}_{t},\dots,P^{\prime}_{1}|\Psi\rangle=P^{\prime\prime}_{t},\dots,P^{\prime\prime}_{1}|\Psi\rangle$.

Then there exist random variables $X_{1},\dots,X_{N}$ with a joint
distribution $D$ such that for any $I=\\{i_{1},\dots,i_{t}\\}$ the joint
distribution of $X_{i_{1}},\dots,X_{i_{t}}$ is the distribution of the
outcomes when we measure $|\Psi\rangle$ with measurements
$P_{i_{1}},\dots,P_{i_{t}}$.

Conjecture 2 states that if any $t$ measurement operators permute on state
$|\Psi\rangle$ then there is a joint distribution. From Theorem 4, we know
that if there is a joint distribution then the operators fully permute. Hence,
the key point of the conjecture is that if any $t$ operators permute on a
state, then they fully permute on it. However, we show here that 2 is not
true, in general.

######  Theorem 5.

There is a set of four projectors $\\{P_{1},P_{2},P_{3},P_{4}\\}$ and a state
$|\phi\rangle\in\mathbb{C}^{8}$ such that the projectors are 2-permutable
(they pairwise commute) on state $|\phi\rangle$ and they are _not_
4-permutable on $|\phi\rangle$.

###### Proof.

To prove the statement we found an example of such operators and a state
numerically by random constrained search. We consider 4 projectors $P_{i}$ and
a state $|\phi\rangle$ of dimension 8. The constraints we impose are

$\displaystyle\forall i,j\neq i\;[P_{i},P_{j}]|\phi\rangle=0,$ (17)

moreover operators $P_{i}$ are projectors: $\forall iP_{i}^{2}=P_{i}$ and
$|\phi\rangle$ is a unit-norm complex vector.

We look for an example to the statement that 2-permutability (commutativity)
does not imply 4-permutability, so that

$\displaystyle(P_{1}P_{2}P_{3}P_{4}-P_{3}P_{4}P_{1}P_{2})|\phi\rangle\neq 0.$
(18)

To find such example we used software for symbolic computing to define the
problem and maximize
$\|(P_{1}P_{2}P_{3}P_{4}-P_{3}P_{4}P_{1}P_{2})|\phi\rangle\|$, where we
maximize over operators $P_{i}$ and the state $|\phi\rangle$.

The result of our optimization can be found in Appendix A. Note that however
we consider vector equalities—instead of just traces like in Theorem 4—our
example provides a stronger argument for the necessity of full permutability.
∎

One can notice by looking at the optimization problem that it is not a
semidefinite problem, nor that it has any other structure that is easy to
exploit. For that reason finding larger instances is computationally very
expensive.

We notice that Theorem 5 actually disproves a slightly stronger version of
Conjecture 2. In the use of Conjecture 2 in [CETU18], they implicitly assume
that we can replace $P_{i}$ by $\mathbbm{1}-P_{i}$ and the permutation still
holds. While this modification gives a slightly stronger assumption, our
counterexample in Theorem 5 works just as well.

For the joint distribution in Conjecture 2 to exist, we know from Theorem 4
that all operators must on-state permute. An important observation is that
Conjecture 2 regards vector equalities and Theorem 4 regards measurement
outcomes. The theorem is “easier” than the former and our counterexample works
with vector equalities, hence we indeed disprove Conjecture 2.

In [Ebr18] the author uses a different conjecture and different reasoning to
prove the existence of the joint distribution. Our counterexample does not
disprove this other approach and we refer interested readers to [Ebr18].

##  4 Almost On-State Commutation

In the last part of the paper we discuss almost commutativity in the on-state
case. In particular, we show here that if we have two projectors that almost
commute on a state then we can define a projector that fully commutes with one
of the original operators and is on-state close to the second one.

The main tool that we need to prove this result is the Jordan’s lemma.

######  Lemma 6 (Jordan’s lemma [Jor75]).

Let $P_{1}$ and $P_{2}$ be two projectors with rank
$r_{i}:=\textnormal{rank}(P_{i})$ for $i\in\\{1,2\\}$. Then both projectors
can be decomposed simultaneously in the form
$P_{i}=\bigoplus_{k=1}^{r_{i}}P_{i}^{k}$, where $P_{i}^{k}$ denote rank-1
projectors acting on one- or two-dimensional subspaces. We denote the one- and
two-dimensional subspaces by $S_{1},\dots,S_{l}$ and subspaces by
$T_{1},\dots,T_{l^{\prime}}$, respectively. The eigenvectors $|v_{k,1}\rangle$
and $|v_{k,2}\rangle$ of $P_{1}^{k}$ and $P_{2}^{k}$ respectively are related
by:

$\displaystyle|v_{k,2}\rangle=\cos\theta_{k}|v_{k,1}\rangle+\sin\theta_{k}|v^{\perp}_{k,1}\rangle,|v_{k,1}\rangle=\cos\theta_{k}|v_{k,2}\rangle-\sin\theta_{k}|v^{\perp}_{k,2}\rangle.$
(19)

We can now prove our result.

######  Theorem 7 (Making almost commuting projectors commute).

Given any two projectors $P_{1}$ and $P_{2}$ and a state $|\psi\rangle$ we
have that if $\left\|(P_{1}P_{2}-P_{2}P_{1})|\psi\rangle\right\|=\epsilon$
then there is a projector $P_{2}^{\prime}$ that is close to the original
projector on the state
$\left\|(P_{2}^{\prime}-P_{2})|\psi\rangle\right\|\leq\sqrt{2}\epsilon$ and
$[P_{1},P_{2}^{\prime}]=0$.

###### Proof.

By Jordan’s lemma (Lemma 6), there exist bits
$\lambda_{i,1},\lambda_{i,2}\in\\{0,1\\}$ and vectors
$|u_{1}\rangle,...,|u_{m}\rangle$ and
$|v_{1,1}\rangle,|v_{1,2}\rangle,...,|v_{\ell,1}\rangle,|v_{\ell,2}\rangle$,
such that

  1. 1.

$P_{1}=\sum_{i\in[m]}\lambda_{i,1}|u_{i}\rangle\langle
u_{i}|+\sum_{i\in[\ell]}|v_{i,1}\rangle\langle v_{i,1}|$ and
$P_{2}=\sum_{i\in[m]}\lambda_{i,2}|u_{i}\rangle\langle
u_{i}|+\sum_{i\in[\ell]}|v_{i,2}\rangle\langle v_{i,2}|$;

  2. 2.

$\langle u_{i}|u_{k}\rangle=0$ and $\langle u_{i}|v_{j,b}\rangle=0$ for all
$b,i,j$ and $k\neq i$;

  3. 3.

$\langle v_{j,b^{\prime}}|v_{i,b}\rangle=0$ for $i\neq j$ and any
$b,b^{\prime}$;

  4. 4.

$0<\langle v_{i,1}|v_{i,2}\rangle<1$.

Let $\theta_{i}$ be the angle between $|v_{i,1}\rangle$ and $|v_{i,2}\rangle$
(i.e. $\cos\theta_{i}=\langle v_{i,1}|v_{i,2}\rangle$), and
$|v_{i,1}^{\perp}\rangle$ be the state orthogonal to $|v_{i,1}\rangle$ in the
subspace spanned by these two vectors. Since the non-commuting part of $P_{1}$
and $P_{2}$ must come from the pairs $|v_{i,1}\rangle,|v_{i,2}\rangle$, we
will define $P_{2}^{\prime}$ by removing the non-commuting part of $P_{2}$,
shifting the vector $|v_{i,2}\rangle$, to either $|v_{i,1}\rangle$ or
$|v_{i,1}^{\perp}\rangle$:

$P_{2}^{\prime}=\sum_{i\in[m]}\lambda_{i,2}|u_{i}\rangle\langle
u_{i}|+\sum_{i\in[\ell]:\theta_{i}\leq\frac{\pi}{4}}|v_{i,1}\rangle\langle
v_{i,1}|+\sum_{i\in[\ell]:\theta_{i}>\frac{\pi}{4}}|v_{i,1}^{\perp}\rangle\langle
v_{i,1}^{\perp}|.$

We have clearly that $[P_{1},P_{2}^{\prime}]=0$ since the two projectors are
simultaneously diagonalizable and we now want to prove that

$\displaystyle\left\|(P_{2}^{\prime}-P_{2})|\psi\rangle\right\|\leq\sqrt{2}\varepsilon.$

Notice that

$\displaystyle\left\|(P_{2}^{\prime}-P_{2})|\psi\rangle\right\|^{2}$
$\displaystyle=\left\|\sum_{i\in[l^{\prime}]:\theta_{i}\leq\frac{\pi}{4}}\left(|v_{i,1}\rangle\langle
v_{i,1}|\psi\rangle-|v_{i,2}\rangle\langle
v_{i,2}|\psi\rangle\right)+\sum_{i\in[l^{\prime}]:\theta_{i}>\frac{\pi}{4}}\left(|v_{i,1}^{\perp}\rangle\langle
v_{i,1}^{\perp}|\psi\rangle-|v_{i,2}\rangle\langle
v_{i,2}|\psi\rangle\right)\right\|^{2}$ (20)
$\displaystyle=\sum_{i\in[l^{\prime}]:\theta_{i}\leq\frac{\pi}{4}}\left\||v_{i,1}\rangle\langle
v_{i,1}|\psi\rangle-|v_{i,2}\rangle\langle
v_{i,2}|\psi\rangle\right\|^{2}+\sum_{i\in[l^{\prime}]:\theta_{i}>\frac{\pi}{4}}\left\||v_{i,1}^{\perp}\rangle\langle
v_{i,1}^{\perp}|\psi\rangle-|v_{i,2}\rangle\langle
v_{i,2}|\psi\rangle\right\|^{2},$ (21)

where in the last step we used that $\langle
v_{i,b^{\prime}}|v_{j,b}\rangle=0$ for $i\neq j$.

Using that
$|v_{i,2}\rangle=\cos{\theta_{i}}|v_{i,1}\rangle+\sin{\theta_{i}}|v_{i,1}^{\perp}\rangle$,
we have that if $\theta_{i}\leq\frac{\pi}{4}$, then

$\displaystyle\left\|\langle v_{i,1}|\psi\rangle|v_{i,1}\rangle-\langle
v_{i,2}|\psi\rangle|v_{i,2}\rangle\right\|^{2}$
$\displaystyle=\sin^{4}\theta_{i}|\langle
v_{i,1}|\psi\rangle|^{2}-2\sin^{3}\theta_{i}\cos\theta_{i}\mathfrak{Re}(\langle
v_{i,1}^{\perp}|\psi\rangle\langle
v_{i,1}|\psi\rangle)+\sin^{2}\theta_{i}\cos^{2}\theta_{i}|\langle
v_{i,1}^{\perp}|\psi\rangle|^{2}$ $\displaystyle+\sin^{4}\theta_{i}|\langle
v_{i,1}^{\perp}|\psi\rangle|^{2}+2\sin^{3}\theta_{i}\cos\theta_{i}\mathfrak{Re}(\langle
v_{i,1}|\psi\rangle\langle
v_{i,1}^{\perp}|\psi\rangle)+\sin^{2}\theta_{i}\cos^{2}\theta_{i}|\langle
v_{i,1}|\psi\rangle|^{2}$ $\displaystyle\leq
2\sin^{2}\theta_{i}\cos^{2}\theta_{i}(|\langle
v_{i,1}^{\perp}|\psi\rangle|^{2}+|\langle v_{i,1}|\psi\rangle|^{2}),$ (22)

where in the inequality we used our assumption that
$\theta_{i}\leq\frac{\pi}{4}$ which implies that
$\sin\theta_{i}\leq\cos\theta_{i}$.

Using similar calculations, we have that if $\theta_{i}\geq\frac{\pi}{4}$

$\displaystyle\left\|\langle
v_{i,1}^{\perp}|\psi\rangle|v_{i,1}^{\perp}\rangle-\langle
v_{i,2}|\psi\rangle|v_{i,2}\rangle\right\|^{2}\leq
2\sin^{2}\theta_{i}\cos^{2}\theta_{i}(|\langle
v_{i,1}^{\perp}|\psi\rangle|^{2}+|\langle v_{i,1}|\psi\rangle|^{2}).$ (23)

We will show now that

$\sum_{i}\sin^{2}\theta_{i}\cos^{2}\theta_{i}(|\langle
v_{i,1}^{\perp}|\psi\rangle|^{2}+|\langle
v_{i,1}|\psi\rangle|^{2})=\varepsilon^{2},$

which finishes the proof:

$\displaystyle\varepsilon^{2}$
$\displaystyle=\left\|(P_{2}P_{1}-P_{1}P_{2})|\psi\rangle\right\|^{2}$
$\displaystyle=\left\|\sum_{i\in[l^{\prime}]}|v_{i,1}\rangle\langle
v_{i,1}|v_{i,2}\rangle\langle v_{i,2}|\psi\rangle-|v_{i,2}\rangle\langle
v_{i,2}|v_{i,1}\rangle\langle v_{i,1}|\psi\rangle.\right\|^{2}$
$\displaystyle=\left\|\sum_{i\in[l^{\prime}]}\cos{\theta_{i}}\left(\left(\cos{\theta_{i}}\langle
v_{i,1}|\psi\rangle+\sin{\theta_{i}}\langle
v_{i,1}^{\perp}|\psi\rangle\right)|v_{i,1}\rangle-\langle
v_{i,1}|\psi\rangle\left(\cos{\theta_{i}}|v_{i,1}\rangle+\sin{\theta_{i}}|v_{i,1}^{\perp}\rangle\right)\right)\right\|^{2}$
$\displaystyle=\left\|\sum_{i\in[l^{\prime}]}\sin{\theta_{i}}\cos{\theta_{i}}\left(\langle
v_{i,1}^{\perp}|\psi\rangle|v_{i,1}\rangle-\langle
v_{i,1}|\psi\rangle|v_{i,1}^{\perp}\rangle\right)\right\|^{2}$
$\displaystyle=\sum_{i\in[l^{\prime}]}\sin^{2}\theta_{i}\cos^{2}\theta_{i}\left(|\langle
v_{i,1}^{\perp}|\psi\rangle|^{2}+|\langle v_{i,1}|\psi\rangle|^{2}\right).$

where in the second equality we again use that
$|v_{i,2}\rangle=\cos{\theta_{i}}|v_{i,1}\rangle+\sin{\theta_{i}}|v_{i,1}^{\perp}\rangle$
and in the fourth equality we use the fact that $\langle
v_{i,b^{\prime}}|v_{j,b}\rangle=0$ for $i\neq j$. ∎

Our proof relies solely on Jordan’s Lemma Note that Jordan’s Lemma is
sufficient only if we analyze commutation of projectors. Results that show how
to make any Hermitian matrices commute [FR96, Has09] are much more complicated
to prove and it is not clear how to translate them to the “on-state” case.

We stress that our proof only works for two projectors, since Jordan’s lemma
does not generalize for three or more projectors. Therefore, we leave as open
problem (dis)proving a generalized version of 7 for more projectors.

In [Ebr18] the author proves Theorem 7 for $\varepsilon=0$, but with a
different proof. They use Halmo’s two rojections theorem instead of Jordan’s
lemma.

## References

  * [BN18] Andreas Bluhm and Ion Nechita.  Joint measurability of quantum effects and the matrix diamond.  Journal of Mathematical Physics, 59(11):112202, 2018.
  * [CETU18] Tore Vincent Carstens, Ehsan Ebrahimi, Gelo Noel Tabia, and Dominique Unruh.  On quantum indifferentiability.  Technical report, Cryptology ePrint Archive, Report 2018/257, 2018. https://eprint. iacr. org/2018/257, 2018.
  * [CZ83] Gianni Cassinelli and N Zanghi.  Conditional probabilities in quantum mechanics. i. – conditioning with respect to a single event.  Il Nuovo Cimento B (1971-1996), 73(2):237–245, 1983.
  * [Cza21] Jan Czajkowski.  Github repository “joints-counterexample”, 2021.
  * [Ebr18] Ehsan Ebrahimi.  Post-quantum security in the presence of superposition queries.  2018\.
  * [Fin73] Arthur Fine.  Probability and the interpretation of quantum mechanics.  The British Journal for the Philosophy of Science, 24(1):1–37, 1973\.
  * [Fin82] Arthur Fine.  Joint distributions, quantum correlations, and commuting observables.  Journal of Mathematical Physics, 23(7):1306–1310, 1982.
  * [FR96] Peter Friis and Mikael Rørdam.  Almost commuting self-adjoint matrices-a short proof of huaxin lin’s theorem.  Journal fur die Reine und Angewandte Mathematik, 479:121–132, 1996\.
  * [GN01] Stan Gudder and Gabriel Nagy.  Sequential quantum measurements.  Journal of Mathematical Physics, 42(11):5212–5222, 2001.
  * [GN02] Stan Gudder and Gabriel Nagy.  Sequentially independent effects.  Proceedings of the American Mathematical Society, 130(4):1125–1130, 2002.
  * [Has09] Matthew B Hastings.  Making almost commuting matrices commute.  Communications in Mathematical Physics, 291(2):321–345, 2009.
  * [HMZ16] Teiko Heinosaari, Takayuki Miyadera, and Mário Ziman.  An invitation to quantum incompatibility.  Journal of Physics A: Mathematical and Theoretical, 49(12):123001, 2016.
  * [Jor75] Camille Jordan.  Essai sur la géométrie à $n$ dimensions.  Bulletin de la Société mathématique de France, 3:103–174, 1875.
  * [Lin97] Huaxin Lin.  Almost commuting selfadjoint matrices and applications.  Fields Inst. Commun, 13:193–233, 1997.
  * [Maa06] Hans Maassen.  Quantum Probability and Quantum Information Theory.  https://www.math.ru.nl/~maassen/lectures/Trieste.pdf, 2006\.
  * [Maa10] Hans Maassen.  Quantum probability and quantum information theory.  In Quantum information, computation and cryptography, pages 65–108. Springer, 2010.
  * [ME84] WM de Muynck and JPHW van den Eijnde.  A derivation of local commutativity from macrocausality using a quantum mechanical theory of measurement.  Foundations of physics, 14(2):111–146, 1984.
  * [NC11] Michael A. Nielsen and Isaac L. Chuang.  Quantum Computation and Quantum Information: 10th Anniversary Edition.  Cambridge University Press, 10th edition, 2011.
  * [Nel67] Edward Nelson.  Dynamical theories of Brownian motion, volume 3.  Princeton university press, 1967.

##  Appendix A Numerical values

Below we present the state and the projectors that are claimed in the proof of
Theorem 5. The script used to generate these values can be found in [Cza21].
Before we write out the state and the projections that we found, let us state
our violation of the permutator:

$\displaystyle\|(P_{1}P_{2}P_{3}P_{4}-P_{3}P_{4}P_{1}P_{2})|\phi\rangle\|=0.25\pm
3\cdot 10^{-8}.$ (24)

All the constraints listed in the proof of Theorem 5 are fulfilled up to the
seventh decimal digit of precision, so up to $10^{-7}$. Internal computations
of the algorithm are performed with machine precision of $10^{-15}$.

The state is

$\displaystyle|\phi\rangle:=\left(\begin{array}[]{c}-0.135381-0.0503468\text{i}\\\
0.325588\,-0.222403\text{i}\\\ -0.209447-0.0404665\text{i}\\\
-0.418336+0.130098\text{i}\\\ -0.503693-0.299414\text{i}\\\
0.379842\,+0.205081\text{i}\\\ -0.179291-0.0381456\text{i}\\\
0.0840381\,-0.125995\text{i}\end{array}\right).$ (33)

We define the projectors by their eigenvectors:

$\displaystyle P_{1}=|\pi^{1}\rangle\langle\pi^{1}|,$ $\displaystyle
P_{2}=|\pi^{2}_{1}\rangle\langle\pi^{2}_{1}|+|\pi^{2}_{2}\rangle\langle\pi^{2}_{2}|,$
(34) $\displaystyle
P_{3}=|\pi^{3}_{1}\rangle\langle\pi^{3}_{1}|+|\pi^{3}_{2}\rangle\langle\pi^{3}_{2}|+|\pi^{3}_{3}\rangle\langle\pi^{3}_{3}|,$
$\displaystyle
P_{4}=|\pi^{4}_{1}\rangle\langle\pi^{4}_{1}|+|\pi^{4}_{2}\rangle\langle\pi^{4}_{2}|.$
(35)

The eigenvector of $P_{1}$ is:

$\displaystyle|\pi^{1}\rangle:=\left(\begin{array}[]{c}0.440777\,+0.168408\text{i}\\\
0.208781\,-0.37351\text{i}\\\ 0.247514\,+0.0276065\text{i}\\\
-0.297971+0.0252308\text{i}\\\ 0.118798\,+0.112225\text{i}\\\
-0.293428+0.270889\text{i}\\\ -0.193073+0.218869\text{i}\\\
-0.41405\end{array}\right).$ (44)

The eigenvectors of $P_{2}$ are:

$\displaystyle|\pi^{2}_{1}\rangle:=\left(\begin{array}[]{c}-0.497016-0.094035\text{i}\\\
0.417527\,-0.0737062\text{i}\\\ -0.000125303+0.35123\text{i}\\\
0.166569\,-0.187245\text{i}\\\ -0.373202+0.205633\text{i}\\\
0.318452\,-0.251475\text{i}\\\ -0.107473-0.123987i\\\
-0.0711523\end{array}\right),|\pi^{2}_{2}\rangle:=\left(\begin{array}[]{c}0.365906\,+0.0620997\text{i}\\\
0.418728\,-0.2059\text{i}\\\ 0.229457\,+0.0557421\text{i}\\\
-0.140393+0.0945029\text{i}\\\ -0.199205-0.188139\text{i}\\\
0.103617\,+0.279644\text{i}\\\ -0.546498+0.147197\text{i}\\\
0.275295\end{array}\right).$ (61)

The eigenvectors of $P_{3}$ are:

$\displaystyle|\pi^{3}_{1}\rangle:=\left(\begin{array}[]{c}-0.453059+0.181543\text{i}\\\
-0.452841+0.0154095\text{i}\\\ -0.17948-0.222827\text{i}\\\
-0.230355-0.0526756\text{i}\\\ -0.0918752-0.250754\text{i}\\\
0.242416\,-0.126917\text{i}\\\ 0.300832\,-0.287566\text{i}\\\
0.315259\end{array}\right),|\pi^{3}_{2}\rangle:=\left(\begin{array}[]{c}-0.0586669-0.269559\text{i}\\\
-0.280155+0.373271\text{i}\\\ -0.150758-0.158539\text{i}\\\
0.158793\,-0.0454731\text{i}\\\ 0.165888\,+0.362832\text{i}\\\
-0.110453-0.310755\text{i}\\\ 0.353894\,-0.00811586\text{i}\\\
-0.487537\end{array}\right),$ (78)
$\displaystyle|\pi^{3}_{3}\rangle:=\left(\begin{array}[]{c}-0.182739-0.114718\text{i}\\\
0.246775\,-0.134678\text{i}\\\ -0.513357-0.193655\text{i}\\\
-0.10451+0.421294\text{i}\\\ 0.111183\,+0.122625\text{i}\\\
-0.200917-0.25897\text{i}\\\ -0.0290851+0.398494\text{i}\\\
0.30081\end{array}\right).$ (87)

The eigenvectors of $P_{4}$ are:

$\displaystyle|\pi^{4}_{1}\rangle:=\left(\begin{array}[]{c}-0.464187+0.213035\text{i}\\\
-0.364421+0.119836\text{i}\\\ -0.324984-0.23097\text{i}\\\
-0.256841+0.0478513\text{i}\\\ -0.0700499-0.192822\text{i}\\\
0.146148\,-0.225755\text{i}\\\ 0.243944\,-0.284786\text{i}\\\
0.331272\end{array}\right),|\pi^{4}_{2}\rangle:=\left(\begin{array}[]{c}0.111757\,+0.151275\text{i}\\\
0.236223\,-0.323279\text{i}\\\ 0.157312\,-0.115385\text{i}\\\
-0.30864+0.0990552\text{i}\\\ -0.260931-0.236239\text{i}\\\
0.240497\,+0.13559\text{i}\\\ -0.453404+0.12357\text{i}\\\
0.490125\end{array}\right).$ (104)