††thanks: These authors contributed equally to this work.††thanks: These
authors contributed equally to this work.

# Local quantum overlapping tomography

Bruna G. M. Araújo  ICFO - Institut de Ciencies Fotoniques, The Barcelona
Institute of Science and Technology, 08860, Castelldefels, Barcelona, Spain
Department of Physics, Universitat Autònoma de Barcelona, Campus UAB,
Bellaterra, 08193 Barcelona, Spain  Márcio M. Taddei  ICFO - Institut de
Ciencies Fotoniques, The Barcelona Institute of Science and Technology, 08860,
Castelldefels, Barcelona, Spain  marciotaddei [at] gmail [dot] com Daniel
Cavalcanti  ICFO - Institut de Ciencies Fotoniques, The Barcelona Institute of
Science and Technology, 08860, Castelldefels, Barcelona, Spain  Bitflow,
Piquer 23, Barcelona, 08004 Spain  Algorithmiq Ltd, Kanavakatu 3 C, FI-00160
Helsinki, Finland  Antonio Acín  ICFO - Institut de Ciencies Fotoniques, The
Barcelona Institute of Science and Technology, 08860, Castelldefels,
Barcelona, Spain  ICREA - Institució Catalana de Recerca i Estudis Avançats,
Lluis Companys 23, 08010 Barcelona, Spain

(August 30, 2024)

###### Abstract

Reconstructing the full quantum state of a many-body system requires the
estimation of a number of parameters that grows exponentially with system
size. Nevertheless, there are situations in which one is only interested in a
subset of these parameters and a full reconstruction is not needed. A
paradigmatic example is a scenario where one aims at determining all the
reduced states only up to a given size. Overlapping tomography provides
constructions to address this problem with a number of product measurements
much smaller than what is obtained when performing independent tomography of
each reduced state. There are however many relevant physical systems with a
natural notion of locality where one is mostly interested in the reduced
states of neighboring particles. In this work, we study this form of local
overlapping tomography. First of all, we show that, contrary to its full
version, the number of product-measurement settings needed for local
overlapping tomography does not grow with system size. Then, we present
strategies for qubit and fermionic systems in selected lattice geometries. The
developed methods find a natural application in the estimation of many-body
systems prepared in current quantum simulators or quantum computing devices,
where interactions are often local.

##  I Introduction

There have been great advances in the construction of quantum devices, with
systems composed of tens of individually addressable qubits [1, 2, 3, 4, 5],
more than a hundred bosonic modes [6, 7], or intermediate-scale systems of up
to thousands of entangled qubits [8, 9], with further advances clearly on the
way. These are based on several different physical systems, such as trapped-
ion spins, superconductors or photons. These developments bring to the fore
the problem of efficiently measuring a quantum system. A full description of a
system of size $n$ requires an amount of parameters exponential in $n$, and
likewise full quantum state tomography requires an exponential amount of
resources (e.g. measurement settings, outcomes), a feat that has been achieved
so far for a maximum of 10 qubits [10].

Several approaches have been presented to circumvent the problem and
reconstruct the quantum state with fewer measurements settings and fewer
produced copies of the state to be measured. Some assume an _a priori_
structure of the measured states, such as classes including matrix-product
states [11, 12], or require certain structures for efficient measurement [13,
14, 15]. The “shadow tomography” technique [16, 17] is not at its most
efficient when reconstructing quantum states, and additionally requires a
quantum memory to store several copies of the state and act collectively on
them, or else its advantage is lost [18]. Randomized techniques [19, 20] aim
at obtaining expectation values of given operators under a quantum state, but
can be used for state reconstruction as well.

A less ambitious, but possibly more realistic approach is to focus not on the
entire quantum state but on some of its properties of interest. A natural
example is that where one is interested in estimating its $k$-body reduced
density matrices ($k$-RDMs). It is not uncommon for there to be interest in
$k$-body operators, e.g. to detect the entanglement [21, 22] or Bell non-
locality [23] of the many-body state from the expectation values of $2$-body
operators. A direct approach consists of measuring each $k$-RDM independently.
If we restrict our considerations to products of single-particle projective
measurements for their experimental feasibility, this already produces a
significant reduction of measurement settings compared to full tomography: the
latter requires $e^{\mathcal{O}(n)}$ measurement settings, while each $k$-RDM
requires $e^{\mathcal{O}(k)}$ measurement settings, hence the complete set of
$k$-RDMs, $e^{\mathcal{O}(k)}\binom{n}{k}\sim e^{\mathcal{O}(k)}(n^{k}/k^{k})$
settings. However, existing techniques [24, 25, 26, 27, 19, 28, 29, 30] based
on parallelization can reduce that amount substantially. For a system of $n$
qubits, the technique in [25] uses at most $\mathcal{O}(e^{k}\log^{k-1}n)$
measurement settings to obtain all $k$-RDMs, and the one in [26] obtains a
constant-factor reduction of the latter for $k=2$; in [27] it is shown that
$e^{\mathcal{O}(k)}\log n$ measurement settings suffice. For systems of
fermions, the $\binom{2n}{2k}$ operators needed can be measured [25, 28] with
$\mathcal{O}(n^{2})$ measurement settings if $k=2$, and for any $k$ there are
schemes [29] with $\mathcal{O}(n^{k})$ or, even better,
$\mathcal{O}(\binom{n}{k})$ measurement settings [30]. It is noticeable that
restrictions to parallelism from fermionic anticommutation relations
negatively impact the reduction of complexity. To the best of our
understanding, none of these results is known to be tight.

The measurement strategies above target obtaining every $k$-RDM of an
$n$-partite system. However, there are often cases where certain subsets are
especially relevant and others, much less so. The most typical example is when
there is a spatial distribution (e.g. a lattice) with local interactions
expected (though not necessarily assumed) to play an important role: RDMs
containing neighboring subsystems are much more important than those
containing faraway ones. The main goal of this work is to provide efficient
strategies to measure these reduced states by means of products of local
measurements, as in overlapping tomography. Our first result is to show that
this form of _local quantum overlapping tomography_ (local QOT) produces a
much more dramatic reduction in complexity: while the naive approach in which
full tomography is performed for all reduced states of interest requires a
number of measurement settings that grows with the number of reduced states,
and hence with the system size, an efficient parallelization can do away with
the system-size dependence. After presenting this general result, we provide
finer measurement strategies for finite-dimensional and fermionic systems in
well-known lattice geometries.

It is propitious at this point to mention scenarios where local overlapping
tomography is more (and less) promising as a measurement tool. Contexts in
which long-range correlations are expected are not well-suited for direct use
of local QOT, since it deliberately forgoes probing them. Nevertheless, in the
case of constructed quantum systems (i.e. quantum circuits), individual
$k$-body gates may be characterized with much parallelization by (few rounds
of) local QOT.

The article is structured as follows: In Sec. II, we present existing results
and set the notation. In Sec. III we present our main results, first in the
form of a general tiling argument, then for qubits (Sec. III.1) and lastly for
fermions (Sec. III.2). In Sec. IV we make our concluding remarks.

##  II Preliminaries

Our main goal is to find descriptions of $k$-body subsystems with as few
measurement settings as possible. In an experimental scenario, the amount of
different measurement settings typically impacts the overall experimental
complexity, and its reduction may turn experimental proposals from potential
to actually feasible. Because we want to obtain practical schemes with
experimental feasibility, we only consider products of projective local
measurements. This excludes entangling measurements, notably harder to
perform, as well as constructions defined by SIC-POVMs (symmetric,
informationally complete positive operator-valued measures), which reduce the
number of different measurements at the cost of a markedly higher complexity
of the experimental setup [31, 32, 33]. As such, one measurement setting for
the system consists in a specific sequence of single-particle measurement
settings. Let us first review some existing results, and with it fix some
relevant definitions and notation. In what follows, when considering finite-
dimensional systems, we restrict our considerations to qubits, although most
of our results can easily be generalized to arbitrary dimension.

###  II.1 Qubits

If $\rho$ is an $n$-qubit state, any state obtained by taking the partial
trace with respect to a set of $n-k$ qubits is a $k$-RDM of $\rho$. It is
possible to reconstruct such $k$-RDMs from the expectation values of products
of Pauli matrices. Consider as an example the $k$-RDM of the first $k$ qubits,
$\operatorname{Tr}_{[n]\backslash[k]}(\rho)$, where we define
$[j]:=\\{0,1,\cdots,j-1\\}$. The set of expectation values of the form
$\langle\sigma_{a_{0}}^{(0)}\otimes\cdots\otimes\sigma_{a_{j}}^{(j)}\otimes\cdots\otimes\sigma_{a_{k-1}}^{(k-1)}\rangle$
clearly suffices to characterize this $k$-RDM if $\sigma_{a_{j}}^{(j)}$ can be
either the identity or one of the Pauli matrices $\sigma_{x}$, $\sigma_{y}$,
$\sigma_{z}$ of the $j$-th qubit. However, this can be simplified by the fact
that the algorithms in question are based on making local measurements with
access to each local outcome. In this scenario, any measurement setting that
includes an identity can be simulated by taking the suitable marginal of a
setting with a Pauli matrix in its place. Thus, obtaining the $k$-RDM
$\operatorname{Tr}_{[n]\backslash[k]}(\rho)$ is equivalent to obtaining the
expectation values in the form
$\sigma_{a_{0}}^{(0)}\otimes\cdots\otimes\sigma_{a_{j}}^{(j)}\otimes\cdots\otimes\sigma_{a_{k-1}}^{(k-1)}$,
with $\sigma_{a_{j}}^{(j)}$ being only the three Pauli matrices $\sigma_{x}$,
$\sigma_{y}$, $\sigma_{z}$ of the $j$-th qubit.

For a system of $n$ qubits, several works have tackled the issue of obtaining
all $\binom{n}{k}$ existing $k$-RDMs with as few different measurement
settings as possible through parallelization. For the $2$-RDM, Refs. [27, 25,
26] have obtained $\langle\sigma_{a}^{(i)}\otimes\sigma_{b}^{(j)}\rangle$ for
all pairs of qubits $(i,j)$ and $a,b$ covering all combinations of
$\sigma_{x}$, $\sigma_{y}$, $\sigma_{z}$. Refs. [25] and [27] present schemes
with $N=3+6\lceil\log_{2}n\rceil$ measurement settings based on partitioning
and a family of hash functions $(n,2)$, respectively; [26] reduces that
scaling to $N=3+6\lceil\log_{3}n\rceil$. The first two allow for
generalizations to $k>2$: [25] presents a scheme based on recursive
partitioning with $N=\mathcal{O}(3^{k}\log_{2}^{k-1}n)$ measurement settings;
[27] reduces the problem to finding hash functions $(n,k)$, yielding
$N=e^{\mathcal{O}(k)}\log_{2}n$ measurement settings (see Section II.3 for a
further result).

All these results target the obtention of all $k$-RDMs, regardless of any
structure. As mentioned, we follow here a different approach, where the RDMs
of interest are those of neighboring sites on a lattice. Many relevant
systems, such as ion traps [8, 34], quantum-dot lattices [35], semiconductor
lattices [36], among others, work based on local interactions with neighbors
(first or beyond), and would benefit from a measurement scheme focused on
them.

###  II.2 Fermions

In addition to qubits, we also tackle the efficient measurement of systems
composed of fermions. Fermionic systems present a much greater challenge than
qubits. Because of their anticommutation relations, operators on different
lattice sites may no longer commute, hence one cannot rely on tensor-product
relations to ensure jointly measurability, as in qubits.

In a fermionic system of $n$ modes with $m$ particles ($n\geqslant m$), the
$k$-RDM is given by tracing out $(m-k)$ particles,
$\operatorname{Tr}_{[m-k]}(\rho)$, with the difference that any set of $(m-k)$
particles is equivalent, due to symmetry. Each mode $i$ has an annihilation
($a_{i}$) and a creation ($a_{i}^{\dagger}$) operator, and to obtain
$\operatorname{Tr}_{[m-k]}(\rho)$ it suffices [37] to obtain the expectation
values of operators composed of $k$ creation and $k$ annihilation operators.
For the 1-RDM, for instance, the values of $\langle
a_{i}^{\dagger}a_{j}\rangle$ for all modes $i,j$ suffice. It will be
convenient, however, to work with Majorana operators [38, 39, 40], which offer
an equivalent description of fermionic systems,

$\gamma_{2j}:=a_{j}^{\dagger}+a_{j}\
,\quad\quad\gamma_{2j+1}:=i(a_{j}^{\dagger}-a_{j})\ .$ (1)

Majorana operators (Majoranas, for short) are Hermitian with $\pm 1$
eigenvalues and have an important role in the (partial) equivalence between
fermions and qubits [41, 38, 42]. The $k$-RDM of a given system requires all
expectation values
$\langle\gamma_{p}\gamma_{q}\cdots\gamma_{r}\gamma_{s}\rangle$ composed of
$2k$ Majoranas, e.g. $\langle\gamma_{p}\gamma_{q}\rangle$ for all $p,q$ for
the 1-RDM. Of utmost relevance for parallelization is that different Majoranas
all anticommute, a marked difference to qubits.

Once again, the existing literature tackles the obtention of all
$\langle\gamma_{p}\gamma_{q}\cdots\gamma_{r}\gamma_{s}\rangle$ for a given
value $k$. By appropriately pairing Majoranas, Ref. [25] obtains so-called
“cliques” composed of commuting multiple-Majorana operators. As all operators
in a clique are Hermitian and commute, they can be determined in a single
measurement setting, hence only one setting is required per clique. There are
established routines to perform such measurements, typically with fermion-to-
qubit mappings [29, 30].

For the 1-RDM, the authors of [25] present a scheme to cover all needed
Majorana operators with $2n-1$ commuting cliques ($N=2n-1$) and for the 2-RDM,
with $(10/3)n^{2}+\mathcal{O}(n)$ commuting cliques. A general lower bound of
$N=\binom{2n}{2k}/\binom{n}{k}$ on the needed number of cliques (hence, of
measurement settings) is also shown in [25]; for the 1-RDM it is saturated by
their scheme, $\binom{2n}{2}/\binom{n}{1}=2n-1$, whereas for the 2-RDM the
bound is below their scheme by a prefactor in the leading-order term,
$\binom{2n}{4}/\binom{n}{2}=(4/3)n^{2}+\mathcal{O}(n)$.

In contrast, here we consider fermions in a lattice [43, 44, 36, 35, 45]; to
each lattice site $j$ belong two Majorana operators, as in Eq. (1). Given the
spatial structure of the lattice, we tackle measurements of neighbors only,
e.g. terms such as $\langle\gamma_{i}\gamma_{j}\rangle$ where $\gamma_{i}$,
$\gamma_{j}$ belong to neighbor sites. Even though this is not sufficient to
fully obtain a $k$-RDM, there is a great interest in efficiently obtaining
such expectation values, which are relevant to survey quantities that hinge on
groups of close neighbors, like coupling energies. Naturally, by focusing on a
smaller subset of modes, the scaling of the number of measurement settings
drastically reduces.

###  II.3 On the total number of repetitions

The results summarized above concern the count $N$ of measurement settings,
e.g. the count of on how many different Pauli bases one must measure. It is
also relevant to consider the number of repetitions $M$ of each setting needed
for accurate statistics. The product $NM$ is the total number of measurement
rounds, or equivalently, the total number of state copies needed. Using the
Chernoff-Hoefding bound, the reasoning from [27] can show that
$M\sim\frac{2}{\varepsilon^{2}}[k\log n+\log(1/\delta)]$ repetitions suffice
to measure a full set of $k$-RDMs such that, with probability at least
$1-\delta$, the error in every local measurement is at most $\varepsilon$.
Adapting that calculation to our localized $k$-RDMs, we see that the number of
repetitions $M$ can be set at $M\sim\frac{2}{\varepsilon^{2}}[k+\log
n+\log(1/\delta)]$ (see Appendix A).

In light of this distinction, the results in [19, Theorem 3] and in [20] can
be properly appreciated. Applied to a $k$-RDM, the former states that the
total number of rounds $NM$ scales as
$NM\sim\frac{2}{\varepsilon^{2}}3^{k}\log(3^{k}\binom{n}{k})\sim\frac{2}{\varepsilon^{2}}\mathcal{O}(3^{k})\log
n$, lower than the literature results mentioned above, for which
$NM\sim\log^{2}n$ or higher. The method of “classical shadows” of the latter
can also be applied to $k$-RDMs and similarly yields the scaling of
$NM=\mathcal{O}(\frac{1}{\varepsilon^{2}}3^{k}\log n)$.

The need for $M$ repetitions is an extra reason to determine the paradigm of
projective local measurements. For the sake of the argument, consider that
three measurement settings on a qubit, one on each Pauli basis, are described
as a single POVM with probability $\frac{1}{3}$ for each basis. Allowing such
POVM would reduce the number of measurement settings $N$ on a qubit to a
third, but would evidently triple the amount of repetitions $M$, leaving the
product $NM$ unchanged. Forbidding nonprojective measurements prevents such
artificial reduction of $N$. Entangling measurements and SIC-POVMs reduce $N$
in a way that is not as artificial [29, 46], but irrespective of how $M$ is
affected, these are ruled out for their much more complex practical
implementation. For the remainder of this paper, we will discuss the number
$N$ of measurement settings, with the number of repetitions $M$ implicitly
assumed.

##  III Local Overlapping Tomography

As mentioned, we are interested in many-particle systems with a natural notion
of locality or distance. The standard way of encapsulating this notion is
through lattices, where each particle is located in a node of the lattice.
Therefore, the general question of efficient local overlapping tomography is
to, out of an $n$-site lattice, obtain the RDMs of all sets of $k$ neighboring
sites arranged in a given shape ($k$-sets). As shown in previous results, full
$k$-RDMs require a number $N$ of measurement settings that grows with system
size $n$. However, when the target are the $k$-RDMs of neighboring lattice
sites, there are efficient parallelization schemes that significantly reduce
$N$ to the point of removing the $n$-dependence altogether. Let us see how
this can happen.

The amount of $k$-sets is $\mathcal{O}(n)$, as can be seen as follows.
Firstly, it cannot be greater than $n$, since each $k$-set is defined by its
first site (“first” according to any ordering, e.g., top to bottom, left to
right, etc); with $n$ sites total, the amount of $k$-sets can be no more than
$n$. Secondly, there are cases where not every site is the “first site” of a
$k$-set. This is better seen with an example on the honeycomb lattice (Fig.1)
where the $k$-sets are its hexagons ($k=6$): taking the topmost site of each
hexagon as its “first”, we see that half the sites are not the topmost site of
any hexagon, and indeed there are only $n/2$ hexagons in this case. However,
because of the repeating nature inherent of a lattice, this may only occur
with a given fraction of all sites ($1/2$ in the example), and the
$\mathcal{O}(n)$ amount of $k$-sets holds in general.

A brute-force approach would be to measure these sets independently. Complete
information on one $k$-set requires $\mathcal{O}(3^{k})$ measurement settings,
to reach all $\mathcal{O}(n)$ $k$-sets, $N=\mathcal{O}(n3^{k})$ settings are
needed. An appropriate tiling, however, reduces $N$. Any lattice presents an
intrinsic tiling of its sites into minimal cells, but can also be tiled into
larger cells each composed of several minimal cells. As such, it is always
possible to embed each $k$-set shape in a cell. A suitable form of tiling for
our measurements is precisely one where each $k$-set shape fits in one cell,
see Fig. 2a). All such $k$-sets belonging to different cells can be measured
simultaneously, consuming $\mathcal{O}(3^{k})$ measurement settings. To cover
the $k$-sets that overlap with the ones in the first measurement settings, one
must displace the cells in the symmetry directions of the lattice, as in Fig.
2b). This procedure will require at most $\mathcal{O}(k^{3})$ displacements
[see Figs. 2c) and 2d); for surface lattices, at most $\mathcal{O}(k^{2})$;
for linear ones, at most $\mathcal{O}(k)$], hence a total of
$N=\mathcal{O}(k^{3}3^{k})$ measurement settings. In conclusion, an
appropriate tiling of the $n$-lattice allows to reduce the number of
measurement settings to obtain its $k$-sets from $N=\mathcal{O}(n3^{k})$ to at
most $N=\mathcal{O}(3^{k})$, independent of $n$. If a fixed number of
rotations of the $k$-set is targeted, this simply incurs in constant-prefactor
increase in the number of $k$-sets and of necessary cells (e.g. if rotations
of the shape in Fig. 2a in 0º, 90º, 180º, and 270º are targeted, this
prefactor is $4$).

Figure 1: In an $n$-site honeycomb lattice there are $n/2$ hexagons, which can
be identified by their topmost site (red circles). Half of all lattice sites
are not the topmost site of any hexagon (blue squares). Figure 2: a) Tiling of
an arbitrary shape by embedding in (non-minimal) lattice cells. The cells
(dashed lines) are chosen as the smallest that contain the desired $k$-set
(here $k=13$). b) Example of displacement needed to cover $k$-sets overlapping
with the ones on the original tiling. Here a displacement of 2 down and 4 to
the right is shown; in total $8\times 3=24$ displacements are needed
[including the original tiling in a)]. At most $k$ displacements in each
direction are needed, so at most $k^{2}$ total for a planar lattice like
above, $k^{3}$ for a three-dimensional lattice. c) Example of a $k$-set shape
(here, $k=10$) requiring $\mathcal{O}(k^{3}/3)$ displacements in the cubic
lattice. d) Illustration of one cell for the scenario of c). e) Tiling of an
$L$-shaped $k$-set with $k=9$ by embedding in $\frac{k+1}{2}$-wide square
cells. In red, the sets that fit the drawn cells; in gray some of the
displaced $L$-shapes, $\frac{k+1}{2}$ down and $\frac{k+1}{2}$ to the right, a
total of $(k+1)^{2}/4=25$ displacements (including the original). f) More
efficient tiling of the same $L$-shapes. In this case only $k=9$ displacements
are necessary in total: a $(k\\!+\\!1)$-th displacement takes the pattern back
to itself, as seen best by the black contoured shape on the left being
displaced exactly onto the one on the right after $k+1$ steps.

Given that the number of repetitions $M$ in our case scales as
$M\sim\frac{2}{\varepsilon^{2}}[k+\log n+\log(1/\delta)]$ (Section II.3), a
comparison with the results in [19, Theorem 3] and in [20, Theorem 1] is in
order. The theorem in [19] offers an algorithm to estimate the expectation
values of $m$ strings of $k$ Pauli operators with
$N\sim\frac{1}{\varepsilon^{2}}3^{k}\log m$ independent, randomly selected
measurement settings, and without repetitions for statistics (effectively
$M=1$). The scheme in [20], when employed with randomized measurements on the
Pauli bases for these expectation values, similarly yield
$N=\mathcal{O}(\frac{1}{\varepsilon^{2}}3^{k}\log n)$ with $M=1$. Applying
these results to a $k$-RDM on $n$ qubits, one has $m=3^{k}\binom{n}{k}$, hence
$NM\sim\mathcal{O}(\frac{1}{\varepsilon^{2}}3^{k}\log n)$.

Theorem 2 of [20] applied to this case shows that the product $NM$ is in fact
lower-bounded by the same expression, which is also reached in the present
work. There is, however, has an important difference: we have a lower number
of different measurement settings $N\sim\mathcal{O}(3^{k})$ (system-size
independent), and a higher number $M\sim\log n$ of repetitions of those for
statistics. For experimental considerations, it is clear that repeating the
same measurement setting several times is much more amenable than making
different ones.

Furthermore, although we can reach this lower bound with the generic embedding
presented above, notice that it is not necessarily optimal. Consider the
L-shaped $k$-set in Fig. 2e), with $(k+1)/2$-long arms. The tiling by
embedding described above would require $(k+1)/2$ displacements to the left
and $(k+1)/2$ down, totaling $(k+1)^{2}/4=\mathcal{O}(k^{2})$ displacements of
the original tiling. A more efficient tiling is shown in Fig. 2f), and
requires only $k$ displacements total.

This tiling procedure demonstrates that the number of measurement settings in
local overlapping tomography is independent of the system size. Note that in a
typical experimental implementation each setting requires $\mathcal{O}(n)$
detectors, which is still size dependent. Nonetheless, such a dependence of
the number of detectors with the system size also holds for the other
available procedures in the literature, and an amount of settings which is
system-size independent represents a valuable advantage.

The tiling above is, however, typically sub-optimal for a given lattice
because of its generality. So we now turn to specific scenarios that are
usually encountered in existing setups, and show more efficient measurement
strategies for each of them.

###  III.1 Qubits in a lattice

The simplest case to consider is that of the $2$-RDM for first neighbors. We
need that, whenever $i,j$ are neighbors,
$\langle\sigma_{a}^{(i)}\otimes\sigma_{b}^{(j)}\rangle$ cover all combinations
of $(a,b)$. This reduces to the problem of vertex coloring of a graph:
neighboring sites must be assigned different labels (colors), and from the
number $c$ of colors one obtains the number of measurement settings $N=3^{c}$
(since each color has to cycle through $x,y,z$). Graph theory shows [47, 48]
that for a graph of degree $\Delta$ (i.e. where a site has at most $\Delta$
first neighbors), it is always possible to color it with $\Delta+1$ colors.
This gives an upper bound of $N\leqslant 3^{\Delta+1}$. Importantly, this
graph-theory bound on $c$ can be far from tight [47, eq. (1.2)], hence the
same holds for the bound on $N$; better bounds can be written in terms of
minimum degrees [48, Theorem 2.2].

Let us now focus on relevant geometries, in which we can obtain bounds that
are tighter and hold beyond $k=2$.

####  III.1.1 Straight qubit lattices: strings, squares, cubes

Figure 3: Labelings for string lattice [a)] and ring lattice [a) and b)] for
$n=9$, $k=4$. For clarity, the numerical labels in the text have been
converted to letters with the standard mapping $0\to A$, $1\to B$, $\cdots$,
and also color-coded.

We begin by the simplest lattice, a string of $n$ qubits, whose results will
serve as a building block for the others. The $k$-RDM of neighboring sites on
a string are recovered from expectation values of the form

$\langle\sigma_{a_{i}}^{(i)}\otimes\sigma_{a_{i+1}}^{(i+1)}\otimes\cdots\otimes\sigma_{a_{i+k-1}}^{(i+k-1)}\rangle\
.$ (2)

The measurement scheme is defined using a single labeling $\boldsymbol{a}$
that cycles through a $k$-alphabet, or

$a_{i}=i\bmod k$ (3)

[see Fig. 3a)]. It assigns measurements in the sense that each label runs
independently through $x,y,z$, totaling $N=3^{k}$ measurement settings. It is
straightforward to see that in this scheme any $k$ consecutive qubits have $k$
different labels, and hence are measured in all combinations of the bases.

It is also clear that, for this or any other $k$-RDM, $k$ is the minimum
amount of labels needed: if $k-1$ or less labels were used, any group of $k$
qubits would have coinciding labels, and the qubits assigned the same label
would always be measured in the same basis, amounting to an incomplete
measurement. Importantly, $N=3^{k}$ does not scale with the system size $n$.

Another one-dimensional lattice is the ring. A ring here is simply a string
whose endpoints are considered first neighbors. A ring of qubits requires
extra measurement settings, compared to the open string, when $n$ is not
divisible by $k$. A single extra labeling $\boldsymbol{b}$ is needed (assuming
$n\geqslant 2k-2$); it labels the first $k-1$ qubits as before, the last $k-1$
qubits with the last $k-1$ letters of the $k$-alphabet, and the remaining
qubits are not labeled (i.e. not measured). Formally,

$b_{i}=\begin{cases}a_{i}\ ,&\ \mathrm{for}\ i\in[k-1]\\\ a_{i-n}\ ,&\
\mathrm{for}\ i\in\mathrm{last}_{k-1}[n]\\\ \mbox{no label}&\
\mbox{otherwise}\ ,\end{cases}$ (4)

where $\mathrm{last}_{k-1}[n]:=[n]\backslash[n-(k-1)]$ and $a_{i}$ obeys Eq.
(3). This labeling is exemplified in Fig. 3b). Notice that it correctly covers
any set of $k$ neighbors across the edge. With two labelings, the number of
measurement settings rises to $N=2\times 3^{k}$.

Figure 4: Labeling to measure star RDM on the planar square lattice, given by
Eq. (5). For clarity, the numerical labels in the text have been converted to
letters with the standard mapping $0\to A$, $1\to B$, $\cdots$, and color-
coded.

We now move on to two-dimensional geometries, starting by the square lattice.
The first RDM tackled here is the star, composed of one qubit and all its
neighbors, a $k=5$-RDM in this geometry. A single labeling $\boldsymbol{a}$
covers all possibilities with the minimum of $k=5$ labels. It labels rows
cycling through a 5-alphabet like the string above, but adding an offset of
$2$ for each row (see Fig. 4). With lattice sites now denoted by the pair
$(i_{1},i_{2})$, its elements read

$a_{i_{1},i_{2}}=(i_{1}+2i_{2})\bmod 5\ .$ (5)

Since $5$ labels are used, $N=3^{5}$ measurement settings are needed.

Figure 5: a) Labeling $\boldsymbol{a}$ for $(\ell_{1},\ell_{2})$-plaquettes in
the planar square qubit lattice, from Eq. (6), with
$(\ell_{1},\ell_{2})=(3,2)$. b) Additional labelings needed for the cylinder
and torus geometries, with $n_{1}=8$, $n_{2}=5$. The cylinder geometry
requires $\boldsymbol{b}$ from Eq. (7) (in parentheses); the torus geometry
requires $\boldsymbol{b}$ and also $\boldsymbol{c}$ from Eq. (8) [in square
brackets]. Plaquettes crossing each edge are illustrated. For clarity, the
numerical labels in the text have been converted to letters with the standard
mapping $0\to A$, $1\to B$, $\cdots$, and color-coded.

An $(\ell_{1},\ell_{2})$-plaquette is defined as an
$(\ell_{1}\times\ell_{2})$-qubit rectangle aligned to the lattice (see Fig.
5). A measurement scheme for the $k$-RDMs of all
$(\ell_{1},\ell_{2})$-plaquettes (with $k=\ell_{1}\ell_{2}$) can be made by
composing the previous string scheme. The first row is labeled with an
$\ell_{1}$-alphabet as in the string, the second row is labeled with a
different $\ell_{1}$-alphabet, and the same goes for the first $\ell_{2}$
rows, each with their different $\ell_{1}$-alphabets. Row labelings repeat
cyclically from the $(\ell_{2}+1)$-th row onwards, in a total of
$\ell_{1}\ell_{2}$ labels (Fig. 5). Formally, the labeling reads

$a_{i_{1},i_{2}}=(i_{1}\bmod\ell_{1})+\ell_{1}(i_{2}\bmod\ell_{2})\ ,$ (6)

and appropriately covers all $(\ell_{1},\ell_{2})$-plaquettes with the minimal
number $k=\ell_{1}\ell_{2}$ of labels, hence $N=3^{k}=3^{\ell_{1}\ell_{2}}$.

We call cylinder a square lattice where sites on the last column are first
neighbors to same-row sites on the first column. Let the total lattice have
dimension $n_{1}\times n_{2}$, where $n=n_{1}n_{2}$. To measure all
$(\ell_{1},\ell_{2})$-plaquettes in the cylinder when $n_{2}\bmod\ell_{2}\neq
0$, it takes an additional labeling as in the ring case. The additional
labeling is $\boldsymbol{b}$, with elements

$b_{i_{1},i_{2}}=\begin{cases}a_{i_{1},i_{2}}\ ,&\mathrm{for}\
i_{1}\in[\ell_{1}-1]\\\ a_{i_{1}-n_{1},i_{2}}\ ,&\mathrm{for}\
i_{1}\in\mathrm{last}_{\ell_{1}-1}[n_{1}]\\\ \mbox{no label}&\mbox{otherwise}\
,\end{cases}$ (7)

with $a_{i_{1},i_{2}}$ from Eq. (6). It labels only the leftmost and rightmost
$(\ell_{1}-1)$ columns and, analogously to the ring, covers all
$(\ell_{1},\ell_{2})$-plaquettes across the vertical edges. With two
labelings, the number of measurement settings is $N=2\times 3^{k}$.

When the first and last rows of a cylinder are also taken as first neighbors
(column-wise), we obtain a torus. If both $n_{1}\bmod\ell_{1}\neq 0$ and
$n_{2}\bmod\ell_{2}\neq 0$, a third labeling $\boldsymbol{c}$ is needed,
analogous to Eq. (7), but switching horizontal and vertical directions. With
$a_{i_{1},i_{2}}$ from Eq. (6), $\boldsymbol{c}$ is given by

$c_{i_{1},i_{2}}=\begin{cases}a_{i_{1},i_{2}}\ ,&\mathrm{for}\
i_{2}\in[\ell_{2}-1]\\\ a_{i_{1},i_{2}-n_{2}}\ ,&\mathrm{for}\
i_{2}\in\mathrm{last}_{\ell_{2}-1}[n_{2}]\\\ \mbox{no label}&\mbox{otherwise}\
,\end{cases}$ (8)

and labels the topmost and bottommost $(\ell_{2}-1)$ rows. With three
labelings, the number of measurement settings is $N=3\times 3^{k}=3^{k+1}$.
Notably, the torus topology makes a third labeling necessary in general
(Appendix B).

In fact, any labeling $\boldsymbol{a}$ of the square lattice can be patched
for the cylinder and torus geometries with the strategy above, as long as the
maximal dimensions of the desired RDM are $\ell_{1}\times\ell_{2}$. Applying
this to the star-RDM labeling — i.e. substituting Eq. (5) in Eqs. (7),(8) with
$\ell_{1}=\ell_{2}=3$ —, one finds

$\displaystyle b_{i_{1},i_{2}}=$
$\displaystyle\begin{cases}(i_{1}+2i_{2})\bmod 5\ ,&\mathrm{for}\
i_{1}\in[2]\\\ (i_{1}-n_{1}+2i_{2})\bmod 5\ ,&\mathrm{for}\
i_{1}\in\mathrm{last}_{2}[n_{1}]\\\ \mbox{no
label}&\mbox{otherwise}\end{cases}$ (9) $\displaystyle c_{i_{1},i_{2}}=$
$\displaystyle\begin{cases}(i_{1}+2i_{2})\bmod 5\ ,&\mathrm{for}\
i_{2}\in[2]\\\ (i_{1}+2i_{2}-2n_{2})\bmod 5\ ,&\mathrm{for}\
i_{2}\in\mathrm{last}_{2}[n_{2}]\\\ \mbox{no
label}&\mbox{otherwise}\end{cases}$ (10)

and the number of measurement settings is $N=2\times 3^{5}$ for the cylinder
($\boldsymbol{a}$ and $\boldsymbol{b}$) and $N=3\times 3^{5}=3^{6}$ for the
torus geometry ($\boldsymbol{a}$, $\boldsymbol{b}$ and $\boldsymbol{c}$).

We now move on to a three-dimensional, cubic lattice. We begin by the star
RDM, which includes a qubit and all its (six) first neighbors. This $k=7$-RDM
can be realized with one labeling $\boldsymbol{a}$ composed of $k=7$ labels;
it labels each plane as in the 2D star configuration (but with a 7-alphabet),
with an offset of $3$ between successive planes. With each site labeled by
$(i_{1},i_{2},i_{3})$, $\boldsymbol{a}$ reads

$a_{i_{1},i_{2},i_{3}}=(i_{1}+2i_{2}+3i_{3})\bmod 7$ (11)

and implies $N=3^{7}$ measurement settings.

Geometry | Labelings |  $N$ (No. of measmts) | Eqs.
---|---|---|---
String | 1 | $3^{k}$ | (3)
Ring (1D) | 2 | $2\times 3^{k}$ | (3),(4)
Star (plane) | 1 | $3^{5}$ | (5)
$(\ell_{1},\ell_{2})$-plaquette | 1 | $3^{k}=3^{\ell_{1}\ell_{2}}$ | (6)
Cylinder |  $2\times$(planar) |  $2\times$(planar) | (6),(7)
Torus |  $3\times$(planar) |  $3\times$(planar) | (6),(7),(8)
Star (cubic) | 1 | $3^{7}$ | (11)
$(\ell_{1},\ell_{2},\ell_{3})$-block | 1 | $3^{k}=3^{\ell_{1}\ell_{2}\ell_{3}}$ | (12)
Thick ring (3D) |  $2\times$(cubic) |  $2\times$(cubic) | (12),(13)
Table 1: Summary of the number of labelings and measurement settings for
$k$-RDMs on the geometries considered in Subsection III.1.1. For comparison,
previous methods in the literature require at least $N\sim
e^{\mathcal{O}(k)}\log n$ different measurement settings. The values of the
cyclic geometries (ring, cylinder, torus, thick ring) are upper bounds,
saturated when the dimensions of the lattice are not divisible by those of the
RDM.

An $(\ell_{1},\ell_{2},\ell_{3})$-block is an
$(\ell_{1},\ell_{2},\ell_{3})$-qubit parallelepiped aligned to the lattice.
Analogously to the plaquette, all such blocks can be labeled by

$a_{i_{1},i_{2},i_{3}}=(i_{1}\bmod\ell_{1})+\ell_{1}(i_{2}\bmod\ell_{2})+\ell_{1}\ell_{2}(i_{3}\bmod\ell_{3})\
,$ (12)

with $N=3^{k}=3^{\ell_{1}\ell_{2}\ell_{3}}$ measurement settings.

If the rightmost face of the cubic lattice is considered first neighbor of the
leftmost face, we then have a “thick” ring. With the lattice having dimensions
$n_{1}\times n_{2}\times n_{3}$, and taking the $i_{1}=0$ face as neighbor to
the $i_{1}=(n_{1}-1)$ face, this thick ring has a cross section of dimension
$n_{2}\times n_{3}$ qubits. As in the original one-dimensional ring, this
geometry requires one additional labeling, given by

$b_{i_{1},i_{2}}=\begin{cases}a_{i_{1},i_{2},i_{3}}\ ,&\mathrm{for}\
i_{1}\in[\ell_{1}-1]\\\ a_{i_{1}-n_{1},i_{2},i_{3}}\ ,&\mathrm{for}\
i_{1}\in\mathrm{last}_{\ell_{1}-1}[n_{1}]\\\ \mbox{no label}&\mbox{otherwise}\
,\end{cases}$ (13)

totaling $2\times 3^{\ell_{1}\ell_{2}\ell_{3}}$ measurement settings. As was
done for the cylinder and torus in the two-dimensional lattice, one can
consider the other faces of the three-dimensional lattice to be first
neighbors, and the additional labelings follow analogously.

We summarize the results of this Subsection in Table 1.

####  III.1.2 Further qubit lattices: triangle and honeycomb

Figure 6: Labeling of the triangle lattice. a) Numbering scheme used in Eqs.
(14), (15). b) Three-label scheme for the (triangular) plaquette. c) Seven-
label scheme for the star RDM (qubit and its neighbors).

In this Subsection we treat different geometries, namely the triangle and the
honeycomb lattices.

For the triangle geometry, we begin with a labeling scheme that covers
triangle RDMs. With three labels, it is also the minimal scheme for 2-RDMs.
With the numbering defined in Fig. 6a), this labeling reads

$a_{i_{1},i_{2}}=(i_{2}\bmod 2+i_{1})\bmod 3$ (14)

and is illustrated in Fig. 6b).

Additionally, we present a scheme for the star RDM on this geometry, composed
of a qubit and all its six neighbors (hence a $7$-RDM):

$a_{i_{1},i_{2}}=\begin{cases}(i_{1}-i_{2})\bmod 7\ ,&\mbox{for $i_{2}$
even}\\\ (i_{1}-i_{2}+3)\bmod 7\ ,&\mbox{for $i_{2}$ odd}\end{cases}$ (15)

which is illustrated in Fig. 6c).

Figure 7: Labeling of the honeycomb lattice for different RDMs. a) Explicit
illustration of the numbering used in Eqs. (16), (17), (18). b) Two-label
scheme for first-neighbor $2$-RDMs, Eq. (16). c) Four-label scheme, suitable
for $3$-RDMs and any $4$-RDM where the four qubits are contiguous, but not in
the same hexagon, given by Eq. (17). d) Six-label scheme, suitable for $4$-,
$5$-, $6$-RDMs where all qubits of the RDM belong to same hexagon, given by
Eq. (18). For clarity, the numerical labels in the text have been converted to
letters with the standard mapping $0\to A$, $1\to B$, $\cdots$, and color-
coded.

We now deal with qubits on a honeycomb lattice. A first-neighbor $2$-RDM can
be achieved with two labels, simply assigning neighbors different labels. With
the numbering exemplified in Fig. 7a), this labeling reads

$a_{i_{1},i_{2}}=i_{1}+i_{2}\bmod 2\ ,$ (16)

and is shown in Fig. 7b).

Now we show a labeling that is useful for different sets of neighbors. It
contains 4 different labels, as seen in Fig. 7c), and covers any $3$-RDM, as
well as any $4$-RDM where the four qubits do not all belong to same hexagon.
This includes the star configuration (a qubit and its three neighbors), as
well as 4 qubits along the rows, among others:

$a_{i_{1},i_{2}}=\begin{cases}(-1)^{i_{2}}\ i_{1}&\mbox{for $i_{2}\bmod
4=0,3$}\ ,\\\ (-1)^{i_{2}}\ i_{1}+2&\mbox{for $i_{2}\bmod 4=1,2$}\
,\end{cases}$ (17)

equivalently,
$a_{i_{1},i_{2}}=\left((-1)^{i_{2}}i_{1}\\!+2\\!\left\lfloor\\!\frac{(i_{2}+1)\bmod
4}{2}\\!\right\rfloor\right)\bmod 4$. It is perhaps clearer to describe this
labeling with the following algorithm: for the first row, assign labels
sequentially ($a_{i_{1},0}=i_{1}\bmod 4$). For the remaining sites, assign
them the same color as the site diametrically opposite to it in any given
hexagon, as in Fig. 7c).

This is evidently the minimal labeling for the $4$-RDMs, and is also the
minimal for the $3$-RDMs, which cannot be covered with 3 labels only.

Lastly, we present a final labeling for the honeycomb, composed of 6 labels.
It covers hexagon RDMs (containing all qubits in a hexagon), as well as 4-RDMs
and 5-RDMs with all qubits in the same hexagon. It is depicted in Fig.7d) and
is given by

$a_{i_{1},i_{2}}=[3(i_{2}\bmod 2)+i_{1}]\bmod 6\ .$ (18)

Interestingly, this labeling also covers (non-optimally) all previously
mentioned honeycomb RDMs.

No. of qubits | Labels |  $N$ (No. of measmts) | Eq.
---|---|---|---
Triangle
$3$ (plaquette) | $3$ | $3^{3}$ | (14)
$7$ (star RDM) | $7$ | $3^{7}$ | (15)
Honeycomb
$2$ | 2 | $3^{2}$ | (16)
$3$, or $4$ not in same hexagon | 4 | $3^{4}$ | (17)
up to $6$ in single hexagon | $6$ | $3^{6}$ | (18)
Table 2: Summary of the number of labels and measurement settings for neighbor
$k$-RDMs on the sets and geometries considered in Subsection III.1.2. For
comparison, previous methods in the literature require at least $N\sim
e^{\mathcal{O}(k)}\log n$ different measurement settings.

We summarize the results of this Section in Table 2.

###  III.2 Fermions in a lattice

For fermions in a lattice, $k$-RDMs provide information on arbitrarily distant
lattice sites, which is not the purpose of this work. We are interested in
$\langle\gamma_{i_{0}}\gamma_{i_{1}}\cdots\gamma_{i_{2k-1}}\rangle$, where all
$\gamma_{i}$ belong to a subset of lattice sites. We call these expectation
values, then, elements of a _lattice-restricted matrix_ of size $k$, or
$k$-LRM, for short. An entire $k$-LRM will contain such expectation values for
all lattice subsets of a certain class, e.g. all neighboring pairs of lattice
sites. A $k$-LRM contains less information than a $k$-RDM, unless the subset
is taken to be the entire lattice, for which the $k$-LRM coincides with the
$k$-RDM.

Additionally, for fermions one cannot simply rely on the tensor-product
structure of operators acting on different sites to ensure commutativity
(hence joint measurability). As such, measuring a given element no longer
assumes access to individual measurements on each site. Different Majoranas
always anticommute, and they can be compounded to form commuting operators —
e.g. two pairs of Majoranas commute as long as all four Majoranas involved are
different. We call $j$-Majorana string a product $\gamma_{p}\cdots\gamma_{q}$
of $j$ Majoranas, and the overlap of two Majorana strings is the set of
Majoranas the two have in common. In general, two Majorana strings commute
when the length of their overlap has the same parity as the product of their
lengths (see Appendix C).

The 1-LRMs for neighbor fermions on a lattice present a simplified structure:
since two different pairs of Majorana operators can only overlap in a single
$\gamma_{i}$, any overlapping pairs anticommute and are incompatible. The
1-LRM then reduces to the problem of covering all relevant pairs of Majoranas
without using any overlap. Interestingly, the problem reduces to that of edge-
coloring a graph [49, 50]: how to color the edges of a graph such that any two
edges that share a vertex have different colors.

Figure 8: Fermionic 1-LRMs, edge-coloring of a graph and Vizing’s theorem.
Each lattice site (black circle) has $\Delta=2$ neighbors and the graph can be
colored with only $c=2$ colors. The scheme shows the $N=2c+1=5$ measurement
settings needed on the Majorana operators (white losanges). a) Same-site
measurement; b) two measurement settings for the red (dark) edges, the first
for equal-parity $\gamma_{j}$ (solid lines) and the second for opposite-parity
$\gamma_{j}$ (dashed lines); c) two measurement settings for the tan (light)
edges, analogous to b).

To see this, consider that a graph $G$ defines the lattice, with each fermion
site being a vertex and an edge connecting first neighbors. To each site $i$
correspond two Majoranas $\gamma_{2i}$, $\gamma_{2i+1}$. Since the pairs
$\gamma_{2i}\gamma_{2i+1}$ for different values of $i$ all commute, they can
all be measured at once in a first measurement setting [same-site measurement,
see Fig. 8a)]. If an edge connects vertices $i$ and $j$, the pairs composed of
the elements in $\\{\gamma_{2i},\gamma_{2i+1},\gamma_{2j},\gamma_{2j+1}\\}$
must be measured. This requires two measurement settings (besides the same-
site one): first the equal-parity measurement
$\\{\gamma_{2i}\gamma_{2j},\gamma_{2i+1}\gamma_{2j+1}\\}$ [Fig. 8b)], and
second the opposite-parity measurement
$\\{\gamma_{2i}\gamma_{2j+1},\gamma_{2i+1}\gamma_{2j}\\}$ [Fig. 8c)]. To
measure the entire LRM one could, in principle, use two measurement settings
for each edge of $G$, but the total amount of settings would be unnecessarily
high. A more efficient approach is to make as many of those measurements in
parallel as possible. The restrictions to parallelization are that edges
connected to the same vertex cannot be measured at the same step: if $(i,j)$
and $(i,j^{\prime})$ are edges of $G$, their measurements cannot be made in
parallel for they would overlap in $\gamma_{2i}$ or $\gamma_{2i+1}$. This
restriction is precisely described by the edge-coloring of $G$. To each color
correspond two measurement settings, on top of the same-site one. For a total
of $c$ colors, this scheme takes $N=2c+1$ measurement settings (see Fig. 8).

Importantly, Vizing’s theorem [49, 50] bounds the amount of colors needed to
edge-color a given graph: for a graph of degree $\Delta$, the amount of colors
needed is either $c=\Delta$ or $c=\Delta+1$. As such, this scheme makes use
of, at most, $N=2\Delta+3$ measurement settings.

Finally, this scheme can be extended to $1$-LRMs that include next-to-nearest
neighbors. One need only create an auxiliary graph $G^{\prime}$ that has all
vertices and edges of the original graph $G$, plus edges that connect next-to-
nearest neighbors. Edge-coloring of $G^{\prime}$ indicates a suitable
measurement scheme that requires at most $N=2\Delta^{\prime}+3$ measurement
settings, where $\Delta^{\prime}$ is the degree of $G^{\prime}$.

The 2-LRM for pairs of first neighbors presents, surprisingly, an even simpler
structure. For any neighboring pair of lattice sites $(i,j)$, the first-
neighbor 2-LRM has a single element
$\langle\gamma_{2i}\gamma_{2i+1}\gamma_{2j}\gamma_{2j+1}\rangle$. For any
other pair $(i^{\prime},j^{\prime})$ of lattice sites, the overlap is either
of two or zero Majoranas, so all such elements commute. Hence all pertinent
Majorana strings are jointly measurable, i.e. a single measurement setting
$N=1$ can be made to provide the 2-LRM for pairs of first neighbors.

Figure 9: Measurement settings of a three-lattice-site tile of a Fermionic
2-LRM. Illustration of the string lattice [black circles, in a)] and of the
Majorana operators, two per lattice site [white losanges, in b)]. In c), the
five measurement settings for each tile are shown, each obtains three
(compatible) elements of the 2-LRM. In d), tiling for the string lattice with
three displacements total.

Let us now go beyond first neighbors in specific geometries, beginning with
the string lattice.

For the 2-LRM for three contiguous sites in the string lattice, $i$, $i+1$,
$i+2$, we will use a tiling strategy. Each tile will be composed of three
sites [six Majoranas; see Fig. 9a) and b)]. Five measurement settings, with
three LRM elements each, suffice to cover a tile; these are shown in Fig. 9c).
A total of three displacements of the original tiling is needed [see Fig.
9d)], which leads to $N=15$ measurement settings total.

Figure 10: Illustration of the tiling for triangle 2-RLM. For a given letter,
e.g. $A$, each tile comprises the three lattice sites of the triangles
assigned that letter. In each tile, measurement settings as in Fig. 9c), with
all same-letter tiles measured simultaneously. Six tilings, one for each
letter, are needed.

In fact, these measurements remain useful for three-site 2-LRMs of any
geometry. Consider, e.g., the triangular lattice from Fig. 10 and in it the
fermionic 2-LRM for sites arranged in a triangle. The lattice needs to be
tiled into triangles, and for each triangle, the five measurement settings in
Fig. 9 are used (with a simple change of geometry). The tiling must be such
that tiles do not overlap, and a total of six displacements are needed, as
shown if Fig. 10. This leads to $N=30$ measurement settings total for this
2-RLM.

##  IV Concluding remarks

The full determination of the quantum state of a many-particle system is
practically out of reach when increasing the system size. However, it is
possible to access to partial, physically relevant information about this
system with a much less demanding effort. We have studied local overlapping
tomography of qubits and fermions in a lattice. We have specifically focused
on $k$-RDMs (and $k$-LRMs) that are localized in neighboring sites of the
lattice, which are often the subset that draws more interest in theoretical
and practical terms. Resorting only to projective, product measurements, we
have shown that optimal measurement complexity can be directly tied to graph-
coloring for the lowest values of $k$; and we have also studied optimal
measurements tailored to several relevant geometries. An important result is
that, unlike for the case of full RDMs or even more efficient randomized
measurement schemes, the amount of measurement settings to obtain these local
matrices no longer depends on system size $n$. This has been seen in the
studied geometries, in connection to graph-coloring, and also in the form of a
general tiling argument.

Local QOT is a promising candidate for measurements of many-body systems whose
correlations are restricted to few bodies, but also as a probe to characterize
$k$-local generators of correlations. One should notice that all relevant
quantum-computing platforms operate based on 1- and 2-qubit gates acting on
neighboring particles, and hence are a potential application of local QOT
methods. This opens the path towards turning this form of local overlapping
tomography into a viable candidate for measurements in practical scenarios.

###### Acknowledgements.

We thank X. Bonet-Monroig, A. Zhao, G. García-Pérez, S. Maniscalco and S.
Flammia for helpful discussions and comments. We acknowledge support from the
Government of Spain (FIS2020-TRANQI, EU NextGen Funds, Misiones CUCO and
Severo Ochoa CEX2019-000910-S), Fundació Cellex, Fundació Mir-Puig,
Generalitat de Catalunya (CERCA and QuantumCAT), the ERC AdG CERQUTE, the
European Union Horizon 2020 research and innovation program under the Marie
Sklodowska-Curie grant agreement No. 754558 (PREBIST), and the AXA Chair in
Quantum Information Science.

## References

  * Arute  _et al._ [2019] F. Arute _et al._ , Quantum supremacy using a programmable superconducting processor, Nature 574, 505 (2019).
  * Kelly  _et al._ [2019] J. Kelly, Z. Chen, B. Chiaro, B. Foxen, and J. M. Martinis, Operating and characterizing a 72 superconducting qubit processor “Bristlecone”, in  _APS Meeting Abstracts_ (2019).
  * Arute  _et al._ [2020] F. Arute _et al._ , Hartree-Fock on a superconducting qubit quantum computer, Science 369, 1084 (2020), arXiv:2004.04174 .
  * Wu  _et al._ [2021] Y. Wu, W.-S. Bao, S. Cao, F. Chen, M.-C. Chen, X. Chen, T.-H. Chung, H. Deng, Y. Du, D. Fan, M. Gong, C. Guo, C. Guo, S. Guo, L. Han, L. Hong, H.-L. Huang, Y.-H. Huo, L. Li, N. Li, S. Li, Y. Li, F. Liang, C. Lin, J. Lin, H. Qian, D. Qiao, H. Rong, H. Su, L. Sun, L. Wang, S. Wang, D. Wu, Y. Xu, K. Yan, W. Yang, Y. Yang, Y. Ye, J. Yin, C. Ying, J. Yu, C. Zha, C. Zhang, H. Zhang, K. Zhang, Y. Zhang, H. Zhao, Y. Zhao, L. Zhou, Q. Zhu, C.-Y. Lu, C.-Z. Peng, X. Zhu, and J.-W. Pan, Strong quantum computational advantage using a superconducting quantum processor, Physical Review Letters 127, 180501 (2021), arXiv:2106.14734 .
  * Cho [2020] A. Cho, IBM promises 1000-qubit quantum computer—a milestone—by 2023, Science (New York, N.Y.) 10.1126/science.abe8122 (2020).
  * Zhong  _et al._ [2020] H.-S. Zhong _et al._ , Quantum computational advantage using photons, Science 370, 1460 (2020), arXiv:2012.01625 .
  * Zhong  _et al._ [2021] H.-S. Zhong, Y.-H. Deng, J. Qin, H. Wang, M.-C. Chen, L.-C. Peng, Y.-H. Luo, D. Wu, S.-Q. Gong, H. Su, Y. Hu, P. Hu, X.-Y. Yang, W.-J. Zhang, H. Li, Y. Li, X. Jiang, L. Gan, G. Yang, L. You, Z. Wang, L. Li, N.-L. Liu, J. J. Renema, C.-Y. Lu, and J.-W. Pan, Phase-programmable gaussian boson sampling using stimulated squeezed light, Physical Review Letters 127, 180502 (2021), arXiv:2106.15534 .
  * Britton  _et al._ [2012] J. W. Britton, B. C. Sawyer, A. C. Keith, C.-C. J. Wang, J. K. Freericks, H. Uys, M. J. Biercuk, and J. J. Bollinger, Engineered two-dimensional Ising interactions in a trapped-ion quantum simulator with hundreds of spins, Nature 484, 489 (2012).
  * McGeoch and Farré [2021] C. McGeoch and P. Farré,  _The Advantage System: Performance Update_ , Tech. Rep. (D-Wave Systems, Inc., 2021).
  * Song  _et al._ [2017] C. Song, K. Xu, W. Liu, C.-p. Yang, S.-B. Zheng, H. Deng, Q. Xie, K. Huang, Q. Guo, L. Zhang, P. Zhang, D. Xu, D. Zheng, X. Zhu, H. Wang, Y.-A. Chen, C.-Y. Lu, S. Han, and J.-W. Pan, 10-Qubit entanglement and parallel logic operations with a superconducting circuit, Physical Review Letters 119, 180511 (2017), arXiv:1703.10302 .
  * Cramer  _et al._ [2010] M. Cramer, M. B. Plenio, S. T. Flammia, R. Somma, D. Gross, S. D. Bartlett, O. Landon-Cardinal, D. Poulin, and Y.-K. Liu, Efficient quantum state tomography, Nature Communications 1, 149 (2010), arXiv:1101.4366 .
  * Lanyon  _et al._ [2017] B. P. Lanyon, C. Maier, M. Holzäpfel, T. Baumgratz, C. Hempel, P. Jurcevic, I. Dhand, A. S. Buyskikh, A. J. Daley, M. Cramer, M. B. Plenio, R. Blatt, and C. F. Roos, Efficient tomography of a quantum many-body system, Nature Physics 13, 1158 (2017), arXiv:1612.08000 .
  * Torlai  _et al._ [2018] G. Torlai, G. Mazzola, J. Carrasquilla, M. Troyer, R. Melko, and G. Carleo, Neural-network quantum state tomography, Nature Physics 14, 447 (2018).
  * Carrasquilla  _et al._ [2019] J. Carrasquilla, G. Torlai, R. G. Melko, and L. Aolita, Reconstructing quantum states with generative models, Nature Machine Intelligence 1, 155 (2019), arXiv:1810.10584 .
  * Smart and Mazziotti [2021] S. E. Smart and D. A. Mazziotti, Lowering tomography costs in quantum simulation with a symmetry projected operator basis, Physical Review A 103, 012420 (2021), arXiv:2008.06027 .
  * Aaronson [2018] S. Aaronson, Shadow tomography of quantum states, in  _Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing_ (ACM, New York, NY, USA, 2018) pp. 325–338, arXiv:1711.01053 .
  * Brandão  _et al._ [2019] F. G. S. L. Brandão, A. Kalev, T. Li, C. Y.-Y. Lin, K. M. Svore, and X. Wu, Quantum SDP Solvers: Large Speed-ups, Optimality, and Applications to Quantum Learning (2019), arXiv:1710.02581 .
  * Chen  _et al._ [2021] S. Chen, J. Cotler, H.-Y. Huang, and J. Li, Exponential separations between learning with and without quantum memory (2021), arXiv:2111.05881 .
  * Evans  _et al._ [2019] T. J. Evans, R. Harper, and S. T. Flammia, Scalable bayesian hamiltonian learning (2019), arXiv:1912.07636 .
  * Huang  _et al._ [2020] H.-Y. Y. Huang, R. Kueng, and J. Preskill, Predicting many properties of a quantum system from very few measurements, Nature Physics 16, 1050 (2020), arXiv:2002.08953 .
  * Tóth  _et al._ [2007] G. Tóth, C. Knapp, O. Gühne, and H. J. Briegel, Optimal spin squeezing inequalities detect bound entanglement in spin models, Physical Review Letters 99, 250405 (2007), arXiv:quant-ph/0702219 .
  * Tóth  _et al._ [2009] G. Tóth, C. Knapp, O. Gühne, and H. J. Briegel, Spin squeezing and entanglement, Physical Review A 79, 042334 (2009), arXiv:0806.1048 .
  * Tura  _et al._ [2014] J. Tura, R. Augusiak, A. B. Sainz, T. Vértesi, M. Lewenstein, and A. Acín, Detecting nonlocality in many-body quantum states, Science (New York, N.Y.) 344, 1256 (2014), arXiv:1306.6860 .
  * Yu [2019] N. Yu, Quantum closeness testing: A streaming algorithm and applications (2019), arXiv:1904.03218 .
  * Bonet-Monroig  _et al._ [2020] X. Bonet-Monroig, R. Babbush, and T. E. O’Brien, Nearly optimal measurement scheduling for partial tomography of quantum states, Physical Review X 10, 031064 (2020), arXiv:1908.05628 .
  * García-Pérez  _et al._ [2020] G. García-Pérez, M. A. C. Rossi, B. Sokolov, E.-M. Borrelli, and S. Maniscalco, Pairwise tomography networks for many-body quantum systems, Physical Review Research 2, 023393 (2020), arXiv:1909.12814 .
  * Cotler and Wilczek [2020] J. Cotler and F. Wilczek, Quantum overlapping tomography, Physical Review Letters 124, 100401 (2020), arXiv:1908.02754 .
  * Tilly  _et al._ [2021] J. Tilly, P. V. Sriluckshmy, A. Patel, E. Fontana, I. Rungger, E. Grant, R. Anderson, J. Tennyson, and G. H. Booth, Reduced density matrix sampling: Self-consistent embedding and multiscale electronic structure on current generation quantum computers, Physical Review Research 3, 033230 (2021), arXiv:2104.05531 .
  * Jiang  _et al._ [2020] Z. Jiang, A. Kalev, W. Mruczkiewicz, and H. Neven, Optimal fermion-to-qubit mapping via ternary trees with applications to reduced quantum states learning, Quantum 4, 276 (2020), arXiv:1910.10746 .
  * Zhao  _et al._ [2021] A. Zhao, N. C. Rubin, and A. Miyake, Fermionic partial tomography via classical shadows, Physical Review Letters 127, 110504 (2021), arXiv:2010.16094 .
  * Durt  _et al._ [2008] T. Durt, C. Kurtsiefer, A. Lamas-Linares, and A. Ling, Wigner tomography of two-qubit states and quantum cryptography, Physical Review A 78, 042338 (2008), arXiv:0806.0272 .
  * Medendorp  _et al._ [2011] Z. E. D. Medendorp, F. A. Torres-Ruiz, L. K. Shalm, G. N. M. Tabia, C. A. Fuchs, and A. M. Steinberg, Experimental characterization of qutrits using symmetric informationally complete positive operator-valued measurements, Physical Review A 83, 051801 (2011), arXiv:1006.4905 .
  * Hou  _et al._ [2018] Z. Hou, J.-F. Tang, J. Shang, H. Zhu, J. Li, Y. Yuan, K.-D. Wu, G.-Y. Xiang, C.-F. Li, and G.-C. Guo, Deterministic realization of collective measurements via photonic quantum walks, Nature Communications 9, 1414 (2018), arXiv:1710.10045 .
  * Bruzewicz  _et al._ [2019] C. D. Bruzewicz, J. Chiaverini, R. McConnell, and J. M. Sage, Trapped-ion quantum computing: Progress and challenges, Applied Physics Reviews 6, 021314 (2019), arXiv:1904.04178 .
  * Hensgens  _et al._ [2017] T. Hensgens, T. Fujita, L. Janssen, X. Li, C. J. Van Diepen, C. Reichl, W. Wegscheider, S. Das Sarma, and L. M. K. Vandersypen, Quantum simulation of a Fermi–Hubbard model using a semiconductor quantum dot array, Nature 548, 70 (2017), arXiv:1702.07511 .
  * Singha  _et al._ [2011] A. Singha, M. Gibertini, B. Karmakar, S. Yuan, M. Polini, G. Vignale, M. I. Katsnelson, A. Pinczuk, L. N. Pfeiffer, K. W. West, and V. Pellegrini, Two-dimensional mott-hubbard electrons in an artificial honeycomb lattice, Science (New York, N.Y.) 332, 1176 (2011), arXiv:1106.3215 .
  * Rubin  _et al._ [2018] N. C. Rubin, R. Babbush, and J. McClean, Application of fermionic marginal constraints to hybrid quantum algorithms, New Journal of Physics 20, 053020 (2018), arXiv:1801.03524 .
  * Bravyi and Kitaev [2002] S. B. Bravyi and A. Y. Kitaev, Fermionic quantum computation, Annals of Physics 298, 210 (2002), arXiv:quant-ph/0003137 .
  * Vidal  _et al._ [2003] G. Vidal, J. I. Latorre, E. Rico, and A. Kitaev, Entanglement in quantum critical phenomena, Physical Review Letters 90, 227902 (2003), arXiv:quant-ph/0211074 .
  * Kraus [2009] C. V. Kraus,  _A Quantum Information Perspective of Fermionic Quantum Many-Body Systems_ , Ph.D. thesis, Technische Universität München (2009).
  * Jordan and Wigner [1928] P. Jordan and E. Wigner, über das paulische äquivalenzverbot, Zeitschrift für Physik 47, 631 (1928).
  * Verstraete and Cirac [2005] F. Verstraete and J. I. Cirac, Mapping local Hamiltonians of fermions to local Hamiltonians of spins, Journal of Statistical Mechanics: Theory and Experiment 2005, P09012 (2005), arXiv:cond-mat/0508353 .
  * Imada  _et al._ [1998] M. Imada, A. Fujimori, and Y. Tokura, Metal-insulator transitions, Reviews of Modern Physics 70, 1039 (1998).
  * Jördens  _et al._ [2008] R. Jördens, N. Strohmaier, K. Günter, H. Moritz, and T. Esslinger, A Mott insulator of fermionic atoms in an optical lattice, Nature 455, 204 (2008), arXiv:0804.4009 .
  * Schuch and Bauer [2019] N. Schuch and B. Bauer, Matrix product state algorithms for Gaussian fermionic states, Physical Review B 100, 245121 (2019), arXiv:1906.10144 .
  * García-Pérez  _et al._ [2021] G. García-Pérez, M. A. C. Rossi, B. Sokolov, F. Tacchino, P. K. Barkoutsos, G. Mazzola, I. Tavernelli, and S. Maniscalco, Learning to measure: Adaptive informationally complete POVMs for near-term quantum algorithms (2021), arXiv:2104.00569 .
  * Kubale [2004] M. Kubale, ed.,  _Graph Colorings_, Contemporary Mathematics, Vol. 352 (American Mathematical Society, Providence, Rhode Island, 2004).
  * Beineke and Wilson [2015] L. W. Beineke and R. J. Wilson, eds.,  _Topics in Chromatic Graph Theory_ (Cambridge University Press, Cambridge, 2015).
  * Vizing [1964] V. G. Vizing, On an estimate of the chromatic class of a p-graph, Diskret. Analiz. 3, 25 (1964).
  * Stiebitz  _et al._ [2012] M. Stiebitz, D. Scheide, B. Toft, and L. M. Favrholdt,  _Graph Edge Coloring: Vizing’s Theorem and Goldberg’s Conjecture_ (Wiley, Hoboken, 2012).

##  Appendix A Number of repetitions

Here we prove some relations on the number of repetitions $M$ needed for
statistical purposes based on the Chernoff-Hoefding bound, as in [27].
Consider that $M$ measurements of each variable are made, and that each
measurement has $\pm 1$ as possible outcomes. Then the Chernoff-Hoefding bound
states that the probability of error obeys

$P(\mathrm{error}_{i}>\varepsilon)\leqslant 2e^{-M\varepsilon^{2}/2}\ ,$ (19)

where $\mathrm{error}_{i}$ is defined as the difference in modulus between the
expectation value of the $i$-th variable and its estimate (arithmetic mean of
$M$ measured values). In words, it states that the probability of error
greater than $\varepsilon$ is exponentially suppressed. The union bound can
then be used to bound the probability of high error in any of the variables:

$P(\mathrm{error}_{i}>\varepsilon\ \mbox{for any}\
i)\leqslant\sum_{i}2e^{-M\varepsilon^{2}/2}\ ,$ (20)

where the sum in $i$ runs over all measured variables. The full $k$-RDM
considered in [27] requires measuring $4^{k}-1$ variables of each of the
$\binom{n}{k}$ sets of $k$ qubits, or $(4^{k}-1)\binom{n}{k}$ variables total.
So for the full $k$-RDM,

$P(\mathrm{error}_{i}>\varepsilon\ \mbox{for any}\ i)\leqslant
2(4^{k}-1)\binom{n}{k}e^{-M\varepsilon^{2}/2}\ ,$ (21)

and for that probability to be smaller than a small value $\delta$ we can set

$M\sim\frac{2}{\varepsilon^{2}}\left(k\log n+\log\frac{1}{\delta}\right)\ \ \
\mbox{(full $k$-RDM).}$ (22)

In our case, we do not measure all $\binom{n}{k}$ sets of $k$ qubits, only
$\mathcal{O}(n)$ of them. We can then set

$M\sim\frac{2}{\varepsilon^{2}}\left(k+\log n+\log\frac{1}{\delta}\right)\ \ \
\mbox{(neighbors only).}$ (23)

For fermions, there are instead $\binom{2n}{2k}$ variables total in the full
$k$-RDM, and still $\mathcal{O}(n)$ for our local $k$-RDMs, and the last two
equations still stand.

Figure 11: Creases on an $8\times 6$ square lattice generated by different
labelings. Black jagged lines: creases by labeling $\boldsymbol{a}$ from Eq.
(6) on a) a cylinder and b) a torus. Gray jagged lines: creases by additional
labeling $\boldsymbol{b}$ on each geometry [in the case of $\ell_{1}=4$,
$\ell_{2}=3$, from Eq. (7) exactly]. Notice how on the cylinder a) the second
labeling fully patches the creases of the first, but on the torus b) there are
two crossing points between black and gray creases that remain unpatched (the
two plaquettes shown cannot be measured with two labelings); the scenario
calls for a third labeling.

##  Appendix B Patching creases on looping geometries

Let us prove the statement that to measure plaquettes on the torus topology a
third labeling is in general necessary. This happens because whenever
$n_{1}\bmod\ell_{1}\neq 0$ and $n_{2}\bmod\ell_{2}\neq 0$ any labeling
produces a vertical and a horizontal “crease” between lattice sites, across
which plaquettes cannot be measured, and the additional labelings are meant to
patch these creases (Fig.11). With only two labelings, we have two pairs of
creases, each pair composed of a horizontal and a vertical crease. The torus
topology ensures that these pairs cross one another in at least two points,
though. Any plaquette that encompasses one of the crossing points cannot be
covered by the two labelings, requiring a third one.

##  Appendix C Majorana overlaps and commutation

Consider that two Majorana strings $s_{A}$, $s_{B}$ are composed of substrings
$s_{j}$, $s_{m}$, $s_{k}$ of length $j,m,k$, and are ordered as

$s_{A}=s_{j}s_{m}\ ,\quad\quad s_{B}=s_{m}s_{k}\ ,$ (24)

i.e. such that the overlapping Majoranas are flushed to the right and left,
respectively. This can be done without loss of generality, because this
reordering merely costs a certain phase $\pm 1$, and in the end the reordering
can be undone, canceling the extra phase. Anticommutation relations imply

$\displaystyle s_{A}s_{B}$
$\displaystyle=s_{j}s_{m}s_{m}s_{k}=(-1)^{jm+mk+jk}s_{m}s_{k}s_{j}s_{m}$ (25)
$\displaystyle=(-1)^{(j+m)(k+m)-m^{2}}s_{B}s_{A}\ .$ (26)

The two strings commute if, and only if, $(j+m)(k+m)-m^{2}$ is even. This
condition is equivalent to the length of the overlap having the same parity as
the product of the string lengths, as in the main text.


# Towards Immersive Virtual Reality Simulations of Bionic Vision

Justin Kasowski  University of California,Santa BarbaraCAUSA
<EMAIL_ADDRESS>,  Nathan Wu  University of California,Santa
BarbaraCAUSA<EMAIL_ADDRESS>and  Michael Beyeler  University of
California,Santa BarbaraCAUSA<EMAIL_ADDRESS>
(2021)

###### Abstract.

Bionic vision is a rapidly advancing field aimed at developing visual
neuroprostheses (‘bionic eyes’) to restore useful vision to people who are
blind. However, a major outstanding challenge is predicting what people ‘see’
when they use their devices. The limited field of view of current devices
necessitates head movements to scan the scene, which is difficult to simulate
on a computer screen. In addition, many computational models of bionic vision
lack biological realism. To address these challenges, we propose to embed
biologically realistic models of simulated prosthetic vision (SPV)in immersive
virtual reality (VR)so that sighted subjects can act as ‘virtual patients’ in
real-world tasks.

retinal implant, visually impaired, virtual reality, immersion, simulated
prosthetic vision, vision augmentation, virtual patient

††copyright: acmcopyright††journalyear: 2021††doi:
10.1145/1122445.1122456††conference: Augmented Humans ’21; February 22–24,
2021; Online††booktitle: Augmented Humans ’21††price: 15.00††isbn:
978-1-4503-XXXX-X/18/06††ccs: Human-centered computing Accessibility
technologies††ccs: Human-centered computing Virtual reality††ccs: Human-
centered computing HCI design and evaluation methods

Figure 1. Virtual and real patients for bionic vision. _Top row:_ Retinal
prosthesis patient. A microelectrode array is implanted in the eye to
stimulate the retina _(left)_. Light captured by an external camera is
transformed into electrical pulses delivered to the retina to evoke visual
percepts (_middle_), which a patient uses to walk towards a door (_right_).
_Bottom row:_ Virtual patient. Anatomical data is used to place a simulated
implant on a simulated retina (_left_). Visual input from a virtual reality
(VR)device is used to generate realistic predictions of simulated prosthetic
vision (SPV, _middle_), which a virtual patient uses to walk to a simulated
door in VR _(inner-right)_ , or a door in the real world captured by the head-
mounted display’s camera _(outer-right)_. Edges stand out due to the specific
preprocessing methods used, but a variety of methods can be tested. Behavioral
performance can then be compared between real prosthesis patients, SPV of the
real world, and SPV of the virtual world.

Virtual patients for bionic vision.

##  1\. Introduction

Retinal degenerative diseases cause profound visual impairment in more than 10
million people worldwide, and retinal prostheses (‘bionic eyes’) are being
developed to restore vision to these individuals. Analogous to a cochlear
implant, these devices convert video from a head-mounted camera into
electrical pulses used to stimulate retinal neurons, which the brain
interprets as visual percepts (‘phosphenes’; Fig. 1, _top row_). Current
devices have been shown to enable basic orientation & mobility tasks (Ayton et
al., 2020), but a growing body of evidence suggests that the vision restored
by these devices differs substantially from normal sight (Beyeler et al.,
2017b; Erickson-Davis and Korzybska, 2020).

A major outstanding challenge is predicting what people ‘see’ when they use
their devices. Studies of simulated prosthetic vision (SPV) often simplify
phosphenes into small independent light sources (Chen et al., 2009; Zapf et
al., 2014; Denis et al., 2014) even though recent evidence suggests phosphenes
vary drastically across subjects and electrodes (Beyeler et al., 2019;
Erickson-Davis and Korzybska, 2020). Another challenge is addressing the
narrow field of view (FOV) found in most devices (but see (Ferlauto et al.,
2018)). This requires patients to scan the environment with head movements
while trying to piece together the information (Erickson-Davis and Korzybska,
2020), but many previous SPV studies are performed on computer monitors. While
some studies attempt to address this (Chen et al., 2009; Denis et al., 2014;
Zapf et al., 2014), most fail to account for phosphene distortions. It is
therefore unclear how the findings of common SPV studies would translate to
real retinal prosthesis patients.

##  2\. Prototype

To address these challenges, we embedded a biologically realistic model of SPV
(Beyeler et al., 2017a; Beyeler et al., 2019) in immersive virtual reality
(VR) using the Unity development platform, allowing sighted subjects to act as
virtual patients in real-world tasks (see Fig. 1, _bottom row_). In this
setup, the visual input about to be rendered to an HTC VIVE head-mounted
display (HMD) mimics the external camera of a retinal implant. This input can
come from the HMD’s camera or can be simulated in a virtual environment. A
combination of compute and fragment shaders is used to simulate how this input
is likely perceived by a real patient. Unlike previous models, our work is
based on open-source code described in (Beyeler et al., 2017b), which
generates a realistic prediction of SPV that matches the field of view and
distortions of real devices. This allows sighted subjects to ‘see’ through the
eyes of a retinal prosthesis patient, taking into account their head and (in
future work) eye movements as they explore an immersive virtual environment.
Future SPV models can be plugged in and applied to new prostheses once they
become available.

##  3\. Research Goals

###  3.1. Provide realistic estimates of current bionic eye technologies

The prevailing approach to SPV is to assume that activating a grid of
electrodes leads to the percept of a grid of luminous dots, the brightness of
which scales linearly with stimulus amplitude (Chen et al., 2009; Zapf et al.,
2014; Denis et al., 2014). By ignoring percept distortions (Beyeler et al.,
2019; Erickson-Davis and Korzybska, 2020), performance predictions of such
studies can be highly misleading. In contrast, our work is constrained by
neuroanatomical and psychophysical data.

In addition, current devices are typically evaluated on simple behavioral
tasks, such as letter/object recognition (Cruz et al., 2013; Edwards et al.,
2018), following a line painted on the ground, or finding a door in an empty
room (Humayun et al., 2009). Even simple letter recognition tasks require head
movements to scan the scene, which is best emulated in an immersive VR
environment (note that FOV bionic eye $<<$ FOV HMD).

###  3.2. Assess the potential of advanced stimulation strategies

With the limited number of pixels found in current devices (e.g., Argus II:
$6\times 10$ electrodes), it is impossible to accurately represent a scene
without preprocessing. Rather than aiming to restore “natural vision”, there
is potential merit in borrowing computer vision algorithms as preprocessing
techniques to maximize the usefulness of bionic vision. Edge enhancement and
contrast maximization are already routinely used in current retinal implants,
and more advanced techniques based on object segmentation or visual saliency
might further improve visual performance (Han et al., 2021). For example,
using an object detection algorithm for cars could help prostheses users at a
crosswalk (Fig. 2), while facial recognition or text magnification would be
useful in other scenarios.

Although current bionic eyes have been implanted in over 500 patients
worldwide, experimentation with improved stimulation protocols remains
challenging and expensive. Virtual patients can offer an affordable
alternative for designing high-throughput experiments that can test
theoretical predictions, the best of which can then be validated in real
prosthesis patients.

Figure 2. Different image processing techniques for simulated prosthetic
vision (SPV). _A)_ Original Image. _B)_ SPV after segmenting important
objects. _C)_ Edge enhancement of the original image. _D)_ SPV of the edge-
enhanced image.

Different preprocessing effects under simulated prosthetic vision

###  3.3. Guide the prototyping of future devices

The insights gained through virtual patients may help drive the changes for
future devices. Obvious improvements could be realized by testing different
electrode layouts and stimulation frequencies. Some of these factors have been
modeled before in isolation, but these models often predicted higher visual
acuity than what was found in clinical trials (Chen et al., 2009; Cheng et
al., 2017; Zapf et al., 2014; Denis et al., 2014). Therefore, using an
established and psychophysically validated computational model of bionic
vision may prove invaluable to generating realistic predictions of visual
prosthetic performance.

##  4\. Conclusion

The present work constitutes a first essential step towards immersive VR
simulations of bionic vision. The proposed system has the potential to 1)
further our understanding of the qualitative experience associated with
different bionic eye technologies, 2) provide realistic expectations of bionic
eye performance for patients, doctors, manufacturers, and regulatory bodies,
and 3) accelerate the prototyping of new devices.

## References

  * (1)
  * Ayton et al. (2020) Lauren N. Ayton, Nick Barnes, Gislin Dagnelie, Takashi Fujikado, Georges Goetz, Ralf Hornig, Bryan W. Jones, Mahiul M. K. Muqit, Daniel L. Rathbun, Katarina Stingl, James D. Weiland, and Matthew A. Petoe. 2020.  An update on retinal prostheses.  _Clinical Neurophysiology_ 131, 6 (June 2020), 1383–1398.  https://doi.org/10.1016/j.clinph.2019.11.029
  * Beyeler et al. (2017a) Michael Beyeler, Geoffrey M. Boynton, Ione Fine, and Ariel Rokem. 2017a.  _pulse2percept: A Python-based simulation framework for bionic vision_.  preprint. Neuroscience.  https://doi.org/10.1101/148015
  * Beyeler et al. (2019) Michael Beyeler, Devyani Nanduri, James D. Weiland, Ariel Rokem, Geoffrey M. Boynton, and Ione Fine. 2019\.  A model of ganglion axon pathways accounts for percepts elicited by retinal implants.  _Scientific Reports_ 9, 1 (June 2019), 9199\.  https://doi.org/10.1038/s41598-019-45416-4 Number: 1 Publisher: Nature Publishing Group.
  * Beyeler et al. (2017b) M. Beyeler, A. Rokem, G. M. Boynton, and I. Fine. 2017b.  Learning to see again: biological constraints on cortical plasticity and the implications for sight restoration technologies.  _J Neural Eng_ 14, 5 (June 2017), 051003\.  https://doi.org/10.1088/1741-2552/aa795e
  * Chen et al. (2009) Spencer C. Chen, Gregg J. Suaning, John W. Morley, and Nigel H. Lovell. 2009.  Simulating prosthetic vision: I. Visual models of phosphenes.  _Vision Research_ 49, 12 (June 2009), 1493–1506.  https://doi.org/10.1016/j.visres.2009.02.003
  * Cheng et al. (2017) Derrick L. Cheng, Paul B. Greenberg, and David A. Borton. 2017\.  Advances in Retinal Prosthetic Research: A Systematic Review of Engineering and Clinical Characteristics of Current Prosthetic Initiatives.  _Current Eye Research_ 42, 3 (March 2017), 334–347.  https://doi.org/10.1080/02713683.2016.1270326 Publisher: Taylor & Francis _eprint: https://doi.org/10.1080/02713683.2016.1270326.
  * Cruz et al. (2013) Lyndon da Cruz, Brian F. Coley, Jessy Dorn, Francesco Merlini, Eugene Filley, Punita Christopher, Fred K. Chen, Varalakshmi Wuyyuru, Jose Sahel, Paulo Stanga, Mark Humayun, Robert J. Greenberg, Gislin Dagnelie, and for the Argus II Study Group. 2013.  The Argus II epiretinal prosthesis system allows letter and word reading and long-term function in patients with profound vision loss.  _British Journal of Ophthalmology_ 97, 5 (May 2013), 632–636.  https://doi.org/10.1136/bjophthalmol-2012-301525 Publisher: BMJ Publishing Group Ltd Section: Clinical science.
  * Denis et al. (2014) Gregoire Denis, Christophe Jouffrais, Corinne Mailhes, and Marc J.-M. Mace. 2014.  Simulated prosthetic vision: improving text accessibility with retinal prostheses.  _Annual International Conference of the IEEE Engineering in Medicine and Biology Society. IEEE Engineering in Medicine and Biology Society. Annual International Conference_ 2014 (2014), 1719–1722.  https://doi.org/10.1109/EMBC.2014.6943939
  * Edwards et al. (2018) Thomas L. Edwards, Charles L. Cottriall, Kanmin Xue, Matthew P. Simunovic, James D. Ramsden, Eberhart Zrenner, and Robert E. MacLaren. 2018.  Assessment of the Electronic Retinal Implant Alpha AMS in Restoring Vision to Blind Patients with End-Stage Retinitis Pigmentosa.  _Ophthalmology_ 125, 3 (March 2018), 432–443.  https://doi.org/10.1016/j.ophtha.2017.09.019
  * Erickson-Davis and Korzybska (2020) Cordelia Erickson-Davis and Helma Korzybska. 2020.  What do blind people “see” with retinal prostheses? Observations and qualitative reports of epiretinal implant users.  , 2020.02.03.932905 pages.  https://doi.org/10.1101/2020.02.03.932905 Publisher: Cold Spring Harbor Laboratory Section: New Results.
  * Ferlauto et al. (2018) Laura Ferlauto, Marta Jole Ildelfonsa Airaghi Leccardi, Naïg Aurelia Ludmilla Chenais, Samuel Charles Antoine Gilliéron, Paola Vagni, Michele Bevilacqua, Thomas J. Wolfensberger, Kevin Sivula, and Diego Ghezzi. 2018.  Design and validation of a foldable and photovoltaic wide-field epiretinal prosthesis.  _Nature Communications_ 9, 1 (March 2018), 992\.  https://doi.org/10.1038/s41467-018-03386-7 Number: 1 Publisher: Nature Publishing Group.
  * Han et al. (2021) Nicole Han, Sudhanshu Srivastava, Aiwen Xu, Devi Klein, and Michael Beyeler. 2021.  Deep Learning–Based Scene Simplification for Bionic Vision.  arXiv:2102.00297 [cs.CV]
  * Humayun et al. (2009) Mark S. Humayun, Jessy D. Dorn, Ashish K. Ahuja, Avi Caspi, Eugene Filley, Gislin Dagnelie, Joël Salzmann, Arturo Santos, Jacque Duncan, Lyndon daCruz, Saddek Mohand-Said, Dean Eliott, Matthew J. McMahon, and Robert J. Greenberg. 2009.  Preliminary 6 month results from the Argus II epiretinal prosthesis feasibility study.  _Conference proceedings: … Annual International Conference of the IEEE Engineering in Medicine and Biology Society. IEEE Engineering in Medicine and Biology Society. Annual Conference_ 2009 (2009), 4566–4568.  https://doi.org/10.1109/IEMBS.2009.5332695
  * Zapf et al. (2014) Marc P. Zapf, Paul B. Matteucci, Nigel H. Lovell, Steven Zheng, and Gregg J. Suaning. 2014\.  Towards photorealistic and immersive virtual-reality environments for simulated prosthetic vision: integrating recent breakthroughs in consumer hardware and software.  _Annual International Conference of the IEEE Engineering in Medicine and Biology Society. IEEE Engineering in Medicine and Biology Society. Annual International Conference_ 2014 (2014), 2597–2600.  https://doi.org/10.1109/EMBC.2014.6944154