# Device-independent characterization of quantum instruments

Sebastian Wagner  Department of Physics, University of Basel,
Klingelbergstrasse 82, CH-4056 Basel, Switzerland  Jean-Daniel Bancal
Department of Physics, University of Basel, Klingelbergstrasse 82, CH-4056
Basel, Switzerland  Nicolas Sangouard  Department of Physics, University of
Basel, Klingelbergstrasse 82, CH-4056 Basel, Switzerland  Pavel Sekatski
Department of Physics, University of Basel, Klingelbergstrasse 82, CH-4056
Basel, Switzerland

###### Abstract

Among certification techniques, those based on the violation of Bell
inequalities are appealing because they do not require assumptions on the
underlying Hilbert space dimension and on the accuracy of calibration methods.
Such device-independent techniques have been proposed to certify the quality
of entangled states, unitary operations, projective measurements following von
Neumann’s model and rank-one positive-operator-valued measures (POVM). Here,
we show that they can be extended to the characterization of quantum
instruments with post-measurement states that are not fully determined by the
Kraus operators but also depend on input states. We provide concrete
certification recipes that are robust to noise.

## Introduction

Experiments using either NV centers [1], photon pair sources [2, 3] or neutral
atoms [4] have recently been used to test Bell inequalities [5] in a very
convincing way. The observed Bell inequality violations have brought new and
fascinating insights about nature by showing that some correlations cannot be
explained by locally causal models. These experiments also revolutionize
branches of applied physics like randomness generation [6, 7, 8, 9, 10, 11,
12] by making it device-independent, i.e. the randomness guarantees hold
without assumptions on the underlying Hilbert space dimension and on the
accuracy of calibration methods.

The possibility of randomness generation from Bell inequalities is clear when
one realizes that the only situation allowing for a maximal quantum violation
of the simplest Bell inequality [13], within the quantum formalism, consists
in using complementary Pauli measurements on a maximally-entangled two-qubit
state [14, 15]. This means that the violation of a Bell inequality can certify
quantum states and von Neumann measurements directly, without resorting to
tomography. Mayers and Yao were among the very first ones to highlight the
usefulness of Bell tests as characterization methods, a technique that they
called self-testing [16]. Self-testing has been applied to many entangled
states [16, 17, 18, 15, 19], projective measurements [16, 20, 21, 22, 23, 24,
25, 26], and unitary operations [27].

Efforts are being devoted to characterise measurements not captured by the
usual von Neumann model. Refs. [28, 29] for example, showed how to
characterise rank-one POVMs that are not composed of orthogonal projection.
Less is known for measurements whose post-measurement state is not fully
determined by the Kraus operator associated with the measurement result, but
also depends on the input state. In this case, the measurement statistics and
the post-measurement states have to be considered together in order to verify
that a measurement achieves the ideal trade-off between disturbance and
information gain. Such quantum instruments [30], sometimes called weak
measurements [31], can be more efficient in practice than projective or rank-
one measurements e.g. for generating randomness. Whereas randomness generation
based on projective measurements requires at least as many maximally-entangled
states as the number of certified random bits, an arbitrary number of random
bits can in principle be extracted from a single maximally-entangled state by
applying successive quantum instruments which do not break entanglement [32,
33, 34, 35]. The certification of such measurements is thus not only of
fundamental interest but could be used in practice to characterise the
potential of an actual quantum instrument for producing large amounts of
device-independent randomness with a single entangled state.

In this manuscript, we provide a recipe to certify quantum instruments that
are neither projective measurements nor rank-one POVMs, i.e. we certify the
states conditioned on each outcome as well as the probability of each outcome.
We also derive a new class of Bell inequalities suitable for the robust self-
testing of partially-entangled two-qubit states. Our final recipe is
realistically robust to experimental noise.

## Device-independent certification of quantum instruments

We consider an unknown instrument, that we denote $\mathcal{M},$ and our goal
is to show that it behaves as an ideal instrument $\mathcal{\overline{M}}$ in
a device-independent way. We start by clarifying the formulation, then
describe the proposed recipe before discussing the results.

### Formulation

Consider an ideal noise-free quantum instrument $\mathcal{\overline{M}}$ with
$k$ outcomes operating on a single system of dimension $d$. It is represented
by a collection of $k$ Kraus operators
$\\{\overline{K}_{\ell}\\}_{\ell=0}^{k-1}$ satisfying the completeness
relation
$\sum_{\ell}\overline{K}_{\ell}^{\dagger}\overline{K}_{\ell}=\mathbb{1}.$ Each
Kraus operator defines a completely positive map
$\rho\mapsto\overline{K}_{\ell}\rho\overline{K}_{\ell}^{\dagger}$. Given a
state $\rho_{\mathscr{B}}\in L(\mathds{C}^{d}),$ the probability to observe
the outcome $\ell$ is given by the Born rule
$\overline{p}_{\ell}=\mathrm{Tr}{\left(\overline{K}_{\ell}\rho_{\mathscr{B}}\overline{K}_{\ell}^{\dagger}\right)}$
and the normalized post-measurement state for this outcome is
$\varrho_{\ell}=\frac{1}{\overline{p}_{\ell}}\overline{K}_{\ell}\rho_{\mathscr{B}}\overline{K}_{\ell}^{\dagger}$.
Note that the dimension of $\varrho_{\ell}$ is not necessarily the same than
the one of $\rho_{\mathscr{B}}.$ To illustrate our method, we consider in this
work measurements operating on qubits and returning qubits, cf. Eq. (3).

Von Neumann measurements and rank-one POVMs correspond to the specific case
where $\\{\overline{K}_{\ell}\\}$ are proportional to projectors onto pure
states $|\psi_{\ell}\rangle$, that is
$\overline{K}_{\ell}=\eta_{\ell}\,|\psi_{\ell}\rangle\\!\langle\psi_{\ell}|$.
In this case, the post-measurement state corresponding to the outcome $\ell$
is $|\psi_{\ell}\rangle$ independently of the pre-measured state of the
system. Performing such a measurement on a physical system can extract full
information about its state but also disturbs it maximally, e.g. it breaks all
entanglement the system might have with the rest of the world.

Quantum instruments that are neither Von Neumann measurements nor rank-one
POVMs introduce less disturbance in the system at the price of extracting less
information [36]. This has the benefit of preserving interesting and useful
features such as entanglement while nevertheless revealing information about
the system. As an example, for $\theta\in[0,\pi/4]$ the Kraus operators

$\displaystyle\overline{K}_{0}(\theta)=\cos(\theta)|0\rangle\\!\langle
0|+\sin(\theta)|1\rangle\\!\langle 1|,$ (1)
$\displaystyle\overline{K}_{1}(\theta)=\sin(\theta)|0\rangle\\!\langle
0|+\cos(\theta)|1\rangle\\!\langle 1|$ (2)

are associated to quantum instruments which tend to be projective in the limit
$\theta\rightarrow 0,$ and the identity in the limit when
$\theta\rightarrow\pi/4$. Such an instrument is sufficient to implement the
scheme proposed in [33, 34, 35] to produce more randomness than possible with
von Neumann measurements.

Whether the considered measurement is a von Neumann measurement or not, it can
be fully characterised by the map

$\displaystyle\overline{\mathcal{M}}:\,L(\mathds{C}^{2})$
$\displaystyle\rightarrow L(\mathds{C}^{2}\otimes\mathcal{H}_{R})\ ,$ (3)
$\displaystyle\sigma$
$\displaystyle\mapsto\sum_{\ell}\left(\overline{K}_{\ell}\,\sigma\,\overline{K}_{\ell}^{\dagger}\right)\otimes|\ell\rangle\\!\langle\ell|_{R}\
,$

where we have introduced a register $R$ indicating the outcome. In comparison
to the map generated by a single Kraus operator $\overline{K}_{\ell}$, the map
$\overline{\mathcal{M}}$ is trace-preserving by construction, hence defines a
quantum channel. We note that every set of Kraus operators uniquely defines a
map through Eq. (3), and any map of this form uniquely defines the post-
measurement states, and hence corresponds to a quantum instrument. We
illustrate our method by showing how to certify a quantum instrument of the
form given in Eq. (3) with the Kraus operators written in Eqs. (1) and (2).

Figure 1: Scheme of the actual experiment that is used to characterise the
measurement box $\mathcal{M}$ in a device-independent way. The source which is
represented by a box with a star, produces an unknown bipartite state $\rho$
shared between $\mathscr{A}$ and $\mathscr{B}.$ Party $\mathscr{B}$ performs
the measurement. The pre- and post-measurement states can be measured with
additional measurements named $A_{0/1}$ for party $\mathscr{A}$ and
$B_{0/1/2/3}$ for party $\mathscr{B}$ that are also unknown (not represented).

An actual - possibly noisy - measurement (see Fig. 1) acting on a Hilbert
space $\mathcal{H}_{\mathscr{B}}$ can be described by the following map

$\displaystyle\mathcal{M}:\,L(\mathcal{H}_{\mathscr{B}})$
$\displaystyle\rightarrow L(\mathcal{H}_{\mathscr{B}}\otimes\mathcal{H}_{R})\
,$ (4) $\displaystyle\sigma$
$\displaystyle\mapsto\sum_{\ell}M_{\ell}[\sigma]\otimes|\ell\rangle\\!\langle\ell|_{R}\
,$

where $M_{\ell}$ are the completely positive maps associated to the outcomes
$\ell$. In general, these maps may not be expressed in terms of a single Kraus
operator, but as a combination of several ones, i.e.
$M_{\ell}[\sigma]=\sum_{m}K_{\ell,m}\sigma K_{\ell,m}^{\dagger}$, with
$\sum_{\ell,m}K_{\ell,m}^{\dagger}K_{\ell,m}=\mathbb{1}$. In order to show
that a measurement described by $\mathcal{M}$ acts like a target measurement
$\overline{\mathcal{M}}$, it is sufficient to identify a subspace of
$\mathcal{H}_{\mathscr{B}}$ on which the action of $\mathcal{M}$ is similar to
the one of $\overline{\mathcal{M}}$. Moreover, a map is fully described by its
action on one half of a maximally-entangled state, a result known as the Choi-
Jamiolkowski isomorphism [37, 38]. Therefore, the equivalence between the
considered measurement and the target one is obtained by showing that there
exist completely positive trace-preserving maps

$\displaystyle\Lambda_{\mathscr{B}}^{i}:L(\mathds{C}^{2})\to
L(\mathcal{H}_{\mathscr{B}})$ (5)

and

$\displaystyle\Lambda_{\mathscr{B}}^{o}:L(\mathcal{H}_{\mathscr{B}}\otimes\mathcal{H}_{R})$
$\displaystyle\to L(\mathds{C}^{2}\otimes\mathcal{H}_{R})\ ,$ (6)
$\displaystyle\sigma\otimes|\ell\rangle\\!\langle\ell|_{R}$
$\displaystyle\mapsto\Lambda^{o}_{\mathscr{B}|}[\sigma]\otimes|\ell\rangle\\!\langle\ell|_{R}\
,$

such that the composition of these maps with the actual measurement is
identical to the reference measurement, that is

$(\text{id}\otimes\Lambda_{\mathscr{B}}^{o}\\!\circ\\!\mathcal{M}\\!\circ\\!\Lambda_{\mathscr{B}}^{i})[|\phi^{+}\rangle\\!\langle\phi^{+}|]=(\text{id}\otimes\overline{\mathcal{M}})[|\phi^{+}\rangle\\!\langle\phi^{+}|].$
(7)

The injection map $\Lambda^{i}_{\mathscr{B}}$ and the output map
$\Lambda^{o}_{\mathscr{B}}$ identify subspaces and subsystems in which the
measurement $\mathcal{M}$ acts as the reference measurement
$\overline{\mathcal{M}},$ see Fig. 2. Note that the output map does not depend
on the measurement output, cf discussion below. Also note that since all
possible outcomes appear in the definition of the maps
$\overline{\mathcal{M}}$ and $\mathcal{M}$ – the corresponding Choi states
include a description of the labels – equality (7) guarantees at the same time
that the outcome states are as expected and that each outcome appears with the
desired probability.

The previous equality cannot be satisfied in an actual experiment due to
unavoidable imperfections. Following [39, 40], we thus propose an extension
for quantifying the distance $\mathcal{F}(\mathcal{M},\overline{\mathcal{M}})$
between $\mathcal{M}$ and $\overline{\mathcal{M}}$ using

$\displaystyle\mathcal{F}(\mathcal{M},\overline{\mathcal{M}})=$ (8)
$\displaystyle\underset{\Lambda_{\mathscr{B}}^{i},\Lambda_{\mathscr{B}}^{o}}{\max}F\Big{(}$
$\displaystyle\\!\left(\text{id}\otimes\Lambda_{\mathscr{B}}^{o}\\!\circ\\!\mathcal{M}\\!\circ\\!\Lambda_{\mathscr{B}}^{i}\right)[|\phi^{+}\rangle\\!\langle\phi^{+}|],$
$\displaystyle(\text{id}\otimes\overline{\mathcal{M}})[|\phi^{+}\rangle\\!\langle\phi^{+}|]\Big{)},$

where
$F(\rho,\sigma)=\mathrm{Tr}{\\!\sqrt{\\!\\!\sqrt{\rho}\,\sigma\\!\sqrt{\rho}}}$
is the Uhlmann fidelity between two states $\rho$ and $\sigma$.

### Recipe

The aim of this section is to show how the quantity (8) can be lower bounded
in the setup presented in Fig. 3. In addition to the source producing the
bipartite state $\rho$ and the measurement $\mathcal{M}$ to be characterised,
each party has a measurement box. The box of party $\mathscr{A}$ has two
inputs $A_{0}$ and $A_{1}$ while the one of party $\mathscr{B}$ has four
inputs $B_{0},B_{1},B_{2},B_{3}.$ For each measurement input, a binary outcome
is obtained called $a$ for $\mathscr{A}$ and $b$ for $\mathscr{B},$ with
$a,b=\pm 1.$ The measurement $\mathcal{M}$ can be applied by party
$\mathscr{B}$ before the measurement input is chosen. Although there is no
assumption about the Hilbert space dimension and on the proper calibration of
the measurement devices, $\mathcal{M}$ can be characterised in two steps: Step
I identifies the quality of the state produced by the source while step II is
used to characterise the states after each outcome of the measurement to be
certified. The certifications associated to steps I and II are then combined
to bound $\mathcal{F}(\mathcal{M},\overline{\mathcal{M}})$ as defined in Eq.
(8)

Figure 2: To characterise an unknown measurement $\mathcal{M},$ we compare the
action of this black box supplemented with injection maps
$\Lambda_{\mathscr{B}}^{i}$ and $\Lambda_{\mathscr{B}|}^{o}$ with the action
of a reference measurement $\overline{\mathcal{M}}$ on one half of a maximally
entangled two-qubit state $|\phi^{+}\rangle.$

Let us first focus on step I. In this step, the measurement settings $A_{0/1}$
and $B_{0/1}$ are chosen freely and applied directly on the state produced by
the source $\rho$ so that party $\mathscr{A}$ and $\mathscr{B}$ can estimate
the Clauser, Horne, Shimony, and Holt (CHSH) value [13]

$\displaystyle\beta=\sum_{k,j=0}^{1}(-1)^{k\cdot j}\langle A_{k}B_{j}\rangle.$
(9)

Here, $\langle A_{k}B_{j}\rangle=\sum_{a,b}\,a\,b\,P(a,b|A_{k},B_{j})$ is the
expectation value of measurements $A_{k}$ and $B_{j}$. The CHSH value allows
one to bound the fidelity of $\rho$ with a maximally-entangled two-qubit
state. In particular, the results of Ref. [41] show that there exist local
extraction maps $\Lambda_{\mathscr{A}}:L(\mathcal{H}_{\mathscr{A}})\to
L(\mathds{C}^{2})$ and
$\tilde{\Lambda}_{\mathscr{B}|}^{i}:L(\mathcal{H}_{\mathscr{B}})\to
L(\mathds{C}^{2})$ such that

$\displaystyle
F\big{(}(\Lambda_{\mathscr{A}}\otimes\tilde{\Lambda}_{\mathscr{B}|}^{i})[\rho],|\phi^{+}\rangle\Big{)}$
(10) $\displaystyle\geq
F^{i}=\sqrt{\frac{1}{2}+\frac{1}{2}\cdot\frac{\beta-\beta^{*}}{2\sqrt{2}-\beta^{*}}},$

where $\beta^{*}=\frac{2(8+7\sqrt{2})}{17}\approx 2.11$. Whenever
$\beta=2\sqrt{2},$ the formula (10) certifies that the source produces
$|\phi^{+}\rangle$ up to local maps, these maps being explicitly defined from
the quantum description of the measurement inputs $A_{0/1}$ and $B_{0/1}.$ In
this case, the same maps can be used to show that $\mathscr{A}$’s settings
correspond to the Pauli measurements $\overline{A}_{0}=\sigma_{z}$ and
$\overline{A}_{1}=\sigma_{x}$ while $\mathscr{B}$’s settings correspond to
$\overline{B}_{0/1}=\frac{1}{\sqrt{2}}(\sigma_{z}\pm\sigma_{x})$
111Mathematically this means, for example for Bob’s first measurement $B_{0}$,
that there exists maps $\Lambda_{\mathscr{B}}^{o}$ and
$\Lambda_{\mathscr{B}}^{i}$ such that Eq. (7) holds with
$\mathcal{M}[\sigma]=\sum_{\ell=0}^{1}\frac{\mathbb{1}+(-1)^{\ell}B_{0}}{2}\sigma\frac{\mathbb{1}+(-1)^{\ell}B_{0}}{2}\otimes|\ell\rangle\\!\langle\ell|$
and
$\overline{\mathcal{M}}[\sigma]=\sum_{\ell=0}^{1}\frac{\mathbb{1}+(-1)^{\ell}\overline{B}_{0}}{2}\sigma\frac{\mathbb{1}+(-1)^{\ell}\overline{B}_{0}}{2}\otimes|\ell\rangle\\!\langle\ell|$.
Here,$\Lambda_{\mathscr{B}}^{i}$ can be obtained from
$\tilde{\Lambda}_{\mathscr{B}|}^{i}$ through Proposition 4 of [27] (in that
work the roles of Alice and Bob are exchanged)..

Figure 3: Recipe for bounding the quality of the measurement box $\mathcal{M}$
in 2 steps. Step I is used to characterize the state of the source while Step
II gives a certificate of the post-measurement states. The statistics recorded
in each step is then used to certify the quality of measurement $\mathcal{M}$
device-independently.

In step II, party $\mathscr{B}$ applies $\mathcal{M}.$ Let us first consider
the state conditioned on the outcome $0$,

$\varrho_{0}=\frac{M_{0}[\rho]}{\mathrm{Tr}{\left(M_{0}[\rho]\right)}},$

which is characterized using $A_{0/1}$ and $B_{2/3}.$ In particular, parties
$\mathscr{A}$ and $\mathscr{B}$ are interested in the Bell inequality

$\displaystyle{\mathcal{I}}_{\theta}$
$\displaystyle=\frac{1}{4}\left[\frac{\langle
A_{0}(B_{2}-B_{3})\rangle}{\sin(b_{\theta})}+\frac{\sin(2\theta)}{\cos(b_{\theta})}\langle
A_{1}(B_{2}+B_{3})\rangle\right.$ $\displaystyle\ \ \ \ \ \ \ \ \ \ \
+\left.\cos(2\theta)\left(\langle A_{0}\rangle+\frac{\langle
B_{2}-B_{3}\rangle}{2\sin(b_{\theta})}\right)\right]$
$\displaystyle\leq\frac{1}{4}\left[\cos(2\theta)+(2+\cos(2\theta))\sqrt{\frac{7-\cos(4\theta)}{5+\cos(4\theta)}}\right]$
(11)

with
$b_{\theta}=\arctan\sqrt{(1+\frac{1}{2}\cos^{2}(2\theta))/\sin^{2}(2\theta)}$,
whose maximal quantum value is one by construction. We derived this Bell
inequality using the variational method presented in [27, 42] to self-test
partially-entangled two-qubit pure states in a particularly robust manner.
Note that for $\theta=\frac{\pi}{4}$, Ineq. (11) is the re-normalized CHSH
inequality. However, we emphasize that Ineq. (11) is not equivalent to the
tilted-CHSH inequality of Refs. [43, 44] but was carefully constructed for the
demands of self-testing presented here. The knowledge of
${\mathcal{I}}_{\theta}$ allows one to bound the fidelity of the conditional
state $\varrho_{0}$, that is, to guarantee the existence of local maps
$\Lambda_{\mathscr{A}}:L(\mathcal{H}_{\mathscr{A}})\to L(\mathds{C}^{2})$ and
$\Lambda_{\mathscr{B}|}^{o,\theta}:L(\mathcal{H}_{\mathscr{B}})\to
L(\mathds{C}^{2})$ such that

$\displaystyle
F((\Lambda_{\mathscr{A}}\\!\otimes\\!\Lambda_{\mathscr{B}|}^{o,\theta})[\varrho_{0}],|\phi_{\theta}^{0}\rangle)$
(12) $\displaystyle\geq
F^{0}_{\theta}=\sqrt{\cos^{2}(\theta)+(1-\cos^{2}(\theta))\frac{{\mathcal{I}}_{\theta}-{\mathcal{I}}_{\theta}^{*}}{1-{\mathcal{I}}_{\theta}^{*}}}.$

Here, ${\mathcal{I}}_{\theta}^{*}$ is a cutoff parameter corresponding to the
violation for which the fidelity matches the square of the largest Schmidt
coefficient of
$|\phi_{\theta}^{0}\rangle=\cos(\theta)|00\rangle+\sin(\theta)|11\rangle$.
Fig. 4 shows the critical value ${\mathcal{I}}_{\theta}^{*}$ for both this
inequality and the tilted CHSH inequality, as calculated in the Appendix. The
previous bound shows that whenever ${\mathcal{I}}_{\theta}$ reaches its
maximal quantum value ${\mathcal{I}}_{\theta}=1,$ the state conditioned on the
outcome $0$ corresponds to the state $|\phi_{\theta}^{0}\rangle$ up to local
maps, these maps being explicitly defined from the quantum description of the
measurements performed by $A_{0/1}$ and $B_{2/3}$ respectively. The same maps
can also be used to show that when ${\mathcal{I}}_{\theta}=1,$ $\mathscr{A}$’s
settings correspond to the Pauli measurements $\overline{A}_{0}=\sigma_{z}$
and $\overline{A}_{1}=\sigma_{x}$ while $\mathscr{B}$’s inputs correspond to
$\overline{B}_{2/3}=\cos(b_{\theta})\sigma_{z}\pm\sin(b_{\theta})\sigma_{x}$.

Figure 4: Plot of the cutoff parameter ${\mathcal{I}}_{\theta}^{*}$ as a
function of $\theta,$ see Eq. (12). The red dashed line is below the blue
solid one, indicating that our new inequality achieves non-trivial fidelities
for smaller violations compared to the tilted-CHSH inequality. Thus it
provides tighter self-testing bounds for partially-entangled states.

The post-measurement state corresponding to the outcome $1$ can be
characterized with the same measurement boxes $A_{0/1}$ and $B_{2/3}$, as well
as the same local extraction maps $\Lambda_{\mathscr{A}}$ and
$\Lambda_{\mathscr{B}|}^{o,\theta}$, see Appendix. Moreover, by including the
classical output of the measurement in a global state including a register, as
mentioned before, the overall post-measurement state can be written in a
compact form

$\varrho=\sum_{\ell=0}^{1}p_{\ell}\varrho_{\ell}\otimes|\ell\rangle\\!\langle\ell|_{R}\
,$ (13)

with
$\varrho_{\ell}=\frac{M_{\ell}[\rho]}{\mathrm{Tr}{\left(M_{\ell}[\rho]\right)}}$
the post-measurement state associated to outcome $\ell$, and $p_{\ell}$ the
probability of this outcome. As the certificates for the two branches
$\varrho_{0}$ and $\varrho_{1}$ are obtained with the same isometries, they
can be combined into a single certificate for $\varrho$. In particular, using
the orthogonality of the register states, we have

$\displaystyle
F((\Lambda_{\mathscr{A}}\otimes\Lambda_{\mathscr{B}}^{o,\theta})[\varrho],\sum_{\ell=0}^{1}\frac{1}{2}|\phi_{\theta}^{\ell}\rangle\\!\langle\phi_{\theta}^{\ell}|\otimes|\ell\rangle\\!\langle\ell|_{R})$
$\displaystyle\geq\sum_{\ell}\sqrt{\frac{p_{\ell}}{2}}F^{\ell}_{\theta}=:F^{o}_{\theta}.$
(14)

Taking into account the fact that the fidelity cannot decrease under
completely-positive trace-preserving maps and using the triangle inequality
$\arccos(F(\rho_{1},\rho_{3}))\leq\arccos(F(\rho_{1},\rho_{2}))+\arccos(F(\rho_{2},\rho_{3}))),$
we can prove that the fidelity of the state before and after the measurement
can be combined to bound the fidelity of the measurement itself, that is,

$\displaystyle\mathcal{F}(\mathcal{M},\overline{\mathcal{M}})\geq\cos(\arccos(F^{i})+\arccos(F_{\theta}^{o}))\
,$ (15)

(see Proposition 5 of [27]). Whenever $\beta=2\sqrt{2}$ and
${\mathcal{I}}_{\theta}=1$ for both output states, this bound guarantees that
$\mathcal{F}(\mathcal{M},\overline{\mathcal{M}})=1.$ In noisy scenarios, the
fidelity that can be certified is shown in Fig. 5.

Figure 5: Lower bounds on the fidelity
$\mathcal{F}(\mathcal{M},\overline{\mathcal{M}})$ of an unknown measurement
$\mathcal{M}$ defined in Eq. (4) with respect to a reference measurement
$\overline{\mathcal{M}}$ defined in Eq. (3) with the Kraus operators given in
Eqs. (1)-(2) for given CHSH violations $\beta$ and violations
${\mathcal{I}}_{\theta}$ of the Bell inequality (11); we assume that the
second output state appears with probability $p_{0}=p_{1}=\frac{1}{2}$
achieving the violation
${\mathcal{I}}_{\theta}^{0},{\mathcal{I}}_{\theta}^{1}\geq I_{\theta}$. The
plot is for $\theta=(2\pi+7)/22\approx 0.6$.

Note that in case where the fidelity of the state before the measurement
cannot be assessed, the quality of the measurement cannot be certified.
Indeed, if the source produces the state
$|\phi_{\theta}^{0}\rangle|0\rangle_{B^{\prime}}+|\phi_{\theta}^{1}\rangle|1\rangle_{B^{\prime}}$,
and the measurement simply reads out the auxiliary $B^{\prime}$ system, then
all post-measurement statistics are reproduced. Hence, it is necessary to be
able to estimate the quality of the pre-measurement state to give a
certificate for the proper functioning of the measurement itself.

### Discussion

So far our exposition was focused on the particular example of Kraus operators
given by Eq. (1) and (2). Nevertheless, the reader might have noticed that
only the tests used to bound the fidelity of the initial state $F^{i}$ and of
the post-measurement states $F^{o}_{\ell}$ are specific to this example.
Consider now a general quantum instrument and assume that one can obtain
certificates for the state produced by the source as in Eq. (10) and for all
the post-measurement states as in Eq. (12). If the extraction maps
$\Lambda_{\mathscr{A}}$ on Alice’s side are the same for all certificates,
straightforward application of Eqs. (14) and (15) provides a self-testing of
the whole instrument. In summary, our approach applies straightforwardly to
quantum instruments with an arbitrary number of classical outcomes, including
qubit measurements with more than two Kraus operators and measurements on
larger-dimensional systems, as well as multipartite instruments.

Note also that we focused on a formulation where the extraction maps
$\Lambda_{\mathscr{B}|}^{o}$ in Eq. (6) act trivially on the classical
measurement output $R$, that is the extraction maps applied on the quantum
output is independent of the measurement result $\ell$. We believe that this
corresponds to the spirit of self-testing in which states and channels are
certified up to passive transformations. Nevertheless, a formulation where the
extraction maps $\Lambda_{\mathscr{B}|}^{o,\ell}$ acting on the post-
measurement quantum state depend on the measurement outputs $\ell$ is also
possible. In this case it is sufficient to certify the initial and all post-
measurement states independently in order to obtain a certificate for the
whole instrument. Our derivation then holds as long as Alice’s maps are the
same.

## Conclusion

We provided a family of Bell inequalities that can be used to self-test non-
maximally-entangled two-qubit states with a greater resistance to noise than
known Bell inequalities. These results allowed us to derive robust bounds that
can be used in practice to certify the quality of qubits measurements beyond
the von Neumann model and rank-one POVMs. This takes essentially three steps.
In the first step, the CHSH test is performed without the measurement to
evaluate the quantity $\beta.$ In the second step, Bell tests are performed
after the measurement to be certified is applied on the system, so as to
evaluate the values ${\mathcal{I}}_{\theta}$ and
${\mathcal{I}}_{\theta}^{\prime}$ (see appendix) for each classical output of
the instrument. In the third step, the fidelity of the actual measurement is
deduced from fidelities of the state before the measurement $F^{i}$ and of the
post-measurement states $F_{\theta}^{\ell}$ using the formula given in Eq.
(15). The robustness of our certification techniques together with the
flexibility of our recipe make us confident that self-testing of quantum
instruments could soon be demonstrated experimentally. For a more theoretical
perspective, our results could be naturally extended to self-test only one
Kraus operator within a family. This could be obtained by generalizing the
’heralded’ fidelity defined in [26] to the current setting.

This work was supported by the Swiss National Science Foundation (SNSF),
through the Grant PP00P2-179109 and 200021-175527. We also acknowledge the
Army Research Laboratory Center for Distributed Quantum Information via the
project SciNet.

## References

  * [1] B. Hensen, H. Bernien, A. E. Dréau, A. Reiserer, N. Kalb, M. S. Blok, J. Ruitenberg, R. F. L. Vermeulen, R. N. Schouten, C. Abellán, W. Amaya, V. Pruneri, M. W. Mitchell, M. Markham, D. J. Twitchen, D. Elkouss, S. Wehner, T. H. Taminiau, R. Hanson, Loophole-free Bell inequality violation using electron spins separated by 1.3 kilometres, Nature 526, 682 (2015).
  * [2] L. K. Shalm, E. Meyer-Scott, B. G. Christensen, P. Bierhorst, M. A. Wayne, M. J. Stevens, T. Gerrits, S. Glancy, D. R. Hamel, M. S. Allman, K. J. Coakley, S. D. Dyer, C. Hodge, A. E. Lita, V. B. Verma, C. Lambrocco, E. Tortorici, A. L. Migdall, Y. Zhang, D. R. Kumor, W. H. Farr, F. Marsili, M. D. Shaw, J. A. Stern, C. Abellán, W. Amaya, V. Pruneri, T. Jennewein, M. W. Mitchell, P. G. Kwiat, J. C. Bienfang, R. P. Mirin, E. Knill, S. W. Nam, Strong Loophole-Free Test of Local Realism, Phys. Rev. Lett. 115, 250402 (2015).
  * [3] M. Giustina, M. A. M. Versteegh, S. Wengerowsky, J. Handsteiner, A. Hochrainer, K. Phelan, F. Steinlechner, J. Kofler, J-Å. Larsson, C. Abellán, W. Amaya, V. Pruneri, M. W. Mitchell, J. Beyer, T. Gerrits, A. E. Lita, L. K. Shalm, S. W. Nam, T. Scheidl, R. Ursin, B. Wittmann, A. Zeilinger, Significant-Loophole-Free Test of Bell’s Theorem with Entangled Photons, Phys. Rev. Lett. 115, 250401 (2015).
  * [4] W. Rosenfeld, D. Burchardt, R. Garthoff, K. Redeker, N. Ortegel, M. Rau, H. Weinfurter, Event-Ready Bell Test Using Entangled Atoms Simultaneously Closing Detection and Locality Loopholes, Phys. Rev. Lett. 119, 010402 (2017).
  * [5] J.S. Bell, On the Einstein Podolsky Rosen paradox, Physics 1, 195 (1964).
  * [6] R. Colbeck, Quantum And Relativistic Protocols For Secure Multi-Party Computation, Ph.D. thesis, (2009).
  * [7] S. Pironio, A. Acín, S. Massar, A. Boyer de la Giroday, D. N. Matsukevich, P. Maunz, S. Olmschenk, D. Hayes, L. Luo, T. A. Manning, C. Monroe, Random numbers certified by Bell’s theorem, Nature 464, 1021 (2010).
  * [8] B. G. Christensen, K. T. McCusker, J. B. Altepeter, B. Calkins, T. Gerrits, A. E. Lita, A. Miller, L. K. Shalm, Y. Zhang, S. W. Nam, N. Brunner, C. C. W. Lim, N. Gisin, and P. G. Kwiat, Detection-Loophole-Free Test of Quantum Nonlocality, and Applications, Phys. Rev. Lett. 111, 130406 (2013).
  * [9] Y. Liu, X. Yuan, M-H. Li, W. Zhang, Q. Zhao, J. Zhong, Y. Cao, Y-H. Li, L-K. Chen, H. Li, T. Peng, Y-A. Chen, C-Z. Peng, S-C. Shi, Z. Wang, L. You, X. Ma, J. Fan, Q. Zhang, J-W. Pan, High-Speed Device-Independent Quantum Random Number Generation without a Detection Loophole,  Phys. Rev. Lett. 120, 010503 (2018).
  * [10] Y. Liu, Q. Zhao, M-H. Li, J-Y. Guan, Y. Zhang, B. Bai, W. Zhang, W-Z. Liu, C. Wu, X. Yuan, H. Li, W. J. Munro, Z. Wang, L. You, J. Zhang, X. Ma, J. Fan, Q. Zhang, J-W. Pan, Device-independent quantum random-number generation, Nature 562, 548 (2018).
  * [11] P. Bierhorst, E. Knill, S. Glancy, Y. Zhang, A. Mink, S. Jordan, A. Rommal, Y-K. Liu, B. Christensen, S. W. Nam, M. J. Stevens, L. K. Shalm, Experimentally Generated Randomness Certified by the Impossibility of Superluminal Signals, Nature 556, 223 (2018).
  * [12] L. Shen, J. Lee, L. P. Thinh, J-D. Bancal, A. Cerè, A. Lamas-Linares, A. Lita, T. Gerrits, S. W. Nam, V. Scarani, C. Kurtsiefer Randomness Extraction from Bell Violation with Continuous Parametric Down-Conversion, Phys. Rev. Lett. 121, 150402 (2018).
  * [13] J. F. Clauser, M. A. Horne, A. Shimony, R.A. Holt, Proposed Experiment to Test Local Hidden-Variable Theories, Phys. Rev. Lett. 23, 880 (1969).
  * [14] S. Popescu, D. Rohrlich, Which states violate Bell’s inequality maximally?, Phys. Lett. A 169, 411 (1992).
  * [15] M. McKague, T. H. Yang, V. Scarani, Robust self-testing of the singlet, J. Phys. A: Math. Theor. 45, 455304 (2012).
  * [16] D. Mayers, A. Yao, Quantum Cryptography with Imperfect Apparatus, Proceedings of the 39th IEEE Conference on Foundations of Computer Science, 1998, page 503, see also Self testing quantum apparatus, Quant. Inf. Comput. 4, 273 (2004).
  * [17] M. McKague, Interactive Proofs for BQP via Self-Tested Graph States, Theory of Computing, 12, 3 (2016).
  * [18] A. Coladangelo, K.T. Goh, V. Scarani, All Pure Bipartite Entangled States can be Self-Tested, Nat. Comm. 8, 15485 (2017).
  * [19] X. Wu, Y. Cai, T. H. Yang, H. Nguyen Le, J-D. Bancal, V. Scarani, Robust self-testing of the three-qubit W state, Phys. Rev. A 90, 042339 (2014).
  * [20] J-D. Bancal, M. Navascués, V. Scarani, T. Vértesi, T. H. Yang, Physical characterization of quantum devices from nonlocal correlations, Phys. Rev. A 91, 022115 (2015).
  * [21] S-L. Chen, C. Budroni, Y-C. Liang, Y-N. Chen, Natural Framework for Device-Independent Quantification of Quantum Steerability, Measurement Incompatibility, and Self-Testing, Phys. Rev. Lett. 116, 240401 (2016).
  * [22] D. Cavalcanti, P. Skrzypczyk, Quantitative relations between measurement incompatibility, quantum steering, and nonlocality, Phys. Rev. A 93, 052112 (2016).
  * [23] J. Kaniewski, Self-testing of binary observables based on commutation, Phys. Rev. A 95, 062323 (2017).
  * [24] J. Bowles, I. Šupić, D. Cavalcanti, A. Acín, Self-testing of Pauli observables for device-independent entanglement certification, Phys. Rev. A 98, 042336 (2018).
  * [25] M-O. Renou, J. Kaniewski, N. Brunner, Self-Testing Entangled Measurements in Quantum Networks, Phys. Rev. Lett. 121, 250507 (2018).
  * [26] J-D. Bancal, N. Sangouard, P. Sekatski, Noise-Resistant Device-Independent Certification of Bell State Measurements, Phys. Rev. Lett. 121, 250506 (2018).
  * [27] P. Sekatski, J-D. Bancal, S. Wagner, N. Sangouard, Certifying the Building Blocks of Quantum Computers from Bell’s Theorem, Phys. Rev. Lett. 121, 180505 (2018).
  * [28] E. S. Gómez, S. Gómez, P. González, G. Cañas, J. F. Barra, A. Delgado, G. B. Xavier, A. Cabello, M. Kleinmann, T. Vértesi, G. Lima, Device-Independent Certification of a Nonprojective Qubit Measurement, Phys. Rev. Lett. 117, 260401 (2016).
  * [29] M. Smania, P. Mironowicz, M. Nawareg, M. Pawłowski, A. Cabello, M. Bourennane, Experimental certification of an informationally complete quantum measurement in a device-independent protocol, Optica 7,123-128 (2020).
  * [30] E. B. Davies, J. T. Lewis, An operational approach to quantum probability, Comm. Math. Phys. 17, 239 (1970).
  * [31] J. A. Gross, C. M. Caves, G. J. Milburn, J. Combes, Qubit models of weak continuous measurements: markovian conditional and open-system dynamics, Quantum Sci. Technol. 3, 024005 (2018).
  * [32] R. Silva, N. Gisin, Y. Guryanova, S. Popescu, Multiple Observers Can Share the Nonlocality of Half of an Entangled Pair by Using Optimal Weak Measurements, Phys. Rev. Lett. 114, 250401 (2015).
  * [33] F. J. Curchod, M. Johansson, R. Augusiak, M. J. Hoban, P. Wittek, A. Acín Unbounded randomness certification using sequences of measurements, Phys. Rev. A 95, 020102 (2017).
  * [34] F. J. Curchod, M. Johansson, R. Augusiak, M. J. Hoban, P. Wittek, A. Acín, A Single Entangled System Is an Unbounded Source of Nonlocal Correlations and of Certified Random Numbers, 12${}^{\text{th}}$ Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2017), Leibniz International Proceedings in Informatics (LIPIcs) 73, 1:1 (2018).
  * [35] B. Coyle, M.J. Hoban, E. Kashefi, One-Sided Device-Independent Certification of Unbounded Random Numbers, EPTCS 273, 14 (2018).
  * [36] K. Banaszek, I. Devetak, Fidelity trade-off for finite ensembles of identically prepared qubits, Phys. Rev. A 64, 052307 (2001).
  * [37] M-D. Choi, Completely positive linear maps on complex matrices, Linear Algebra Appl., 10, 285 (1975).
  * [38] A. Jamiołkowski, Linear transformations which preserve trace and positive semidefiniteness of operators, Rep. Math. Phys. 3, 275 (1972).
  * [39] M. Raginsky, A fidelity measure for quantum channels, Phys. Lett. A 290, 11 (2001).
  * [40] V. P. Belavkin, G. M. D’Ariano, M. Raginsky, Operational distance and fidelity for quantum channels, J. Math. Phys. 46, 062106 (2005).
  * [41] J. Kaniewski, Analytic and Nearly Optimal Self-Testing Bounds for the Clauser-Horne-Shimony-Holt and Mermin Inequalities, Phys. Rev. Lett. 117, 070402 (2016).
  * [42] P. Sekatski et al., in preparation.
  * [43] A. Acín, S. Massar, S. Pironio, Randomness versus Nonlocality and Entanglement, Phys. Rev. Lett, 108, 100402 (2012).
  * [44] C. Bamps, S. Pironio, Sum-of-squares decompositions for a family of Clauser-Horne-Shimony-Holt-like inequalities and their application to self-testing,  Phys. Rev. A 91, 052111 (2015).
  * [45] T. Coopmans, J. Kaniewski, C. Schaffner, Robust self-testing of two-qubit states, Phys. Rev. A 99, 052123 (2019).

##  Appendix A Appendix

In the supplemental material we will prove the inequality in Eq. (12) of the
main text. To do so we have to lower bound the fidelity of an unknown state
$\rho$ with respect to

$|\phi_{\theta}^{0}\rangle=\cos(\theta)|00\rangle+\sin(\theta)|11\rangle$ (16)

as a function of the expected value of the following Bell expression evaluated
on the state $\rho$

$\displaystyle{\mathcal{I}}_{\theta}$
$\displaystyle=\langle\frac{1}{4}\left[\frac{A_{0}(B_{0}-B_{1})}{\sin(b_{\theta})}+\frac{\sin(2\theta)}{\cos(b_{\theta})}A_{1}(B_{0}+B_{1})\right.$
$\displaystyle\ \ \ \ \ \ \ \ \ \ \
+\left.\cos(2\theta)\left(A_{0}+\frac{B_{0}-B_{1}}{2\sin(b_{\theta})}\right)\right]\rangle,$
(17)

where
$b_{\theta}=\arctan\sqrt{\frac{1+\tfrac{1}{2}c_{2\theta}^{2}}{s_{2\theta}^{2}}}$.
Here and in the rest of the appendix we use the short notation
$c_{\theta}=\cos(\theta)$ and $s_{\theta}=\sin(\theta)$. The Bell expression
Eq. (17) has a quantum bound of $1$, achieved by measuring precisely the two-
qubit state $|\phi_{\theta}^{0}\rangle$ with the observables

$\displaystyle A_{0}$ $\displaystyle=\sigma_{z}\ ,$ $\displaystyle B_{0}$
$\displaystyle=\cos(b_{\theta})\sigma_{x}+\sin(b_{\theta})\sigma_{z},$ (18)
$\displaystyle A_{1}$ $\displaystyle=\sigma_{x}\ ,$ $\displaystyle B_{1}$
$\displaystyle=\cos(b_{\theta})\sigma_{x}-\sin(b_{\theta})\sigma_{z}.$ (19)

We find that the local bound of Eq. (17) achieved by the deterministic local
strategy $\\{A_{0}=A_{1}=B_{0}=1,B_{1}=-1\\}$ is given by

$\displaystyle{\mathcal{I}}_{L}=\frac{1}{4}\left[c_{2\theta}+(2+c_{2\theta})\sqrt{\frac{7-c_{4\theta}}{5+c_{4\theta}}}\right].$
(20)

This value is to be compared with the local bound of the well-known
(normalized) tilted-CHSH

${\mathcal{I}}_{\theta}^{(T)}=\left\langle\frac{\alpha_{\theta}A_{0}+A_{0}(B_{0}+B_{1})+A_{1}(B_{0}-B_{1})}{\sqrt{8+2\alpha_{\theta}^{2}}}\right\rangle$
(21)

with $\alpha_{\theta}=\frac{2}{\sqrt{1+2\tan^{2}(2\theta)}}$, also known to
attain the quantum bound of $1$ for the partially entangled state of Eq. (16)
and well-chosen measurement settings, see Ref. [43, 44] of the main text. We
find that the local bound of Eq. (20) is always higher than the local bound of
the tilted-CHSH
${\mathcal{I}}_{L}\geq{\mathcal{I}}_{L}^{(T)}=\frac{2+\alpha_{\theta}}{\sqrt{8+2\alpha_{\theta}^{2}}}$,
meaning that the violation of the tilted-CHSH inequality is more robust to
white noise than the violation of our new Bell inequality. Nevertheless, our
later studies will show that the new Bell operator allows for a more noise-
tolerant state certification. The reason for this counter-intuitive result is
the following: comparing the observed violation to the local bound only
provides information on the distance between the target state (in our case
$|\phi_{\theta}^{0}\rangle$) and deterministic strategies, given by parallel
measurement setting $A_{0}=\pm A_{1}$ with $B_{0}=\pm B_{1}$ and product
states $|\psi_{A}\rangle|\psi_{B}\rangle$ with
$A_{0}|\psi_{A}\rangle=\pm|\psi_{A}\rangle$ and
$B_{0}|\psi_{B}\rangle=\pm|\psi_{B}\rangle$. In self-testing, on the other
hand, we need to bound the distance of the target state to arbitrary states
for arbitrary measurement settings. It is then crucial that the violation
worsens drastically when departing from the perfect settings.

###  A.1 Fidelity Bounds

To derive lower bounds on the state fidelity from a Bell violation
${\mathcal{I}}_{\theta}$ we use the tools presented in Ref. [27] of the main
text. There, it is shown that such a global lower bound can be obtained by
solving a two-qubit problem. More precisely, the state fidelity can be bounded
by minimizing the quantity

$O((\Lambda_{\mathscr{A}}\otimes\Lambda_{\mathscr{B}}^{o,\theta})[\rho],|\phi_{\theta}\rangle\\!\langle\phi_{\theta}|)$
(22)

with $O(\rho,\sigma)=\mathrm{Tr}(\sigma\rho)$, over all possible two-qubit
states $\rho$ and all possible qubit observables $A_{0},A_{1},B_{0},B_{1}$
(with eigenvalues $\pm 1$) that are compatible with the value
${\mathcal{I}}_{\theta}$ of the Bell operator. Here,

$\Lambda_{\mathscr{A}},\Lambda_{\mathscr{B}}^{o,\theta}:L(\mathds{C}^{2})\rightarrow
L(\mathds{C}^{2})$ (23)

are the local extraction channels that can depend on the local observable
$A_{0}$ with $A_{1}$ for $\Lambda_{\mathscr{A}}$ and $B_{0}$ with $B_{1}$ for
$\Lambda_{\mathscr{B}}^{o,\theta}$. The first step, therefore, is to fix these
extraction channels.

Before we do so, let us fix some notation for the local observables. Any qubit
observable with eigenvalues $+1$ and $-1$ can be written as
${\bm{n}}\cdot{\bm{\sigma}}$ with $|{\bm{n}}|=1$. Furthermore, without loss of
generality, we can set the local bases such that

$\displaystyle A_{0}(a)$ $\displaystyle=\cos(a)H+\sin(a)V$ $\displaystyle
A_{1}(a)$ $\displaystyle=\cos(a)H-\sin(a)V$ (24) $\displaystyle B_{0}(b)$
$\displaystyle=\cos(b)\sigma_{x}+\sin(b)\sigma_{z}$ $\displaystyle B_{1}(b)$
$\displaystyle=\cos(b)\sigma_{x}-\sin(b)\sigma_{z}$ (25)

where $H=\tfrac{1}{\sqrt{2}}(\sigma_{z}+\sigma_{x})$,
$V=\tfrac{1}{\sqrt{2}}(\sigma_{z}-\sigma_{x})$. Hence, in the minimization the
pairs of observable $A_{0}$, $A_{1}$ and $B_{1}$, $B_{2}$ as well as the
extraction channels $\Lambda_{\mathscr{A}}$ and
$\Lambda_{\mathscr{B}}^{o,\theta}$ only depend on a single parameter $a$ and
$b$ respectively.

###  A.2 Extraction Channels

The extraction channels we will use are adapted versions of the dephasing
channels from Ref. [41] of the main text. Note that since any local map can be
seen as an isometry acting on the state plus the auxiliary degrees of freedom,
these maps can also be understood as defining local isometries of particular
interest. On Alice’s side, the observables are maximally dephased if they are
parallel or anti-parallel, and unchanged if they are orthogonal. More
precisely, for $a$ being half the angle between Alice’s observables in Eq.
(24) the dephasing acts according to

$\displaystyle\Lambda_{a}[\rho]:=\frac{1+g(a)}{2}\rho+\frac{1-g(a)}{2}\Gamma_{a}\rho\Gamma_{a}\
,$ (26)

where $g(a)=(1+\sqrt{2})(\cos(a)+\sin(a)-1)$, and $\Gamma_{a}=H$ if
$a\in[0,\frac{\pi}{4}]$ and $\Gamma_{a}=V$ if
$a\in]\frac{\pi}{4},\frac{\pi}{2}]$. Here and from now on, $\Lambda_{a}$ is
the short notation of $\Lambda_{\mathscr{A}}(a)$.

On Bob’s side, the observables are also maximally dephased if they are
parallel or anti-parallel, but here they are unchanged if half the angle
between them equals $b_{\theta}$, where
$b_{\theta}=\arctan\sqrt{\frac{1+\tfrac{1}{2}c_{2\theta}^{2}}{s_{2\theta}^{2}}}$
for the new inequality and $b_{\theta}=\arctan(\sin(2\theta))$ for the tilted-
CHSH one. For $b$ denoting half the angle between Bob’s observables in Eq.
(25) the dephasing channel on Bob’s side is

$\displaystyle\Lambda_{b}[\rho]:=\frac{1+g(t_{\theta}(b))}{2}\rho+\frac{1-g(t_{\theta}(b))}{2}\Omega_{b}\rho\Omega_{b}\
,$ (27)

where

$\displaystyle t_{\theta}(b)$
$\displaystyle=\gamma_{\theta}^{-1}\ln\left(\frac{b-\delta_{\theta}}{\delta_{\theta}}\right),$
(28) $\displaystyle\gamma_{\theta}$
$\displaystyle=\frac{4}{\pi}\ln\left(\frac{\frac{\pi}{2}-b_{\theta}}{b_{\theta}}\right),$
(29) $\displaystyle\delta_{\theta}$
$\displaystyle=\frac{b_{\theta}^{2}}{\pi^{2}-2b_{\theta}}.$ (30)

For the observables of Bob, the dephasing happens in the direction
$\Omega_{b}=\sigma_{x}$ if $b\in[0,b_{\theta}]$ and $\Omega_{b}=\sigma_{z}$ if
$b\in]b_{\theta},\frac{\pi}{2}]$. Again, we introduced the simplified notation
$\Lambda_{b}=\Lambda_{\mathscr{B}}^{o,\theta}(b)$.

Using these extraction channels and applying the numerical method presented
Ref. [27] of the main text, we find the values of $I_{\theta}^{*}$ such that
the convex bound

$\displaystyle
O((\Lambda_{\mathscr{A}}\otimes\Lambda_{\mathscr{B}}^{o,\theta})[\rho],|\phi_{\theta}^{0}\rangle\\!\langle\phi_{\theta}^{0}|)\geq(1-c_{\theta}^{2})\frac{{\mathcal{I}}_{\theta}-{\mathcal{I}}_{\theta}^{*}}{1-{\mathcal{I}}_{\theta}^{*}}+c_{\theta}^{2}$
(31)

holds for our new inequality, as well as for the tilted-CHSH one (using then
${\mathcal{I}}_{\theta}^{(T)}$ instead of ${\mathcal{I}}_{\theta}$). Here
${\mathcal{I}}_{\theta}$ is the observed Bell violation and
${\mathcal{I}}_{\theta}^{*}$ is the non-trivial cutoff corresponding to the
violation for which the fidelity matches the square of the largest Schmidt
coefficient of $|\phi_{\theta}^{0}\rangle$. This means that
${\mathcal{I}}_{\theta}^{*}$ is the relevant quantity for comparing the self-
testing performance of Bell operators in device-independent tasks. Figure 4 in
the main text depicts ${\mathcal{I}}_{\theta}^{*}$ for both the tilted-CHSH
and the new inequality.

###  A.3 Extension to the other state

We have just shown how the observed violation of a Bell inequalities
${\mathcal{I}}_{\theta}$ gives a bound on the overlap of the state $\rho$ with
the target state

$\displaystyle|\phi_{\theta}^{0}\rangle=c_{\theta}|00\rangle+s_{\theta}|11\rangle$
(32)

upon applying the extraction maps $\Lambda_{a}$ and $\Lambda_{b}$. We will now
show the violation of another inequality ${\mathcal{I}}_{\theta}^{\prime}$,
related to ${\mathcal{I}}_{\theta}$ by a mere relabeling of some of the inputs
and outputs, bounds the overlap of a state $\rho^{\prime}$ with the other
target state

$\displaystyle|\phi_{\theta}^{1}\rangle=c_{\theta}|11\rangle+s_{\theta}|00\rangle.$
(33)

The proof follows the line of Ref. [26] from the main text. Before we start,
note that the two target states are related via
$|\phi_{\theta}^{0}\rangle\overset{\sigma_{x}\otimes\sigma_{x}}{\longleftrightarrow}|\phi_{\theta}^{1}\rangle$.
In the ideal case this transformation corresponds to a permutation of the
outputs of $A_{1}\leftrightarrow-A_{1}$ and the exchange of $B_{0}$ and
$B_{1}$. We will now show that this observation also holds in the non-ideal
case.

Let us first have a closer look at Eq. (31). As it holds for any state $\rho$,
it can be expressed as the expectation value of the operator

$\displaystyle\Lambda_{a}\\!\otimes\\!\Lambda_{b}\left[|\phi_{\theta}^{0}\rangle\\!\langle\phi_{\theta}^{0}|\right]-s\mathcal{B}(a,b)-\mu\mathbb{1}\geq
0,$ (34)

where $\mathcal{B}(a,b)$ is the Bell operator obtained by choosing the
settings (24), (25) in the Bell expression (17). Here we used the fact that
the maps $\Lambda_{a(b)}$ are self-adjoint and
$s=\frac{1-c_{\theta}^{2}}{1-{\mathcal{I}}_{\theta}^{*}}$ and
$\mu=\frac{c_{\theta}^{2}-{\mathcal{I}}_{\theta}^{*}}{1-{\mathcal{I}}_{\theta}^{*}}$.
This operator inequality holds for all measurement angles $a$ and $b$.

Now consider a new Bell expression corresponding to an operator
$\mathcal{B}^{\prime}$, obtained by exchanging the outputs of $A_{1}$ and
exchanging the role of the measurements $B_{0}$ and $B_{1}$ in the previous
expression. The operator $\mathcal{B}^{\prime}(a,b)$ can be obtained by
applying the rotation $R:=R_{\hat{x}}(\pi)=e^{i\frac{\pi}{2}\sigma_{x}}$:

$\mathcal{B}^{\prime}(a,b)=(R\otimes
R)\mathcal{B}^{\prime}(\frac{\pi}{2}-a,b)(R^{\dagger}\otimes R^{\dagger})$
(35)

as illustrated in Figure 6.

Figure 6: The first row shows the settings present in the experiment, the left
column belongs to Alice, the right one to Bob. In case the outcome of the
generalized measurement is $0$, they just collect the data. If the outcome is
$1$, Bob reinterprets his inputs, i.e. if he chose $B_{0}$ he saves the result
as the outcome of $B_{1}$ and vice versa. Alice on the other hand collects her
data applying $A_{0}\to-A_{0}$. This transformation is sketched in the second
row. The effect of this post-processing on the settings correspond to Alice
applying a shift to her measurement angle followed by a rotation around
$\hat{x}$ by $\pi$, i.e. $R_{\hat{x}}(\pi)\\!\circ\\!(a\to\frac{\pi}{2}-a)$,
where $R_{\hat{x}}(\pi)=e^{i\frac{\pi}{2}\sigma_{x}}$. The observables of Bob
are simply rotated by $R_{\hat{x}}(\pi)$.

Since Eq. (34) holds for all angles, it also holds for $a\to\frac{\pi}{2}-a$.
Then we act with $(R\otimes R)$ and $(R^{\dagger}\otimes R^{\dagger})$ from
the left and right respectively. We arrive at

$\displaystyle(R\\!\otimes\\!R)(\Lambda_{\tfrac{\pi}{2}-a}\\!\\!\otimes\\!\Lambda_{b})\\!\\!\left[|\phi_{\theta}^{0}\rangle\\!\langle\phi_{\theta}^{0}|\right]\\!(R^{\dagger}\\!\otimes\\!R^{\dagger})$
(36) $\displaystyle-s\mathcal{B}^{\prime}(a,b)-\mu\mathbb{1}$
$\displaystyle\geq 0.$

The rotation on Bob’s side commutes with the extraction channel $\Lambda_{b}$.
This is easily verified by reminding ourselves that
$\Omega_{b}\in\\{\sigma_{x},\sigma_{z}\\}$ and therefore
$R\Omega_{b}\rho\Omega_{b}R^{\dagger}=\Omega_{b}R\rho R^{\dagger}\Omega_{b}$.

On Alice’s side, we realize that $RHR^{\dagger}=V$. Therefore
$R\Gamma_{\tfrac{\pi}{2}-a}R^{\dagger}=\Gamma_{a}$. By also recalling that
$g(\tfrac{\pi}{2}-a)=g(a)$, we find that
$R\Lambda_{\tfrac{\pi}{2}-a}[\rho]R^{\dagger}=\Lambda_{a}[R\rho R^{\dagger}]$.

Combining everything and using $R\otimes
R|\phi_{\theta}^{0}\rangle=|\phi_{\theta}^{1}\rangle$, Eq. (36) is equivalent
to

$\displaystyle\Lambda_{a}\\!\otimes\\!\Lambda_{b}\left[|\phi_{\theta}^{1}\rangle\\!\langle\phi_{\theta}^{1}|\right]-s\mathcal{B}^{\prime}(a,b)-\mu\mathbb{1}\geq
0,$ (37)

which implies that with the same extraction channels and observables, and a
new Bell test ${\mathcal{I}}_{\theta}^{\prime}$, one can device-independently
self-test the second output state $|\phi_{\theta}^{1}\rangle$.


# A description of the Zeta map on Dyck paths area sequences

Viviane Pons  CNRS, IRL CRM Montréal – Université Paris-Saclay, CNRS,
Laboratoire Interdisciplinaire des Sciences du Numérique
<EMAIL_ADDRESS>
###### Abstract.

We give a simple iterative description of the well known Zeta map on Dyck
paths which sends the _dinv,area_ statistics to the _area,bounce_ statistics.
Our description uses Dyck paths area sequences and can be implemented easily.

## Introduction

The $qt$-Catalan symmetry is known to be one of the most intriguing questions
in algebraic combinatorics. Rooted in the study of diagonal harmonic
polynomials [Hag08], it leads to numerous combinatorial interpretations and
open questions. One of the main problems can be stated in an elementary
combinatorial way but has, to this day, no elementary solution. Dyck paths are
a well known family of combinatorial objects counted by the Catalan numbers.
The _area_ of a Dyck path is a natural statistic leading to common
$q$-enumerations of Catalan objects. The _dinv_ is another statistic which
appears to be more mysterious but has the particularity of having the same
distribution as the _area_. Moreover, there are algebraic proofs that these
two statistics are _symmetric_ : the number of Dyck paths with _area_ $q$ and
_dinv_ $t$ is the same as the number of Dyck paths with _area_ $t$ and _dinv_
$q$. There is no combinatorial proof of this symmetry, _i.e._ , there is no
bijection on Dyck paths which exchange the two statistics. Besides, this
symmetry can be extended to more general settings such as triangular Dyck
paths [BM22] and is conjectured to be schur-positive.

The purpose of this note is to share an algorithm that I have had for some
time and which might be useful to the many mathematicians working around this
problem. I got an early interest in this question and of course tried to find
the mysterious bijection myself. I failed like many others and instead came up
with a bijective map that did not switch the statistics but did send the
_area_ to the _dinv_. As I soon discovered, this turned out to the very well
known $\zeta$ map described by Haglund [Hag08] (page 50) and since then
generalized and largely studied [ALW14, TW18]. More precisely, this is
$\zeta^{-1}$. As this was no breakthrough and as I could not make much of it,
I never properly wrote it until today.

However, in recent discussions I had, I discovered that many people with
strong interest in the original problem were actually not aware of this
natural description of the $\zeta$ map. It has the advantage of being an
iterative process: it inserts letters inside the _area sequence_. The image of
a Dyck path of size $n$ is obtained through a single insertion on the image of
the corresponding Dyck path of size $n-1$. As a consequence, it can be
implemented easily and we hereby share the SageMath implementation directly
derived from this paper [Pon22].

Even though this description seems very natural, I have not seen it anywhere
else. There is already an implementation of the $\zeta$ map in SageMath
[The22] using a recursive approach on the area sequence. I tend to believe
that the proof that the SageMath implementation is indeed the map described by
Haglund is rather close to mine but the only reference found in the SageMath
manual is the Haglund map and no proper proof of the implementation is
offered. Besides, the SageMath map is slightly different as it works on a
reversed Dyck path and is then not directly the $\zeta$ map. This is why I
have decided to properly write and prove the present construction of the
$\zeta$ map with no other ambition than to share this piece of knowledge.

The paper is organized in a very straight forward manner. We first present in
Section 1 the objects at stake, namely: Dyck paths, area sequences, and the
three important statistics of the $\zeta$ map _area_ , _dinv_ , and _bounce_.
The map itself is found in Section 2.1 along with the proof that it is
bijective and sends the _area_ of a Dyck path to the _dinv_. In Section 2.2,
we prove that, like the original $\zeta^{-1}$ map, it sends the _bounce_ to
the _area_. Finally, in Section 2.3, we show that our map is indeed
$\zeta^{-1}$.

In an external annex [Pon22], we provide the detailed implementation of the
map in SageMap and a demo SageMath Jupyter Notebook following the same
structure as the paper, implementing all examples and providing tests for all
results. This demo is hosted on a Github repo providing a dynamic link
allowing to run the code on a distant server without any installation needed.

##  1\. Area sequences and statistics

###  1.1. Area sequence of a Dyck path

A Dyck path is a path in the grid consisting of north steps and east steps
starting at $(0,0)$ and such that the path never goes below the line $y=x$.
The size of a Dyck path is the number of north steps. Dyck paths are a very
classical family of combinatorial objects. The number of Dyck paths of size
$n$ is given by the Catalan numbers

$\frac{1}{n+1}\binom{2n}{n}.$

The _area sequence_ of a Dyck path is a word on $\\{0,1,\dots,n-1\\}$ such
that the letter in position $i$ gives the number of full $1\times 1$ cell in
the grid to the right of the $i^{th}$ north step and to the left of the $y=x$
line. In other words, these are the cells on the $i^{th}$ line between the
path and the $y=x$ line. In Fig. 1, we show all Dyck words of size $3$ with
their area sequences. An example of size $17$ is given on Fig. 2.

|  |  |  |
---|---|---|---|---
$000$ | $001$ | $010$ | $011$ | $012$

Figure 1. The Dyck paths of size 3 and their area sequences.

$01211123301101221$

Figure 2. An example of a Dyck path of size 17 with its area sequence.

The following characterization of area sequences is a well known fact.

######  Proposition 1.

A word $w_{1}\dots w_{n}$ of size $n$ on $\\{0,1,\dots,n-1\\}$ is the area
sequence of a Dyck path if and only if $w_{1}=0$ and for all $1\leq i<n$, we
have $0\leq w_{i+1}\leq w_{i}+1$.

The proof is immediate. The letter $w_{i}$ corresponds to the number of cells
to the right of the $i^{th}$ north step $x_{i}$. If $x_{i}$ is not the last
north step, it is followed by a certain number $e$ of east steps before the
next north step. The conditions on the Dyck path impose that $0\leq e\leq
w_{i}+1$ and we see that $w_{i+1}=w_{i}+1-e$. Here are the 14 area sequences
for Dyck paths of size 4.

$0000$ | $0001$ | $0010$ | $0011$ | $0012$ | $0100$ | $0101$
---|---|---|---|---|---|---
$0110$ | $0111$ | $0112$ | $0120$ | $0121$ | $0122$ | $0123$

The _area_ of a Dyck path is the total number of grid cells between the path
and the $y=x$ line. In other words, this is the sum of the values of the area
sequence. For example, the _area_ of the Dyck Path of Fig. 2 is $22$.

###  1.2. The _dinv_

The _dinv_ statistic on Dyck paths appears in the work of Haglund [Hag08].
There are many equivalent definitions. We directly give a description on the
area sequence.

######  Definition 2.

Let $w=w_{1}\dots w_{n}$ be an area sequence. For each letter $w_{i}$, we call
$d_{i}$ the number of letters $w_{j}$ with $j>i$ and $w_{j}=w_{i}$ or
$w_{j}=w_{i}-1$. Then, the _dinv_ of w is the sum of the $d_{i}$.

For example, for $w=010$, we obtain $d_{1}=1$, $d_{2}=1$ and $d_{3}=0$, and so
$\operatorname{dinv}(w)=2$. In the example of Fig. 2, the $d_{i}$ are given by
$2,9,10,8,7,6,6,3,2,1,4,3,0,1,2,1$ giving a total _dinv_ of 65.

###  1.3. The _bounce_

Another important statistic when working on the $\zeta$ map is the _bounce_ of
a Dyck path. The _bounce_ can be computed by drawing a “bounce path” under the
Dyck path. The bounce path is a Dyck path which starts at $(0,0)$ and goes up
as much as possible by staying under the original Dyck path, then goes
straight to the $y=x$ line and “bounces back” again as much as possible as
drawn on Fig. 3. The area sequence of the bounce path is the _bounce sequence_
which can be computed directly from the area sequence of the Dyck path.

######  Definition 3.

Let $w=w_{1}\dots w_{n}$ be an area sequence, the bounce sequence $b_{1}\dots
b_{n}$ of $w$ is given by

$\displaystyle b_{1}$ $\displaystyle=0$ $\displaystyle b_{i}$
$\displaystyle=\begin{cases}b_{i-1}+1&\text{if }b_{i-1}+1\leq w_{i}\\\
0&\text{otherwise.}\end{cases}$

Fig. 3 shows an example of Dyck path with its bounce path and bounce sequence
in red. The “bounces” of the bounce sequence correspond to all the non initial
zeros, we write $\operatorname{\mathcal{B}}(w)=\\{i>1;b_{i}=0\\}$. Now the
_bounce_ statistic is obtained by the summing the _reversed positions_ of the
bounces, _i.e._ , their distance to the end of the path which is given by
$n-i+1$. For example, in Fig. 3, we have
$b_{4}=b_{6}=b_{10}=b_{12}=b_{13}=b_{16}=0$. We sum all their reversed
positions and we obtain $\operatorname{bounce}(w)=14+12+8+6+5+2=47$.

$01211123301101221$
$\color[rgb]{1,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,0}{01201012301001201}$

Figure 3. The bounce path of a Dyck path

Note that the external annex [Pon22] provides an implementation of those
statistics following the exact definitions of the paper.

##  2\. The map

###  2.1. Area to dinv

In this section, we describe a map which, given an area sequence $w$ with
$\sum w=q$, creates a new area sequence $w^{\prime}$ such that
$\operatorname{dinv}(w^{\prime})=q$. Our algorithm is based on the notion of
_insertion_. An _insertion_ on an area sequence $w$ at position $i$ is defined
as follows

(2.1) $\displaystyle\operatorname{ins}_{0}(w)$ $\displaystyle:=0w_{1}\dots
w_{n};$ (2.2) $\displaystyle\operatorname{ins}_{i}(w)$
$\displaystyle:=w_{1}\dots w_{i}(w_{i}+1)w_{i+1}\dots w_{n}$

for $1\leq i\leq n$. For example, $\operatorname{ins}_{0}(010)=0010$,
$\operatorname{ins}_{1}(010)=0110$, $\operatorname{ins}_{2}(010)=0120$, and
$\operatorname{ins}_{3}(010)=0101$.

It is clear that the result of an insertion on an area sequence is also an
area sequence. We are now going to specify a certain list of possible
insertions on a given area sequence in order to control the exact _dinv_ added
by the insertion.

######  Definition 4.

Let $w$ be an area sequence whose maximum value is $m$. We write
$\operatorname{\mathcal{M}}(w)=w^{-1}(m):=\\{i;w_{i}=m\\}$, the positions of
the letters $m$ in $w$. We now define $\operatorname{\mathcal{M}^{\prime}}(w)$
the set of positions $i$ such that $w_{i}=m-1$ and for all $j>i$, $w_{j}<m$.
And finally, let us define $i_{0}(w)$ to be the position of the leftmost
letter $m$ in the rightmost block of consecutive $m$ letters. Then the set
$\operatorname{\mathcal{M}}\cup\operatorname{\mathcal{M}^{\prime}}\cup\\{i_{0}-1\\}$
are the _admissible insertion positions_ of $w$. The _admissible order_ on
this set is a total order given by the elements of
$\operatorname{\mathcal{M}}$ in decreasing order followed by the elements of
$\operatorname{\mathcal{M}^{\prime}}$ in decreasing order followed by
$i_{0}-1$.

If $w$ is the empty word, the admissible insertion positions of $w$ are the
set of size $1$ $\\{0\\}$.

For example, if $w=0122210122011$, then
$\operatorname{\mathcal{M}}(w)=\\{3,4,5,9,10\\}$,
$\operatorname{\mathcal{M}^{\prime}}(w)=\\{12,13\\}$, and $i_{0}(w)=9$. The
admissible insertion position in admissible order are $10,9,5,4,3,13,12,8$.
The annex [Pon22] provides the code to compute more examples.

######  Proposition 5.

Let $w$ be an area sequence and $C=c_{0},\dots,c_{k}$ its admissible insertion
positions taken in admissible order, then

(2.3)
$\operatorname{dinv}(\operatorname{ins}_{c_{i}}(w))=\operatorname{dinv}(w)+i,$

and the new word $\operatorname{ins}_{c_{i}}(w)$ has $i+2$ admissible
insertion positions. Besides, the inserted value, at position $c_{i}+1$, is
always of maximal value in $\operatorname{ins}_{c_{i}}(w)$ and it is the
leftmost element of the rightmost block of consecutive maximal values.

###### Proof.

If $i<|\operatorname{\mathcal{M}}(w)|$, then we have $w_{c_{i}}=m$. For
convenience, we write $\tilde{w}:=\operatorname{ins}_{c_{i}}(w)$. When
inserting, we obtain $\tilde{w}_{c_{i}+1}=m+1$. As $m$ was the maximal value
of $w$, there are no other letters equal to $m+1$ in $\tilde{w}$ and because
we take the positions of $\operatorname{\mathcal{M}}(w)$ in decreasing order,
there are $i$ letters equal to $m$ to the right of $\tilde{w}_{c_{i}}$ so
$d_{c_{i}+1}=i$ in $\tilde{w}$ and the rest of the _dinv_ is left unchanged.
Besides, we have $\operatorname{\mathcal{M}}(\tilde{w})=\\{c_{i}+1\\}$ and
$\operatorname{\mathcal{M}^{\prime}}(\tilde{w})=\\{c_{i-1}+1,c_{i-2}+1,\dots,c_{0}+1\\}$,
_i.e._ , the shifted positions of the letters $m$ in $w$ which were to the
right of the position $c_{i}$, and $i_{0}(\tilde{w})=c_{i}-1$. The number of
admissible insertion positions in $\tilde{w}$ is then given by $i+2$. Finally,
the inserted letter is of maximal value and as it is the only letter with such
value, it has the desired properties.

If $|\operatorname{\mathcal{M}}(w)|\leq
i<|\operatorname{\mathcal{M}}(w)|+|\operatorname{\mathcal{M}^{\prime}}(w)|$,
then we have $w_{c_{i}}=m-1$. When inserting, we obtain
$\tilde{w}_{c_{i}+1}=m$. Note that in this case,
$i=|\operatorname{\mathcal{M}}(w)|+j$ with $j\geq 0$. Besides, by definition
of the admissible order, $c_{i}$ is greater than all the elements of
$\operatorname{\mathcal{M}}(w)$. This means that for all
$k\in\operatorname{\mathcal{M}}$, $d_{k}$ is increased by one in $\tilde{w}$
and there are no elements equal to $m$ to the right of $\tilde{w}_{c_{i}+1}$.
On top of that, as we take the values of
$\operatorname{\mathcal{M}^{\prime}}(w)$ in decreasing order, there are $j$
elements in $\tilde{w}$ with value $m-1$ to the right of
$\tilde{w}_{c_{i}+1}$. So $d_{c_{i}+1}=j$ and in total, the _dinv_ is
increased by $|\operatorname{\mathcal{M}}(w)|+j=i$. Besides,
$|\operatorname{\mathcal{M}}(\tilde{w})|=|\operatorname{\mathcal{M}}(w)|+1$
whereas $|\operatorname{\mathcal{M}^{\prime}}(\tilde{w})|=j$ and so
$\tilde{w}$ has $|\operatorname{\mathcal{M}}(w)|+1+j+1=i+2$ admissible
insertion positions. Finally, the inserted letter is of value $m$, which is
still the maximal value in $\tilde{w}$, it is to the right of all the other
letters $m$ and forms by itself a block of a single element.

Now, the last case is when the insertion occurs at $i_{0}-1$. Remember that
$i_{0}$ is the leftmost letter $m$ in the rightmost block of consecutive
letters $m$ in $w$. It is possible that $i_{0}=1$ is the first letter of $w$.
In this case, $w_{i_{0}}$ as well as all letters of $w$ are actually equal to
$0$, and after the insertion, we obtain $\tilde{w}_{i_{0}}=\tilde{w}_{0}=0=m$.
Otherwise, as $w_{i_{0}}=m$, we have $w_{i_{0}-1}\geq m-1$. By definition of
$i_{0}$, $w_{i_{0}-1}$ cannot be equal to $m$ and because $m$ is maximal among
the letters of $w$, we obtain $w_{i_{0}-1}=m-1$. After the insertion, we have
$\tilde{w}_{i_{0}}=m$. For all $j\in\operatorname{\mathcal{M}}(w)$ such that
$j<i_{0}$, the value $d_{j}$ increases by $1$ whereas
$d_{i_{0}}=|\\{j\in\operatorname{\mathcal{M}}(w);j>i_{0}\\}|+\operatorname{\mathcal{M}^{\prime}}(w)$
so the _dinv_ is indeed increased by
$|\operatorname{\mathcal{M}}(w)|+|\operatorname{\mathcal{M}^{\prime}}(w)|$.
Besides,
$|\operatorname{\mathcal{M}}(\tilde{w})|=|\operatorname{\mathcal{M}}(w)|+1$
whereas
$\operatorname{\mathcal{M}^{\prime}}(\tilde{w})=\operatorname{\mathcal{M}^{\prime}}(w)$
and so $\tilde{w}$ has
$|\operatorname{\mathcal{M}}(w)|+|\operatorname{\mathcal{M}^{\prime}}(w)|+2$
admissible insertion positions. Finally, the inserted letter is of maximal
value and by definition of $i_{0}$, it is the leftmost of the rightmost block
of consecutive maximal letters. ∎

To illustrate this proof, we show all admissible insertions on the area
sequence $0122210122011$ on Fig. 4. The _dinv_ of the sequence is $44$. We
have marked the admissible insertion positions with $\cdot_{i}$ where $i$ is
the index in the admissible order. You can check that an insertion at $c_{i}$
corresponds to an increase of $i$ in the _dinv_ and that the new sequence has
$i+2$ insertion positions.

insertion position | area sequence | _dinv_
---|---|---
| $0\leavevmode\nobreak\ 1\leavevmode\nobreak\ 2\cdot_{4}2\cdot_{3}2\cdot_{2}1\leavevmode\nobreak\ 0\leavevmode\nobreak\ 1\cdot_{7}2\cdot_{1}2\cdot_{0}0\leavevmode\nobreak\ 1\cdot_{6}1\cdot_{5}$ | 44
$c_{0}=10$ | $0\leavevmode\nobreak\ 1\leavevmode\nobreak\ 2\leavevmode\nobreak\ 2\leavevmode\nobreak\ 2\leavevmode\nobreak\ 1\leavevmode\nobreak\ 0\leavevmode\nobreak\ 1\leavevmode\nobreak\ 2\leavevmode\nobreak\ 2\cdot_{1}{\color[rgb]{1,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,0}3}\cdot_{0}0\leavevmode\nobreak\ 1\leavevmode\nobreak\ 1$ | 44
$c_{1}=9$ | $0\leavevmode\nobreak\ 1\leavevmode\nobreak\ 2\leavevmode\nobreak\ 2\leavevmode\nobreak\ 2\leavevmode\nobreak\ 1\leavevmode\nobreak\ 0\leavevmode\nobreak\ 1\leavevmode\nobreak\ 2\cdot_{2}{\color[rgb]{1,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,0}3}\cdot_{0}2\cdot_{1}0\leavevmode\nobreak\ 1\leavevmode\nobreak\ 1$ | 45
$c_{2}=5$ | $0\leavevmode\nobreak\ 1\leavevmode\nobreak\ 2\leavevmode\nobreak\ 2\leavevmode\nobreak\ 2\cdot_{3}{\color[rgb]{1,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,0}3}\cdot_{0}1\leavevmode\nobreak\ 0\leavevmode\nobreak\ 1\leavevmode\nobreak\ 2\cdot_{2}2\cdot_{1}$ | 46
$c_{3}=4$ | $0\leavevmode\nobreak\ 1\leavevmode\nobreak\ 2\leavevmode\nobreak\ 2\cdot_{4}{\color[rgb]{1,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,0}3}\cdot_{0}2\cdot_{3}1\leavevmode\nobreak\ 0\leavevmode\nobreak\ 1\leavevmode\nobreak\ 2\cdot_{2}2\cdot_{1}0\leavevmode\nobreak\ 1\leavevmode\nobreak\ 1$ | 47
$c_{4}=3$ | $0\leavevmode\nobreak\ 1\leavevmode\nobreak\ 2\cdot_{5}{\color[rgb]{1,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,0}3}\cdot_{0}2\cdot_{4}2\cdot_{3}1\leavevmode\nobreak\ 0\leavevmode\nobreak\ 1\leavevmode\nobreak\ 2\cdot_{2}2\cdot_{1}0\leavevmode\nobreak\ 1\leavevmode\nobreak\ 1$ | 48
$c_{5}=13$ | $0\leavevmode\nobreak\ 1\leavevmode\nobreak\ 2\cdot_{5}2\cdot_{4}2\cdot_{3}1\leavevmode\nobreak\ 0\leavevmode\nobreak\ 1\leavevmode\nobreak\ 2\cdot_{2}2\cdot_{1}0\leavevmode\nobreak\ 1\leavevmode\nobreak\ 1\cdot_{6}{\color[rgb]{1,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,0}2}\cdot_{0}$ | 49
$c_{6}=12$ | $0\leavevmode\nobreak\ 1\leavevmode\nobreak\ 2\cdot_{5}2\cdot_{4}2\cdot_{3}1\leavevmode\nobreak\ 0\leavevmode\nobreak\ 1\leavevmode\nobreak\ 2\cdot_{2}2\cdot_{1}0\leavevmode\nobreak\ 1\cdot_{7}{\color[rgb]{1,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,0}2}\cdot_{0}1\cdot_{6}$ | 50
$c_{7}=8$ | $0\leavevmode\nobreak\ 1\leavevmode\nobreak\ 2\cdot_{5}2\cdot_{4}2\cdot_{3}1\leavevmode\nobreak\ 0\leavevmode\nobreak\ 1\cdot_{8}{\color[rgb]{1,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,0}2}\cdot_{2}2\cdot_{1}2\cdot_{0}0\leavevmode\nobreak\ 1\cdot_{7}1\cdot_{6}$ | 51
Figure 4. All admissible insertions on a given area sequence.

######  Theorem 6.

Let $w$ be an area sequence, we define $\psi(w)$ recursively as follows. If
$w=\varepsilon$, then $\psi(w):=\varepsilon$. Otherwise, $w=ua$ where $u$ is a
word and $a$ is a letter, and $\psi(w):=\operatorname{ins}_{c_{a}}(\psi(u))$
where $c_{0},c_{1},\dots,c_{k}$ are the admissible insertion positions of
$\psi(u)$ taken in admissible order.

Then $\psi$ defines a bijection on area sequences such that
$\operatorname{dinv}(\psi(w))=\operatorname{area}(w)$.

In other words, you read the area sequence from left to right and each letter
is giving you an insertion to perform on the image using the admissible
insertion positions.

###### Proof.

This is immediate by induction using Proposition 5. Indeed, you first need to
check that the map is well defined, _i.e._ that $a\leq k$, $k+1$ being the
number of admissible insertion positions of $\psi(u)$. It is true on the
initial case: the first of letter of $w$ is $0$ and there is $1$ admissible
insertion position on the empty word. Then Proposition 5 ensures that after
inserting at $c_{a}$, you obtain $a+2$ admissible insertion positions
corresponding to the $a+2$ possible letters that could follow $a$ (from $0$ to
$a+1$). Then (2.3) gives you the expected result for the _dinv_. Besides, it
is indeed a bijection as the operation is reversible: by Proposition 5, the
last inserted letter is the leftmost letter in the rightmost block of maximal
values. By removing this letter from a word $w^{\prime}$, the difference in
_dinv_ tells you by which letter $a$ the preimage $w$ of $w^{\prime}$ ends. ∎

Fig. 5 shows the step by step computation of the word of Fig. 2. At each step,
the admissible insertion positions are indicated with their order on the image
$\psi$.

$0$ | $\cdot_{1}0\cdot_{0}$
---|---
$0$ |
$01$ | $\cdot_{2}0\cdot_{1}0\cdot_{0}$
$01$ |
$012$ | $\cdot_{3}0\cdot_{2}0\cdot_{1}0\cdot_{0}$
$012$ |
$0121$ | $0\leavevmode\nobreak\ 0\cdot_{2}1\cdot_{0}0\cdot_{1}$
$0120$ |
$01211$ | $0\leavevmode\nobreak\ 0\leavevmode\nobreak\ 1\cdot_{1}0\cdot_{2}1\cdot_{0}$
$01201$ |
$012111$ | $0\leavevmode\nobreak\ 0\leavevmode\nobreak\ 1\cdot_{2}2\cdot_{0}0\leavevmode\nobreak\ 1\cdot_{1}$
$012010$ |
$0121112$ | $0\leavevmode\nobreak\ 0\leavevmode\nobreak\ 1\cdot_{3}2\cdot_{1}2\cdot_{0}0\leavevmode\nobreak\ 1\cdot_{2}$
$0120101$ |
$01211123$ | $0\leavevmode\nobreak\ 0\leavevmode\nobreak\ 1\cdot_{4}2\cdot_{2}2\cdot_{1}2\cdot_{0}0\leavevmode\nobreak\ 1\cdot_{3}$
$01201012$ |
$012111233$ | $0\leavevmode\nobreak\ 0\leavevmode\nobreak\ 1\leavevmode\nobreak\ 2\cdot_{3}2\cdot_{2}2\cdot_{1}0\leavevmode\nobreak\ 1\cdot_{4}2\cdot_{0}$
$012010123$ |
$0121112330$ | $0\leavevmode\nobreak\ 0\leavevmode\nobreak\ 1\leavevmode\nobreak\ 2\leavevmode\nobreak\ 2\leavevmode\nobreak\ 2\leavevmode\nobreak\ 0\leavevmode\nobreak\ 1\leavevmode\nobreak\ 2\cdot_{1}3\cdot_{0}$
$0120101230$ |
$01211123301$ | $0\leavevmode\nobreak\ 0\leavevmode\nobreak\ 1\leavevmode\nobreak\ 2\leavevmode\nobreak\ 2\leavevmode\nobreak\ 2\leavevmode\nobreak\ 0\leavevmode\nobreak\ 1\leavevmode\nobreak\ 2\cdot_{2}3\cdot_{1}3\cdot_{0}$
$01201012301$ |
$012111233011$ | $0\leavevmode\nobreak\ 0\leavevmode\nobreak\ 1\leavevmode\nobreak\ 2\leavevmode\nobreak\ 2\leavevmode\nobreak\ 2\leavevmode\nobreak\ 0\leavevmode\nobreak\ 1\leavevmode\nobreak\ 2\leavevmode\nobreak\ 3\cdot_{2}4\cdot_{0}3\cdot_{1}$
$012010123010$ |
$0121112330110$ | $0\leavevmode\nobreak\ 0\leavevmode\nobreak\ 1\leavevmode\nobreak\ 2\leavevmode\nobreak\ 2\leavevmode\nobreak\ 2\leavevmode\nobreak\ 0\leavevmode\nobreak\ 1\leavevmode\nobreak\ 2\leavevmode\nobreak\ 3\leavevmode\nobreak\ 4\cdot_{1}5\cdot_{0}3$
$0120101230100$ |
$01211123301101$ | $0\leavevmode\nobreak\ 0\leavevmode\nobreak\ 1\leavevmode\nobreak\ 2\leavevmode\nobreak\ 2\leavevmode\nobreak\ 2\leavevmode\nobreak\ 0\leavevmode\nobreak\ 1\leavevmode\nobreak\ 2\leavevmode\nobreak\ 3\leavevmode\nobreak\ 4\cdot_{2}5\cdot_{1}5\cdot_{0}3$
$01201012301001$ |
$012111233011012$ | $0\leavevmode\nobreak\ 0\leavevmode\nobreak\ 1\leavevmode\nobreak\ 2\leavevmode\nobreak\ 2\leavevmode\nobreak\ 2\leavevmode\nobreak\ 0\leavevmode\nobreak\ 1\leavevmode\nobreak\ 2\leavevmode\nobreak\ 3\leavevmode\nobreak\ 4\cdot_{3}5\cdot_{2}5\cdot_{1}5\cdot_{0}3$
$012010123010012$ |
$0121112330110122$ | $0\leavevmode\nobreak\ 0\leavevmode\nobreak\ 1\leavevmode\nobreak\ 2\leavevmode\nobreak\ 2\leavevmode\nobreak\ 2\leavevmode\nobreak\ 0\leavevmode\nobreak\ 1\leavevmode\nobreak\ 2\leavevmode\nobreak\ 3\leavevmode\nobreak\ 4\leavevmode\nobreak\ 5\cdot_{3}6\cdot_{0}5\cdot_{2}5\cdot_{1}3$
$0120101230100120$ |
$01211123301101221$ | $0\leavevmode\nobreak\ 0\leavevmode\nobreak\ 1\leavevmode\nobreak\ 2\leavevmode\nobreak\ 2\leavevmode\nobreak\ 2\leavevmode\nobreak\ 0\leavevmode\nobreak\ 1\leavevmode\nobreak\ 2\leavevmode\nobreak\ 3\leavevmode\nobreak\ 4\leavevmode\nobreak\ 5\leavevmode\nobreak\ 6\cdot_{1}5\leavevmode\nobreak\ 5\cdot_{2}6\cdot_{0}3$
$01201012301001201$ |
Figure 5. The step by step $\psi$ map on an example. On the left, an area
sequence $w$ with its bouncing path underneath. On the right, $\psi(w)$ with
its admissible insertion positions.

###  2.2. Bounce to area

In this section, we explain how the _bounce_ statistic can be understood
through the $\psi$ map. This will also be key to prove that this map is
actually $\zeta^{-1}$.

######  Proposition 7.

Let $w$ be an area sequence of size $n$ and $\psi$ the map defined in Theorem
6. We write $b_{1},\dots b_{n}$ the bounce sequence of $w$ and
$\operatorname{\mathcal{B}}(w)$ the bounces of $w$, _i.e._ the non initial $0$
of the bounce sequence. Remember that the _bounce_ of $w$ is given by the sum
of the reversed position $n-i+1$ for all $i$ in
$\operatorname{\mathcal{B}}(w)$. We have

  * •

$b_{n}=0$ if and only if $\max(\psi(w))=\max(\psi(u))+1$, where $u$ is the
prefix of $w$ of size $n-1$;

  * •

$|\operatorname{\mathcal{B}}(w)|=\max(\psi(w))$

  * •

$|\operatorname{\mathcal{M}}(\psi(w))|=b_{n}+1$;

  * •

$|\operatorname{\mathcal{M}^{\prime}}(\psi(w))|=w_{n}-b_{n}$;

where $\operatorname{\mathcal{M}^{\prime}}$ and $\operatorname{\mathcal{M}}$
are taken from Definition 4. Besides, for each $1\leq k\leq\max(\psi(w))$, the
number of values greater than or equal to $k$ in $\psi(w)$ is given by the
reversed position of the $k^{th}$ bounce of the the bounce sequence of $w$.

For example, look at the image of $w=01211123301101221$ which can be found on
the last line of Fig. 5. As before, we write $b_{1}\dots b_{n}$ its bounce
sequence given in red underneath $w$. We have that $b_{n}>0$ and the last
inserted value is a $6$ which is equal to $\max(\psi(u))$. We have
$|\operatorname{\mathcal{B}}(w)|=6$ because the bounce sequence has $6$ non
initial zeros. $|\operatorname{\mathcal{M}}(\psi(w))|$ corresponds to the
number of letters equal to $6$ in $\psi(w)$, there are indeed $2=b_{n}+1$ of
them. And $|\operatorname{\mathcal{M}^{\prime}}(\psi(w)|$ is the number of
letters equal to $5$ to the right of the last $6$, there are none of them and
indeed $w_{n}-b_{n}=0$. Besides, the first bounce of $w$ is $b_{4}=0$, with
reversed position $14$, and there are $14$ values greater than or equal to $1$
in $\psi(w)$. The second bounce is $b_{6}=0$ with reversed position $12$ which
is the number of values greater than or equal to $2$ in $\psi(w)$. This can be
checked for all the other bounces of $w$.

###### Proof.

Again, the proof can be made by induction. First note that the area sequence
$0$ of size $1$ satisfies all the conditions. In this case, the bounce
sequence is also $0$ as well as $\psi(w)$. We have
$\operatorname{\mathcal{B}}(w)=\emptyset$,
$\operatorname{\mathcal{M}}(\psi(w))=\\{1\\}$ and
$\operatorname{\mathcal{M}^{\prime}}(\psi(w))=\emptyset$.

Now take $w$ an area sequence of size $n>0$ and suppose that it satisfies the
conditions. We prove that the area sequence $wa$ with $0\leq a\leq w_{n}+1$
also satisfies it. We use all the previous notations and write
$m:=\max(\psi(w))$ for convenience.

Let us look at the case where $a<|\operatorname{\mathcal{M}}(\psi(w))|$. In
particular, this means that $b_{n}+1>a$. By definition of the bounce sequence,
this implies $b_{n+1}=0$. Remember from the proof of Proposition 5 that if we
take $a<|\operatorname{\mathcal{M}}(\psi(w))|$, the inserted letter in
$\psi(w)$ is going to be $m+1$. So we have indeed that $b_{n+1}=0$ and
$\max(\psi(wa))=m+1$. Besides
$\operatorname{\mathcal{B}}(wa)=\operatorname{\mathcal{B}}(w)\cup\\{n+1\\}$
and so $|\operatorname{\mathcal{B}}(wa)|=\max(\psi(wa))$. Now as we added a
letter $m+1$, for all $k\leq m$ we have increased by $1$ the number of letters
in the image with a value greater than or equal to $k$. As the length of the
bounce sequence has increased, the reversed positions of all the elements of
$\operatorname{\mathcal{B}}(w)$ has also been increased by one. And there is a
unique value $m+1$ which corresponds to the reversed position $1$ of
$b_{n+1}$. This ensures that the proposition is satisfied. We still need to
check that the conditions on $\operatorname{\mathcal{M}}$ and
$\operatorname{\mathcal{M}^{\prime}}$ are still satisfied on $wa$. We have
indeed that $|\operatorname{\mathcal{M}}(wa)|=1=b_{n+1}+1$. By definition of
the map and of the admissible insertion order, the value of $a$ indicates the
number of letters equal to $m$ which will end up to the right of the inserted
$m+1$ in $\psi(wa)$. So we have
$|\operatorname{\mathcal{M}^{\prime}}(\psi(wa)|=a=a-b_{n+1}$, because
$b_{n+1}=0$.

In the case where $a>|\operatorname{\mathcal{M}}(\psi(w))|$, the letter
inserted in $\psi(w)$ is $m$. On the bounce sequence, we have $a>b_{n}+1$ and
so $b_{n+1}=b_{n}+1>0$, and
$|\operatorname{\mathcal{B}}(wa)|=|\operatorname{\mathcal{B}}(w)|=m=\max(\psi(wa))$.
As before, for all $k\leq m$ we have increased by $1$ the number of letters in
the image with a value greater than or equal to $k$. As the length of the
bounce sequence has increased, the reversed positions of all the elements of
$\operatorname{\mathcal{B}}(wa)=\operatorname{\mathcal{B}}(w)$ has also been
increased by one and the proposition is satisfied. Now
$|\operatorname{\mathcal{M}}(\psi(wa)|=|\operatorname{\mathcal{M}}(\psi(w))|+1=b_{n}+1+1=b_{n+1}+1$
as we have added one letter of maximal value $m$. Finally, by definition of
the map, we have $a=|\operatorname{\mathcal{M}}(w)|+j$ where $j$ is the number
of letters equal to $m-1$ to the right of the newly inserted value $m$ in
$\psi(wa)$. We obtain
$|\operatorname{\mathcal{M}^{\prime}}(\psi(wa))|=j=a-|\operatorname{\mathcal{M}}(\psi(w))|=a-(b_{n}+1)=a-b_{n+1}$.
∎

######  Corollary 8.

Let $w$ be an area sequence and $\psi$ the map defined in Theorem 6. Then

(2.4) $\operatorname{bounce}(w)=\operatorname{area}(\psi(w)).$

###### Proof.

This is immediate: the proposition ensures that the sum of the area sequence
$\psi(w)$ is the sum of the reversed positions of the bounce sequence of $w$.
∎

###  2.3. The $\zeta$ map

Haglund describes the $\zeta$ map in [Hag08], page 50. In particular, it has
the property that for a Dyck path $w$,
$\operatorname{dinv}(w)=\operatorname{area}(\zeta(w))$ and
$\operatorname{area}(w)=\operatorname{bounce}(\zeta(w))$. We have seen that
this is also the case for $\psi^{-1}$ and we can prove that these are the same
maps.

######  Proposition 9.

The $\psi$ map is the inverse of the classical $\zeta$ map defined by Haglund.

###### Proof.

This is a direct consequence of Proposition 7. Indeed, in his book Haglund
describes the image of a path $\pi$ though $\zeta$ by first constructing the
bounce path of $\pi$. He gives the bounce steps $\alpha_{1},\dots,\alpha_{k}$.
The bounces of the pre-image of $\pi$ through $\psi$ as described in
Proposition 7 are just a reformulation of those and follow the same rule.

Now the path $\zeta(\pi)$ between two peaks of the bounce path is entirely
determined by the relative positions of the occurrences of two consecutive
values in the area sequence of $\pi$ (first the $0$ and $1$, then the $1$ and
$2$, etc.). Similarly, each new $0$ in the bounce path of an area sequence $w$
creates a new maximum $m$ in $\psi(w)$, the values of $w$ before the next
bounce will determine the relative placements of the $m$ and $m-1$ values in a
way that is similar to Haglund’s construction. ∎

## Acknowledgments

This work has received funding from the PAGCAP Project ANR-21-CE48-0020. I
also thank the CNRS and INSMI for the opportunity to spend a year at IRL CRM
in Montreal. Thank you to Hugh Thomas and Nathan Williams for looking at the
paper before its release.

## References

  * [ALW14] D. Armstrong, N. Loehr, and G. Warrington.  Sweep maps: A continuous family of sorting algorithms.  Advances in Mathematics, 284, 06 2014.
  * [BM22] François Bergeron and Mikhail Mazin.  Combinatorics of triangular partitions, 2022.  preprint, arXiv:2203.15942.
  * [Hag08] J. Haglund.  The Q, T-Catalan Numbers and the Space of Diagonal Harmonics: With an Appendix on the Combinatorics of Macdonald Polynomials.  University lecture series. American Mathematical Soc., 2008.
  * [Pon22] V Pons.  An implementation of the zeta map on dyck paths area sequences, 2022.  https://github.com/VivianePons/zeta_areaseq.
  * [The22] The Sage Developers.  SageMath, the Sage Mathematics Software System (Version 9.5), 2022.  https://www.sagemath.org.
  * [TW18] H. Thomas and N. Williams.  Sweeping up zeta.  Selecta Mathematica, 24, 03 2018.