# Foundations for learning from noisy quantum experiments

Hsin-Yuan Huang  Institute for Quantum Information and Matter and
Department of Computing and Mathematical Sciences, Caltech, Pasadena, CA, USA
AWS Center for Quantum Computing, Pasadena, CA, USA  Steven T. Flammia  AWS
Center for Quantum Computing, Pasadena, CA, USA  California Institute of
Technology, Pasadena, CA, USA  John Preskill  Institute for Quantum
Information and Matter and
Department of Computing and Mathematical Sciences, Caltech, Pasadena, CA, USA
AWS Center for Quantum Computing, Pasadena, CA, USA

(August 27, 2024)

###### Abstract

Understanding what can be learned from experiments is central to scientific
progress. In this work, we use a learning-theoretic perspective to study the
task of learning physical operations in a quantum machine when all operations
(state preparation, dynamics, and measurement) are _a priori_ unknown. We
prove that, without any prior knowledge, if one can explore the full quantum
state space by composing the operations, then every operation can be learned.
When one cannot explore the full state space but all operations are
approximately known and noise in Clifford gates is gate-independent, we find
an efficient algorithm for learning all operations up to a single unlearnable
parameter characterizing the fidelity of the initial state. For learning a
noise channel on Clifford gates to a fixed accuracy, our algorithm uses
quadratically fewer experiments than previously known protocols. Under more
general conditions, the true description of the noise can be unlearnable; for
example, we prove that no benchmarking protocol can learn gate-dependent Pauli
noise on Clifford+T gates even under perfect state preparation and
measurement. Despite not being able to learn the noise, we show that a noisy
quantum computer that performs entangled measurements on multiple copies of an
unknown state can yield a large advantage in learning properties of the state
compared to a noiseless device that measures individual copies and then
processes the measurement data using a classical computer. Concretely, we
prove that noisy quantum computers with two-qubit gate error rate $\epsilon$
can achieve a learning task using $N$ copies of the state, while
$N^{\Omega(1/\epsilon)}$ copies are required classically.

Understanding what we can learn from experiments is central to many scientific
fields. By conducting experiments we obtain information about the physical
world. This information can be organized into knowledge allowing us to predict
how the world would behave under different circumstances and to design complex
systems with desired functionalities. In particular, the development of
sophisticated quantum technologies is guided by knowledge acquired in
experiments on quantum systems.

In this work, we build on computational learning theory kearns1994introduction
; goodfellow2016deep ; mohri2018foundations  to develop a rigorous theory for
reasoning about what can and cannot be learned in a world governed by quantum
mechanics. We represent scientists and their classical algorithms abstractly
as classical agents that conduct experiments by specifying actions that
control a quantum system. Actions include specifying which initial states are
prepared, which CPTP maps are performed, and which POVM measurements are
executed at the end of an experiment. Classical agents do not have perfect
knowledge about how these actions affect the quantum world, e.g., what state
is prepared, or what quantum processes and measurements are actually
implemented. But classical agents can improve their understanding of the
physical world through experiments. We refer to the mapping from each action
to the corresponding physical operation as a world model ${\mathcal{W}}$. The
central question we would like to answer is: What can a classical agent learn
about the true world model $\mathcal{W}_{\mathrm{true}}$ describing the
underlying physical reality?

To answer this question, we make a distinction between two different
viewpoints for assessing how well the classical agent learns. The first
viewpoint judges whether the classical agent accurately _learns the intrinsic
descriptions_ of the physical operations. This is the viewpoint commonly
considered in quantum state or process tomography hradil1997quantum ;
gross2010quantum ; blume2010optimal ; d2003quantum ; mohseni2008quantum ;
o2016efficient ; o2017efficient ; haah2017sample ; guta2020fast ;
huang2020predicting ; huang2021provably  or in Hamiltonian learning
anshu2021sample ; haah2021optimal . For example, given a quantum computer, we
might want the classical agent to characterize the noise afflicting the state
preparations, maps, or measurements acting on various qubits. Knowledge about
the intrinsic descriptions of the physical operations is crucial for
calibrating, controlling, and improving a complex quantum many-body system
wiseman2009quantum ; brif2010control ; yang2014robust . If, for example, the
classical agent finds the measurements to be particularly noisy, we should
focus on improving our measurement procedure.

The second viewpoint examines whether the classical agent can _predict the
extrinsic behavior_ of the quantum system. In particular, given an experiment,
we ask the classical agent to predict the experimental outcomes. The classical
agent does not need to learn the actual descriptions of the physical
operations and is free to use any model as long as the predictions are
accurate. The second viewpoint is relevant when we want to control the quantum
system to achieve specific tasks, such as mitigating errors in a particular
computation temme2017error ; endo2018practical ; kandala2019error ;
strikis2021learning . Because the true physical descriptions are not learned,
a model that can predict extrinsic behavior might not provide useful guidance
regarding how to improve the quantum device. While intrinsic descriptions are
more informative than a model for predicting extrinsic behavior, intrinsic
descriptions are also more challenging to learn.

In this work, we obtain fundamental results regarding what one can learn from
noisy quantum experiments. We also present case studies illustrating some
practical implications of these foundational results. In related work to
appear elsewhere, we will present a versatile mathematical framework for
developing rigorous neural network algorithms capable of learning a wide range
of noise models in quantum many-body systems.

Figure 1: Illustration of a classical agent that can learn from quantum
experiments. The classical agent specifies an instruction consisting of the
actions $x,y,z$ for the experiment. The quantum system runs the experiment
using a state $\rho_{x}$, a quantum process ${{\mathcal{E}}}_{y}$, and a POVM
measurement ${\mathcal{M}}_{z}$ to produce an experimental outcome. The
classical agent does not have prior knowledge on what
$\rho_{x},{{\mathcal{E}}}_{y},{\mathcal{M}}_{z}$ are. The goal of the
classical agent is to either learn
$\rho_{x},{{\mathcal{E}}}_{y},{\mathcal{M}}_{z}$ (learning intrinsic
descriptions) or predict the distribution of experimental outcomes (predicting
extrinsic behaviors).

##  I Foundations

To elucidate the basic features of learning intrinsic descriptions and
predicting extrinsic behaviors, we prove a series of fundamental results
regarding what the classical agent can learn and how efficiently the classical
agent can learn it. We begin by establishing the formalism. Then, we present
results that elucidate the two viewpoints.

###  I.1 A formalism for learning from quantum experiments

We consider three sets of actions that the classical agent could perform:
$\mathcal{X}$ is the set of actions for preparing different kinds of states,
$\mathcal{Y}$ consists of actions for implementing certain physical
evolutions, and $\mathcal{Z}$ is a set of possible POVM measurements. A world
model $\mathcal{W}$ is a mapping from the actions to the actual physical
operations. For example, each action $y\in\mathcal{Y}$ corresponds to a
quantum channel $\mathcal{E}_{y}$ that is applied to the quantum system when
the classical agent performs the action $y$. We represent the world model by
the collection of physical operations associated to all actions,

$\mathcal{W}=\left(\\{\rho_{x}\\}_{x\in\mathcal{X}},\\{\mathcal{E}_{y}\\}_{y\in\mathcal{Y}},\\{\mathcal{M}_{z}\\}_{z\in\mathcal{Z}}\right),$
(1)

where $\rho_{x}$ is a quantum state, $\mathcal{E}_{y}$ is a quantum channel,
and $\mathcal{M}_{z}$ is a POVM measurement. In Appendix A, we provide formal
definitions of world models and formulate some relations between world models.
Due to the intrinsic degeneracy in the formulation of quantum mechanics, two
world models related by a global unitary or anti-unitary transformation
describe the same physical reality Wigner1931GruppentheorieUI .

The classical agent conducts an experiment by instructing the quantum system
to execute a given sequence of actions. Each experiment $E$ begins with an
action $x\in\mathcal{X}$ that prepares the state $\rho_{x}$, followed by a
sequence of actions $y_{1},\ldots,y_{L}\in\mathcal{Y}$ that evolves the state
$\rho_{x}$ to
$\mathcal{E}_{y_{L}}(\ldots\mathcal{E}_{y_{2}}(\mathcal{E}_{y_{1}}(\rho_{x}))\ldots)$,
and the experiment ends with an action $z\in\mathcal{Z}$ that produces a
measurement outcome after performing the POVM $\mathcal{M}_{z}$ on
$\mathcal{E}_{y_{L}}(\ldots\mathcal{E}_{y_{2}}(\mathcal{E}_{y_{1}}(\rho_{x}))\ldots)$.
We suppose that the classical agent has prior knowledge that the true world
model $\mathcal{W}_{\mathrm{true}}$ belongs to a class of candidate models
$\mathcal{Q}=\\{\mathcal{W}\\}$. The goal of the classical agent is to learn
about the true world model $\mathcal{W}_{\mathrm{true}}$ by conducting
experiments. The set of models $\mathcal{Q}$ will be referred to as the _model
class_ , following the nomenclature in classical learning theory
mohri2018foundations .

Note that this framework is very general. For example, the set $\mathcal{Q}$
of candidate models could be uncountably large, which might describe an
unknown noise processes occurring in an experimental setup described by
continuous parameters. There could even be non-Markovian or time-dependent
effects in this framework. For example, in a real experiment a sequence of
actions $x,y_{1},y_{2},y_{3}$ might prepare a state
$\mathcal{E}_{y_{3}|y_{2}y_{1}}(\mathcal{E}_{y_{2}|y_{1}}(\mathcal{E}_{y_{1}}(\rho_{x})))$
where each physical operation depends on the history of previous actions.
Superficially, this appears to lie outside the framework. However, these time-
dependent and non-Markovian effects can be put into our framework by embedding
into a new world model where state preparations contain an additional memory
register, which is continually updated as subsequent actions are performed.
The details of this mapping are in Appendix A.1. Thus, our framework can model
many situations where a classical agent learns about a quantum system.

###  I.2 Learning intrinsic descriptions of the world model

We will say that a model class $\mathcal{Q}$ is _learnable_ if for any world
model $\mathcal{W}\in\mathcal{Q}$, the classical agent can determine all
physical operations in $\mathcal{W}$ with an arbitrarily small error using a
finite number of experiments, up to one global unitary or anti-unitary
transformation. A formal definition of learnability is given in Appendix C. A
similar criterion is often invoked in discussions of quantum tomography;
however, in quantum state/process/measurement tomography, it is typically
assumed that some actions are perfectly known, and the goal is to characterize
other actions which are not perfectly known. For example, we might envision
using perfect state preparations and perfect measurements to characterize
noisy gates. We will consider instead a setting in which all actions are
unknown _a priori_ , and our goal is to learn the true physical description of
each action to arbitrary accuracy.

Learning the intrinsic physical description might be challenging or even
impossible because the classical agent can perform only a limited set of
actions. For example, a classical agent cannot distinguish between the
following two distinct physical realities in a single-qubit system with
universal control using Hadamard ($H$) and $T$ ( $=Z^{1/4}$) gates,

$\displaystyle\mathcal{W}^{A}:\quad\rho^{A}_{0}$ $\displaystyle=I/2,$
$\displaystyle\mathcal{E}^{A}_{H}(\rho)$ $\displaystyle=H\rho H^{\dagger},$
$\displaystyle\mathcal{E}^{A}_{T}(\rho)$ $\displaystyle=T\rho T^{\dagger},$
$\displaystyle\mathcal{M}^{A}_{0}$ $\displaystyle=\\{\lvert 0\rangle\\!\langle
0\rvert,\lvert 1\rangle\\!\langle 1\rvert\\},$ (2)
$\displaystyle\mathcal{W}^{B}:\quad\rho^{B}_{0}$ $\displaystyle=I/2,$
$\displaystyle\mathcal{E}^{B}_{H}(\rho)$ $\displaystyle=I/2,$
$\displaystyle\mathcal{E}^{B}_{T}(\rho)$ $\displaystyle=I/2,$
$\displaystyle\mathcal{M}^{B}_{0}$ $\displaystyle=\\{\lvert 0\rangle\\!\langle
0\rvert,\lvert 1\rangle\\!\langle 1\rvert\\},$ (3)

with actions $\mathcal{X}=\\{0\\},\mathcal{Y}=\\{H,T\\},\mathcal{Z}=\\{0\\}$.
In both world A and world B, no matter what sequence of actions drawn from
$\\{H,T\\}$ is performed between the initial state preparation and the final
measurement, the probability distribution governing the measurement outcomes
is always the same, namely the uniform distribution over the two outcomes
$\\{0,1\\}$. Hence, although the maps labeled by $H$ and $T$ are certainly
intrinsically different in world A than in world B, this difference cannot be
perceived by the classical agent. It follows that any model class
$\mathcal{Q}$ that contains both $\mathcal{W}^{A}$ and $\mathcal{W}^{B}$ is
unlearnable, even if $\mathcal{Q}$ is uncountably large.

If the classical agent has no prior knowledge of the state preparations, maps,
and measurements, is it possible to learn the intrinsic descriptions of all
actions to arbitrary accuracy? Our first result shows that a model class
$\mathcal{Q}$ is learnable if a suitable condition is met. Suppose that each
world model $\mathcal{W}\in\mathcal{Q}$ contains a nontrivial measurement (one
whose outcome depends on the state being measured), and that each
$\mathcal{W}\in\mathcal{Q}$ contains actions that fully explore the quantum
state space. Then $\mathcal{Q}$ is learnable. This observation motivates the
following definition.

######  Definition 1.

A world model
$\mathcal{W}=\left(\\{\rho_{x}\\}_{x\in\mathcal{X}},\\{\mathcal{E}_{y}\\}_{y\in\mathcal{Y}},\\{\mathcal{M}_{z}\\}_{z\in\mathcal{Z}}\right)$
is _universal_ if (i) there is $x\in\mathcal{X}$, such that the state
$\rho_{x}$ is pure; (ii) there are $y_{1},\ldots,y_{k}\in\mathcal{Y}$, such
that the maps $\mathcal{E}_{y_{1}},\ldots\mathcal{E}_{y_{k}}$ constitute a
universal set of unitary transformations; (iii) there is $z\in\mathcal{Z}$,
such that the POVM $\mathcal{M}_{z}$ has at least one POVM element not
proportional to the identity.

When a world model is universal, we do not assume that the classical agent
knows for which value of $x$ the state $\rho_{x}$ is pure, for which values of
$y$ the maps form a universal set, or for which value of $z$ the measurement
is nontrivial. Nor does the classical agent have any other prior knowledge of
the state preparations, maps, and measurements. Nevertheless, the agent can
learn all actions to arbitrary accuracy according to the following theorem.

######  Theorem 2 (Learning intrinsic descriptions).

Consider a (possibly uncountably large) model class ${\mathcal{Q}}$ such that
each candidate world model in ${\mathcal{Q}}$ is universal as in Definition 1.
If the true world model is ${\mathcal{W}}_{\mathrm{true}}\in{\mathcal{Q}}$,
then the classical agent can learn the description of every action in
${\mathcal{W}}_{\mathrm{true}}$ to arbitrarily small error (up to one global
unitary or anti-unitary transformation).

###### Proof idea.

Here, we present the general idea of the proof; further details are in
Appendix D. First, we design a procedure for testing whether a composed CPTP
map $\mathcal{E}_{y_{k}}\circ\ldots\circ\mathcal{E}_{y_{1}}$ is the identity
map. Then, we use the fact that unitaries are the only reversible CPTP maps
and the identity testing procedure to create a protocol for testing whether a
CPTP map $\mathcal{E}_{y}$ is a unitary. The unitary test allows the learning
agent to identify every action that implements a unitary transformation to
within a specified error tolerance.

Next, we show that a random composition of the identified unitaries forms an
approximate Haar random unitary. This is proven using a contraction theorem
for random walks on compact semi-simple Lie groups Varj2012RandomWI . This
result holds for any universal set of unitaries without the need to include
inverses or have algebraic entries, but the theorem is weaker than the
spectral gap theorem in bourgain2012spectral . Building on Corollary 7 in
Varj2012RandomWI , we can show that the expectation value of any Lipschitz
continuous function over randomly composed unitaries (chosen from a universal
set) is approximately equal to the expectation value over Haar random
unitaries. Hence, although the learning agent doesn’t know what each unitary
is, the learning agent can still sample from approximately Haar-random
unitaries. In fact, it will suffice to sample approximately from a unitary
two-design. Up to this point, the learning agent has not learned the
description for any of the actions.

We then prove the following: given a procedure that samples approximately from
a unitary two-design and the availability of an unknown POVM with at least one
POVM element not proportional to identity, we can create a procedure that
estimates the overlap $\operatorname{tr}(\rho_{1}\rho_{2})$ for any two states
$\rho_{1},\rho_{2}$. This procedure makes use of the two-design property of
the random unitary ensemble.

Applying this overlap estimation procedure, the learning agent can determine
for which value of $x$ the state $\rho_{x}$ is pure, and then reach other pure
states by applying unitary circuits to $\rho_{x}$. Through further
applications of the overlap estimation procedure, the learning agent can find
a special set of states $\\{\ket{\psi_{k}}\\}$ with a particular geometry.
Specifically, the special set of states corresponds to an orthonormal basis of
pure states $\ket{e_{1}},\ldots,\ket{e_{d}}$, superpositions of pairs of these
basis states $\frac{1}{\sqrt{2}}(\ket{e_{i}}+\ket{e_{j}})$,
$\frac{1}{\sqrt{2}}(\ket{e_{i}}+\mathrm{i}\ket{e_{j}})$ with a real or
imaginary relative phase, and also superpositions of three basis states
$\frac{1}{\sqrt{3}}(\ket{e_{1}}+\ket{e_{i}}+\ket{e_{j}})$,
$\frac{1}{\sqrt{3}}(\ket{e_{1}}+\mathrm{i}\ket{e_{2}}+\mathrm{i}\ket{e_{j}})$,
$\frac{1}{\sqrt{3}}(\ket{e_{1}}+\ket{e_{i}}+\mathrm{i}\ket{e_{j}})$. The only
ambiguity in this procedure is that all experiments would yield the same
results if each state $\ket{\psi_{k}}$ were replaced by $U\ket{\psi_{k}}$
where $U$ is a fixed unitary transformation, and/or if $(i)$ were replaced by
$(-i)$ in the superpositions of basis states (i.e., if a fixed antiunitary
transformation were applied to each state $\ket{\psi_{k}}$). This ambiguity is
also present in the formulation of quantum mechanics as characterized by
Wigner’s theorem Wigner1931GruppentheorieUI . Without the superpositions of
three basis states, there would be further ambiguity beyond the freedom to
perform a global transformation.

Given the special set of states $\\{\ket{\psi_{k}}\\}$ and the procedure for
estimating state overlaps, the classical agent can perform a version of
quantum state tomography to learn the physical representation of $\rho_{x}$
for all $x\in\mathcal{X}$. Similarly, the classical agent can learn the CPTP
map $\mathcal{E}_{y}$ for all $y\in\mathcal{Y}$ by performing quantum state
tomography on the states
$\mathcal{E}_{y}(\lvert\psi_{k}\rangle\\!\langle\psi_{k}\rvert)$ for all
special states $\ket{\psi_{k}}$. The classical agent can also learn the POVM
$\mathcal{M}_{z}$ for all $z\in\mathcal{Z}$ from the outcome probability
distribution when $\mathcal{M}_{z}$ is performed on the special states
$\\{\ket{\psi_{k}}\\}$. Hence, the classical agent has learned all the
actions, up to a global unitary or antiunitary transformation. ∎

When we cannot explore the quantum state space completely, it may be
impossible to learn the intrinsic description to arbitrarily small error even
with an infinite number of experiments. In Appendix E, we present some basic
results establishing how modifying a model class affects the learnability of
the model class. Building on these results, we prove the unlearnability of
various classes of quantum systems in Appendices F and G.

As a further example illustrating the concept of unlearnability, consider an
$n$-qubit system with an initial state $\rho_{0}$, a set of unital CPTP maps
(${{\mathcal{E}}}_{y}(I)=I$ for all $y$), and a POVM measurement
${\mathcal{M}}_{0}$. It is not hard to see that no learning algorithm can
distinguish between the following two physical realities.

  1. 1.

The initial state is slightly depolarized, $\rho_{0}=0.9\lvert
0^{n}\rangle\\!\langle 0^{n}\rvert+0.1(I/2^{n})$. But the computational basis
measurement is perfect, ${\mathcal{M}}_{0}=\\{\lvert b\rangle\\!\langle
b\rvert\\}_{b\in\\{0,1\\}^{n}}$.

  2. 2.

The initial state is perfect, $\rho_{0}=\lvert 0^{n}\rangle\\!\langle
0^{n}\rvert$. But the computational basis measurement is slightly depolarized,
${\mathcal{M}}_{0}=\\{0.9\lvert b\rangle\\!\langle
b\rvert+0.1(I/2^{n})\\}_{b\in\\{0,1\\}^{n}}$.

This follows immediately from the property that unital maps preserve the
maximally mixed state. We will present a less trivial example in Section II.2
and discuss some practical implications.

###  I.3 Predicting extrinsic behavior of the world model

Rather than insisting that the classical agent learn the intrinsic description
of a world model, we might settle instead for a description of the world
model’s extrinsic behavior. We give a formal definition of extrinsic behavior
in Appendix I. Suppose we would like to predict the probability distribution
of measurement outcomes for any experiment with $L$ CPTP maps, and suppose
there are only finitely many actions. How many experiments will the classical
agent need to perform in order to make accurate predictions? It would
certainly suffice to perform each possible experiment many times, but because
there are $|\mathcal{X}||\mathcal{Y}|^{L}|\mathcal{Z}|$ possible experiments,
this procedure is very costly for large $L$. Is there a more efficient method?
In fact, in the worst case we can improve on the cost of this exhaustive
procedure by at best a logarithmic factor.

######  Theorem 3 (Worst case complexity for predicting extrinsic behavior).

To predict the probability of each experimental outcome to error $\epsilon$
for every experiment with $L$ maps, the classical agent has to perform at
least $\Omega(|\mathcal{X}||\mathcal{Y}|^{L}|\mathcal{Z}|/\epsilon^{2})$
experiments in the worst case, and the classical agent can always achieve the
task by running
$\widetilde{\mathcal{O}}(|\mathcal{X}||\mathcal{Y}|^{L}|\mathcal{Z}|/\epsilon^{2})$
experiments111$\widetilde{\mathcal{O}}(\cdot)$ neglects the logarithmic
factors..

To derive the lower bound, we construct world models that behave like a
special kind of maze. The classical agent has to navigate through the maze by
performing a specific sequence of actions. Whenever the classical agent makes
the wrong action, he/she fails. We then combine this picture with a proof
technique used in huang2021information ; chen2021exponential  to establish the
stated lower bound. The detailed proof is given in Appendix I.1.

One way to avoid this daunting worst case complexity is to assume that we have
found a set of composed states and POVM elements such that both sets span all
possible states one can generate by performing actions in the world model. The
following theorem shows that in such cases a speed-up exponential in $L$ over
the worst case can be achieved. The full algorithm and the proof are given in
Appendix J.

######  Theorem 4 (Predicting extrinsic behavior).

Suppose we have found a set of unknown linearly independent states composed
from $\\{\rho_{x},\mathcal{E}_{y}\\}$ and a set of unknown POVM elements
composed from $\\{{{\mathcal{E}}}_{y},{\mathcal{M}}_{z}\\}$, such that both
sets span all the states that can be prepared in world model $\mathcal{W}$.
Then, we can predict the probability of each experimental outcome to error
$\epsilon$ for any experiment with $L$ maps after running
$\widetilde{\mathcal{O}}((|\mathcal{X}|+L^{2}|\mathcal{Y}|+|\mathcal{Z}|)/\epsilon^{2})$
experiments.

Comparing Theorems 3 and 4, we infer that the spanning set of composed states
and POVM elements assumed in Theorem 4 cannot be found efficiently in the
worst case. But for many world models they can be found efficiently.

In Appendix K we discuss gate set tomography from the perspective of our
mathematical theory. There we argue that existing gate set tomography
protocols greenbaum2015introduction ; blume2017demonstration ; nielsen2020gate
; brieger2021compressive  may be viewed as methods for predicting the
extrinsic behavior of a world model. Based on this understanding, the
algorithm used in the proof of Theorem 4 establishes rigorous gate set
tomography learning algorithms with provable prediction guarantees under
suitable conditions.

##  II Case studies

Let us now consider three case studies that illustrate the power and wide
applicability of the formalism that we have developed.

###  II.1 Learning under gate-independent noise on Clifford gates

A common assumption used in the randomized benchmarking literature
emerson2005scalable ; knill2008randomized ; magesan2011scalable ;
kimmel2014robust ; roth2018recovering ; helsen2021estimating  is that the
noise processes afflicting Clifford gates are independent of the specific
gate. This assumption applies to all elements in the Clifford group and is
used to ensure that randomized benchmarking can extract an accurate estimate
for the average gate fidelity proctor2017randomized , although weak gate-
dependent noise can also be accommodated Wallman2018 ; Merkel2021 . More
precisely, when the classical agent performs a Clifford gate $C$, the CPTP map
implemented is

${{\mathcal{E}}}_{C}(\rho)={{\mathcal{N}}}(C\rho C^{\dagger}),$ (4)

where ${{\mathcal{N}}}$ is a CPTP map close to the identity that does not
depend on the gate $C$. In the benchmarking literature, it is also commonly
assumed that there is a noisy zero state $\rho_{0}$ that is close to the all
zero state $\ket{0^{n}}$, and there is a noisy computational basis measurement
${\mathcal{M}}_{0}=\\{M_{b}\\}_{b\in\\{0,1\\}^{n}}$, where $M_{b}$ is close to
$\lvert b\rangle\\!\langle b\rvert$. We will refer to these assumptions as
bounded gate-independent noise on Clifford gates, and bounded noise on initial
zero state preparation and computational basis measurement. Typically, these
assumptions are expected to hold (approximately) only for a subsystem
consisting of a constant number of qubits in a many-qubit quantum computer.

Under these assumptions, we give a simple and practical algorithm for learning
every physical operation up to one unknown parameter
$f=\bra{0^{n}}\rho_{0}\ket{0^{n}}$. The parameter $f$ is the fidelity of the
noisy zero state $\rho_{0}$, which is assumed to be close to one. Using
techniques presented in the appendices, it is straightforward to show that $f$
is unlearnable. To see this, assume that the noise channel ${{\mathcal{N}}}$
is the identity channel, and use the result in Appendix G showing that one
cannot distinguish whether the initial state or the measurement is subjected
to a depolarizing channel. When the Clifford gate noise ${{\mathcal{N}}}$ is
not assumed to be the identity channel, the learning does not become any
easier; hence $f$ is still unlearnable.

When the Clifford gate noise is unital, ${{\mathcal{N}}}(I)=I$, the
unlearnability of $f$ does not prevent ${{\mathcal{N}}}$ from being determined
to arbitrarily small error. Under this assumption of unital noise, several
existing algorithms, robust to state preparation and measurement error, have
been proposed to learn ${{\mathcal{N}}}$ using information obtained from
randomized benchmarking kimmel2014robust ; roth2018recovering ;
helsen2021estimating . The best existing algorithm helsen2021estimating
learns ${{\mathcal{N}}}$ using $\mathcal{O}(d^{8}\log d)$ experiments, where
$d=2^{n}$. Our proposed algorithm only requires $\mathcal{O}(d^{4}\log d)$
experiments. This number of experiments scales linearly, up to a logarithmic
factor, with the number of parameters characterizing the noise channel. The
rigorous guarantees are expressed in the following theorem; the proof is in
Appendix H.

######  Theorem 5 (Learning gate-independent noise on Clifford gates).

Assume bounded gate-independent noise on Clifford gates, and bounded noise on
initial zero state preparation and computational basis measurement. All
states, processes, and measurements
$\\{\rho_{x},{{\mathcal{E}}}_{y},{\mathcal{M}}_{z}\\}$ can be learned up to a
single unlearnable parameter $f=\bra{0^{n}}\rho_{0}\ket{0^{n}}$.

Furthermore, if the Clifford gate noise channel ${{\mathcal{N}}}$ obeys
${{\mathcal{N}}}(I)=I$, then the Choi matrix for ${{\mathcal{N}}}$ can be
learned up to error $\epsilon$ in the Hilbert-Schmidt norm using
$\mathcal{O}(d^{4}\log d/\epsilon^{2})$ experiments.

###### Proof idea.

We conduct two sets of randomized experiments to learn about the initial state
$\rho_{0}$ (the noisy zero state), the Clifford gate noise ${{\mathcal{N}}}$,
and the measurement ${\mathcal{M}}_{0}$ (the noisy computational basis
measurement). The first set of experiments prepares $\rho_{0}$, evolves by
${{\mathcal{E}}}_{C}$ for a random Clifford $C$, and measures
${\mathcal{M}}_{0}$. The second set of experiments prepares $\rho_{0}$,
evolves by ${{\mathcal{E}}}_{C_{1}}$ for a random Clifford $C_{1}$, evolves by
${{\mathcal{E}}}_{C_{2}}$ for a second random Clifford $C_{2}$, and measures
${\mathcal{M}}_{0}$. (The division of the Clifford into $C_{1}$ and $C_{2}$,
each with noise channel ${{\mathcal{N}}}$, is used in the postprocessing of
the measurement results.) The learning procedure exploits the unitary 2-design
property of random Clifford gates and follows closely the classical shadow
formalism huang2020predicting ; huang2022learning , which is based on least
squares estimation of the quantum objects guta2020fast .

From the first set of experiments we can learn, up to the unlearnable
parameter $f$, the state $\rho_{0}$ and the POVM
${{\mathcal{N}}}^{\dagger}({\mathcal{M}}_{0})$, which corresponds to applying
${{\mathcal{N}}}$ followed by the POVM ${\mathcal{M}}_{0}$, Then, the second
set of experiments allows us to learn ${{\mathcal{N}}}$. Once
${{\mathcal{N}}}$ and ${{\mathcal{N}}}^{\dagger}({\mathcal{M}}_{0})$ are
known, we can invert ${{\mathcal{N}}}^{\dagger}$ to determine
${\mathcal{M}}_{0}$.

With data obtained from the first and the second sets of randomized
experiments, we can learn all physical operations. To learn the state
$\rho_{x}$, we repeatedly perform the randomized experiment: prepare
$\rho_{x}$, evolve by ${{\mathcal{E}}}_{C}$ for a random Clifford $C$, and
measure ${\mathcal{M}}_{0}$. To learn the CPTP map ${{\mathcal{E}}}_{y}$, we
repeatedly perform the randomized experiment: prepare $\rho_{0}$, evolve by
${{\mathcal{E}}}_{C_{1}}$ for a random Clifford $C_{1}$, evolve by
${{\mathcal{E}}}_{y}$, evolve by ${{\mathcal{E}}}_{C_{2}}$ for a second random
Clifford $C_{2}$, and measure ${\mathcal{M}}_{0}$. To learn POVM
${\mathcal{M}}_{z}$, we repeat the randomized experiment: prepare $\rho_{0}$,
evolve by ${{\mathcal{E}}}_{C}$ for a random Clifford $C$, and measure
${\mathcal{M}}_{z}$.

The unitary 2-design property of random Clifford gates and standard
concentration inequalities can be used to characterize the number of
experiments needed to estimate all objects with a small error. In particular,
we show that if ${{\mathcal{N}}}(I)=I$ then the proposed algorithm learns the
Clifford gate noise ${{\mathcal{N}}}$ to error $\epsilon$ from a total of
$\mathcal{O}(d^{4}\log d/\epsilon^{2})$ experiments. ∎

###  II.2 Bit-flip or phase-flip error?

In this case study, we relax the assumption of gate-independent noise and
consider the task of learning the noise on Clifford and $T$ gates when the
noise channel depends on the gate. We assume that the noisy version of the
Clifford or $T$ gate $G$ is

${{\mathcal{E}}}_{G}(\rho)={\mathcal{P}}_{G}(G\rho G^{\dagger}),$ (5)

where ${\mathcal{P}}_{G}$ is a Pauli channel that depends on the gate $G$ and
is close to the identity; tailoring a more general noise process using
randomized compiling might result in such a channel Viola2005 ; Knill2005 ;
wallman2016noise . In the following theorem, we show that it is impossible to
learn the true gate-dependent Pauli noise even in a single-qubit system. To be
concrete, we suppose that the classical agent can apply noisy versions of the
$H$, $S$, and $T$ gates, and hopes to characterize the noise channel for each
of these gates.

######  Theorem 6 (Gate-dependent Pauli noise is unlearnable with Clifford+T
gates).

Consider a qubit system. Suppose one can prepare $\ket{0}$ perfectly, measure
in the computational basis perfectly, and apply $H$, $S$, and $T$ gates, where
each gate is followed by an unknown gate-dependent Pauli noise channel close
to the identity channel. It is impossible for any algorithm to learn all the
gate-dependent Pauli noise channels to arbitrarily small error.

###### Proof idea.

The theorem is established by proving that one is unable to determine whether
a bit-flip ($X$) error is more likely to happen than a phase-flip ($Z$) error
after the Hadamard gate $H$; these two possibilities define distinct physical
realities that are not related by a global unitary or anti-unitary
transformation. Importantly, perfect preparation of $\ket{0}$ and perfect
measurement in the computational basis are not sufficient by themselves for
learning a general quantum channel via complete quantum process tomography.
Using a graphical method to track the Heisenberg-picture evolution of Pauli
operators under circuits of noisy Clifford + $T$ gates, we show that the noise
in the Hadamard gate is unlearnable if only the state $|0\rangle$ can be
prepared. Then using reduction methods developed in Appendix E, we show that
the unlearnability persists if noisy versions of arbitrary states can also be
prepared. The full proof is given in Appendix F. ∎

This result may seem to contradict claims about known protocols, such as gate
set tomography greenbaum2015introduction ; blume2017demonstration ;
nielsen2020gate ; brieger2021compressive  and ACES flammia2021averaged . To
resolve the conflict, recall that gate set tomography learns an effective
model that can be used to predict the extrinsic behavior. While gate set
tomography might be able to learn some intrinsic features of the true world
model, it is still unable to learn all the gate-dependent Pauli noise channels
due to the gauge freedom in the protocol. In ACES flammia2021averaged , it is
assumed that one can prepare any tensor product of single-qubit stabilizer
states perfectly. By making this additional assumption, the no-go result in
Theorem 6 can be evaded.

Theorem 6 is relevant in the setting where we would like to identify a noise
process to facilitate the task of improving our hardware. For example, one may
want to know whether the Hadamard gate is experiencing a higher rate of bit-
flip error or phase-flip error, so that the dominant error can be suppressed
by modifying the device. Theorem 6 shows that characterizing the noise process
precisely is not always possible.

###  II.3 Quantum advantage in learning from noisy experiments

Recent theoretical results have established that _quantum-enhanced
experiments_ can exhibit a substantial advantage compared to _conventional
experiments_ in learning properties of an unknown quantum state or process
aharonov2021quantum ; huang2021information ; chen2021quantum ;
chen2021exponential ; chen2021hierarchy ; huang2021quantum . The prior works
concerned the idealized setting in which the quantum device used for learning
is perfectly known and perfectly controllable. But recent experiments using up
to 40 qubits in the Sycamore processor have demonstrated that a notable
quantum advantage can be achieved even with the relatively noisy quantum
devices that are currently available huang2021quantum . This experimental
demonstration highlights the need for a theoretical analysis of quantum
advantage when the device used in learning is noisy and initially
uncharacterized. Here we establish a provable quantum advantage in this more
realistic setting.

We focus on a particular task that was analyzed in huang2021information ;
chen2021exponential ; huang2021quantum  and studied experimentally in
huang2021quantum . In this task, the learning agent is provided with multiple
copies of an unknown quantum state $\rho$. In conventional experiments, the
agent collects classical data by measuring each copy of $\rho$ separately.
These measurements may be adaptive; that is, the measurement performed on each
copy can depend on the results obtained in measurements on previous copies.
Using the collected classical data, the agent learns a model of $\rho$. After
the learning is complete, the agent is asked to predict a property of $\rho$
which is selected from a long list of incompatible properties. In quantum-
enhanced experiments, the agent can load copies of $\rho$ into a quantum
memory, and perform collective measurements acting on multiple copies. It was
shown in huang2021information ; chen2021exponential ; huang2021quantum  that
in some cases the number of copies of $\rho$ needed to predict accurately is
exponentially smaller in the (ideal) quantum-enhanced scenario than in the
conventional scenario. Furthermore, this exponential quantum advantage can be
achieved using quite simple two-copy measurements in which qubit pairs are
measured in the Bell basis. These simple measurements can be executed in
practice with reasonable fidelity.

We wish to show that the quantum advantage persists when we compare ideal
conventional experiments with noisy quantum-enhanced experiments. We assume
that the noisy quantum device can prepare a noisy and unknown initial product
state, load a copy of the unknown physical state $\rho$ into memory, apply
noisy and unknown single-qubit and two-qubit gates, and perform a noisy and
unknown product measurement. Multiple layers of gates can be performed, where
each layer contains multiple non-overlapping gates applied in parallel. The
noise in quantum gates may be highly correlated — the CPTP map implemented by
each gate can depend arbitrarily on how other gates implemented in the same
layer are chosen. We _do not assume_ that each gate is affected by only a
constant number of other gates in the same layer. Furthermore the noisy CPTP
maps are _not_ guaranteed to be close to the ideal unitary gates up to a
constant error. Under these assumptions, it is not possible to learn the
intrinsic description of the device to arbitrary accuracy. In addition,
exponentially many experiments are required to learn the extrinsic behaviors
to high but constant accuracy because the noise processes are highly non-
local. Because the noise cannot be learned efficiently, it is not clear how to
make use of standard error mitigation techniques temme2017error ;
endo2018practical ; kandala2019error .

Even though the device cannot be learned to arbitrarily small error, one can
learn the intrinsic description of the device up to a certain accuracy floor.
To establish this, we adapt the strategy from the proof of Theorem 2 to this
modified setting. Recall that in that proof we found a set of states with a
specified geometry, and then built quantum tomography protocols making use of
those states. Under the assumptions of Theorem 2, we could find states with
the desired geometry to arbitrary accuracy. Under our current assumptions,
this is no longer possible, but the geometry can be realized with a small
error $\eta$, which suffices for characterizing two-qubit gates up to an error
$\epsilon=\mathcal{O}(\eta)$. Details of the procedure and proof are in
Appendix L.2.

With these noisy two-qubit gates we can perform a noisy version of Bell
measurement on qubit pairs, and hence execute a noisy version of the quantum-
enhanced protocol that achieves an exponential quantum advantage in the ideal
case huang2021information ; chen2021exponential ; huang2021quantum . For an
$n$-qubit system this protocol calls for the evaluation of the parity of
$\mathcal{O}(n)$ measurement outcomes, so that
$(1-4\epsilon)^{\mathcal{O}(n)}$ measurement repetitions suffice to extract a
statistically useful result. In contrast, $\Omega(2^{n})$ copies of $\rho$ are
needed to make accurate predictions in the conventional scenario, even in the
case where the state $\rho$ is separable. Therefore, the noisy quantum-
enhanced protocol has a significant polynomial advantage over the optimal
protocol in the ideal conventional scenario if $\epsilon$ is small. This
conclusion is expressed by the following theorem.

######  Theorem 7 (Quantum advantage with noisy devices).

There exists a set of unentangled physical states $\rho$ and properties we
would like to predict, such that if we need $N_{\mathrm{Q}}$ copies of $\rho$
in the noisy quantum-enhanced scenario to predict the property, then the
required number of copies in noiseless conventional experiments must be
$N_{\mathrm{C}}=\Omega(N_{\mathrm{Q}}^{a})$, where
$a=-\log(2)/(2\log(1-4\epsilon))=\mathcal{O}(1/\epsilon)$ and $\epsilon$ is
the error on each of the two-qubit operations.

If each of the two-qubit operations has an error $\epsilon$ of at most
$0.5\%$, then we can obtain a separation of
$N_{\mathrm{C}}=\Omega(N_{\mathrm{Q}}^{17.15})$. The detailed proof of Theorem
7 is given in Appendix L.

##  III Conclusion

We have developed a rigorous theory for reasoning about what can be learned
from noisy quantum experiments, emphasizing the distinction between learning
the extrinsic behavior of a noisy quantum system and the more challenging task
of learning its intrinsic description. We have applied our framework to
several examples of learning tasks and to give a large polynomial quantum
advantage for a learning task using noisy quantum devices. While we have
largely focused on issues of principle, more practical considerations,
including a rigorous neural network algorithm for learning noisy quantum
systems, will be discussed in future work.

This theory opens up several future directions. In particular, the essential
features of learnable and unlearnable model classes remain to be clarified. In
Appendix E we presented some deductive rules relating the learnability of
distinct model classes. Might this framework be extended, so that the
learnability or unlearnability of a wide variety of model classes can be
inferred by applying such deductive rules to a small number of paradigmatic
cases? We have also seen that some model classes are very hard to learn, while
others are relatively easy. Can we deliberately engineer our quantum systems
to make learning easier? This question evokes an oft-cited principle of
software design — programs are more broadly useful if they are easier to
troubleshoot.

More philosophically, it is remarkable that humans, assisted by our classical
machines, can gain precise knowledge of the elusive quantum world. What is the
explanation for this ability, and what knowledge will remain beyond our grasp
due to fundamental limitations on learning with classical agents? Deepening
our understanding of what can be learned from quantum experiments will not
only facilitate the advance of quantum technology, but may also illuminate
what is knowable and unknowable about the physical world.

### Acknowledgments:

The authors thank Sitan Chen, Jordan Cotler, Jerry Li, Richard Kueng, and
Thomas Vidick for valuable input and inspiring discussions. HH is supported by
a Google PhD Fellowship. JP acknowledges funding from the U.S. Department of
Energy Office of Science, Office of Advanced Scientific Computing Research,
(DE-NA0003525, DE-SC0020290), and the National Science Foundation
(PHY-1733907). The Institute for Quantum Information and Matter is an NSF
Physics Frontiers Center.

Appendices

###### Contents

  1. I Foundations
    1. I.1 A formalism for learning from quantum experiments
    2. I.2 Learning intrinsic descriptions of the world model
    3. I.3 Predicting extrinsic behavior of the world model
  2. II Case studies
    1. II.1 Learning under gate-independent noise on Clifford gates
    2. II.2 Bit-flip or phase-flip error?
    3. II.3 Quantum advantage in learning from noisy experiments
  3. III Conclusion
  4. A World models
    1. A.1 Time dependent and non-Markovian models
    2. A.2 Basic properties and relations
  5. B A characterization of equivalence: Proof
  6. C Foundations for learning intrinsic descriptions
  7. D A general theorem for learning intrinsic physical descriptions
    1. D.1 A lemma on generating Haar-random unitaries
    2. D.2 The precision parameter
    3. D.3 Testing identity and unitarity
    4. D.4 Estimating state overlaps
    5. D.5 Learning descriptions of a special set of states
    6. D.6 Quantum state/process/measurement tomography
    7. D.7 Putting everything together
  8. E Basic properties of learnability and unlearnability
  9. F Gate-dependent Pauli noise is unlearnable with Clifford+T gates
    1. F.1 Statement and unlearnability of a target model class
    2. F.2 Unlearnability of $\mathcal{Q}^{\epsilon}$
    3. F.3 Unlearnability of a simpler model class
    4. F.4 Actions of Clifford+T on Pauli operators
      1. F.4.a Experiments as multiple particles traversing a graph
      2. F.4.b Polynomial forms and unlearnability
    5. F.5 Unlearnability of simple model class implies unlearnability of target model class
      1. F.5.a Composing all Clifford gates
      2. F.5.b Composing all quantum states
  10. G Noise and unlearnability
  11. H Learning under gate-independent noise on Clifford gates
    1. H.1 Review on unitary design for Clifford gates
    2. H.2 Learning noisy zero state, Clifford gate noise, and noisy basis measurement
      1. H.2.a Learning noisy basis measurement conflated with Clifford gate noise
      2. H.2.b Learning noisy zero state
      3. H.2.c Learning Clifford gate noise
      4. H.2.d Learning noisy basis measurement
    3. H.3 Learning any state, CPTP map, and POVM
      1. H.3.a Learning POVM
      2. H.3.b Learning states
      3. H.3.c Learning CPTP maps
    4. H.4 Sample complexity for learning Clifford gate noise
      1. H.4.a $P=I$ and $Q=I$
      2. H.4.b Exactly one of $P$ and $Q$ is equal to $I$
      3. H.4.c $P\neq I$ and $Q\neq I$
      4. H.4.d Final result
  12. I Foundations for predicting extrinsic behavior
    1. I.1 Hardness in predicting extrinsic behaviors
  13. J A general theorem for predicting extrinsic behavior
    1. J.1 Assumptions
    2. J.2 Learning a frame
    3. J.3 Learning states
    4. J.4 Learning CPTP maps
    5. J.5 Learning POVMs
    6. J.6 Prediction procedure and rigorous guarantee
    7. J.7 Proof of Theorem J.1 — Step A. Representations of target outputs
    8. J.8 Proof of Theorem J.1 — Step B. Error analysis for the learned representations
    9. J.9 Proof of Theorem J.1 — Step C. Error analysis for the prediction
    10. J.10 Proof of Theorem J.1 — Step D. Putting everything together
  14. K Related work
    1. K.1 Gate set tomography
    2. K.2 Quantum state/process/measurement tomography
  15. L Quantum advantage with noisy devices that cannot be fully learned
    1. L.1 Setting
      1. L.1.a State preparation and measurements
      2. L.1.b Operations
    2. L.2 Algorithm for partially learning the device
      1. L.2.a Experiments and loss functions: Single-qubit
      2. L.2.b Rigorous guarantee: Single-qubit
      3. L.2.c Experiments and loss functions: Two-qubit
      4. L.2.d Rigorous guarantee: Two-qubit
      5. L.2.e Putting everything together
    3. L.3 Task description and quantum advantage
    4. L.4 A class of states and properties
      1. L.4.a Characterization of the probability distribution
    5. L.5 Upper bound for noisy quantum-enhanced experiments
      1. L.5.a Detailed procedure
      2. L.5.b Noise analysis
      3. L.5.c Sample complexity analysis
    6. L.6 Lower bound for noiseless conventional experiments

##  APPENDIX A World models

We consider a general framework involving classical agents interacting with a
quantum system. This is a mathematical framework for reasoning about what
experimentalists could learn from a finite-dimensional quantum system that
they can interact with by various means.

######  Definition A.1 ($d$-dimensional world model).

Given sets $\mathcal{X},\mathcal{Y},\mathcal{Z}$ denoting the action space and
a finite set $\mathcal{B}$ denoting the possible measurement outcomes. A
$d$-dimensional world model $\mathcal{W}$ is a tuple with three sets

$\mathcal{W}=\left(\\{\rho_{x}\\}_{x\in\mathcal{X}},\\{\mathcal{E}_{y}\\}_{y\in\mathcal{Y}},\\{\mathcal{M}_{z}\\}_{z\in\mathcal{Z}}\right),$
(6)

where $\rho_{x}$ is a $d$-dimensional density matrix, $\mathcal{E}_{y}$ is a
$d$-dimensional CPTP map, $\mathcal{M}_{z}=\\{M_{zb}\\}_{b\in\mathcal{B}}$ is
a POVM with finitely many elements indexed by $b\in\mathcal{B}$.

Consider $d=2$, which is equivalent to a qubit system. We give an example to
illustrate the above definition. Let
$\mathcal{X}=\\{(\theta,\phi)\,\,|\,\,\theta\in[0,\pi],\phi\in[0,2\pi]\\}$ be
an uncountably large set; we define

$\rho_{\theta,\phi}=\frac{I+\sin(\theta)\cos(\phi)X+\sin(\theta)\sin(\phi)Y+\cos(\theta)Z}{2}.$
(7)

In this world, we can prepare any pure state on the single-qubit bloch sphere.
Let $\mathcal{Y}=\\{h,t\\}$ be a finite set consisting of two elements. We
consider $\mathcal{E}_{h}(\rho)=H\rho H^{\dagger}$ to be the Hadamard gate and
$\mathcal{E}_{t}(\rho)=T\rho T^{\dagger}$ to be the $T$ gate. Finally, we
consider $\mathcal{Z}=\\{0\\}$ to be a singleton and $\mathcal{B}=\\{0,1\\}$
to be a two-outcome space, where $\mathcal{M}_{0}=\\{\lvert 0\rangle\\!\langle
0\rvert,\lvert 1\rangle\\!\langle 1\rvert\\}$ is the computational basis
measurement. $\mathcal{W}$ defines a single-qubit world where one can perform
universal single-qubit quantum computation. Alternatively, one could also
consider $\mathcal{X}$ to be a set of $\vec{n}\in\mathbb{R}^{3}$ with
$\left\lVert\vec{n}\right\rVert_{2}\leq 1$. Or we could consider $\mathcal{Y}$
to be a set of sequences where each sequence is a pulse sequence the
experimentalist could use to control the qubit system. Intuitively,
$\mathcal{X},\mathcal{Y},\mathcal{Z}$ contain descriptions of the actions an
experimentalist could perform on the finite-dimensional quantum system, and
$\mathcal{B}$ contains descriptions of the measurement outcomes.

######  Remark 1.

In the above definition, we can have $x_{1},x_{2}\in\mathcal{X}$, such that
$x_{1}\neq x_{2}$ but $\rho_{x_{1}}=\rho_{x_{2}}$. This construction encodes
the intuition that there could be two different actions an experimentalist
could perform that will result in the same initial state. For example, we can
generate the state $\ket{1}$ from $\ket{0}$ by applying $\pi$ rotation along
the X axis or the Y axis.

The experimentalists could interact with the $d$-dimensional world model by
performing experiments. The experimentalist selects a state $\rho_{x}$ to be
prepared, composes various different evolutions
$\mathcal{E}_{y_{1}},\ldots,\mathcal{E}_{y_{L}}$, then reads out the final
state through a chosen measurement apparatus $\mathcal{M}_{z}$.

######  Definition A.2 (Experiment).

Given a $d$-dimensional world model $\mathcal{W}$. An experiment is a list of
finite elements given as

$E=(x\in\mathcal{X},y_{1}\in\mathcal{Y},\ldots,y_{L}\in\mathcal{Y},z\in\mathcal{Z}).$
(8)

Each experiment results in an outcome $b\in\mathcal{B}$ with probability
$\operatorname{tr}\left(M_{zb}\left(\mathcal{E}_{y_{L}}\circ\ldots\circ\mathcal{E}_{y_{1}}\right)(\rho_{x})\right).$

###  A.1 Time dependent and non-Markovian models

From the definition of experiment given in Def. A.2, we can see that applying
the same action $y\in{\mathcal{Y}}$ results in the same CPTP map
${{\mathcal{E}}}_{y}$. In many practical settings, the quantum systems could
have explicit time dependence (${{\mathcal{E}}}_{y}$ depends on the time it is
applied) and could be non-Markovian (each physical operation depends on what
operations are performed before). In this subsection, we briefly describe how
models with explicit time dependence and non-Markovian behavior can be reduced
to a model that is time-independent and Markovian.

Suppose we have a model ${\mathcal{W}}^{(\mathrm{exception})}$ where the
sequence of actions $x,y_{1},y_{2},\ldots,y_{L},z$ results in an outcome
$b\in\mathcal{B}$ with probability

$\operatorname{tr}\left(M_{zb|x,y_{1},\ldots,y_{L}}\left(\mathcal{E}_{y_{L}|x,y_{1},\ldots,y_{L-1}}\circ\ldots\circ\mathcal{E}_{y_{1}|x}\right)(\rho_{x})\right),$
(9)

and all the states, CPTP maps, POVMs are $d$-dimensional. This model
${\mathcal{W}}^{(\mathrm{exception})}$ is time-dependent and non-Markovian,
hence is formally not covered by our definition of world model. However, we
can consider a world model ${\mathcal{W}}$ that yields the same experimental
outcome as ${\mathcal{W}}^{(\mathrm{exception})}$ but is time-independent and
Markovian. We simply define
${\mathcal{W}}^{\prime}==\left(\\{\rho^{\prime}_{x}\\}_{x\in\mathcal{X}},\\{\mathcal{E}^{\prime}_{y}\\}_{y\in\mathcal{Y}},\\{\mathcal{M}^{\prime}_{z}\\}_{z\in\mathcal{Z}}\right)$
to be a world model, where the state space contains both the original
$d$-dimensional state and memory state that stores the history of the actions.
The initial state $\rho^{\prime}_{x}$ is given by

$\rho^{\prime}_{x}=\rho_{x}\otimes\lvert\varnothing\rangle\\!\langle\varnothing\rvert,$
(10)

where the history is initialized to be empty. The CPTP map
${{\mathcal{E}}}^{\prime}_{y}$ implements a CPTP based on the history stored
in the memory state,

${{\mathcal{E}}}^{\prime}_{y}(\rho\otimes\lvert\mathrm{history}\rangle\\!\langle\mathrm{history}\rvert)={{\mathcal{E}}}_{y|\mathrm{history}}(\rho)\otimes\lvert\mathrm{history},y\rangle\\!\langle\mathrm{history},y\rvert,$
(11)

where $\mathrm{history}$ is a sequence of the past actions
$x,y_{1},y_{2},y_{3},\ldots$. Similarly, the POVM ${\mathcal{M}}^{\prime}_{z}$
in the newly defined world model ${\mathcal{W}}^{\prime}$ also depends on the
history,

$\operatorname{tr}(M^{\prime}_{zb}(\rho\otimes\lvert\mathrm{history}\rangle\\!\langle\mathrm{history}\rvert))=\operatorname{tr}(M_{zb|\mathrm{history}}\rho).$
(12)

It is not hard to see that for the time-independent and Markovian world model
${\mathcal{W}}^{\prime}$, an experiment specified by the sequence of actions
$x,y_{1},y_{2},\ldots,y_{L},z$ results in an outcome $b\in\mathcal{B}$ with
probability

$\displaystyle\operatorname{tr}\left(M^{\prime}_{zb}\left(\mathcal{E}^{\prime}_{y_{L}}\circ\ldots\circ\mathcal{E}^{\prime}_{y_{1}}\right)(\rho^{\prime}_{x})\right)$
(13) $\displaystyle=$
$\displaystyle\operatorname{tr}\left(M_{zb|x,y_{1},\ldots,y_{L}}\left(\mathcal{E}_{y_{L}|x,y_{1},\ldots,y_{L-1}}\circ\ldots\circ\mathcal{E}_{y_{1}|x}\right)(\rho_{x})\right).$
(14)

Together, we see that time-dependent and non-Markovian models can be covered
by our definition at the expense of having a world model with much larger
dimension.

We do mention a pathological case. Suppose that given a sequence of
$x,y_{1},\ldots,y_{\ell-1}$, the CPTP map
$\mathcal{E}_{y_{\ell}|x,y_{1},\ldots,y_{\ell-1}}$ is uncomputable. This means
that the size of the memory state for storing the history would have to grow
unboundedly. In this case, we need to reduce time-dependent and non-Markovian
models to an infinite-dimensional time-independent and Markovian world model.
This pathological case is not practically relevant since there is no finite
description of such a time-dependent and non-Markovian model.

###  A.2 Basic properties and relations

As the experimentalists improve their physical control (lasers, cavity, etc.),
more initial states $\rho_{x}$ can be created, more evolutions
$\mathcal{E}_{y}$ can be performed, and more types of qubit readout
$\mathcal{M}_{z}$ can be achieved. We could imagine an ideal case, where we
are able to generate all states, perform all operations, and conduct all
measurements. We consider such a world model to be complete. A formal
definition is given below.

######  Definition A.3 (Completeness).

A $d$-dimensional
$\mathcal{W}=\left(\\{\rho_{x}\\}_{x\in\mathcal{X}},\\{\mathcal{E}_{y}\\}_{y\in\mathcal{Y}},\\{\mathcal{M}_{z}\\}_{z\in\mathcal{Z}}\right)$
is complete if

  * •

for all states $\rho$, $\exists x\in\mathcal{X}$, $\rho_{x}=\rho$,

  * •

for all CPTP maps $\mathcal{E}$, $\exists y\in\mathcal{Y}$,
$\mathcal{E}_{y}=\mathcal{E}$,

  * •

for all POVM $\mathcal{M}$ with outcomes indexed by $b\in\mathcal{B}$,
$\exists z\in\mathcal{Z}$, $\mathcal{M}_{z}=\mathcal{M}$.

We say the world model $\mathcal{W}$ has been extended to a richer world model
$\mathcal{W}^{\prime}$ if $\mathcal{W}^{\prime}$ contains more actions
corresponding to more initial states, quantum evolutions, and POVM
measurements. The formal definition is given below.

######  Definition A.4 (Extension).

A $d$-dimensional world model
$\mathcal{W}^{\prime}=\left(\\{\rho_{x}^{\prime}\\}_{x\in\mathcal{X}^{\prime}},\\{\mathcal{E}_{y}^{\prime}\\}_{y\in\mathcal{Y}^{\prime}},\\{\mathcal{M}_{z}^{\prime}\\}_{z\in\mathcal{Z}^{\prime}}\right)$
is an extension of a $d$-dimensional world model
$\mathcal{W}=\left(\\{\rho_{x}\\}_{x\in\mathcal{X}},\\{\mathcal{E}_{y}\\}_{y\in\mathcal{Y}},\\{\mathcal{M}_{z}\\}_{z\in\mathcal{Z}}\right)$,
denoted as $\mathcal{W}^{\prime}\rhd\mathcal{W}$, if the following conditions
hold

  * •

$\mathcal{X}\subseteq\mathcal{X}^{\prime}$ and $\forall
x\in\mathcal{X},\rho_{x}=\rho_{x}^{\prime}$ (State extension),

  * •

$\mathcal{Y}\subseteq\mathcal{Y}^{\prime}$ and $\forall
y\in\mathcal{Y},\mathcal{E}_{y}=\mathcal{E}_{y}^{\prime}$ (CPTP map
extension),

  * •

$\mathcal{Z}\subseteq\mathcal{Z}^{\prime}$ and $\forall
z\in\mathcal{Z},\mathcal{M}_{z}=\mathcal{M}_{z}^{\prime}$ (POVM extension).

We are now ready to define equivalence between two world models. Before giving
the formal definition, let us consider two $2$-dimensional worlds
$\mathcal{W}_{A},\mathcal{W}_{B}$ with the same spaces
$\mathcal{X}=\\{0\\},\mathcal{Y}=\\{h,t\\},\mathcal{Z}=\\{0\\},\mathcal{B}=\\{0,1\\}$.
Furthermore, we consider the particular actions in the two world models
$\mathcal{W}_{A},\mathcal{W}_{B}$ to be given by

$\displaystyle\rho^{A}_{0}$ $\displaystyle=I/2,$
$\displaystyle\mathcal{E}^{A}_{h}(\rho)$ $\displaystyle=H\rho H^{\dagger},$
$\displaystyle\mathcal{E}^{A}_{t}(\rho)$ $\displaystyle=T\rho T^{\dagger},$
$\displaystyle\mathcal{M}^{A}_{0}$ $\displaystyle=\\{\lvert 0\rangle\\!\langle
0\rvert,\lvert 1\rangle\\!\langle 1\rvert\\},$ (15)
$\displaystyle\rho^{B}_{0}$ $\displaystyle=I/2,$
$\displaystyle\mathcal{E}^{B}_{h}(\rho)$ $\displaystyle=I/2,$
$\displaystyle\mathcal{E}^{B}_{t}(\rho)$ $\displaystyle=I/2,$
$\displaystyle\mathcal{M}^{B}_{0}$ $\displaystyle=\\{\lvert 0\rangle\\!\langle
0\rvert,\lvert 1\rangle\\!\langle 1\rvert\\}.$ (16)

It is not hard to show that we cannot distinguish between world A and B by
performing experiments using the limited set of actions — in both cases the
measurement outcomes are sampled from the uniform distribution. However, we
can clearly see that the two world models are intrinsically different. In
particular, in world A, the set of maps is a universal gate set that generates
a dense subset of $\mathrm{SU}(2)$. But, in world B, all the maps are
completely depolarizing channels. Even though world A and B can not be
distinguish using the limited set of actions
$\mathcal{X}=\\{0\\},\mathcal{Y}=\\{h,t\\},\mathcal{Z}=\\{0\\}$, the two
worlds are fundamentally different. By adding new actions, such as the ability
to prepare some non-trivial states, we can distinguish between the two world
models by performing experiments.

To discuss these concepts in a rigorous manner, we formally define the
following relations between two world models
$\mathcal{W}_{1},\mathcal{W}_{2}$. We consider two world models to be equal
$\mathcal{W}_{1}=\mathcal{W}_{2}$ if all of the states, maps, and POVMs are
equal. And we say the two world models are different
$\mathcal{W}_{1}\neq\mathcal{W}_{2}$ if one of the states, maps, or POVMs is
different. In the above example, the two world models
$\mathcal{W}_{A},\mathcal{W}_{B}$ are different because the CPTP maps are
different $\mathcal{E}^{A}_{h}\neq\mathcal{E}^{B}_{h}$ and
$\mathcal{E}^{A}_{t}\neq\mathcal{E}^{B}_{t}$.

######  Definition A.5 (Equality).

Consider two $d$-dimensional world models $\mathcal{W}_{A},\mathcal{W}_{B}$
with the same spaces $\mathcal{X},\mathcal{Y},\mathcal{Z},\mathcal{B}$.
$\mathcal{W}_{A}$ is equal to $\mathcal{W}_{B}$, denoted as
$\mathcal{W}_{A}=\mathcal{W}_{B}$, if all states are the same
$\rho^{A}_{x}=\rho^{B}_{x},\forall x\in\mathcal{X},$ all CPTP maps are the
same $\mathcal{E}^{A}_{y}=\mathcal{E}^{B}_{y},\forall y\in\mathcal{Y},$ and
all POVMs are the same $M^{A}_{zb}=M^{B}_{zb},\forall
z\in\mathcal{Z},b\in\mathcal{B}$.

Then, we consider two world models to be weakly indistinguishable if they can
not be distinguished using the set of actions in the world model. In the
example given in Equation (15) and (16), $\mathcal{W}_{A},\mathcal{W}_{B}$ are
weakly indistinguishable because the measurement outcomes are always uniformly
distributed.

######  Definition A.6 (Weakly indistinguishable).

Consider two $d$-dimensional world models $\mathcal{W}_{A},\mathcal{W}_{B}$
with the same spaces $\mathcal{X},\mathcal{Y},\mathcal{Z},\mathcal{B}$.
$\mathcal{W}_{A}$ and $\mathcal{W}_{B}$ are weakly indistinguishable if for
any experiment
$E=(x\in\mathcal{X},y_{1}\in\mathcal{Y},\ldots,y_{L}\in\mathcal{Y},z\in\mathcal{Z})$
and outcome $b\in\mathcal{B}$, we have

$\operatorname{tr}\left(M^{A}_{zb}\left(\mathcal{E}^{A}_{y_{L}}\circ\ldots\circ\mathcal{E}^{A}_{y_{1}}\right)(\rho^{A}_{x})\right)=\operatorname{tr}\left(M^{B}_{zb}\left(\mathcal{E}^{B}_{y_{L}}\circ\ldots\circ\mathcal{E}^{B}_{y_{1}}\right)(\rho^{B}_{x})\right),$
(17)

i.e., the probabilities for obtaining the outcome $b$ in experiment $E$ are
the same.

We say two world models are strongly indistinguishable or equivalent to one
another if they can not be distinguished by adding any set of actions. World
models $\mathcal{W}_{A},\mathcal{W}_{B}$ are not equivalent because adding a
non-completely-mixed state enables us to distinguish between $\mathcal{W}_{A}$
and $\mathcal{W}_{B}$.

######  Definition A.7 (Strongly indistinguishable / Equivalence).

Consider two $d$-dimensional world models $\mathcal{W}_{A},\mathcal{W}_{B}$
with the same spaces $\mathcal{X},\mathcal{Y},\mathcal{Z},\mathcal{B}$.
$\mathcal{W}_{A}$ and $\mathcal{W}_{B}$ are equivalent or strongly
indistinguishable, denoted as $\mathcal{W}_{A}\equiv\mathcal{W}_{B}$, if for
all extensions of $\mathcal{W}_{A}$,

$\mathcal{W}_{A}^{\prime}=\left(\\{\rho^{A^{\prime}}_{x}\\}_{x\in\mathcal{X}^{\prime}},\\{\mathcal{E}^{A^{\prime}}_{y}\\}_{y\in\mathcal{Y}^{\prime}},\\{\mathcal{M}^{A^{\prime}}_{z}\\}_{z\in\mathcal{Z}^{\prime}}\right)\rhd\mathcal{W}_{A},$
(18)

there exists an extension of $\mathcal{W}_{B}$ with the same action space
$\mathcal{X}^{\prime},\mathcal{Y}^{\prime},\mathcal{Z}^{\prime}$,

$\mathcal{W}_{B}^{\prime}=\left(\\{\rho^{B^{\prime}}_{x}\\}_{x\in\mathcal{X}^{\prime}},\\{\mathcal{E}^{B^{\prime}}_{y}\\}_{y\in\mathcal{Y}^{\prime}},\\{\mathcal{M}^{B^{\prime}}_{z}\\}_{z\in\mathcal{Z}^{\prime}}\right)\rhd\mathcal{W}_{B},$
(19)

such that $\mathcal{W}_{A}^{\prime}$ and $\mathcal{W}_{B}^{\prime}$ are weakly
indistinguishable.

The above definition of equivalence has a natural characterization given by
Theorem A.8. Before stating the theorem, let us recall the definition of
unitary and anti-unitary transformation $U$. Given a $d\times d$ complex
matrix $C$ with a chosen basis. We define $\overline{C}$ to be the matrix
where we take complex conjugation for all entries in $C$. A unitary
transformation $U$ is a $d\times d$ unitary matrix with $U^{-1}=U^{\dagger}$
that transforms $C$ to $UCU^{-1}=UCU^{\dagger}$. An anti-unitary
transformation $A$ is a product of a $d\times d$ unitary matrix $U$ and the
complex conjugation operator $K$ that transforms $C$ to
$ACA^{-1}=U\overline{C}U^{\dagger}$. Theorem A.8 shows that equivalent world
models are related by a unitary or anti-unitary transformation.

######  Theorem A.8 (A characterization of equivalence).

Consider two $d$-dimensional world models with the same spaces
$\mathcal{X},\mathcal{Y},\mathcal{Z},\mathcal{B}$,

$\displaystyle\mathcal{W}_{A}$
$\displaystyle=\left(\\{\rho^{A}_{x}\\}_{x\in\mathcal{X}},\\{\mathcal{E}^{A}_{y}\\}_{y\in\mathcal{Y}},\\{\mathcal{M}^{A}_{z}\\}_{z\in\mathcal{Z}}\right),$
(20) $\displaystyle\mathcal{W}_{B}$
$\displaystyle=\left(\\{\rho^{B}_{x}\\}_{x\in\mathcal{X}},\\{\mathcal{E}^{B}_{y}\\}_{y\in\mathcal{Y}},\\{\mathcal{M}^{B}_{z}\\}_{z\in\mathcal{Z}}\right).$
(21)

$\mathcal{W}_{A}\equiv\mathcal{W}_{B}$ if and only if there exists a unitary
or anti-unitary transformation $U$, such that

$\displaystyle\rho^{B}_{x}=U\rho^{A}_{x}U^{-1},$ $\displaystyle\,\,\forall
x\in\mathcal{X},$ (22)
$\displaystyle\mathcal{E}^{B}_{y}(\cdot)=U\mathcal{E}^{A}_{y}(U^{-1}(\cdot)U)U^{-1},$
$\displaystyle\,\,\forall y\in\mathcal{Y},$ (23) $\displaystyle
M^{B}_{zb}=UM^{A}_{zb}U^{-1},$ $\displaystyle\,\,\forall
z\in\mathcal{Z},b\in\mathcal{B}.$ (24)

We defer the proof to Appendix B. As an example, the following two world
models with the action spaces $\mathcal{X}=\\{0\\},\mathcal{Y}=\\{h,s\\}$ for
Hadamard and Phase gates, $\mathcal{Z}=\\{0\\},$ and outcome space
$\mathcal{B}=\\{0,1\\}$ are equivalent (related by an anti-unitary
transformation $XK$):

$\displaystyle\rho^{A}_{0}$ $\displaystyle=\lvert 0\rangle\\!\langle 0\rvert,$
$\displaystyle\mathcal{E}^{A}_{h}(\rho)$ $\displaystyle=H\rho H^{\dagger},$
$\displaystyle\mathcal{E}^{A}_{s}(\rho)$ $\displaystyle=S\rho S^{\dagger},$
$\displaystyle\mathcal{M}^{A}_{0}$ $\displaystyle=\\{\lvert 0\rangle\\!\langle
0\rvert,\lvert 1\rangle\\!\langle 1\rvert\\},$ (25)
$\displaystyle\rho^{B}_{0}$ $\displaystyle=\lvert 1\rangle\\!\langle 1\rvert,$
$\displaystyle\mathcal{E}^{B}_{h}(\rho)$ $\displaystyle=H\rho H^{\dagger},$
$\displaystyle\mathcal{E}^{B}_{s}(\rho)$ $\displaystyle=S\rho S^{\dagger},$
$\displaystyle\mathcal{M}^{B}_{0}$ $\displaystyle=\\{\lvert 1\rangle\\!\langle
1\rvert,\lvert 0\rangle\\!\langle 0\rvert\\}.$ (26)

The possibility to describe the same physical world by two distinct
descriptions arises from the intrinsic degeneracy in quantum mechanics: the
freedom to choose an arbitrary basis in the Hilbert space (the unitary
relation) or reverse the direction of time (the anti-unitary relation).

##  APPENDIX B A characterization of equivalence: Proof

We will focus on showing that $\mathcal{W}_{A}\equiv\mathcal{W}_{B}$ implies
the existence of a unitary or anti-unitary transformation. The other direction
can be shown easily by noting that for all world model extensions of
$\mathcal{W}_{A}$, we can extend $\mathcal{W}_{B}$ using the same unitary or
anti-unitary transformation $U$.

First, we extend world model $\mathcal{W}_{A}$ to world model
$\mathcal{W}^{\prime}_{A}$ that comes with an expanded state preparation
actions $\mathcal{X}^{\prime}=\mathcal{X}\cup\Omega^{\mathrm{pure}}$ and an
expanded measurement actions
$\mathcal{Z}^{\prime}=\mathcal{Z}\cup\Omega^{\mathrm{pure-POVM}}$. In
particular, $\rho^{A^{\prime}}_{\xi},\forall\xi\in\Omega^{\mathrm{pure}}$
consists of all the $d$-dimensional pure states, and
$\mathcal{M}^{A^{\prime}}_{\zeta},\forall\zeta\in\Omega^{\mathrm{pure-POVM}}$
consists of all the POVMs such that a particular POVM element associated to
$b^{*}\in\mathcal{B}$ is a pure state. The definition of equivalence shows
that there exists an extension $\mathcal{W}^{\prime}_{B}$ with the same action
space as $\mathcal{W}^{\prime}_{A}$ such that $\mathcal{W}^{\prime}_{A}$ and
$\mathcal{W}^{\prime}_{B}$ are weakly indistinguishable, i.e., all experiments
yield the same distribution. The above condition yields the following,

$\operatorname{tr}(M^{A^{\prime}}_{\zeta
b^{*}}\rho^{A^{\prime}}_{\xi})=\operatorname{tr}(M^{B^{\prime}}_{\zeta
b^{*}}\rho^{B^{\prime}}_{\xi}),\forall\xi\in\Omega^{\mathrm{pure}},\zeta\in\Omega^{\mathrm{pure-
POVM}}.$ (27)

This concludes the basic construction of the extended world models.

Recall that $M^{A^{\prime}}_{\zeta b^{*}},\forall\zeta\in\Omega^{\mathrm{pure-
POVM}}$ consists of all pure states. Hence, for each
$\xi\in\Omega^{\mathrm{pure}}$, there exists
$\zeta(\xi)\in\Omega^{\mathrm{pure-POVM}}$ such that $M^{A^{\prime}}_{\zeta
b^{*}}=\rho^{A^{\prime}}_{\xi}$ are the same pure state. We extend
$\rho^{A^{\prime}}_{\xi}$ to an orthonormal set of basis consisting of $d$
pure states
$\\{\rho^{A^{\prime}}_{\xi_{1}},\ldots,\rho^{A^{\prime}}_{\xi_{d}}\\}$, where
$\xi_{1}=\xi$. We have the following from the above construction and Eq. (27),

$\operatorname{tr}\left(M^{A^{\prime}}_{\zeta(\xi_{j})b^{*}}\rho^{A^{\prime}}_{\xi_{i}}\right)=\delta_{ij}=\operatorname{tr}\left(M^{B^{\prime}}_{\zeta(\xi_{j})b^{*}}\rho^{B^{\prime}}_{\xi_{i}}\right),\forall
i,j\in\\{1,\ldots,d\\},$ (28)

where $\delta_{ij}=1$ if $i=j$ and $0$ otherwise. We are now going to utilize
the structure of the quantum states and POVM elements, in particular, a
quantum state is a positive-semidefinite matrix with trace one, and a POVM
element is a positive-semidefinite matrix with eigenvalues less than equal to
one. In particular, we use the following basic lemma that can be established
by induction.

######  Lemma B.1.

Consider $\ell\geq 1$. Given quantum states $\\{\rho_{i}\\}_{i=1,\ldots,\ell}$
and POVM elements $\\{F_{j}\\}_{j=1,\ldots,\ell}$. If
$\operatorname{tr}(F_{j}\rho_{i})=\delta_{ij},\forall
i,j\in\\{1,\ldots,\ell\\}$, then the collection of eigenvectors of $\rho_{i}$
with non-zero eigenvalues over all $i$ from 1 to $\ell$ span a subspace with
dimension at least $\ell$.

###### Proof.

Consider the eigenvectors of $\rho_{i}$ with non-zero eigenvalues to be
$\\{v^{i}_{a}\\}_{a\in A_{i}}$ and the associated eigenvalues be
$\\{p^{i}_{a}\\}_{a\in A_{i}}$, then $\sum_{a\in
A_{i}}p^{i}_{a}(v^{i}_{a})^{\dagger}F_{i}v^{i}_{a}=1$. Since
$0\leq(v^{i}_{a})^{\dagger}F_{i}v_{a}^{i}\leq 1$ (from the definition of POVM
element), $p_{a}^{i}>0$ (we only consider non-zero eigenvalues), $\sum_{a\in
A_{i}}p_{a}^{i}=1$ (from the definition of quantum state), and $\sum_{a\in
A_{i}}p_{a}(v_{a}^{i})^{\dagger}F_{i}v_{a}^{i}=1$, we have

$(v_{a}^{i})^{\dagger}F_{i}v_{a}^{i}=1,\forall a\in A_{i}.$ (29)

Similarly, for all $j\neq i$, $\sum_{a\in
A_{i}}p_{a}(v_{a}^{i})^{\dagger}F_{j}v_{a}^{i}=0$ implies that
$(v_{a}^{i})^{\dagger}F_{j}v_{a}^{i}=0,\forall a\in A_{i}$. Equivalently,

$\sqrt{F_{j}}v_{a}^{i}=0,\forall a\in A_{i},$ (30)

when $i\neq j$. With the basic results given above, we are ready to prove the
statement through induction. The base case $\ell=1$ is trivially true. Suppose
the statement holds for $\ell-1$. We assume that all the eigenvectors of
$\rho_{\ell}$ with non-zero eigenvalues lie in the span of the eigenvectors
with non-zero eigenvalues for $\rho_{i}$ with $i<\ell$. Under this assumption,
for all $a\in A_{\ell}$, there exists a set of coefficients
$\\{c_{i,a^{\prime}}\\}$ such that
$v^{\ell}_{a}=\sum_{i<\ell}\sum_{a^{\prime}\in
A_{i}}c_{i,a^{\prime}}v^{i}_{a^{\prime}}$. This implies that

$1=(v^{\ell}_{a})^{\dagger}F_{\ell}v^{\ell}_{a}=\left(\sum_{i<\ell}\sum_{a^{\prime}\in
A_{i}}c_{i,a^{\prime}}\sqrt{F_{\ell}}v^{i}_{a^{\prime}}\right)^{\dagger}\left(\sum_{i<\ell}\sum_{a^{\prime}\in
A_{i}}c_{i,a^{\prime}}\sqrt{F_{\ell}}v^{i}_{a^{\prime}}\right)=0.$ (31)

The first equality follows from Eq. (29). The last equality follows from Eq.
(30). The contradiction shows that one of the eigenvectors of $\rho_{\ell}$
with non-zero eigenvalues is not in the span of the eigenvectors with non-zero
eigenvalues for $\rho_{i}$ with $i<\ell$. Therefore the statement holds for
$\ell$. ∎

If there exists $k\in\\{1,\ldots,d\\}$, such that the rank of
$M^{B^{\prime}}_{\zeta(\xi_{k})b^{*}}$ is greater than one, then the $d-1$
states $\\{\rho^{B^{\prime}}_{\xi_{i}}\\}_{i\neq k}$ must have their
eigenvectors with non-zero eigenvalues span a $(d-2)$-dimensional subspace to
ensure that
$\operatorname{tr}\left(M^{B^{\prime}}_{\zeta(\xi_{k})b^{*}}\rho^{B^{\prime}}_{\xi_{i}}\right)=0$.
However, from Lemma B.1, the eigenvectors of the $d-1$ states
$\\{\rho^{B^{\prime}}_{\xi_{i}}\\}_{i\neq k}$ with non-zero eigenvalues must
span at least a $(d-1)$-dimensional state space. The contradiction implies
that $M^{B^{\prime}}_{\zeta(\xi_{j})b^{*}},\forall j\in\\{1,\ldots,d\\}$ must
all be rank-one matrices. The condition
$\operatorname{tr}\left(M^{B^{\prime}}_{\zeta(\xi_{1})b^{*}}\rho^{B^{\prime}}_{\xi_{1}}\right)=1$
then implies that $\rho^{B^{\prime}}_{\xi_{1}}$ must be a pure state and
$M^{B^{\prime}}_{\zeta(\xi_{1})b^{*}}=\rho^{B^{\prime}}_{\xi_{1}}$. We have
now shown the following statement:

$\forall\xi\in\Omega^{\mathrm{pure}}$, $\rho^{B^{\prime}}_{\xi}$ is a pure
state and the POVM element
$M^{B^{\prime}}_{\zeta(\xi)b^{*}}=\rho^{B^{\prime}}_{\xi}$.  (32)

An implication of this result is that
$\forall\xi_{1},\xi_{2}\in\Omega^{\mathrm{pure}}$, we have

$\operatorname{tr}\left(\rho^{A^{\prime}}_{\xi_{1}}\rho^{A^{\prime}}_{\xi_{2}}\right)=\operatorname{tr}\left(M^{A^{\prime}}_{\zeta(\xi_{1})b^{*}}\rho^{A^{\prime}}_{\xi_{2}}\right)=\operatorname{tr}\left(M^{B^{\prime}}_{\zeta(\xi_{1})b^{*}}\rho^{B^{\prime}}_{\xi_{2}}\right)=\operatorname{tr}\left(\rho^{B^{\prime}}_{\xi_{1}}\rho^{B^{\prime}}_{\xi_{2}}\right),$
(33)

where the second equation follows from Eq. (27).

We can now construct a transformation $T$ over pure state space by considering
$T(\rho^{A^{\prime}}_{\xi})=\rho^{B^{\prime}}_{\xi},\forall\xi\in\Omega^{\mathrm{pure}}.$
$T$ is a transformation that takes pure states to pure states that satisfies

$\operatorname{tr}\left(\rho^{A^{\prime}}_{\xi_{1}}\rho^{A^{\prime}}_{\xi_{2}}\right)=\operatorname{tr}\left(T(\rho^{A^{\prime}}_{\xi_{1}})T(\rho^{A^{\prime}}_{\xi_{2}})\right),\forall\xi_{1},\xi_{2}\in\Omega^{\mathrm{pure}},$
(34)

as a result of Eq. (33). Such a transformation $T$ is also known as a symmetry
transformation. By Wigner’s theorem, $T$ must take the following form:

$T(\rho)=U\rho U^{-1},$ (35)

where $U$ is a unitary or an anti-unitary transformation. For a proof of
Wigner’s theorem, see Appendix A of Chapter 2 in The Quantum Theory of Fields,
Vol. 1, by Weinberg. The above representation of the symmetry transformation
$T$ yields

$\rho^{B^{\prime}}_{\xi}=U\rho^{A^{\prime}}_{\xi}U^{-1},\,\,\forall\xi\in\Omega^{\mathrm{pure}}.$
(36)

Using Eq. (32), we also have the following relation for a subset of POVM
elements,

$M^{B^{\prime}}_{\zeta(\xi)b^{*}}=UM^{A^{\prime}}_{\zeta(\xi)b^{*}}U^{-1},\,\,\forall\xi\in\Omega^{\mathrm{pure}}.$
(37)

Intuitively, we will now use the pure states
$\rho_{\xi},\forall\xi\in\Omega^{\mathrm{pure}}$ to perform quantum POVM
tomography. Then use the rank-one POVM elements
$M_{\zeta(\xi)b^{*}},\forall\xi\in\Omega^{\mathrm{pure}}$ to perform quantum
state tomography. Finally, we use both $\rho_{\xi}$ and $M_{\zeta(\xi)b^{*}}$
to perform quantum process tomography. Together, we have established the
statement of Theorem A.8.

##### POVMs:

$\forall z\in\mathcal{Z},b\in\mathcal{B}$, we have
$\operatorname{tr}(M^{A^{\prime}}_{zb}\rho^{A^{\prime}}_{\xi})=\operatorname{tr}(M^{B^{\prime}}_{zb}\rho^{B^{\prime}}_{\xi})=\operatorname{tr}(M^{B^{\prime}}_{zb}U\rho^{A^{\prime}}_{\xi}U^{-1}),\forall\xi\in\Omega^{\mathrm{pure}}$.
The first equality follows from the weak indistinguishability between
$\mathcal{W}_{A}^{\prime}$ and $\mathcal{W}_{B}^{\prime}$. The second equality
follows from Eq. (36). We consider a measure $\mu_{\xi}$ over $\xi$ such that
$\rho^{A^{\prime}}_{\xi}$ forms the Haar measure over the pure state space.
The Haar integration formulas $\int
d\mu\lvert\psi\rangle\\!\langle\psi\rvert=I/d$ and $\int
d\mu\lvert\psi\rangle\\!\langle\psi\rvert^{\otimes
2}=(I+\mathrm{SWAP})/(d(d+1))$ give us

$\displaystyle\frac{\operatorname{tr}(M^{A^{\prime}}_{zb})}{d}=\int
d\mu_{\xi}\operatorname{tr}(M^{A^{\prime}}_{zb}\rho^{A^{\prime}}_{\xi})$
$\displaystyle=\int
d\mu_{\xi}\operatorname{tr}(M^{B^{\prime}}_{zb}U\rho^{A^{\prime}}_{\xi}U^{-1})=\frac{\operatorname{tr}(M^{B^{\prime}}_{zb})}{d},$
(38)
$\displaystyle\frac{\operatorname{tr}(M^{A^{\prime}}_{zb})I+M^{A^{\prime}}_{zb}}{d(d+1)}=\int
d\mu_{\xi}\operatorname{tr}(M^{A^{\prime}}_{zb}\rho^{A^{\prime}}_{\xi})\rho^{A^{\prime}}_{\xi}$
$\displaystyle=\int
d\mu_{\xi}\operatorname{tr}(M^{B^{\prime}}_{zb}U\rho^{A^{\prime}}_{\xi}U^{-1})\rho^{A^{\prime}}_{\xi}$
(39)
$\displaystyle=\frac{\operatorname{tr}(M^{B^{\prime}}_{zb})I+U^{-1}M^{B^{\prime}}_{zb}U}{d(d+1)}.$
(40)

Therefore, $\forall
z\in\mathcal{Z},b\in\mathcal{B},M^{B}_{zb}=M^{B^{\prime}}_{zb}=UM^{A^{\prime}}_{zb}U^{-1}=UM^{A}_{zb}U^{-1}$
as stated in Theorem A.8.

##### States:

$\forall x\in\mathcal{X}$, we have
$\operatorname{tr}(M^{A^{\prime}}_{\zeta(\xi)b^{*}}\rho^{A^{\prime}}_{x})=\operatorname{tr}(M^{B^{\prime}}_{\zeta(\xi)b^{*}}\rho^{B^{\prime}}_{x})=\operatorname{tr}(UM^{A^{\prime}}_{\zeta(\xi)b^{*}}U^{-1}\rho^{B^{\prime}}_{x}),\forall\xi\in\Omega^{\mathrm{pure}}$.
The first equality follows from the weak indistinguishability between
$\mathcal{W}_{A}^{\prime}$ and $\mathcal{W}_{B}^{\prime}$. The second equality
follows from Eq. (37). We consider a measure $\mu_{\xi}$ over $\xi$ such that
$M^{A^{\prime}}_{\zeta(\xi)b^{*}}$ forms the Haar measure over the pure state
space. The Haar integration formulas give us

$\displaystyle\frac{I+\rho^{A^{\prime}}_{x}}{d(d+1)}$ $\displaystyle=\int
d\mu_{\xi}\operatorname{tr}(M^{A^{\prime}}_{\zeta(\xi)b^{*}}\rho^{A^{\prime}}_{x})M^{A^{\prime}}_{\zeta(\xi)b^{*}}$
(41) $\displaystyle=\int
d\mu_{\xi}\operatorname{tr}(UM^{A^{\prime}}_{\zeta(\xi)b^{*}}U^{-1}\rho^{B^{\prime}}_{x})M^{A^{\prime}}_{\zeta(\xi)b^{*}}=\frac{I+U^{-1}\rho^{B^{\prime}}_{x}U}{d(d+1)}.$
(42)

Therefore, $\forall
x\in\mathcal{X},\rho^{B}_{x}=\rho^{B^{\prime}}_{x}=U\rho^{A^{\prime}}_{x}U^{-1}=U\rho^{A}_{x}U^{-1}$
as stated in Theorem A.8.

##### CPTP maps:

$\forall y\in\mathcal{Y}$, we have
$\forall\xi_{1},\xi_{2}\in\Omega^{\mathrm{pure}},$

$\displaystyle\operatorname{tr}(M^{A^{\prime}}_{\zeta(\xi_{2})b^{*}}\mathcal{E}^{A^{\prime}}_{y}(\rho^{A^{\prime}}_{\xi_{1}}))$
$\displaystyle=\operatorname{tr}(M^{B^{\prime}}_{\zeta(\xi_{2})b^{*}}\mathcal{E}^{B^{\prime}}_{y}(\rho^{B^{\prime}}_{\xi_{1}}))=\operatorname{tr}(UM^{A^{\prime}}_{\zeta(\xi)b^{*}}U^{-1}\mathcal{E}^{B^{\prime}}_{y}(U\rho^{A^{\prime}}_{\xi_{1}}U^{-1})).$
(43)

From the same analysis for states, we have

$\mathcal{E}^{A^{\prime}}_{y}(\rho^{A^{\prime}}_{\xi_{1}})=U^{-1}\mathcal{E}^{B^{\prime}}_{y}(U\rho^{A^{\prime}}_{\xi_{1}}U^{-1})U.$
(44)

Because $\rho^{A^{\prime}}_{\xi_{1}}$ can be any pure state, we have

$U\mathcal{E}^{A}_{y}(U^{-1}(\cdot)U)U^{-1}=U\mathcal{E}^{A^{\prime}}_{y}(U^{-1}(\cdot)U)U^{-1}=\mathcal{E}^{B^{\prime}}_{y}(\cdot)=\mathcal{E}^{B}_{y}(\cdot)$
(45)

as stated in Theorem A.8.

##  APPENDIX C Foundations for learning intrinsic descriptions

The goal of learning is to conduct experiments to gain knowledge about the
actual world model among a collection of potential world models. Learning
theory provides a formal language to study such an information gathering
process. For learning about a quantum-mechanical world, we would like to know
what quantum-mechanical operations each action
$x\in\mathcal{X},y\in\mathcal{Y},z\in\mathcal{Z}$ corresponds to assuming the
true world model belongs to a specified set of world models.

One should think of the learning process as follows. A classical agent is
given the premise that the true world model belongs to some set of world
models. Then, the classical agent conducts experiments to learn what the true
model is. The set of possible models is called the concept class (often when
each model is a classical Boolean function), hypothesis class (often when each
model is a function from space $X$ to space $Y$), or model class in machine
learning. We will use the less loaded word, model class, to refer to a set of
potential world models. In many branches of mathematics, including learning
theory mohri2018foundations , a class is a set of mathematical objects. We
will follow the same convention here.

######  Definition C.1 (Model class for $d$-dimensional world model).

Given sets $\mathcal{X},\mathcal{Y},\mathcal{Z}$ denoting the action spaces
and set $\mathcal{B}$ denoting the outcome space. A $d$-dimensional model
class $\mathcal{Q}$ over $\mathcal{X},\mathcal{Y},\mathcal{Z},\mathcal{B}$ is
a set $\\{\mathcal{W}\\}$ of $d$-dimensional world model models with the same
spaces $\mathcal{X},\mathcal{Y},\mathcal{Z},\mathcal{B}$.

Recall that some world models are equivalent to one another (describe the same
physical reality) while not being equal (the mathematical description looks
nominally different), i.e., $\mathcal{W}_{1}\neq\mathcal{W}_{2}$ but
$\mathcal{W}_{1}\equiv\mathcal{W}_{2}$. This is intrinsic to the description
of quantum mechanics as we have shown in Theorem A.8. When a model class
contains two world models that are nominally different but physically the
same, we say the model class is redundant. A formal definition is given below.

######  Definition C.2 (Redundant model class).

Given sets $\mathcal{X},\mathcal{Y},\mathcal{Z},\mathcal{B}$ and a model class
$\mathcal{Q}=\\{\mathcal{W}\\}$ over
$\mathcal{X},\mathcal{Y},\mathcal{Z},\mathcal{B}$. $\mathcal{Q}$ is redundant
if $\exists\,\mathcal{W}_{1}\neq\mathcal{W}_{2}\in\mathcal{Q}$,
$\mathcal{W}_{1}\equiv\mathcal{W}_{2}$.

Another basic concept about model classes is that two model classes could be
equivalent to one another as a result of the equivalence of world models. For
example, if we have three equivalent world models
$\mathcal{W}\equiv\mathcal{W}_{1}\equiv\mathcal{W}_{2}$, then the model class
$\mathcal{Q}=\\{\mathcal{W}\\}$ contains the same set of equivalent world
models as $\tilde{\mathcal{Q}}=\\{\mathcal{W}_{1},\mathcal{W}_{2}\\}$. Hence,
we say the two model classes are equivalent. We give the formal definition of
equivalent model classes below.

######  Definition C.3 (Equivalent model classes).

Given sets $\mathcal{X},\mathcal{Y},\mathcal{Z},\mathcal{B}$. Model classes
$\mathcal{Q},\tilde{\mathcal{Q}}$ over
$\mathcal{X},\mathcal{Y},\mathcal{Z},\mathcal{B}$ are equivalent if and only
if
$\forall\mathcal{W}\in\mathcal{Q},\exists\tilde{\mathcal{W}}\in\tilde{\mathcal{Q}},\mathcal{W}\equiv\tilde{\mathcal{W}}$,
and
$\forall\tilde{\mathcal{W}}\in\tilde{\mathcal{Q}},\exists\mathcal{W}\in\mathcal{Q},\mathcal{W}\equiv\tilde{\mathcal{W}}$.

A redundant model class is not preferred as the same physical reality is
described by two different representations. However, the following basic
proposition shows that a redundant model class is equivalent to a non-
redundant model class. For example, if
$\mathcal{Q}=\\{\mathcal{W}_{1},\mathcal{W}_{2},\mathcal{W}_{3}\\}$, where
$\mathcal{W}_{1}\equiv\mathcal{W}_{2}$ and
$\mathcal{W}_{1}\not\equiv\mathcal{W}_{3}$, then we have $\mathcal{Q}$ is
equivalent to $\mathcal{Q}^{\prime}=\\{\mathcal{W}_{1},\mathcal{W}_{3}\\}$.

######  Proposition C.4.

Given sets $\mathcal{X},\mathcal{Y},\mathcal{Z},\mathcal{B}$ and a model class
$\mathcal{Q}=\\{\mathcal{W}\\}$ over
$\mathcal{X},\mathcal{Y},\mathcal{Z},\mathcal{B}$. There exists a non-
redundant model class $\tilde{\mathcal{Q}}$ over
$\mathcal{X},\mathcal{Y},\mathcal{Z},\mathcal{B}$, such that
$\tilde{\mathcal{Q}}$ is equivalent to $\mathcal{Q}$.

###### Proof.

We partition all world models in $\mathcal{Q}$ into equivalence classes, where
all models in the same equivalence class are equivalent to one another, and
those that are in different equivalence classes are not equivalent. We choose
one representative from each equivalence class of world models in
$\mathcal{Q}$. We define $\tilde{\mathcal{Q}}$ to be the set of the
representatives. $\tilde{\mathcal{Q}}$ is equivalent to ${\mathcal{Q}}$ and
$\tilde{\mathcal{Q}}$ is non-redundant. ∎

After defining and illustrating some basic properties of model classes, we
consider the learnability of a model class. We say a model class is learnable
if for any world model $\mathcal{W}$ in the model class, the classical agent
can identify the physical operations to an arbitrarily small error up to a
global unitary or anti-unitary transformation using a finite number of
experiments. The unitary or anti-unitary transformation $U$ is necessary as
Theorem A.8 states that two world models related by $U$ are equivalent and
describe the same physical reality. The transformation $U$ corresponds to a
change of basis in the quantum Hilbert space and potentially followed by a
complex conjugation operation.

######  Definition C.5 (Learnability of a model class).

Given sets $\mathcal{X},\mathcal{Y},\mathcal{Z},\mathcal{B}$ and a model class
$\mathcal{Q}=\\{\mathcal{W}\\}$ for $d$-dimensional world models over
$\mathcal{X},\mathcal{Y},\mathcal{Z},\mathcal{B}$. The model class
$\mathcal{Q}$ is learnable if
$\forall\,\epsilon,\delta>0,\forall\mathcal{W}\in\mathcal{Q}$, there exists a
unitary or anti-unitary transformation $U$,

  * •

$\forall\,x\in\mathcal{X}$, with probability $\geq 1-\delta$, a classical
agent can conduct finitely many experiments as defined in Def. A.2 to output
$\tilde{\rho}_{x}$ satisfying
$\left\lVert\rho_{x}-U\tilde{\rho}_{x}U^{-1}\right\rVert_{1}\leq\epsilon$,

  * •

$\forall\,y\in\mathcal{Y}$, with probability $\geq 1-\delta$, a classical
agent can conduct finitely many experiments as defined in Def. A.2 to output
$\tilde{\mathcal{E}}_{y}$ satisfying
$\left\lVert\mathcal{E}_{y}-U\tilde{\mathcal{E}}_{y}(U^{-1}(\cdot)U)U^{-1}\right\rVert_{\diamond}\leq\epsilon$.

  * •

$\forall\,z\in\mathcal{Z}$, $b\in\mathcal{B}$, with probability $\geq
1-\delta$, a classical agent can conduct finitely many experiments as defined
in Def. A.2 to output $\tilde{M}_{zb}$ satisfying $\left\lVert
M_{zb}-U\tilde{M}_{zb}U^{-1}\right\rVert_{1}\leq\epsilon$.

In many scenarios, it is too much to ask for the ability to learn everything
about a world model, i.e., all initial states, CPTP maps, and measurements.
For example, we might only want to predict a property of one of the possible
initial states, such as its purity. Predicting properties can often be
significantly more efficient than learning the full description
huang2020predicting . Furthermore, even if a model class $\mathcal{Q}$ is
unlearnable according to the above definition, we may still be able to predict
some properties.

######  Definition C.6 (Predictability of a property).

Given sets $\mathcal{X},\mathcal{Y},\mathcal{Z},\mathcal{B}$, a model class
$\mathcal{Q}=\\{\mathcal{W}\\}$ for $d$-dimensional world models over
$\mathcal{X},\mathcal{Y},\mathcal{Z},\mathcal{B}$, and a function $f$ that
maps a world model $\mathcal{W}$ to a property represented by a value in
$\mathbb{R}$. The property $f$ is predictable in the model class $\mathcal{Q}$
if $\forall\,\epsilon,\delta>0,\forall\mathcal{W}\in\mathcal{Q}$, with
probability $\geq 1-\delta$, a classical agent can conduct finitely many
experiments as defined in Def. A.2 to output $\tilde{o}\in\mathbb{R}$
satisfying $|f(\mathcal{W})-\tilde{o}|\leq\epsilon$.

##  APPENDIX D A general theorem for learning intrinsic physical descriptions

The goal of this appendix is to prove the following theorem. Here, we consider
a model class $\mathcal{Q}$ such that for any candidate world model
$\mathcal{W}$ in $\mathcal{Q}$, there exists an action to prepare a pure
state, a set of actions for implementing a universal set of unitaries, and an
action for implementing a nontrivial POVM. A trivial POVM produces a
measurement outcome independent of the input state. The actions that satisfy
the above conditions could be different for different candidate world model
$\mathcal{W}$. The classical agent has no knowledge of what these actions are
and what the corresponding physical operations are. Furthermore the model
class $\mathcal{Q}$ could contain uncountably many candidate world models. The
theorem states that even without knowing what any action is, the classical
agent can learn the intrinsic descriptions of all actions when the actions
enable the exploration of the entire quantum state space.

######  Theorem D.1 (Restatement of Theorem 2).

Given finite sets $\mathcal{X},\mathcal{Y},\mathcal{Z},\mathcal{B}$. Consider
a $d$-dimensional model class $\mathcal{Q}$ over action spaces
$\mathcal{X},\mathcal{Y},\mathcal{Z}$ and outcome space $\mathcal{B}$. Suppose
that for all
$\mathcal{W}=(\\{\rho_{x}\\}_{x\in\mathcal{X}},\\{\mathcal{E}_{y}\\}_{y\in\mathcal{Y}},\\{\mathcal{M}_{x}\\}_{x\in\mathcal{Z}})\in\mathcal{Q}$,

  * •

$\exists x\in\mathcal{X}$, $\rho_{x}$ is pure.

  * •

$\exists y_{1},\ldots,y_{k}\in\mathcal{Y}$,
$\mathcal{E}_{y_{1}},\ldots\mathcal{E}_{y_{k}}$ constitute a universal set of
unitary transformations.

  * •

$\exists z\in\mathcal{Z}$, $\mathcal{M}_{z}$ has at least one element not
proportional to identity.

Then, $\mathcal{Q}$ is learnable.

To prove Theorem D.1, we give a learning algorithm such that for each world
model $\mathcal{W}$ in $\mathcal{Q}$, the algorithm learns a world model
$\tilde{\mathcal{W}}$ that satisfies $\tilde{\mathcal{W}}\equiv{\mathcal{W}}$
approximately, i.e., all physical descriptions of the actions in
$\mathcal{X},\mathcal{Y},\mathcal{Z}$ are related by a global unitary or anti-
unitary transformation (see Theorem A.8). The approximation error can be made
arbitrarily close to zero as the algorithm conducts more experiments. From
Definition C.5 on learnability of model class, we have $\mathcal{Q}$ is
learnable.

In the following, we present an important lemma used in the proof. Then, we
separate each step of the learning algorithm to learn the actions in the world
model into subsections. The proof will consider the dimension $d$ to be a
constant.

###  D.1 A lemma on generating Haar-random unitaries

The proof of Theorem D.1 relies on the following lemma about the generation of
approximate Haar measure using a universal set of unitaries. Here, we say
$U_{1},\ldots,U_{k}$ forms a universal set of unitaries if the set
$\mathcal{U}=\\{U_{1},\ldots,U_{k},U_{1}^{-1},\ldots,U_{k}^{-1}\\}$ generates
a dense subgroup of the special unitary group. We follow the standard
terminology, where the subgroup generated by the set $\mathcal{U}$ is the
group consisting of elements that can be written as a product of elements in
$\mathcal{U}$.

######  Definition D.2 (Real-valued Lipschitz function).

A real-valued Lipschitz function $\phi$ over the special unitary group
satisfies $|\phi(U)-\phi(V)|\leq\left\lVert U-V\right\rVert_{F}$ for all
unitaries $U,V$.

######  Lemma D.3 (Random unitaries approximately form Haar measure).

Given $k$ unitaries $U_{1},\ldots,U_{k}$ that form a universal set of
unitaries. For any $\epsilon>0$ and any real-valued Lipschitz function $\phi$
over the special unitary group, there exists $L>0$, such that $\forall\ell\geq
L$,

$\left|\frac{1}{k^{\ell}}\sum_{i_{1}=1}^{k}\ldots\sum_{i_{\ell}=1}^{k}\phi(U_{i_{1}}\ldots
U_{i_{\ell}})-\int d\mu_{\mathrm{Haar}}(U)\phi(U)\right|<\epsilon,$ (46)

where $\mu_{\mathrm{Haar}}$ is the Haar measure (uniform distribution) over
the special unitary group.

We prove Lemma D.3 using a theorem given in Varj2012RandomWI , which is a
corollary of a spectral gap theorem regarding semi-simple compact connected
Lie group. Before stating the theorem, we give a few definitions. Consider a
semi-simple compact connected Lie group $G$ endowed with the bi-invariant
Riemannian metric. The bi-invariant Riemannian metric gives a distance
$d(g,h),\forall g,h\in G$. We define $\mathrm{Lip}(G)$ to be the set of
functions $\\{\phi\\}:G\rightarrow\mathbb{R}$ such that
$\forall\phi\in\mathrm{Lip}(G)$, $\sup_{g\neq h\in
G}\frac{|\phi(g)-\phi(h)|}{d(g,h)}<\infty$. For $\phi\in\mathrm{Lip}(G)$, we
consider $\left\lVert\phi\right\rVert_{\mathrm{Lip}}=\sup_{g\neq h\in
G}\frac{|\phi(g)-\phi(h)|}{d(g,h)}$. We also define $\mu_{\mathrm{Haar}}$ to
be the Haar measure over $G$. The root second moment of a function
$\phi:G\rightarrow\mathbb{R}$ is given by
$\left\lVert\phi\right\rVert_{2}=\sqrt{\int|\phi(x)|^{2}d\mu_{\mathrm{Haar}}(x)}$.
For a probability measure $\mu$, consider $\tilde{\mu}$ to be the probability
measure such that

$\int f(x)d\tilde{\mu}(x)=\int f(x^{-1})d\mu(x)$ (47)

for all continuous function $f$. One can think of $\tilde{\mu}$ as the
probability distribution over the inverse of the probability measure $\mu$.
For example, a uniform distribution over $U_{1},\ldots,U_{k}$ yields a uniform
distribution over $U_{1}^{-1},\ldots,U_{k}^{-1}$. Consider the convolution
between two probability measure $\mu$ and $\nu$ to be a probability measure,

$(\mu\ast\nu)(g)=\sum_{h\in G}\mu(gh^{-1})\nu(h).$ (48)

One can interpret $\mu\ast\nu$ as the probability distribution of $h\ell$ when
we sample $h$ according to $\mu$ and $\ell$ according to $\nu$. For example, a
convolution of the uniform distribution over $U_{1},\ldots,U_{k}$ with itself
would be a uniform distribution over $U_{i}U_{j},\forall i,j=1,\ldots,k$.
Also, for a probability measure $\mu$, we consider the support of $\mu$,
denoted as $\mathrm{supp}(\mu)$, to be the intersection of every set $A$ such
that $\mu(A^{c})=0$.

######  Theorem D.4 (Corollary 7 in Varj2012RandomWI ).

Let $G$ be a semi-simple compact connected Lie group endowed with the bi-
invariant Riemannian metric, and $\mu$ be a probability measure on $G$. If
$\mathrm{supp}(\tilde{\mu}\ast\mu)$ generates a dense subgroup in $G$, then
$\forall\psi_{A}\in\mathrm{Lip}(G)$ with
$\left\lVert\psi_{A}\right\rVert_{2}=1$ and
$\int\psi_{A}(x)d\mu_{\mathrm{Haar}}(x)=0$, we have

$\left\lVert\psi_{B}\right\rVert_{2}<1-\frac{c}{\log^{A}(\left\lVert\psi_{A}\right\rVert_{\mathrm{Lip}}+2)},$
(49)

where $\psi_{B}(g)=\int\psi_{A}(h^{-1}g)d\mu(h)$, $A\leq 2$ depends on $G$,
and $c>0$ depends only on $\mu$.

We are now ready to prove Lemma D.3. We apply Theorem D.4 by considering $G$
to be the special unitary group with a representation in the vector space of
matrices, and consider the bi-invariant Riemannian metric to be the Euclidean
metric in the matrix space. The distance $d(U,V)$ on $G$ is the the length of
the shortest path from $U$ to $V$ on the special unitary group. Because we
consider a constant dimensional special unitary group, we have

$\left\lVert U-V\right\rVert_{F}\leq d(U,V)\leq C\left\lVert
U-V\right\rVert_{F},$ (50)

for a constant $C\geq 1$, where $\left\lVert
X\right\rVert_{F}=\sqrt{\operatorname{tr}(X^{\dagger}X)}$. Hence, any real-
valued function $\phi$ satisfying $|\phi(U)-\phi(V)|\leq\left\lVert
U-V\right\rVert_{F}$ for all unitaries $U,V$ is in $\mathrm{Lip}(G)$ with the
Lipschitz norm $\left\lVert\phi\right\rVert_{\mathrm{Lip}}\leq 1$. Because
$\phi$ is Lipschitz continuous, $\left\lVert\phi\right\rVert_{2}<\infty$.

###### Proof for Lemma D.3.

For the edge case where $\phi$ is a constant function, the lemma trivially
holds. Let $\mu$ be the uniform distribution over
$U_{1}^{-1},\ldots,U_{k}^{-1}$. The probability distribution $\tilde{\mu}$
over the inverse of $\mu$ is the uniform distribution over
$U_{1},\ldots,U_{k}$. $\tilde{\mu}\ast\mu$ is the uniform distribution over
$U_{i}U_{j}^{-1},\forall i,j=1,\ldots,k$, and
$\mathrm{supp}(\tilde{\mu}\ast\mu)$ is $\\{U_{i}U_{j}^{-1},\forall
i,j=1,\ldots,k\\}$, which generates a dense subgroup of the special unitary
group. Because $\phi$ is not a constant function, we can let $\psi_{1}$ be

$\psi_{1}(g)=\frac{\phi(g)-\int\phi(U)d\mu_{\mathrm{Haar}}(U)}{\left\lVert\phi-\int\phi(U)d\mu_{\mathrm{Haar}}(U)\right\rVert_{2}},\,\,\forall
g\in G,$ (51)

which satisfies $\left\lVert\psi_{1}\right\rVert_{2}=1$,
$\int\psi_{1}(x)d\mu_{\mathrm{Haar}}(x)=0$, and

$\left\lVert\psi_{1}\right\rVert_{\mathrm{Lip}}\leq\left\lVert\phi-\int\phi(U)d\mu_{\mathrm{Haar}(U)}\right\rVert_{2}\left\lVert\phi\right\rVert_{\mathrm{Lip}}\leq\left\lVert\phi-\int\phi(U)d\mu_{\mathrm{Haar}}(U)\right\rVert_{2}.$
(52)

For any $\ell>1$, we define

$\psi_{\ell}(g)=\frac{\frac{1}{k^{\ell}}\sum_{i_{1}=1}^{k}\ldots\sum_{i_{\ell}=1}^{k}\phi(U_{i_{1}}\ldots
U_{i_{\ell}}g)-\int\phi
d\mu_{\mathrm{Haar}}}{\left\lVert\phi-\int\phi(U)d\mu_{\mathrm{Haar}}\right\rVert_{2}},\,\,\forall
g\in G,$ (53)

which satisfies $\int\psi_{\ell}(x)d\mu_{\mathrm{Haar}}(x)=0$ and

$\displaystyle|\psi_{\ell}(g_{1})-\psi_{\ell}(g_{2})|$
$\displaystyle\leq\int\left|\psi_{\ell-1}(h^{-1}g_{1})-\psi_{\ell-1}(h^{-1}g_{2})\right|d\mu(h)$
(54) $\displaystyle\leq\left\lVert\psi_{\ell-1}\right\rVert_{\mathrm{Lip}}\int
d(h^{-1}g_{1},h^{-1}g_{2})d\mu(h)\leq\left\lVert\psi_{\ell-1}\right\rVert_{\mathrm{Lip}}d(g_{1},g_{2}).$
(55)

Hence,
$\left\lVert\psi_{\ell}\right\rVert_{\mathrm{Lip}}\leq\left\lVert\psi_{\ell-1}\right\rVert_{\mathrm{Lip}}\leq\left\lVert\psi_{1}\right\rVert_{\mathrm{Lip}}$
for any $\ell>1$.

We can apply Theorem D.4 with the probability measure $\mu$ defined above,
$\psi_{A}=\psi_{\ell-1}/\left\lVert\psi_{\ell-1}\right\rVert_{2}$, and
$\psi_{B}=\psi_{\ell}/\left\lVert\psi_{\ell-1}\right\rVert_{2}$ to obtain

$\displaystyle\left\lVert\psi_{\ell}\right\rVert_{2}$
$\displaystyle\leq\left(1-\frac{c}{\log^{A}(\left\lVert\psi_{\ell-1}\right\rVert_{\mathrm{Lip}}/\left\lVert\psi_{\ell-1}\right\rVert_{2}+2)}\right)\left\lVert\psi_{\ell-1}\right\rVert_{2}$
(56)
$\displaystyle\leq\left(1-\frac{c}{\log^{A}(\left\lVert\psi_{1}\right\rVert_{\mathrm{Lip}}/\left\lVert\psi_{\ell-1}\right\rVert_{2}+2)}\right)\left\lVert\psi_{\ell-1}\right\rVert_{2}.$
(57)

The second inequality follows from
$\left\lVert\psi_{\ell}\right\rVert_{\mathrm{Lip}}\leq\left\lVert\psi_{1}\right\rVert_{\mathrm{Lip}}$.
By solving the above recursive relation, given any $\tilde{\epsilon}>0$, there
exists a large enough $L$ such that

$\left\lVert\psi_{\ell}\right\rVert_{2}\leq\tilde{\epsilon},\,\,\forall\ell\geq
L.$ (58)

From the definition of $\psi_{\ell}$ and the fact that $\phi$ is Lipschitz-
continuous over the special unitary group, $\forall\epsilon>0$, there exists
$L>0$, such that $\forall\ell\geq L$, we have

$\left|\frac{1}{k^{\ell}}\sum_{i_{1}=1}^{k}\ldots\sum_{i_{\ell}=1}^{k}\phi(U_{i_{1}}\ldots
U_{i_{\ell}}g)-\int\phi d\mu_{\mathrm{Haar}}\right|\leq\epsilon,\,\,\forall
g\in G.$ (59)

By setting $g=I$, we conclude the proof of Lemma D.3. ∎

###  D.2 The precision parameter

Consider the precision parameter $\eta$ to be a fixed number at the start of
the learning algorithm. Each subsection below corresponds to a set of
subroutines in the learning algorithm that depends on $\eta$. After completion
of all subroutines, the algorithm restarts with $\eta\leftarrow\eta/2$.

###  D.3 Testing identity and unitarity

We first present the subroutine for finding all actions
$y_{1},\ldots,y_{k^{\prime}}$ that correspond to unitary transformations,
which is presented in the following lemma.

######  Lemma D.5 (Unitary identification).

For a sufficiently small $\eta$, there is a subroutine that returns
$y_{1},\ldots,y_{k^{\prime}}$ such that
${{\mathcal{E}}}_{y_{1}},\ldots,{{\mathcal{E}}}_{y_{k^{\prime}}}$ are all the
unitary transformations in $\\{{{\mathcal{E}}}_{y}\\}_{y\in\mathcal{Y}}$.

###### Proof.

Consider an arbitrary norm $\left\lVert\cdot\right\rVert$ over the space of
maps over quantum states. Assume that we have a subroutine for estimating how
close a composition of CPTP maps
$\mathcal{E}_{y_{1}^{\prime}}\circ\ldots\circ\mathcal{E}_{y_{\ell}^{\prime}}$
is to an identity under the norm $\left\lVert\cdot\right\rVert$. The
subroutine will be presented in Lemma D.6. Recall that in the finite set
$\mathcal{Y}$, there are some CPTP maps
$\mathcal{E}_{y_{1}},\ldots,\mathcal{E}_{y_{k}}$ that correspond to unitary
transformations. We define

$\mathcal{Y}_{\mathrm{unitary}}=\left\\{{{\mathcal{E}}}_{y}^{\dagger}{{\mathcal{E}}}_{y}=I|\forall
y\in\mathcal{Y}\right\\}.$ (60)

We now present a subroutine that returns $\mathcal{Y}_{\mathrm{unitary}}$. The
proof of this lemma relies on a basic geometric fact about unitary: the only
CPTP maps with some CPTP maps as their inverse are unitaries.

For each $y\in\mathcal{Y}$, we consider composing $\mathcal{E}_{y}$ with
$\mathcal{E}_{y_{1}^{\prime}}\circ\ldots\circ\mathcal{E}_{y_{\ell-1}^{\prime}}$
for $y_{1}^{\prime},\ldots,y_{\ell-1}^{\prime}\in\mathcal{Y}$ and $\ell\leq
1/\eta$. The subroutine returns all actions $y\in\mathcal{Y}$ such that

$\min_{y_{1}^{\prime},\ldots,y_{\ell-1}^{\prime}}\left\lVert\mathcal{E}_{y_{1}^{\prime}}\circ\ldots\circ\mathcal{E}_{y_{\ell-1}^{\prime}}\circ\mathcal{E}_{y}-I\right\rVert\leq\eta.$
(61)

If $\mathcal{E}_{y}$ is a unitary transformation, we can find some
$y_{1}^{\prime},\ldots,y_{\ell-1}^{\prime}$ such that
$\mathcal{E}_{y_{1}^{\prime}}\circ\ldots\circ\mathcal{E}_{y_{\ell-1}^{\prime}}\circ\mathcal{E}_{y}$
is arbitrarily close to the identity under $\left\lVert\cdot\right\rVert$ as
$\eta$ goes to zero. If $\mathcal{E}_{y}$ is not a unitary transformation,
then for all $y_{1}^{\prime},\ldots,y_{\ell-1}^{\prime}$ and $\eta>0$, there
is a lower bound to how close
$\mathcal{E}_{y_{1}^{\prime}}\circ\ldots\circ\mathcal{E}_{y_{\ell-1}^{\prime}}\circ\mathcal{E}_{y}$
could be to the identity under $\left\lVert\cdot\right\rVert$. As a result,
when $\eta$ becomes small enough, the set of actions returned by the learning
algorithm will be equal to $\mathcal{Y}_{\mathrm{unitary}}$. ∎

######  Lemma D.6 (Identity testing).

For a sufficiently small $\eta$ and any $\epsilon>0$, there exists a norm
$\left\lVert\cdot\right\rVert$ over the space of maps over quantum states and
a subroutine that takes in $y_{1}^{\prime},\ldots,y_{\ell}^{\prime}$ and
returns an estimate for

$\left\lVert\mathcal{E}_{y_{1}^{\prime}}\circ\ldots\circ\mathcal{E}_{y_{\ell}^{\prime}}-I\right\rVert$
(62)

up to an additive error $\epsilon$ with high probability.

###### Proof.

The central property is that an identity map
$\mathcal{E}_{y_{1}^{\prime}}\circ\ldots\circ\mathcal{E}_{y_{\ell}^{\prime}}$
satisfies

$\displaystyle\operatorname{tr}(M_{zb}\left((\mathcal{E}_{y_{2k}}\circ\ldots\circ\mathcal{E}_{y_{k+1}})\circ(\mathcal{E}_{y_{1}^{\prime}}\circ\ldots\circ\mathcal{E}_{y_{\ell}^{\prime}})\circ(\mathcal{E}_{y_{k}}\circ\ldots\circ\mathcal{E}_{y_{1}})\right)(\rho_{x}))$
(63)
$\displaystyle=\operatorname{tr}(M_{zb}\left((\mathcal{E}_{y_{2k}}\circ\ldots\circ\mathcal{E}_{y_{k+1}})\circ(\mathcal{E}_{y_{k}}\circ\ldots\circ\mathcal{E}_{y_{1}})\right)(\rho_{x})),$
(64)

for all $x\in\mathcal{X},y_{1},\ldots
y_{2k}\in\mathcal{Y}\cup\\{\mathrm{NULL}\\},z\in\mathcal{Z},b\in\mathcal{B}$.
We denote the first expression as $h(x,y_{1},\ldots,y_{2k},z,b)$ and the
second expression as $h_{0}(x,y_{1},\ldots,y_{2k},z,b)$. Here, the action
$y=\mathrm{NULL}$ corresponds to not implementing the action in the experiment
defined in Def. A.2. The learning algorithm considers all possible
compositions of maps with $2k=\lceil 1/\eta\rceil$, where $\eta$ is the
precision parameter.

The learning algorithm can obtain estimates for $h(x,y_{1},\ldots,y_{2k},z,b)$
and $h_{0}(x,y_{1},\ldots,y_{2k},z,b)$ by running the corresponding
experiments with $K$ repetitions. By Hoeffding’s inequality, with
$K=\mathcal{O}(\log(1/\delta)/\epsilon^{2})$, the algorithm can estimate
$h(x,y_{1},\ldots,y_{2k},z,b)$ and $h_{0}(x,y_{1},\ldots,y_{2k},z,b)$ to
$\epsilon$-error with probability at least $1-\delta$. We consider $K$ to be
large enough such that the algorithm outputs an estimate for the quantity $A$
defined as

$\displaystyle A$ $\displaystyle=\max_{x\in\mathcal{X},y_{1},\ldots
y_{2k}\in\mathcal{Y}\cup\\{\mathrm{NULL}\\},z\in\mathcal{Z},b\in\mathcal{B}}\left|h(x,y_{1},\ldots,y_{2k},z,b)-h_{0}(x,y_{1},\ldots,y_{2k},z,b)\right|$
(65) $\displaystyle=\max_{x\in\mathcal{X},y_{1},\ldots
y_{2k}\in\mathcal{Y}\cup\\{\mathrm{NULL}\\},z\in\mathcal{Z},b\in\mathcal{B}}$
(66)
$\displaystyle\quad\quad\quad\quad\quad\left|\operatorname{tr}(M_{zb}\left((\mathcal{E}_{y_{2k}}\circ\ldots\circ\mathcal{E}_{y_{k+1}})\circ(\mathcal{E}_{y_{1}^{\prime}}\circ\ldots\circ\mathcal{E}_{y_{\ell}^{\prime}}-I)\circ(\mathcal{E}_{y_{k}}\circ\ldots\circ\mathcal{E}_{y_{1}})\right)(\rho_{x}))\right|.$
(67)

up to $\epsilon$-error with high probability. We can interpret $A$ as a norm
$\left\lVert\cdot\right\rVert$ over the space of maps over quantum states when
$\eta$ is sufficiently small,

$A=\left\lVert\mathcal{E}_{y_{1}^{\prime}}\circ\ldots\circ\mathcal{E}_{y_{\ell}^{\prime}}-I\right\rVert.$
(68)

Positive definiteness follows from the fact that $A$ is zero when
$\mathcal{E}_{y_{1}^{\prime}}\circ\ldots\circ\mathcal{E}_{y_{\ell}^{\prime}}$
is an identity; and $A$ must be greater than zero for a sufficiently small
$\eta$ if
$\mathcal{E}_{y_{1}^{\prime}}\circ\ldots\circ\mathcal{E}_{y_{\ell}^{\prime}}$
is not equal to an identity from Lemma D.7. The two other conditions, absolute
homogeneity and subadditivity, both follow from the definition of $A$ in Eq.
(67). ∎

######  Lemma D.7 (Characterization of $A$).

For a sufficiently small $\eta$, we have

$\displaystyle A$ $\displaystyle=\max_{x\in\mathcal{X},y_{1},\ldots
y_{2k}\in\mathcal{Y}\cup\\{\mathrm{NULL}\\},z\in\mathcal{Z},b\in\mathcal{B}}$
(69)
$\displaystyle\quad\quad\quad\quad\quad\left|\operatorname{tr}(M_{zb}\left((\mathcal{E}_{y_{2k}}\circ\ldots\circ\mathcal{E}_{y_{k+1}})\circ(\mathcal{E}_{y_{1}^{\prime}}\circ\ldots\circ\mathcal{E}_{y_{\ell}^{\prime}}-I)\circ(\mathcal{E}_{y_{k}}\circ\ldots\circ\mathcal{E}_{y_{1}})\right)(\rho_{x}))\right|>0$
(70)

if
$\mathcal{E}_{y_{1}^{\prime}}\circ\ldots\circ\mathcal{E}_{y_{\ell}^{\prime}}$
is not equal to an identity.

###### Proof.

This claim follows from the assumption that there exists a universal set of
unitaries and a pure state in the action space. Hence, we can generate a pure
state
$\left(\mathcal{E}_{y_{k}}\circ\ldots\circ\mathcal{E}_{y_{1}})\right)(\rho_{x})$
such that

$(\mathcal{E}_{y_{1}^{\prime}}\circ\ldots\circ\mathcal{E}_{y_{\ell}^{\prime}})((\mathcal{E}_{y_{k}}\circ\ldots\circ\mathcal{E}_{y_{1}})(\rho_{x}))\neq(\mathcal{E}_{y_{k}}\circ\ldots\circ\mathcal{E}_{y_{1}})(\rho_{x}).$
(71)

From the assumption, we can also find a POVM $\mathcal{M}_{z}$ such that one
of the POVM element $M_{zb}$ is not proportional to the identity. There always
exists a unitary $U_{1}$ that diagonalizes the Hermitian matrix

$D\equiv(\mathcal{E}_{y_{1}^{\prime}}\circ\ldots\circ\mathcal{E}_{y_{\ell}^{\prime}})((\mathcal{E}_{y_{k}}\circ\ldots\circ\mathcal{E}_{y_{1}})(\rho_{x}))-(\mathcal{E}_{y_{k}}\circ\ldots\circ\mathcal{E}_{y_{1}})(\rho_{x}),$
(72)

such that the eigenvalues $\\{\lambda^{D}_{i}\\}$ are sorted from a greater
value to a smaller value. Also, there exists a unitary $U_{2}$ that
diagonalizes $M_{zb}$ with eigenvalues $\\{\lambda^{M_{zb}}_{i}\\}$ sorted
from large to small. We have

$\operatorname{tr}(U_{2}M_{zb}U_{2}^{\dagger}U_{1}DU_{1}^{\dagger})=\sum_{i=1}^{d}\lambda^{M_{zb}}_{i}\lambda^{D}_{i}.$
(73)

Because $D\neq 0$ and $\operatorname{tr}(D)=0$, the largest eigenvalue
$\lambda^{D}_{1}>0$, the smallest eigenvalue $\lambda^{D}_{d}<0$, and
$\sum_{i=1}^{d}\lambda^{D}_{i}=0$. We can thus find an index $k\geq 2$ such
that $\lambda^{D}_{i}>0,\forall i<k$ and $\lambda^{D}_{i}\leq 0,\forall i\geq
k$. Since $M_{zb}\succeq 0$ is not proportional to identity, we have the
largest eigenvalue $\lambda^{M_{zb}}_{1}>\lambda^{M_{zb}}_{d}\geq 0$.

$\sum_{i=1}^{d}\lambda^{M_{zb}}_{i}\lambda^{D}_{i}=\sum_{i=1}^{d}(\lambda^{M_{zb}}_{i}-\lambda^{M_{zb}}_{k})\lambda^{D}_{i}>0.$
(74)

When the precision parameter $\eta$ is smaller enough,
$(\mathcal{E}_{y_{2k}}\circ\ldots\circ\mathcal{E}_{y_{k+1}})$ can approximate
any unitary with a properly chosen $y_{k+1},\ldots,y_{2k}$ because there
exists a universal set of unitaries by choosing the proper actions. Hence,
there exists $x\in\mathcal{X},y_{1},\ldots
y_{2k}\in\mathcal{Y}\cup\\{\mathrm{NULL}\\},z\in\mathcal{Z},b\in\mathcal{B}$
such that $h(x,y_{1},\ldots,y_{2k},z,b)>h_{0}(x,y_{1},\ldots,y_{2k},z,b)$.
Together, we see that $A$ must be greater than zero if
$\mathcal{E}_{y_{1}^{\prime}}\circ\ldots\circ\mathcal{E}_{y_{\ell}^{\prime}}$
is not equal to an identity. ∎

###  D.4 Estimating state overlaps

The learning algorithm has now identified a set
$\\{y_{1},\ldots,y_{k^{\prime}}\\}$ of unitary transformation. The algorithm
randomly composes the identified unitary transformations
${{\mathcal{E}}}_{y_{1}},\ldots,{{\mathcal{E}}}_{y_{k^{\prime}}}$. In
particular, the algorithm randomly selects $1/\eta$ unitaries with replacement
and composes them to form an approximate Haar random unitary. Using Lemma D.3,
as $\eta$ becomes smaller, we can obtain a better approximation to the Haar
random unitary. The learning algorithm has no additional information other
than the randomly composed operation is approximately Haar random.

The ability to generate Haar random unitary enables the learning algorithm to
estimate state overlaps. Given two states $\rho_{1},\rho_{2}$ which can be
obtained by composing some initial states and CPTP maps, we have a randomized
measurement procedure that guarantees the following.

######  Lemma D.8 (State overlap estimation with a fixed POVM).

Given two states $\rho_{1},\rho_{2}$, $\epsilon>0$,
$z\in{\mathcal{Z}},b\in{\mathcal{B}}$, and a sufficiently small $\eta>0$,
there is a subroutine that estimates

$f_{M_{zb}}(\rho_{1},\rho_{2})=\alpha_{M_{zb}}\operatorname{tr}(\rho_{1}\rho_{2})+\beta_{M_{zb}}$
(75)

up to $\epsilon$ additive error, where $\alpha_{M_{zb}},\beta_{M_{zb}}$
depends on POVM element $M_{zb}$.

###### Proof.

Consider $R$ repetitions. For repetition $r\in\\{1,\ldots,R\\}$, the
subroutine performs:

  1. 1.

Randomly compose $1/\eta$ actions in $\mathcal{Y}_{\mathrm{unitary}}$ to
generate a random CPTP map $\mathcal{E}$.

  2. 2.

Measure the POVM $\mathcal{M}_{z}$ on $\mathcal{E}(\rho_{1})$ and check if the
measurement outcome is $b$.

  3. 3.

Record a binary variable $C_{r}\in\\{0,1\\}$ indicating if the outcome is $b$.

  4. 4.

Measure the POVM $\mathcal{M}_{z}$ on $\mathcal{E}(\rho_{2})$ and check if the
measurement outcome is $b$.

  5. 5.

Record a binary variable $D_{r}\in\\{0,1\\}$ indicating if the outcome is $b$.

From Lemma D.9, we can show that $\hat{X}=\frac{1}{R}\sum_{r=1}^{R}C_{r}D_{r}$
is an accurate estimate for

$\displaystyle f_{M_{zb}}(\rho_{1},\rho_{2})$
$\displaystyle=\frac{1}{d^{2}-1}\left((\operatorname{tr}(M_{zb})^{2}-\operatorname{tr}(M_{zb}^{2})/d)+\operatorname{tr}(\rho_{1}\rho_{2})(\operatorname{tr}(M_{zb}^{2})-\operatorname{tr}(M_{zb})^{2}/d)\right),$
(76)
$\displaystyle=\alpha_{M_{zb}}\operatorname{tr}(\rho_{1}\rho_{2})+\beta_{M_{zb}},$
(77)

up to $\epsilon$ error when $\eta$ is sufficiently small. Hence this lemma can
be established. ∎

######  Lemma D.9 (Characterization of $\hat{X}$).

Given two states $\rho_{1},\rho_{2}$, $\epsilon>0$,
$z\in{\mathcal{Z}},b\in{\mathcal{B}}$, a sufficiently large $R$ and a
sufficiently small $\eta>0$, we have

$\left|\hat{X}-f_{M_{zb}}(\rho_{1},\rho_{2})\right|<\epsilon$ (78)

with high probability.

###### Proof.

The expectation value of $\hat{X}=\frac{1}{R}\sum_{r=1}^{R}C_{r}D_{r}$ is
equal to

$\displaystyle\operatorname*{{\mathbb{E}}}\left[\frac{1}{R}\sum_{r=1}^{R}C_{r}D_{r}\right]$
$\displaystyle=\operatorname*{{\mathbb{E}}}_{\mathcal{E}}\operatorname{tr}(M_{zb}\mathcal{E}(\rho_{1}))\operatorname{tr}(M_{zb}\mathcal{E}(\rho_{2}))$
(79)
$\displaystyle\approx\int_{U}d\mu_{\mathrm{Haar}}(U)\operatorname{tr}(M_{zb}U\rho_{1}U^{\dagger})\operatorname{tr}(M_{zb}U\rho_{2}U^{\dagger})$
(80)
$\displaystyle=\int_{U}d\mu_{\mathrm{Haar}}(U)\operatorname{tr}((M_{zb}\otimes
M_{zb})(U\otimes U)(\rho_{1}\otimes\rho_{2})(U^{\dagger}\otimes U^{\dagger}))$
(81)
$\displaystyle=\frac{1}{d^{2}-1}\left((\operatorname{tr}(M_{zb})^{2}-\operatorname{tr}(M_{zb}^{2})/d)+\operatorname{tr}(\rho_{1}\rho_{2})(\operatorname{tr}(M_{zb}^{2})-\operatorname{tr}(M_{zb})^{2}/d)\right).$
(82)

Eq. (80) is the consequence of the fact that a random composition of universal
set of unitaries approximately forms a Haar random unitary. In particular,
using the Lipschitz continuity of the function
$\phi(U)\equiv\operatorname{tr}(M_{zb}U\rho_{1}U^{\dagger})\operatorname{tr}(M_{zb}U\rho_{2}U^{\dagger})$,
Lemma D.3 shows that the approximation error can be made arbitrarily small as
the number of composed unitary becomes sufficiently large (i.e., $\eta$
sufficiently small). Because $C_{r}D_{r}$ is a random variable bounded by one,
using Hoeffding’s inequality, we can choose
$R=\mathcal{O}(\log(1/\delta))/\epsilon^{2}$, such that
$\frac{1}{R}\sum_{r=1}^{R}C_{r}D_{r}$ equals to
$\operatorname*{{\mathbb{E}}}_{\mathcal{E}}\operatorname{tr}(M_{zb}\mathcal{E}(\rho_{1}))\operatorname{tr}(M_{zb}\mathcal{E}(\rho_{2}))$
up to error $\epsilon/2$ with probability at least $1-\delta$. Eq. (82), on
the other hand, uses the second moment Haar integration formula over special
unitary group. In particular, for $\mathrm{SU}(d)$ and
$X\in\mathbb{C}^{(d\times d)\times(d\times d)}$, we have

$\int_{U}d\mu_{\mathrm{Haar}}(U)(U\otimes U)X(U^{\dagger}\otimes
U^{\dagger})=\frac{1}{d^{2}-1}\left(I\operatorname{tr}(X)+S\operatorname{tr}(SX)-\frac{1}{d}S\operatorname{tr}(X)-\frac{1}{d}I\operatorname{tr}(SX)\right),$
(83)

where $S$ is the swap operator over the tensor product space. Hence, when the
precision parameter $\eta$ is small enough and the number $R$ of randomized
experiments is large enough, $\hat{X}=\frac{1}{R}\sum_{r=1}^{R}C_{r}D_{r}$ is
an accurate estimate for

$f_{M_{zb}}(\rho_{1},\rho_{2})=\frac{1}{d^{2}-1}\left((\operatorname{tr}(M_{zb})^{2}-\operatorname{tr}(M_{zb}^{2})/d)+\operatorname{tr}(\rho_{1}\rho_{2})(\operatorname{tr}(M_{zb}^{2})-\operatorname{tr}(M_{zb})^{2}/d)\right),$
(84)

with an additive error at most $\epsilon$. This establishes the claim. ∎

We are now ready to combine the two lemmas above to establish the main result
of this subsection.

######  Lemma D.10 (State overlap estimation).

Given two states $\rho_{1},\rho_{2}$, $\epsilon>0$, a sufficiently small
$\eta>0$, and the existence of a non-identity $M_{zb}$ for some
$z\in{\mathcal{Z}},b\in{\mathcal{B}}$. There is a subroutine that estimates
$\operatorname{tr}(\rho_{1}\rho_{2})$ up to $\epsilon$ additive error.

###### Proof.

The learning algorithm utilizes the procedure in Lemma D.8 to build the
subroutine achieving the claim of this lemma. Using the fact that for a
$d$-dimensional vector $x$, $d\left\lVert x\right\rVert_{2}^{2}\geq\left\lVert
x\right\rVert_{1}^{2}$, we have

$\operatorname{tr}(M_{zb}^{2})-\operatorname{tr}(M_{zb})^{2}/d\geq 0.$ (85)

Furthermore, equality holds in Eq. (85) if and only if all eigenvalues of
$M_{zb}$ are equal, which implies that $M_{zb}$ is proportional to identity.
If $M_{zb}$ is proportional to identity, $f_{M_{zb}}(\rho_{1},\rho_{2})$ will
be a constant function independent of $\rho_{1},\rho_{2}$. In contrast, if
$M_{zb}$ is not proportional to identity, then for some
$x\in\mathcal{X},y\in\mathcal{Y}$, $f_{M_{zb}}(\rho_{1},\rho_{2})$ will be
distinct between the following two pairs of states,

$\rho_{1}=\rho_{x},\rho_{2}=\mathcal{E}_{y}(\rho_{x})\,\,\mbox{ and
}\,\,\rho_{1}=\rho_{x},\rho_{2}=\rho_{x}.$ (86)

In particular, this is true if we choose the $x$ such that $\rho_{x}$ is pure
and $y$ such that $\mathcal{E}_{y}$ is one of the universal set of unitaries
such that $\mathcal{E}_{y}(\rho_{x})\neq\rho_{x}$.

From the assumption on the true world model (exists actions corresponding to
preparation of a pure state, a universal set of unitaries, and a POVM element
not proportional to identity), there always exists $z,b,x,y$ such that
$f_{M_{zb}}(\rho_{1},\rho_{2})$ is distinct under the two pairs of states in
Eq. (86). Hence, as $\eta$ goes to zero, if $M_{zb}$ is proportional to the
identity, then the largest difference for the estimate of
$f_{M_{zb}}(\rho_{1},\rho_{2})$ maximized over
$x\in\mathcal{X},y\in\mathcal{Y}$ will approach zero. In contrast, if $M_{zb}$
is not proportional to the identity, the largest difference for the estimate
of $f_{M_{zb}}(\rho_{1},\rho_{2})$ maximized over
$x\in\mathcal{X},y\in\mathcal{Y}$ will be greater than a positive value.
Hence, we can consider an algorithm that finds the pair of
$z\in\mathcal{Z},b\in\mathcal{B}$ that yields the largest difference for the
estimate of $f_{M_{zb}}(\rho_{1},\rho_{2})$ maximized over
$x\in\mathcal{X},y\in\mathcal{Y}$. The deduction above guarantees that the
algorithm would find a POVM element $M_{zb}$ that is not proportional to the
identity under a sufficiently small $\eta$.

After finding a pair of $z,b$ such that $M_{zb}$ is not proportional to
identity, we can now describe the procedure that estimates
$\operatorname{tr}(\rho_{1}\rho_{2})$ for any state $\rho_{1},\rho_{2}$.
Recall from Lemma D.8 and Eq. 85 that

$f_{M_{zb}}(\rho_{1},\rho_{2})=\alpha_{M_{zb}}\operatorname{tr}(\rho_{1}\rho_{2})+\beta_{M_{zb}},$
(87)

where $\alpha_{M_{zb}}>0$. Because $\alpha_{M_{zb}}>0$, when
$\rho_{1}=\rho_{2}$, we can see that $f_{M_{zb}}(\rho_{1},\rho_{1})$ is
maximized when $\rho_{1}$ is a pure state. The maximum value of
$f_{M_{zb}}(\rho_{1},\rho_{2})$ is $\alpha_{M_{zb}}+\beta_{M_{zb}}$, and the
minimum value is $\beta_{M_{zb}}$. If $\rho_{1}$ is not a pure state, we can
see that $f_{M_{zb}}(\rho_{1},\rho_{2})<\alpha_{M_{zb}}+\beta_{M_{zb}}$. The
subroutine would hence go through all $x\in\mathcal{X}$ and find an $x^{*}$
such that the estimate for $f_{M_{zb}}(\rho_{x},\rho_{x})$ is maximized.
Recall from the assumption of the true world model, there exists an action $x$
that prepares a pure state. The gap between the finite set of actions that
prepare pure states and those that prepare mixed states allows us to guarantee
that the action $x^{*}$ we found prepares a pure state $\rho_{x^{*}}$ when
$\eta$ is sufficiently small. Because $\rho_{x^{*}}$ is a pure state, we have
$\operatorname{tr}(\rho_{x^{*}}^{2})=1$ and hence from Eq. (76),

$f_{M_{zb}}(\rho_{x^{*}},\rho_{x^{*}})=\frac{1}{(d+1)d}(\operatorname{tr}(M_{zb}^{2})+\operatorname{tr}(M_{zb})^{2}).$
(88)

The learning algorithm can obtain an estimate for
$f_{M_{zb}}(\rho_{x^{*}},\rho_{x^{*}})$. After that, it is only necessary to
estimate $\operatorname{tr}(M_{zb})$ in order to determine
$\operatorname{tr}(M_{zb}^{2})$, which suffices to specify the two values
$\alpha_{M_{zb}}$ and $\beta_{M_{zb}}$.

An estimate for $\operatorname{tr}(M_{zb})$ can be obtained by reusing the
randomized measurement data from the procedure described in Lemma D.8. We can
show that $\hat{Y}=\frac{1}{R}\sum_{r=1}^{R}C_{r}$ is an accurate estimate for
$\operatorname{tr}(M_{zb})/d$. Using the following first-moment Haar
integration formula over the special unitary group,

$\int_{U}d\mu_{\mathrm{Haar}}\,UXU^{\dagger}=\operatorname{tr}(X)I/d,$ (89)

and the standard concentration inequality, we have that
$\frac{1}{R}\sum_{r=1}^{R}C_{r}$ gives an estimate for
$\frac{\operatorname{tr}(M_{zb})}{d}$ up to a small error $\epsilon$ for
sufficiently large $R$ and sufficiently small $\eta$. Along with an estimate
for Eq. (88), the learning algorithm can determine both
$\operatorname{tr}(M_{zb}^{2})$ and $\operatorname{tr}(M_{zb})^{2}$, and hence
$\alpha_{M_{zb}}$ and $\beta_{M_{zb}}$. Together, the learning algorithm can
produce an accurate estimate for quantum state overlap
$\operatorname{tr}(\rho_{1}\rho_{2})$ from an estimate for
$f_{M_{zb}}(\rho_{1},\rho_{2})$ given in Lemma D.8 and the estimates for
$\alpha_{M_{zb}}$ and $\beta_{M_{zb}}$. This concludes the proof of this
lemma. ∎

###  D.5 Learning descriptions of a special set of states

At this point, the algorithm still has not learned a description for any of
the actions. However, the algorithm has identified several important features
of the actions. The algorithm has found $x^{*}\in\mathcal{X}$ where
$\rho_{x^{*}}$ is a pure state. The algorithm has also discovered
$\mathcal{Y}_{\mathrm{unitary}}=\\{y_{1},\ldots,y_{k}\\}\in\mathcal{Y}$ that
forms a universal set of unitaries, which we will now denote as
$U_{y_{1}},\ldots,U_{y_{k}}\in\mathrm{SU}(d)$. Furthermore, the algorithm has
now obtained a subroutine that provides accurate estimate for state overlap
$\operatorname{tr}(\rho_{1}\rho_{2})$. The learning algorithm can now utilize
these tools to construct the entire structure of quantum state space.

More precisely, the algorithm will find a special set of pure quantum states
$\\{\rho_{i}\\}$ that satisfies a certain geometry. The algorithm generates
the special set of pure states by applying compositions of the unitaries
$U_{y},\forall y\in\mathcal{Y}_{\mathrm{unitary}}$ to the pure state
$\rho_{x^{*}}$. We will limit the algorithm to consider a composition of at
most $1/\eta$ unitaries. This means that the algorithm will only find a
collection of states that satisfies the geometry _approximately_. However, an
approximate geometry with small error implies that the learned descriptions
will only be subject to a small error. As $\eta$ goes to zero, the geometry
and the learned description will become accurate to an arbitrarily small
error. The geometry enables us to provide the intrinsic physical descriptions
for states in the special set. Using properties of the geometry, we can
guarantee that the description for the special set of pure states is accurate
up to the equivalence relation – a global unitary or anti-unitary
transformation – characterized by Theorem A.8. The construction of the special
set of pure states is related to the proof of Wigner’s theorem.

We denote the special collection of pure states as
$\rho^{\mathrm{(basis)}}_{i},\forall i\in\\{1,\ldots,d\\}$,
$\rho^{\mathrm{(real)}}_{ij},\forall i\neq j\in\\{1,\ldots,d\\}$,
$\rho^{\mathrm{(imag)}}_{ij},\forall i\neq j\in\\{1,\ldots,d\\}$,
$\rho^{\mathrm{(triplet)}}_{ij},\forall i\neq j\in\\{2,\ldots,d\\}$,
$\rho^{\mathrm{(triplet,12)}}_{j},\forall j\in\\{3,\ldots,d\\}$ and
$\rho^{\mathrm{(triplet,i)}}_{ij},\forall i\neq j\in\\{2,\ldots,d\\}$. The
geometry of the states is given by the following equations.

$\displaystyle\operatorname{tr}(\rho^{\mathrm{(basis)}}_{i}\rho^{\mathrm{(basis)}}_{j})$
$\displaystyle=\delta_{ij},$ $\displaystyle\forall i,j\in\\{1,\ldots,d\\},$
(Fix the basis) (90)
$\displaystyle\operatorname{tr}(\rho^{\mathrm{(basis)}}_{i}\rho^{\mathrm{(real)}}_{ij})$
$\displaystyle=\frac{1}{2},$ $\displaystyle\forall i\neq
j\in\\{1,\ldots,d\\},$ (Fix absolute amplitude for
$\rho^{\mathrm{(real)}}_{ij}$) (91)
$\displaystyle\operatorname{tr}(\rho^{\mathrm{(basis)}}_{j}\rho^{\mathrm{(real)}}_{ij})$
$\displaystyle=\frac{1}{2},$ $\displaystyle\forall i\neq
j\in\\{1,\ldots,d\\},$ (Fix absolute amplitude for
$\rho^{\mathrm{(real)}}_{ij}$) (92)
$\displaystyle\operatorname{tr}(\rho^{\mathrm{(basis)}}_{1}\rho^{\mathrm{(triplet)}}_{ij})$
$\displaystyle=\frac{1}{3},$ $\displaystyle\forall i\neq
j\in\\{2,\ldots,d\\},$ (Fix absolute amplitude for
$\rho^{\mathrm{(triplet)}}_{ij}$) (93)
$\displaystyle\operatorname{tr}(\rho^{\mathrm{(basis)}}_{i}\rho^{\mathrm{(triplet)}}_{ij})$
$\displaystyle=\frac{1}{3},$ $\displaystyle\forall i\neq
j\in\\{2,\ldots,d\\},$ (Fix absolute amplitude for
$\rho^{\mathrm{(triplet)}}_{ij}$) (94)
$\displaystyle\operatorname{tr}(\rho^{\mathrm{(basis)}}_{j}\rho^{\mathrm{(triplet)}}_{ij})$
$\displaystyle=\frac{1}{3},$ $\displaystyle\forall i\neq
j\in\\{2,\ldots,d\\},$ (Fix absolute amplitude for
$\rho^{\mathrm{(triplet)}}_{ij}$) (95)
$\displaystyle\operatorname{tr}(\rho^{\mathrm{(real)}}_{1i}\rho^{\mathrm{(triplet)}}_{ij})$
$\displaystyle=\frac{2}{3},$ $\displaystyle\forall i\neq
j\in\\{2,\ldots,d\\},$ (Transfer relative phase $+1$, a) (96)
$\displaystyle\operatorname{tr}(\rho^{\mathrm{real}}_{1j}\rho^{\mathrm{(triplet)}}_{ij})$
$\displaystyle=\frac{2}{3},$ $\displaystyle\forall i\neq
j\in\\{2,\ldots,d\\},$ (Transfer relative phase $+1$, b) (97)
$\displaystyle\operatorname{tr}(\rho^{\mathrm{(real)}}_{ij}\rho^{\mathrm{(triplet)}}_{ij})$
$\displaystyle=\frac{2}{3},$ $\displaystyle\forall i\neq
j\in\\{2,\ldots,d\\},$ (Transfer relative phase $+1$, c) (98)
$\displaystyle\operatorname{tr}(\rho^{\mathrm{(basis)}}_{i}\rho^{\mathrm{(imag)}}_{ij})$
$\displaystyle=\frac{1}{2},$ $\displaystyle\forall i\neq
j\in\\{1,\ldots,d\\},$ (Fix absolute amplitude for
$\rho^{\mathrm{(imag)}}_{ij}$) (99)
$\displaystyle\operatorname{tr}(\rho^{\mathrm{basis}}_{j}\rho^{\mathrm{(imag)}}_{ij})$
$\displaystyle=\frac{1}{2},$ $\displaystyle\forall i\neq
j\in\\{1,\ldots,d\\},$ (Fix absolute amplitude for
$\rho^{\mathrm{(imag)}}_{ij}$) (100)
$\displaystyle\operatorname{tr}(\rho^{\mathrm{real}}_{ij}\rho^{\mathrm{(imag)}}_{ij})$
$\displaystyle=\frac{1}{2},$ $\displaystyle\forall i\neq
j\in\\{1,\ldots,d\\},$ (Partially fix the phase for
$\rho^{\mathrm{(imag)}}_{ij}$) (101)
$\displaystyle\operatorname{tr}(\rho^{\mathrm{(basis)}}_{1}\rho^{\mathrm{(triplet,12)}}_{j})$
$\displaystyle=\frac{1}{3},$ $\displaystyle\forall j\in\\{3,\ldots,d\\},$ (Fix
absolute amplitude for $\rho^{\mathrm{(triplet,12)}}_{j}$) (102)
$\displaystyle\operatorname{tr}(\rho^{\mathrm{(basis)}}_{2}\rho^{\mathrm{(triplet,12)}}_{j})$
$\displaystyle=\frac{1}{3},$ $\displaystyle\forall j\in\\{3,\ldots,d\\},$ (Fix
absolute amplitude for $\rho^{\mathrm{(triplet,12)}}_{j}$) (103)
$\displaystyle\operatorname{tr}(\rho^{\mathrm{(basis)}}_{j}\rho^{\mathrm{(triplet,12)}}_{j})$
$\displaystyle=\frac{1}{3},$ $\displaystyle\forall j\in\\{3,\ldots,d\\},$ (Fix
absolute amplitude for $\rho^{\mathrm{(triplet,12)}}_{j}$) (104)
$\displaystyle\operatorname{tr}(\rho^{\mathrm{(real)}}_{2j}\rho^{\mathrm{(triplet,12)}}_{j})$
$\displaystyle=\frac{2}{3},$ $\displaystyle\forall j\in\\{3,\ldots,d\\},$
(Transfer relative phase $+1$, a’) (105)
$\displaystyle\operatorname{tr}(\rho^{\mathrm{(imag)}}_{12}\rho^{\mathrm{(triplet,12)}}_{j})$
$\displaystyle=\frac{2}{3},$ $\displaystyle\forall j\in\\{3,\ldots,d\\},$
(Transfer relative phase $+\mathrm{i}$, b’) (106)
$\displaystyle\operatorname{tr}(\rho^{\mathrm{(imag)}}_{1j}\rho^{\mathrm{(triplet,12)}}_{j})$
$\displaystyle=\frac{2}{3},$ $\displaystyle\forall j\in\\{3,\ldots,d\\},$
(Transfer relative phase $+\mathrm{i}$, c’) (107)
$\displaystyle\operatorname{tr}(\rho^{\mathrm{(basis)}}_{1}\rho^{\mathrm{(triplet,i)}}_{ij})$
$\displaystyle=\frac{1}{3},$ $\displaystyle\forall i\neq
j\in\\{2,\ldots,d\\},$ (Fix absolute amplitude for
$\rho^{\mathrm{(triplet,i)}}_{ij}$) (108)
$\displaystyle\operatorname{tr}(\rho^{\mathrm{(basis)}}_{i}\rho^{\mathrm{(triplet,i)}}_{ij})$
$\displaystyle=\frac{1}{3},$ $\displaystyle\forall i\neq
j\in\\{2,\ldots,d\\},$ (Fix absolute amplitude for
$\rho^{\mathrm{(triplet,i)}}_{ij}$) (109)
$\displaystyle\operatorname{tr}(\rho^{\mathrm{(basis)}}_{j}\rho^{\mathrm{(triplet,i)}}_{ij})$
$\displaystyle=\frac{1}{3},$ $\displaystyle\forall i\neq
j\in\\{2,\ldots,d\\},$ (Fix absolute amplitude for
$\rho^{\mathrm{(triplet,i)}}_{ij}$) (110)
$\displaystyle\operatorname{tr}(\rho^{\mathrm{(real)}}_{1i}\rho^{\mathrm{(triplet,i)}}_{ij})$
$\displaystyle=\frac{2}{3},$ $\displaystyle\forall i\neq
j\in\\{2,\ldots,d\\},$ (Transfer relative phase $+1$, a”) (111)