Consider a 4-generic measurement setup as in Theorem 19 and the same constants
$C$ and $\lambda$. Fix $q\geq 1$, some Kraus rank $r$, a number of measurement
settings

$m\geq C\,r\,\ln(n)n^{2}$ (147)

and $p\in[1,2]$. Then, with probability at least $1-\mathrm{e}^{-\lambda m}$,
for all $T_{0}\in\operatorname{CPT}(\mathbb{C}^{n})$ the solution
$T^{\ell_{q}}$ of (146) with $y=\mathcal{A}(T_{0})+e$ approximates $T_{0}$
with an error

$\bigl{\|}J(T_{0}-T^{\ell_{q}})\bigr{\|}_{p}\leq\\\ 4\left\|J(T_{0})_{\neg
r}\right\|_{1}+\tilde{c}\frac{n^{2}r^{1/p-1/2}}{m^{\frac{1}{q}}\bigl{\|}\tilde{A}_{0}\bigr{\|}_{2}}\frac{\left\|e\right\|_{\ell_{q}}}{\left\|A_{0}\right\|_{\infty}}\,.$
(148)

The constants $C$, $\lambda$, and $\tilde{c}$ again only depend on each other.

###### Proof.

This proof is analogous to the proof of Theorem 19 with two exceptions: First,
$\left\|J(T^{\ell_{q}})\right\|_{1}=\left\|J(T_{0})\right\|_{1}=1$, because
both are constrained to be Choi matrices of CPT maps. Consequently, their
difference vanishes in (144). Secondly, the minimization (146) assures

$\displaystyle\left\|\mathcal{A}(T_{0}-T^{\ell_{q}}_{\eta})\right\|_{\ell_{q}}\leq$
$\displaystyle\left\|\mathcal{A}(T^{\ell_{q}}_{\eta})-y\right\|_{\ell_{q}}+\left\|y-\mathcal{A}(T_{0}\right\|_{\ell_{q}}$
$\displaystyle\leq$ $\displaystyle 2\left\|e\right\|_{\ell_{q}},$

because $T_{0}$ is a feasible satisfying
$\left\|y-\mathcal{A}(T_{0})\right\|_{\ell_{q}}=\left\|e\right\|_{\ell_{q}}$
and $T^{\ell_{q}}$ being the minimizer. ∎

####  III.4.3 Constrained trace and diamond norm minimization

In Ref. Kliesch  _et al._ (2016) is shown that certain recovery guarantees for
trace norm regularization (such as (15) and (16)) automatically imply recovery
guarantees for the analogous diamond norm regularization (such as (17) and
(18)). This holds when the recovery guarantees can be proven as, e.g., in Ref.
Tropp (2015) via the descent cone of the reguralizer. In this section, we
follow this strategy in order to obtain a recovery guarantee for diamond norm
regularization in our quantum process tomography setting.

##### An error bound from the descent cone

: For the proof of Theorem 19 we use an error bound relying on the so-called
descent cone of the function that is minimized in the reconstruction. The
descent cone of a function is the cone of directions in which the function
decreases Tropp (2015):

######  Definition 21 (Descent cone).

Let $\mathcal{V}$ be an affine space and
$f:\mathcal{V}\to\overline{\mathbb{R}}$ be a proper convex function. The
_descent cone_ of $f$ at a point $x\in\mathcal{V}$ is

$\operatorname{\mathscr{D}}(f,x)\coloneqq\operatorname{\operatorname{cone}}\,\\{u\in\mathcal{V}_{0}:\
f(x+u)\leq f(x)\\}\,.$ (149)

The following error bound is the basis for many recovery guarantees from
bounds to the conic singular value from Definition 8. It has been proven in
Ref. Chandrasekaran  _et al._ (2012) (where the descent cone is given as a
tangent cone) and has later been restated by Tropp Tropp (2015) for
optimizations over a vector space. One can easily see from its proof that it
also holds if one optimizes over an affine space and chooses arbitrary
$\ell_{q}$-norms ($q\geq 1$) to measure the size of the minimum conic singular
value.

######  Proposition 22 (Error bound for convex recovery, Tropp’s version
(Tropp, 2015, Proposition 2.6)).

Let $x_{0}\in\mathcal{V}$ be a signal,
$\mathcal{A}\in\mathcal{V}\to\mathbb{R}^{m}$ be an affine linear measurement
map, $y=\mathcal{A}(x_{0})+e$ a vector of $m$ measurements with additive error
$e\in\mathbb{R}^{m}$. Fix $q\geq 1$ and let $x^{f}_{\eta,q}$ be the solution
of the optimization

$x^{f}_{\eta,q}=\operatorname*{arg\,min}\\{f(x)\mid x\in\mathcal{V}:\
\left\|\mathcal{A}(x)-y\right\|_{\ell_{q}}\leq\eta\\}$ (150)

for a convex function $f:\mathcal{V}\to\overline{\mathbb{R}}$. If
$\left\|e\right\|_{\ell_{q}}\leq\eta$ then

$\bigl{\|}x^{f}_{\eta}-x_{0}\bigr{\|}_{\mathrm{F}}\leq\frac{2\eta}{\lambda_{\min{}}(\mathcal{A};\operatorname{\mathscr{D}}(f,x_{0}),\ell_{q})}\,.$
(151)

where
$\lambda_{\min{}}(\mathcal{A};\operatorname{\mathscr{D}}(f,x_{0}),\ell_{q})$
has been defined in (37).

###### Proof.

In the proof of (Tropp, 2015, Proposition 2.6) one uses Definition 8 of the
conic singular value only for element in $\mathcal{V}-\mathcal{V}$.
Generalizing the proof from errors measured in Euclidean norm ($q=2$) to any
$\ell_{q}$-norm is also straightforward, provided that the definition of the
minimum conic singular value is properly adjusted. ∎

##### Our recovery guarantee for the diamond norm

: First we prove a weaker version of Theorem 19 with a different argument. In
turn this reconstruction guarantee for minimization (136) will imply a
recovery guarantee for the following generalization of diamond norm
reconstruction:

$T^{\diamond
c}_{\eta,q}=\operatorname*{arg\,min}\\{\left\|T\right\|_{\diamond}:T\in\operatorname{HT}(\mathbb{C}^{n}),\
\left\|\mathcal{A}(T)-y\right\|_{\ell_{q}}\leq\eta\\}.$ (152)

Note that the minimization (18) discussed in the main text is a special case
of (152), where $q=2$.

######  Theorem 23 (Stable reconstruction from trace norm minimization).

Consider a measurement setting as in Theorem 19 with possibly different
constants $C$ and $\lambda$. Fix some Kraus rank $r$ and

$m\geq C\,r\,\ln(n)n^{2}\,,$ (153)

as well as $q\geq 1$. Then, with probability at least $1-\mathrm{e}^{-\lambda
m}$, for all $T_{0}\in\operatorname{HT}(\mathbb{C}^{n})$ with Kraus rank
$\operatorname{rank}(J(T_{0}))\leq r$ the solution $T^{\ast c}_{\eta,q}$ of
the minimization (136) with $y=\mathcal{A}(T_{0})+e$ approximates $T_{0}$ with
an error

$\bigl{\|}J(T_{0}-T^{\ast
c}_{\eta})\bigr{\|}_{2}\leq\tilde{c}\frac{n^{2}}{m^{\frac{1}{q}}\bigl{\|}\tilde{A}_{0}\bigr{\|}_{2}}\,\frac{\eta}{\left\|A_{0}\right\|_{\infty}}$
(154)

provided that $\left\|e\right\|_{\ell_{q}}\leq\eta$. The constants $C$,
$\lambda$, and $\tilde{c}$ again only on each other.

###### Proof.

Thanks to Observations 6 and 7 it is enough to prove the theorem of the case
where $A_{0}$ is traceless (i.e., $A_{0}=\tilde{A}_{0}$) and normalized to
$\left\|A_{0}\right\|_{\infty}=1$. This proof relies on Proposition 22 where
the reconstruction error is bounded in terms of the $\ell_{q}$-minimum conic
singular value of $\mathcal{A}$ w.r.t. the descent cone of the trace norm at
$T_{0}$.

From Ref. (Kueng  _et al._ , 2017, Lemma 10) it follows that any
$T_{0}\in\operatorname{HT}(\mathbb{C}^{n})$ with
$\operatorname{rank}(J(T_{0}))\leq r$ and any
$M\in\operatorname{\mathscr{D}}(\left\|J({\,\cdot\,})\right\|_{1},T_{0})$ the
Hölder-type inequality

$\left\|J(M)\right\|_{1}\leq 2\sqrt{r}\left\|J(M)\right\|_{2}$ (155)

is satisfied. Hence, we choose $c_{\mu}$ in Theorem 12 to be $c_{\mu}=2$. Then
the theorem implies that with probability at least $1-\mathrm{e}^{-\lambda m}$
the minimum conic singular value $\lambda_{\min{}}$ of $\mathcal{A}$ w.r.t.
the descent cone
$\operatorname{\mathscr{D}}(\left\|J({\,\cdot\,})\right\|_{1},T_{0})$ is
bounded as

$\lambda_{\min{}}\left(\mathcal{A};\operatorname{\mathscr{D}}(\left\|J({\,\cdot\,})\right\|_{1},T_{0});q\right)\geq\tilde{C}\,\frac{\left\|A\right\|_{2}m^{\frac{1}{q}}}{n^{2}}\,\quad\forall
q\geq 1,$ (156)

where $\tilde{C}$ is a constant only depending on $\lambda$. Proposition 22
finishes the proof. ∎

Now, the results from Ref. Kliesch  _et al._ (2016), specifically (Kliesch
_et al._ , 2016, Implication 9) tell us that the diamond norm minimization
performs at least as well as the trace norm minimization.

######  Corollary 24 (Stable reconstruction from diamond norm minimization
Kliesch  _et al._ (2016)).

Choosing the diamond norm minimization (18) instead of the trace norm
minimization (16) in Theorem 23 yields a smaller smaller reconstruction error,

$\bigl{\|}J(T_{0}-T^{\diamond
c}_{\eta})\bigr{\|}_{2}\leq\bigl{\|}J(T_{0}-T^{\ast
c}_{\eta})\bigr{\|}_{2}\,.$ (157)

###  III.5 Reconstruction from approximate 4-generic measurements

As stated, our recovery guarantees hold if the input states are drawn from a
complex $4$-design and the output states are measured with observables that
have unitary $4$-designs as eigenbases. Here, we show that for the recovery
guarantees to hold $\epsilon/n^{4}$-approximate $4$-designs are enough, in the
sense that the $\epsilon$ only changes the constants in the recovery guarantee
but not directly the reconstruction error. This significantly lesses the
burden for experimental realizations. Similar generalization have been proven
for low-rank matrix recovery Kueng  _et al._ (2017) and we will extend those
arguments here.

For some probability distribution $\mu$ on the sphere in $\mathbb{C}^{n}$ we
denote the corresponding average of
$\left.\left|{\psi}\right.\right\rangle\\!\\!\left.\left\langle{\psi}\right.\right|^{\otimes
k}$ by

$\psi^{(k)}_{\mu}\coloneqq\mathbb{E}_{\left.\left|{\psi}\right.\right\rangle\sim\mu}\mathopen{}\mathclose{{}\left[\left.\left|{\psi}\right.\right\rangle\\!\\!\left.\left\langle{\psi}\right.\right|^{\otimes
k}}\right]$ (158)

and set $\psi^{(k)}\coloneqq\psi^{(k)}_{\mathrm{Haar}}$ to be the uniform
average. We call $\mu$ and _$\epsilon$ -approximate spherical $k$-design_ if

$\left\|\psi^{(k)}_{\mu}-\psi^{(k)}\right\|_{\infty}\leq\epsilon\left\|\psi^{(k)}\right\|_{\infty}=\frac{\epsilon}{\binom{n+k-1}{k}}\,.$
(159)

Such an $\epsilon$-approximate $k$-design is also an $\epsilon$-approximate
$k^{\prime}$-design for any $k^{\prime}\leq k$ (see, e.g., (Kueng  _et al._ ,
2017, Lemma 16)).

Analogously, given a probability measure $\nu$ on $U(n)$ we define the $k$-th
moment (super)operator by

$\mathcal{G}_{\nu}^{(k)}(X)\coloneqq\mathbb{E}_{U\sim\nu}\mathopen{}\mathclose{{}\left[U^{\otimes
k}XU^{\dagger\otimes k}}\right]$ (160)

and set $\mathcal{G}^{(k)}\coloneqq\mathcal{G}_{\mathrm{Haar}}^{(k)}$. We
define $\nu$ to be an _$\epsilon$ -approximate unitary $k$-design_ if for all
traceless product operators $X$

$\displaystyle\left\|\mathcal{G}_{\nu}^{(k)}(X)-\mathcal{G}^{(k)}(X)\right\|_{\infty}$
$\displaystyle\leq\epsilon\left\|\mathcal{G}^{(k)}(X)\right\|_{\infty}\,.$
(161)

This bound means that the traceless part of observables is not changed too
much. By the embedding $X\mapsto X\otimes\mathds{1}_{n}$ it is easy to see
that an $\epsilon$-approximate unitary $k$-design is also an
$\epsilon$-approximate unitary $k^{\prime}$-design for all $k^{\prime}\leq k$.

There are also other definitions of approximate designs, which are partially
discussed, e.g., in Low’s PhD thesis (Low, 2010, Section 2.2). However, for
our purposes these definitions are the most natural ones.

We note that for a traceless product operator $X$

$\left\|\mathcal{G}^{(k)}(X)\right\|_{\infty}\leq\frac{c(k)}{n^{k}}\left\|X\right\|_{2}\,,$
(162)

which follows from Eq. (47), expanding $P_{\lambda}$ in terms of permutations
$\sigma$, viewing $\operatorname{Tr}[\sigma X]$ as tensor network, and using
Proposition 18. Hence, any $\epsilon$-approximate unitary $k$-design from one
of the other definitions (Low, 2010, Section 2.2) is also an
$\epsilon^{\prime}$-approximate unitary $k$-design according to our
definition. As usual, there is some dimension factor overhead when going from
one definition to another.

######  Definition 25 ($\epsilon$-approximate $4$-generic measurement
ensemble).

We call a measurement ensemble
$\left(A,\left.\left|{\psi}\right.\right\rangle\right)$ with observable $A$
acting on $\mathbb{C}^{n}$ and state $\left.\left|{\psi}\right.\right\rangle$
in $\mathbb{C}^{n}$ _$\epsilon$ -approximate 4-generic_ if it fulfills the
following criteria:

  1. i)

The distribution of $\left.\left|{\psi}\right.\right\rangle$ in
$\mathbb{C}^{n}$ is an $\epsilon$-approximate spherical $4$-design.

  2. ii)

$A=UA_{0}U^{\dagger}$, where $A_{0}\in\operatorname{Herm}(\mathbb{C}^{n})$ is
fixed and $U$ in $\operatorname{U}(n)$ is an $\epsilon$-approximate unitary
$4$-design.

The measurement ensemble is called _normalized $\epsilon$-approximate
4-generic_ if the observables are traceless and normalized in spectral norm,
i.e. $\operatorname{Tr}[A_{0}]=0$ and $\left\|A_{0}\right\|_{\infty}=1$.

######  Theorem 26 ($\lambda_{\min{}}$ for $\epsilon/n^{4}$-approximate
$4$-generic measurements).

Theorem 12 also holds for $\epsilon$-approximate $4$-generic measurements with
a smaller constant $c>0$ whenever $\epsilon\leq\frac{c_{4}}{n^{4}}$, where
$c_{4}>0$ is an absolute constant.

As a direct consequence, all reconstruction guarantees proven in this work
also hold for $\epsilon/n^{4}$-approximate $4$-generic measurements with
different absolute constants.

The theorem is a consequence of the two following lemmas.

######  Lemma 27 ($Q_{\xi}$ for $\epsilon/n^{4}$-approximate $4$-generic
measurements).

Lemma 14 also holds for $\epsilon$-approximate $4$-generic measurements with a
smaller constant $c>0$ whenever $\epsilon\leq\frac{c_{4}}{n^{4}}$, where
$c_{4}>0$ is an absolute constant.

###### Proof.

Let $\mu$ and $\nu$ be an $\epsilon$-approximate spherical and unitary
$k$-design, respectively. We will use that for any operators
$G,B\in\operatorname{\mathrm{L}}(\mathbb{C}^{d})$ and superoperator
$M\in\operatorname{\mathbb{L}}(\mathbb{C}^{d})$

$|\operatorname{Tr}[GM(B)]|\leq\left\|G\right\|_{2}\left\|M\right\|_{\infty}\left\|B\right\|_{2}\leq
d\left\|G\right\|_{\infty}\left\|M\right\|_{\infty}\left\|B\right\|_{\infty}\,.$
(163)

Moreover, we denote $M_{2k}\coloneqq M^{k,k}=M^{\otimes k}\otimes
M^{\ast\otimes k}$. Then, for any traceless and normalized observable
$A\in\operatorname{Herm}(\mathbb{C}^{n})$ and $l=2k$,

$\displaystyle\phantom{\leq.}\mathopen{}\mathclose{{}\left|\operatorname{Tr}\mathopen{}\mathclose{{}\left[\mathcal{G}^{(l)}_{\nu}(A^{\otimes
l})M_{l}(\psi^{(l)}_{\mu})}\right]-\operatorname{Tr}\mathopen{}\mathclose{{}\left[\mathcal{G}^{(l)}(A^{\otimes
l})M_{l}(\psi^{(l)})}\right]}\right|$ (164)
$\displaystyle\leq\mathopen{}\mathclose{{}\left|\operatorname{Tr}\mathopen{}\mathclose{{}\left[\bigl{(}\mathcal{G}^{(l)}_{\nu}(A^{\otimes
l})-\mathcal{G}^{(l)}(A^{\otimes
l})\bigr{)}M_{l}\bigl{(}\psi^{(l)}_{\mu}-\psi^{(l)}\bigr{)}}\right]}\right|$
$\displaystyle\qquad+\mathopen{}\mathclose{{}\left|\operatorname{Tr}\mathopen{}\mathclose{{}\left[\mathcal{G}^{(l)}(A^{\otimes
l})M_{l}\bigl{(}\psi^{(l)}_{\mu}-\psi^{(l)}\bigr{)}}\right]}\right|$
$\displaystyle\qquad+\mathopen{}\mathclose{{}\left|\operatorname{Tr}\mathopen{}\mathclose{{}\left[\bigl{(}\mathcal{G}^{(l)}_{\nu}(A^{\otimes
l})-\mathcal{G}^{(l)}(A^{\otimes l})\bigr{)}M_{l}(\psi^{(l)})}\right]}\right|$
$\displaystyle\leq n^{l}\left\|\bigl{(}\mathcal{G}^{(l)}_{\nu}(A^{\otimes
l})-\mathcal{G}^{(l)}(A^{\otimes
l})\bigr{)}\right\|_{\infty}\left\|M_{l}\right\|_{\infty}\left\|\psi^{(l)}_{\mu}-\psi^{(l)}\right\|_{\infty}$
$\displaystyle\qquad+n^{l}\left\|\mathcal{G}^{(l)}(A^{\otimes
l})\right\|_{\infty}\left\|M_{l}\right\|_{\infty}\left\|\psi^{(l)}_{\mu}-\psi^{(l)}\right\|_{\infty}$
$\displaystyle\qquad+n^{l}\left\|\mathcal{G}^{(l)}_{\nu}(A^{\otimes
l})-\mathcal{G}^{(l)}(A^{\otimes
l})\right\|_{\infty}\left\|M_{l}\right\|_{\infty}\left\|\psi^{(l)}\right\|_{\infty}$
$\displaystyle\leq\frac{c(l)}{n^{l}}\left\|A\right\|_{2}^{l}\left\|M\right\|_{\infty}^{l}\epsilon\,,$

where $c(l)$ is a constant only depending on $l$. We note that
$\left\|M\right\|_{\infty}^{2}\leq\left\|M(\mathds{1})\right\|_{2}^{2}+\left\|M\right\|_{\mathrm{F}}^{2}$
and choose a small enough absolute constant $c_{4}>0$ and

$\epsilon\leq\frac{c_{4}}{n^{4}}$ (165)

so that the ($l=4$)-th moment (117) and the second moment (99) (with traceless
$A$) change only by a constant. This proves the lemma. ∎

######  Lemma 28 ($W_{m}$ for $\epsilon$-approximate 4-generic measurements).

Lemma 13 still holds for $\epsilon$-approximate $4$-generic measurements with
$\left\|A\right\|_{2}$ replaced by $(1+\epsilon)\left\|A\right\|_{2}$.

###### Proof.

The only thing that needs slightly to be changed in the proof of Lemma 13 is
the bound (86) on $\left\|\mathbb{E}[H_{1}^{2}]\right\|_{\infty}$. Using the
definitions above with $k=1$, we have

$\displaystyle\left\|\psi^{(1)}_{\mu}\right\|_{\infty}$
$\displaystyle\leq\left\|\psi^{(1)}_{\mu}-\psi^{(1)}\right\|_{\infty}+\left\|\psi^{(1)}\right\|_{\infty}$
(166) $\displaystyle\leq(1+\epsilon)\left\|\psi^{(1)}\right\|_{\infty}$ (167)

and, similarly,

$\displaystyle\left\|\mathcal{G}^{(1)}_{\nu}(1)\right\|_{\infty}\leq(1+\epsilon)\left\|\mathcal{G}^{(1)}(X)\right\|_{\infty}\,.$
(168)

Hence,

$\left\|\mathbb{E}_{\mu,\nu}[H_{1}^{2}]\right\|_{\infty}\leq(1+\epsilon)^{2}\left\|\mathbb{E}[H_{1}^{2}]\right\|_{\infty}\,.$
(169)

∎

###  III.6 Bosonic and fermionic linear optical circuits

It is worth mentioning that the above results largely carry over to another
important task which is the tomography of bosonic and fermionic circuits. For
bosonic systems, this refers to the tomography of linear optical circuits,
which play an important role in quantum information processing, with such
circuits becoming available for a large number of modes with the advent of
integrated optical circuits Kok  _et al._ (2007); Carolan  _et al._ (2015).
For fermionic systems, this applies to what is called fermionic linear optics
Knill . Interestingly, the results laid out above readily apply to both
situations, once the objects of interest are appropriately identified.

For the bosonic setting, consider $n$ modes associated with bosonic
annihilation operators $(b_{1},\dots,b_{n})$ and Hilbert space ${\cal
H}_{n}^{B}$ in second quantization. The correlation matrix of a quantum state
$\rho\in{\cal S}({\cal H}_{n}^{B})$ is defined as
$C\in\operatorname{Herm}(\mathbb{C}^{n})$ with
$C_{j,k}=\operatorname{Tr}(b_{j}^{\dagger}b_{k}\rho)$. Mode transformations
that preserve the boson number are reflected by maps
$(b_{1},\dots,b_{n})\mapsto(c_{1},\dots,c_{n})$, where

$c_{j}=\sum_{k=1}^{n}U_{j,k}b_{k}$ (170)

with $U\in\operatorname{U}(n)$. Such maps are usually referred to as passive
transformations, or linear optical transformations in the quantum optical
context. Under such mode transformations, correlation matrices transform as

$C\mapsto U^{\dagger}CU\,.$ (171)

Initial correlation matrices reflecting the quantum state can hence be taken
as

$C=U^{\dagger}\left.\left|{1}\right.\right\rangle\\!\\!\left.\left\langle{1}\right.\right|U\,,$
(172)

reflecting the situation that mode labelled $1$ is first prepared in a
Gaussian state satisfying $\operatorname{Tr}(b_{1}^{\dagger}b_{1}\rho)=1$,
while the others are kept in the vacuum
$\operatorname{Tr}(b_{j}^{\dagger}b_{j}\rho)=0$ for $j=2,\dots,n$. This is
then conjugated by a Haar random unitary $U\in\operatorname{U}(n)$, giving
formally rise to an identical transformation as considered above, with
$\left.\left|{\psi_{i}}\right.\right\rangle\\!\\!\left.\left\langle{\psi_{i}}\right.\right|\sim\left.\left|{\psi}\right.\right\rangle\\!\\!\left.\left\langle{\psi}\right.\right|$
are i.i.d. realizations of
$\left.\left|{\psi}\right.\right\rangle\\!\\!\left.\left\langle{\psi}\right.\right|=U^{\dagger}\left.\left|{1}\right.\right\rangle\\!\\!\left.\left\langle{1}\right.\right|U$,
with $U\in\operatorname{U}(n)$ drawn from the Haar measure. Such preparations
are optically readily feasible with present technology, as Gaussian states are
particularly accessible with common sources.

Random measurements can again be seen as i.i.d. realizations $A_{i}\sim
UAU^{\dagger}$ with $U\in\operatorname{U}(n)$ being Haar random. Here $A$ does
not take the role of the observable itself, but reflect natural homodyne
measurements on the level of correlation matrices. Their expectation values
are obtained as $\operatorname{Tr}(AC)$ for correlation matrices $C$. So
again, while the type of measurement is different and the objects involved
take an altered physical role, the map realized is formally identical with

$y=\mathcal{A}(T)+e\ \in\mathbb{R}^{m}$ (173)

with single expectation values

$\mathcal{A}(T)_{i}=\operatorname{Tr}[A_{i}T(\left.\left|{\psi_{i}}\right.\right\rangle\\!\\!\left.\left\langle{\psi_{i}}\right.\right|)]+e_{i}\,,$
(174)

for
$T(\left.\left|{\psi_{i}}\right.\right\rangle\\!\\!\left.\left\langle{\psi_{i}}\right.\right|):=V^{\dagger}\left.\left|{\psi_{i}}\right.\right\rangle\\!\\!\left.\left\langle{\psi_{i}}\right.\right|V$,
with $V\in\operatorname{U}(n)$ reflecting the unknown linear process. In this
way, process tomography of the kind discussed here is applicable to the
bosonic setting. This seems particularly important with the advent of
monolithic bosonic integrated optical devices Carolan  _et al._ (2015), as
they are, e.g., employed in boson samplers.

Fermionic linear circuits associated with fermionic annihilation operators
$(f_{1},\dots,f_{n})$ have the same structure (on that level). Again,
correlation matrices $C\in\operatorname{Herm}(\mathbb{C}^{n})$ transform as

$C\mapsto U^{\dagger}CU$ (175)

for $U\in\operatorname{U}(n)$, and the same preparations are feasible. Here
$\left.\left|{1}\right.\right\rangle\\!\\!\left.\left\langle{1}\right.\right|$
reflects a fermionic Gaussian state in which the first mode contains exactly a
single fermion, while the other $n-1$ modes contain no fermion. The same type
of measurement is therefore again possible.

##  IV Conclusion

We have proven that quantum processes can be reconstructed from an essentially
optimal number of expectation values without the requirement of ancillary
quantum systems. Moreover, by an extensive numerical analysis we have (i)
demonstrated the practical feasibility of our approach and (ii) that the
reconstruction procedures also work for Pauli-type measurement settings. The
number of necessary expectation values scales as $\sim r\,n^{2}\ln(n)$, where
$r$ is the anticipated Kraus rank of the channel. The reconstructions are
stable against measurement noise and robust against violations of the measured
quantum channel having the anticipated Kraus rank. In particular, no strict
assumptions on the noise level or the Kraus rank are required for a simple
fitting procedure (CPT-fit) to be guaranteed to give a good approximation of
the measured quantum channel. In several physically feasible and realistic
setting, the prescriptions laid out give direct and concrete advice on how to
optimally perform quantum process tomography.

###  IV.1 Outlook

In this outlook, we present a short outline of several aspects that seem to be
interesting starting points for future research.

##### Mixed input states

: The first potential generalization concerns the use of pure quantum states
in the reconstruction procedure. Numerically, we have observed that our
reconstructions work almost equally well when the input states to the channels
are mixed. Finding a recovery guarantee following this observation would be a
step towards more practical measurements.

##### The restricted isometry property (RIP) and perspectives for thresholding
methods

: The RIP can be adapted to our setting. A measurement map $\mathcal{A}$ is
said to fulfill RIP for Kraus rank $r$ if

$(1-\delta)\left\|T\right\|_{\mathrm{F}}\leq\left\|\mathcal{A}(T)\right\|_{\ell_{2}}\leq(1+\delta)\left\|T\right\|_{\mathrm{F}}$
(176)

for all quantum channels $T\in\operatorname{CPT}(\mathbb{C}^{n})$ with Kraus
rank at most $r$. The lower RIP bound is — as in our case — typically enough
to obtain recovery guarantees for optimization procedures. But their
computational cost is often not optimal. For instance, iterative hard Cai  _et
al._ (2010); Chatterjee (2015) and soft Boyd  _et al._ (2011) thresholding
algorithms are faster in many instances. But here, recovery guarantees are
typically more difficult to prove and also required the upper RIP bound.
Analyzing such algorithms for process tomography setting would be an
interesting endeavour for future research.

##### Random Clifford unitaries

: The work Zhu  _et al._ (2016) shows that random Clifford gates are very
close to being unitary $4$-designs, and that they provide a precise
characterization in terms of irreducible representations of the Clifford
group. Such tools might be helpful to further relax the requirements on the
measurement settings. Here, it would be interesting to see if these new
insights can be used in order to prove our recovery guarantees with the input
states of the channels being random stabilizer states and the bases of the
observables random Clifford unitaries. This might be particular useful in
order to achieve fault tolerance.

##### Diamond norm

: We have observed numerically (Figure II.4.2) that the minimum value (the
diamond norm of the reconstructed channel) of the unconstrained diamond norm
reconstruction (17), Kliesch  _et al._ (2016) is one if the reconstruction
error is small and decreases with increasing reconstruction error. It would be
interesting to also understand this observation analytically. In this way one
can obtain some confidence about reconstructed quantum channels. Of course,
also other types of reconstruction certificates would be of great interest.

##### Frequencies and dependent measurements

: In a typical experiment, one does not only learn the expectation value of an
observable $A$, but rather acquires statistics about the POVM associated with
its spectral decomposition. Indeed, it is straightforward to apply our
reconstruction procedures to observed frequencies of POVM measurements.
However, in this work we disregard this finer-grained information. We have
made this decision to avoid technical complications: The various POVM elements
associated with any given setting are clearly not independent. However our
proof techniques work best for independently drawn measurements and our
natural measurements lead to independence in a natural way.
There are now related theoretical recovery guarantees that can handle some
form of dependency – e.g. Refs. Voroninski (2013); Kueng (2015); Acharya  _et
al._ (2016); Acharya and Guta (2017); Candès  _et al._ (2015); Gross  _et al._
(2016). Applying such techniques to process tomography remains an interesting
open problem. As a first step towards dependent measurements, it would be
interesting to numerically compare sample complexities in the cases of our
natural measurement setup and the corresponding frequency measurements, with a
fair accounting for statistical noise.

##### Sample complexity

: For quantum state tomography, fundamental lower bounds on the sample
complexity have been established in Refs. Haah  _et al._ (2017) and Flammia
_et al._ (2012). They are valid for arbitrary POVM measurements Haah  _et al._
(2017) and measuring Pauli observables Flammia  _et al._ (2012), respectively.
Moreover, these works also determine the sample complexity associated with
different compressed-sensing based state tomography techniques. A comparison
with the associated fundamental lower bounds shows a close to optimal scaling
(at least for low-rank states).

In contrast to state tomography, very little is known about the sample
complexity associated with process tomography. A straightforward adaptation of
the results Haah  _et al._ (2017) and Flammia  _et al._ (2012) is hindered by:
(i) Typical process tomography measurements – such as the 4-generic
measurements considered here – have neither a Pauli structure, nor can they be
interpreted as state POVMs in a strict sense Ziman (2008). This makes the task
of determining the exact sample complexity associated with a concrete
tomographic procedure more difficult. (ii) Due to the trace preservation
condition, quantum channels are more restricted than quantum states. Suitable
packing nets – a key ingredient in the derivation of the fundamental lower
bounds in Haah  _et al._ (2017); Flammia  _et al._ (2012) – must fulfill these
additional requirements which makes their construction considerably more
challenging. Despite these obstacles, we believe that such a generalization is
timely and well-motivated.

##  V Acknowledgements

We thank I. Roth and M. Horodecki for helpful discussions. This work has been
supported by the Polonez grant 2015/19/P/ST2/03001, the Excellence Initiative
of the German Federal and State Governments (Grant ZUK 81), the ARO under
contract W911NF-14-1-0098 (Quantum Characterization, Verification, and
Validation), Universities Australia and DAAD’s Joint Research Co-operation
Scheme (using funds provided by the German Federal Ministry of Education and
Research), the Templeton Foundation, the ERC (TAQ), and the DFG (SPP1798
CoSIP, EI 519/9-1, EI 519/7-1).

## Appendix

In this appendix, we provide some auxiliary statements in order to keep this
work largely self-contained. In Appendix A, we provide semidefinite
programming formulations of the reconstruction procedures (15), (16), (17),
and (18). In Appendix B, we state a non-commutative Khintchine inequality used
in the proof of our bound on the conic minimum singular value, more precisely
in the proof of Lemma 13 with the bound on the mean empirical width. Then,
finally, we provide some facts about the symmetric group $S_{4}$ in Appendix
C. These facts are also used in the derivation of the bound on the conic
minimum singular value in order to bound the fourth moment of our measurements
(Lemma 16).

##  Appendix A Semidefinite programs for trace and diamond norm reconstruction

Our reconstructions can be implemented as semidefinite programs (SDPs) Kliesch
_et al._ (2016), which can practically be solved using standard software such
as CVX Grant and Boyd (2014, 2008). Let us consider the reconstruction of a
quantum channel mapping operators in $\operatorname{\mathrm{L}}(\mathcal{X})$
to operators in $\operatorname{\mathrm{L}}(\mathcal{Y})$. The minimization
(15) can be rewritten as the following SDP,

$\begin{array}[]{r l
l}T^{\ast}_{\eta}=&\underset{T,X,Y}{\operatorname*{arg\,min}}&\frac{1}{2}\bigl{(}\operatorname{Tr}[X]+\operatorname{Tr}[Y]\bigr{)},\\\\[3.00003pt]
&\mathrm{subject\ to}&\begin{pmatrix}X&-J(T)\\\
-J(T)^{\dagger}&Y\end{pmatrix}\succeq 0\,,\\\\[8.99994pt]
&&X,Y\in\operatorname{Pos}(\mathcal{Y}\otimes\mathcal{X})\,,\\\
&&\left\|\mathcal{A}(T)-y\right\|_{\mathrm{F}}\leq\eta\,.\end{array}$ (177)

The reconstruction (16) is obtained by adding the constraint
$T^{\dagger}(\mathds{1}_{\mathcal{Y}})=\mathds{1}_{\mathcal{X}}$ into this
SDP.

By only changing the objective function with the spectral norm of _partial_
traces $\operatorname{Tr}_{\mathcal{Y}}$ over the output space $\mathcal{Y}$
of
$T:\operatorname{\mathrm{L}}(\mathcal{X})\to\operatorname{\mathrm{L}}(\mathcal{Y})$,
we obtain the minimization (17) as the following SDP Watrous (2012); Kliesch
_et al._ (2016),

$\begin{array}[]{r l
l}T^{\diamond}_{\eta}=&\underset{T,X,Y}{\operatorname*{arg\,min}}&\frac{1}{2}\bigl{(}\left\|\operatorname{Tr}_{\mathcal{Y}}[X]\right\|_{\infty}+\left\|\operatorname{Tr}_{\mathcal{Y}}[Y]\right\|_{\infty}\bigr{)},\\\\[3.00003pt]
&\mathrm{subject\ to}&\begin{pmatrix}X&-J(T)\\\
-J(T)^{\dagger}&Y\end{pmatrix}\succeq 0\,,\\\\[8.99994pt]
&&X,Y\in\operatorname{Pos}(\mathcal{Y}\otimes\mathcal{X})\,,\\\
&&\left\|\mathcal{A}(T)-y\right\|_{\mathrm{F}}\leq\eta\,.\end{array}$ (178)

Again, the constrained minimization (18) is obtained by adding the constraint
$T^{\dagger}(\mathds{1}_{\mathcal{Y}})=\mathds{1}_{\mathcal{X}}$ into the SDP.

##  Appendix B A non-commutative Khintchine inequality

######  Theorem 29 ( (Vershynin, 2012, Remark 5.27.2) with constants from
(Foucart and Rauhut, 2013, Exercise 8.6(d)) ).

Let $B_{1},\ldots,B_{m}$ be self adjoint $N\times N$ matrices and
$\epsilon_{1},\ldots,\epsilon_{m}\in\\{-1,1\\}$ uniformly and independently
drawn signs (called a Rademacher sequence). Then

$\operatorname{\mathbb{E}}\biggl{[}\Bigl{\|}\sum_{j=1}^{m}\epsilon_{j}B_{j}\Bigr{\|}_{\infty}\biggr{]}\leq\sqrt{2\ln(2N)}\,\Bigl{\|}\sum_{j=1}^{n}B_{j}^{2}\Bigr{\|}_{\infty}^{1/2}.$
(179)

##  Appendix C Linear representation of the symmetric group $S_{4}$

In order to bound the fourth moment of the measurement map some facts about
the representation of the permutation group $S_{4}$ are helpful. In this
section, they are summarized and partially derived. Facts that we just state
can, e.g., be found in the Wikis Wik (2016a) and Wik (2016b).

By $k_{1}^{j_{1}}k_{2}^{j_{2}}\dots k_{l}^{j_{l}}$ we denote the conjugacy
class containing permutations composed of each $j_{i}$ disjoint cycles of
sizes $\\{k_{i}\\}_{i\in[l]}$, e.g., $2^{2}\subset S_{4}$ are products of
disjoint transpositions. Corresponding to each conjugacy class there is one
irrep. They are given by the Young Frames Wik (2016b)

$\displaystyle\mathcal{F}_{1}$ $\displaystyle\coloneqq\yng(4)$ (trivial rep.)
(180) $\displaystyle\mathcal{F}_{2}$ $\displaystyle\coloneqq\yng(1,1,1,1)$
(sign rep.). $\displaystyle\mathcal{F}_{3}$ $\displaystyle\coloneqq\yng(2,2)$
(degree two irreducible rep.) $\displaystyle\mathcal{F}_{4}$
$\displaystyle\coloneqq\yng(3,1)$ (standard rep.)
$\displaystyle\mathcal{F}_{5}$ $\displaystyle\coloneqq\yng(2,1,1)$
$\displaystyle\begin{array}[]{l}\text{(product of standard rep.}\\\
\text{\phantom{({}}and sign rep.)}\end{array}$

We will denote the character corresponding to $\mathcal{F}_{i}$ by
$\chi_{i}:S_{4}\to\mathbb{Z}$. The characters are constant on the conjugacy
classes. The sizes of the conjugacy classes and the characters of $S_{4}$ are
Wik (2016a)

${\begin{array}[]{| l " c | c | c | c | c |}\hline\cr\text{Cycle type}{\phantom{I^{I^{I}}}}\hfil\hskip 6.0pt\vrule width=1.0pt\hskip 6.0&1^{4}&2^{2}&2^{1}&4^{1}&3^{1}\\\ \hline\cr\text{\\# elements}\hfil\hskip 6.0pt\vrule width=1.0pt\hskip 6.0&1&3&6&6&8\\\ \cr\hrule height=1.0pt}\chi_{1}=[4]\hfil\hskip 6.0pt\vrule width=1.0pt\hskip 6.0&1&1&1&1&1\\\ \hline\cr\chi_{2}=[1,1,1,1]\hfil\hskip 6.0pt\vrule width=1.0pt\hskip 6.0&1&1&-1&-1&1\\\ \hline\cr\chi_{3}=[2,2]\hfil\hskip 6.0pt\vrule width=1.0pt\hskip 6.0&2&2&0&0&-1\\\ \hline\cr\chi_{4}=[3,1]\hfil\hskip 6.0pt\vrule width=1.0pt\hskip 6.0&3&-1&1&-1&0\\\ \hline\cr\chi_{5}=[2,1,1]\hfil\hskip 6.0pt\vrule width=1.0pt\hskip 6.0&3&-1&-1&1&0\\\ \hline\cr\end{array}$ (181)

The dimension of the representation $\mathcal{F}_{i}$ (in the group algebra)
will be denoted by $d_{i}$ (also called _degree_ Wik (2016b)). These
dimensions are given by $d_{i}=\chi_{i}([1])$.

Expanding a character $\chi$ in the group algebra yields

$\displaystyle\chi$ $\displaystyle=\frac{1}{|S_{4}|}\sum_{\sigma\in
S_{4}}\chi(\sigma)\langle\sigma,{\,\cdot\,}\rangle$ (182)
$\displaystyle=\frac{1}{|S_{4}|}\sum_{C}\chi(C)\langle\Sigma
C,{\,\cdot\,}\rangle\,,$ (183)

where $\langle{\,\cdot\,},{\,\cdot\,}\rangle$ is the inner product of the
group algebra, $\sum_{C}$ denotes the sum over all conjugacy classes $C$ in
$S_{4}$, and $\Sigma C\coloneqq\sum_{\sigma\in C}\sigma$ the sum over the
conjugacy class $C$. The central minimal projections

$p_{i}=\frac{d_{i}}{|S_{4}|}\chi_{i}$ (184)

(see, e.g., Ref. (Simon, 1996, Theorem III.7.2)) are hence given by

$\displaystyle p_{1}$
$\displaystyle=\frac{1}{24}\left(\mathrm{id}+\Sigma[2,2]+\Sigma[2]+\Sigma[4]+\Sigma[3]\right)$
(185) $\displaystyle p_{2}$
$\displaystyle=\frac{1}{24}\left(\mathrm{id}+\Sigma[2,2]-\Sigma[2]-\Sigma[4]+\Sigma[3]\right)$
$\displaystyle p_{3}$
$\displaystyle=\frac{1}{12}\left(2\,\mathrm{id}+2\,\Sigma[2,2]-\Sigma[3]\right)$
$\displaystyle p_{4}$
$\displaystyle=\frac{1}{8}\left(3\,\mathrm{id}-\Sigma[2,2]+\Sigma[2]-\Sigma[4]\right)$
$\displaystyle p_{5}$
$\displaystyle=\frac{1}{8}\left(3\,\mathrm{id}-\Sigma[2,2]-\Sigma[2]+\Sigma[4]\right)$

where we have made the identification
$\langle\sigma,{\,\cdot\,}\rangle\cong\sigma$.

Now we consider the linear representation $R:S_{4}\to(\mathbb{C}^{n})^{\otimes
4}$, which is given by permuting the for tensor factors, i.e., the
representation of $\sigma\in S_{4}$ is a unitary $R(\sigma)$ on
$(\mathbb{C}^{n})^{\otimes 4}$ given by

$R(\sigma)=\sum_{i_{1},i_{2},i_{3},i_{4}=1}^{n}\left.\left|{i_{\sigma(1)},i_{\sigma(2)},i_{\sigma(3)},i_{\sigma(4)}}\right.\right\rangle\\!\\!\left.\left\langle{i_{1},i_{2},i_{3},i_{4}}\right.\right|\,.$
(186)

Often we write $\sigma$ instead of $R(\sigma)$. This representation naturally
extends to a representation of the group algebra.

As $\sum_{i=1}^{5}p_{i}$ is a decomposition of the identity on the group
algebra, we obtain the decomposition

$\mathds{1}_{(\mathbb{C}^{n})^{\otimes 4}}=\sum_{i=1}^{5}P_{i}$ (187)

with $P_{i}=R(p_{i})$. The dimension of the representation $\mathcal{F}_{i}$
is $\operatorname{Tr}[R(p_{i})]$ and is given by the dimension $d_{i}(n)$ of
the Schur functor corresponding to $\mathcal{F}_{i}$ when applied to a vector
space of dimension $n$ Wik (2016b)

$\displaystyle d_{1}(n)$ $\displaystyle=n\,(n+1)(n+2)(n+3)/24$ (188)
$\displaystyle d_{2}(n)$ $\displaystyle=(n-3)(n-2)(n-1)\,n/24$ $\displaystyle
d_{3}(n)$ $\displaystyle=(n-1)\,n^{2}\,(n+1)/12$ $\displaystyle d_{4}(n)$
$\displaystyle=(n-1)\,n\,(n+1)(n+2)/8$ $\displaystyle d_{5}(n)$
$\displaystyle=(n-2)(n-1)\,n\,(n+1)/8\,.$

##  Appendix D Proof of the tensor network bound Proposition 18

We start with some preliminaries that are helpful for the proof. A contraction
$C$ of a tensors with $K$ indices is defined by pairs of pointers
$\\{(k_{l},k^{\prime}_{l})\\}_{l\in[L]}$. For any
$\mathcal{L}\subset[L]\subset[K]$, we define the partial contraction
$C_{\mathcal{L}}$ of a tensor $t$ to be the one given by the subset of pointer
pairs $\\{(k_{l},k^{\prime}_{l})\\}_{l\in\mathcal{L}}$. For
$\mathcal{L}_{1}\subset[K]$ and $\mathcal{L}_{2}\subset[K]$ with
$\mathcal{L}_{1}\cap\mathcal{L}_{2}=\emptyset$ we can naturally apply
$C_{\mathcal{L}_{2}}$ to $C_{\mathcal{L}_{1}}(t)$ and it holds that
$C_{\mathcal{L}_{2}}(C_{\mathcal{L}_{1}}(t))=C_{\mathcal{L}_{1}}(C_{\mathcal{L}_{2}}(t))$
and $C(t)=C_{[K]\setminus\mathcal{L}}(C_{\mathcal{L}}(t))$.

We will use the following facts about matrices $A\in\mathbb{C}^{n_{1}\times
n_{2}}$ and $B\in\mathbb{C}^{n_{2}\times n_{3}}$ with dimensions
$n_{1},n_{2},n_{3}\geq 1$:

$\displaystyle\left\|AB\right\|_{\infty}$
$\displaystyle\leq\left\|A\right\|_{\infty}\left\|B\right\|_{\infty}$ (189)
$\displaystyle\left\|A\right\|_{\infty}$
$\displaystyle\leq\left\|A\right\|_{2}=\left\|A\right\|_{2}\,.$ (190)

For $n_{1}=n_{3}=1$ one has $\left\|A\right\|_{\infty}=\left\|A\right\|_{2}$
and similarly for $B$. We will also use the identity

$\left\|A\otimes
B\right\|_{\infty}=\left\|A\right\|_{\infty}\left\|B\right\|_{\infty}\,,$
(191)

which holds for arbitrary matrices $A\in\mathbb{C}^{n_{1}\times n_{2}}$ and
$B\in\mathbb{C}^{n_{3}\times n_{4}}$.

Any bipartition of the indices of a tensor $t$ yields a class of unitarily
equivalent matrices. More specifically, a _matricization_ of a tensor
$t\in\mathbb{C}^{n_{1}\times n_{2}\times\dots\times n_{K}}$ is a matrix $A$ of
which the matrix elements are given by

$A_{(i_{\sigma(1)},i_{\sigma(2)},\dots,i_{\sigma(K^{\prime})}),(i_{\sigma(K^{\prime}+1)},\dots,i_{\sigma(K)})}=t_{i_{1},i_{2},\dots,i_{K}}$
(192)

for some permutation $\sigma\in S_{K}$. Two such matricizations given by
$\tau,\sigma\in S_{K}$ and the same $K^{\prime}\in[K]$ are unitarily
equivalent if
$\\{\sigma(i)\\}_{i\in[K^{\prime}]}=\\{\tau(i)\\}_{i\in[K^{\prime}]}$, i.e.,
if $\sigma$ and $\tau$ yield the same bipartition of the pointers $[K]$. For a
tensor $t\in\mathbb{C}^{n_{1}\times n_{2}\times\dots\times n_{K}}$ and a
disjoint bipartition $\mathcal{L}\,\dot{\cup}\,\mathcal{R}=[K]$ of the pointer
set $[K]$ we denote by $t_{\mathcal{L},\mathcal{R}}$ some matricization of $t$
that comes from this bipartition. For any such matricization
$t_{\mathcal{L},\mathcal{R}}$ holds that

$\left\|t_{\mathcal{L},\mathcal{R}}\right\|_{2}=\left\|t\right\|_{\mathrm{F}}\,.$
(193)

A _vectorization_ of a tensor is a matricization that yields a vector, i.e., a
matrix with one column or row.

###### Proof of Proposition 18.

It is enough to prove the proposition for the case where the tensor network is
closed, i.e., where $C(T)\in\mathbb{C}$. This is so because we can write
$\left\|C(T)\right\|_{\mathrm{F}}^{2}$ always as a closed tensor network,
where all previous tensors plus their complex conjugates occur. A tensor and
its conjugate have the same norm, which shows the reduction argument.

We denote the tensors of the tensor network by
$t^{j}\in\mathbb{C}^{n_{1}^{j}\times n_{2}^{j}\times\dots\times
n_{K^{j}}^{j}}$ where $j\in[J]$ and the pointer pairs defining the contraction
$C$ by $(\\{k_{l},k^{\prime}_{l}\\})_{l\in[K]}$ with $K=\sum_{j\in[J]}K^{j}$.

Let us consider first the case $J=2$. As there are no self-contractions, we
can relabel the pointer pairs $(\\{k_{l},k^{\prime}_{l}\\})_{l\in[K]}$ so that
the $k_{l}$ belong to $t^{1}$ and the $k^{\prime}_{l}$ to $t^{2}$. Hence,
$C(T)$ is an inner product $C(T)=\left\langle t^{1}\middle|t^{2}\right\rangle$
of matricizations of $t^{1}$ and $t^{2}$ into vectors
$\left.\left|{t^{1}}\right.\right\rangle$ and
$\left.\left|{t^{2}}\right.\right\rangle$. Therefore, the Cauchy-Schwarz
inequality and the invariance of the Frobenius norm (193) prove the
proposition for $J=2$.

Now we consider $J\geq 3$. If there are contractions
$\\{k_{l},k^{\prime}_{l}\\}$ where one of the indices belongs to $t^{1}$ and
one to $t^{J}$, for each such $l$ we introduce an auxiliary tensor $s^{l}$ as
identity matrix with components
$s^{l}_{m_{k_{l}},m_{k^{\prime}_{l}}}\coloneqq\delta_{m_{k_{l}},m_{k^{\prime}_{l}}}$
that is contracted with $t^{1}$ and $t^{2}$ and replaces their contraction
$\\{k_{l},k^{\prime}_{l}\\}$. This corresponds to tensoring $t^{2}\otimes
t^{3}\otimes\dots\otimes t^{J-1}$ with an $n_{k_{l}}\times n_{k_{l}^{\prime}}$
identity matrix. Denote by $s^{l_{1}},s^{l_{2}},\dots,s^{l_{M}}$ the tensors
that are introduced in this way. We obtain $\tilde{C}$ from $C$ by, the this
modification, so that $\tilde{C}$ contracts the modified tensor network
$\tilde{T}=(t^{1},\tilde{T}^{\prime},t^{J})$ with

$\displaystyle\tilde{T}^{\prime}$ $\displaystyle=S\cup T^{\prime}$ (194)
$\displaystyle S$
$\displaystyle\coloneqq\bigl{(}s^{l_{1}},s^{l_{2}},\dots,s^{l_{M}}\bigr{)}$
$\displaystyle T^{\prime}$
$\displaystyle\coloneqq\bigl{(}t^{2},t^{3},\dots,t^{J-1}\bigr{)}$

where $\tilde{C}$ is obtained from $C$ by adding the contractions
$\\{k_{l},k^{\prime}_{l}\\}_{l=L+1,\dots,K+M}$ with
$s^{l_{1}},s^{l_{2}},\dots,s^{l_{M}}$ to the previous ones. With this
construction we have $C(T)=\tilde{C}(\tilde{T})$.

Next, we rename the pointers such that the $k_{l}$ of the first $K^{1}$ pairs
$(\\{k_{l},k^{\prime}_{l}\\})_{l\in[K^{1}]}$ belong to $t^{1}$. As there are
no contractions between $t^{1}$ and $t^{J}$, we rename the pointers so that
the $k^{\prime}_{l}$ of the last $K^{J}$ pairs
$(\\{k_{l},k^{\prime}_{l}\\})_{l\in[K]\setminus[K-K^{J}]}$ belong to $t^{J}$.
The remaining pointers pairs are

$\displaystyle\tilde{\mathcal{K}}^{\prime}$
$\displaystyle\coloneqq\mathcal{K}^{\prime}\cup\mathcal{M}$ (195)
$\displaystyle\mathcal{K}^{\prime}$
$\displaystyle\coloneqq\\{K^{1}+1,K^{1}+2,\dots,K-K^{J}\\}$
$\displaystyle\mathcal{M}$ $\displaystyle\coloneqq\\{K+1,K+2,L+M\\}\,,$

which contain no further contractions between $t^{1}$ and $t^{J}$. Now we have
achieved that the pointer pairs connected to $t^{1}$ are
$\mathcal{K}^{1}\coloneqq[K^{1}]$ and the ones of $t^{J}$ are
$\mathcal{K}^{J}\coloneqq[K]\setminus[K-K^{J}]$, so that they are clearly
disjoint.

Hence, we can write

$\displaystyle
C(T)=\tilde{C}_{\mathcal{K}^{1}}\Bigl{(}t^{1}\otimes\tilde{C}_{\mathcal{K}^{J}}\bigl{(}\tilde{C}_{\tilde{\mathcal{K}}^{\prime}}(\tilde{T}^{\prime})\otimes
t^{J}\bigr{)}\Bigr{)}\,.$ (196)

In fact
$\tilde{C}_{\mathcal{K}^{J}}\bigl{(}\tilde{C}_{\tilde{\mathcal{K}}^{\prime}}(\tilde{T}^{\prime})\otimes
t^{J}\bigr{)}\mapsto\tilde{C}(T)$ is the action of the functional given by
$\tilde{C}_{\mathcal{K}^{1}}\Bigl{(}t^{1}\otimes{\,\cdot\,}\Bigr{)}$, which,
in turn, is given by a vectorization $\left.\left|{t^{1}}\right.\right\rangle$
of $t^{1}$. Hence, we can obtain

$\displaystyle|C(T)|\leq\left\|t^{1}\right\|_{\mathrm{F}}\left\|\tilde{C}_{\mathcal{K}^{J}}\bigl{(}\tilde{C}_{\tilde{\mathcal{K}}^{\prime}}(\tilde{T}^{\prime})\otimes
t^{J}\bigr{)}\right\|_{\mathrm{F}}\,.$ (197)

Similarly,
$t^{J}\mapsto\tilde{C}_{\mathcal{K}^{J}}\bigl{(}\tilde{C}_{\tilde{\mathcal{K}}^{\prime}}(\tilde{T}^{\prime})\otimes
t^{J}\bigr{)}$ is a linear mapping, where we view
$\tilde{C}_{\tilde{\mathcal{K}}^{\prime}}(\tilde{T}^{\prime})$ as a linear map
contracting the indices $\mathcal{K}^{J}$ and having non-contracted indices
$\mathcal{K}^{1}$. This yields a vectorization
$\left.\left|{t^{J}}\right.\right\rangle$ of $t^{J}$ an a map is represented
by a matricization
$\tilde{C}_{\tilde{\mathcal{K}}^{\prime}}(\tilde{T}^{\prime})_{\mathcal{K}^{1},\mathcal{K}^{J}}$
of $\tilde{C}_{\tilde{\mathcal{K}}^{\prime}}(\tilde{T}^{\prime})$ so that

$\displaystyle\left\|\tilde{C}_{\mathcal{K}^{J}}\bigl{(}\tilde{C}_{\tilde{\mathcal{K}}^{\prime}}(\tilde{T}^{\prime})\otimes
t^{J}\bigr{)}\right\|_{\mathrm{F}}$
$\displaystyle=\left\|\tilde{C}_{\tilde{\mathcal{K}}^{\prime}}(\tilde{T}^{\prime})_{\mathcal{K}^{1},\mathcal{K}^{J}}\left.\left|{t^{J}}\right.\right\rangle\right\|$
(198)
$\displaystyle\leq\left\|\tilde{C}_{\tilde{\mathcal{K}}^{\prime}}(\tilde{T}^{\prime})_{\mathcal{K}^{1},\mathcal{K}^{J}}\right\|_{\infty}\left\|t^{J}\right\|_{\mathrm{F}}$
(199)

Using Eq. (194) we arrive at

$\tilde{C}_{\tilde{\mathcal{K}}^{\prime}}(\tilde{T}^{\prime})_{\mathcal{K}^{1},\mathcal{K}^{J}}=\bigl{(}s^{l_{1}}\otimes
s^{l_{2}}\otimes\dots\otimes s^{l_{M}}\otimes
C_{\mathcal{K}^{\prime}}(T^{\prime})\bigr{)}_{\mathcal{K}^{1},\mathcal{K}^{J}}\,.$
(200)

By construction, each auxiliary tensor $s^{l}$ is an identity matrix with one
index in $\mathcal{K}^{1}$ and one in $\mathcal{K}^{J}$ and the corresponding
matricization has unit spectral norm. Using Eq. (191), we obtain

$\left\|\tilde{C}_{\tilde{\mathcal{K}}^{\prime}}(\tilde{T}^{\prime})_{\mathcal{K}^{1},\mathcal{K}^{J}}\right\|_{\infty}=\left\|C_{\mathcal{K}^{\prime}}(T^{\prime})_{{\mathcal{K}^{\prime}}^{1},{\mathcal{K}^{\prime}}^{J}}\right\|_{\infty},$
(201)

where ${\mathcal{K}^{\prime}}^{1}\subset\mathcal{K}^{1}$ and
${\mathcal{K}^{\prime}}^{J}\subset\mathcal{K}$ are those pointer pairs of
$\mathcal{K}^{1}$ and $\mathcal{K}^{2}$ have no pointer to any $s^{l}$ (there
are no contractions between $S$ and $T^{\prime}$).

Iterating Lemma 30 and using the bound (190) and Eq. (193) we obtain that

$\left\|C_{\mathcal{K}^{\prime}}(T^{\prime})_{{\mathcal{K}^{\prime}}^{1},{\mathcal{K}^{\prime}}^{J}}\right\|_{\infty}\leq\left\|t^{2}\right\|_{\mathrm{F}}\left\|t^{3}\right\|_{\mathrm{F}}\dots\left\|t^{J-1}\right\|_{\mathrm{F}}\,.$
(202)

This completes the proof. ∎

We use the notation for matricizations introduced right before Proposition 18
to state the following.

######  Lemma 30.

Let $t^{1}\in\mathbb{C}^{n_{1}\times n_{2}\times\dots\times n_{K^{1}}}$ and
$t^{2}\in\mathbb{C}^{n_{K^{1}+1}\times n_{K^{2}+2}\times\dots\times
n_{K^{1}+K^{2}}}$ be tensors with index pointers
$\mathcal{K}^{1}\coloneqq[K^{1}]$ and
$\mathcal{K}^{2}\coloneqq[K^{1}+K^{2}]\setminus[K^{1}]$, respectively.
Further, let $C_{\mathcal{M}}$ be a partial contraction over indices
$\mathcal{M}=\\{(k_{l},k^{\prime}_{l})\\}_{l\in[L]}$ with
$M^{1}\coloneqq\\{k_{l}\\}_{l\in[L]}\subset\mathcal{K}^{1}$ pointing to
indices of $t^{1}$ and
$M^{2}\coloneqq\\{k^{\prime}_{l}\\}_{l\in[L]}\subset\mathcal{K}^{2}$ pointing
to indices of $t^{2}$. Let $C_{\mathcal{M}}(T)_{L,R}$ be a matricization of
$C_{\mathcal{M}}(s,t)$ with row indices $L$ and column indices $R$ where
$L\,\dot{\cup}\,M^{1}\,\dot{\cup}\,M^{2}\,\dot{\cup}\,R=\mathcal{K}^{1}\,\dot{\cup}\,\mathcal{K}^{2}$.
Then

$\left\|C_{\mathcal{M}}(s,t)_{L,R}\right\|_{\infty}\leq\left\|t^{1}_{L^{1},R^{1}\cup
M^{1}}\right\|_{\infty}\left\|t^{2}_{M^{2}\cup
L^{2},R^{2}}\right\|_{\infty}\,,$ (203)

where $L^{1}=\mathcal{K}^{1}\cap L$, $R^{1}=\mathcal{K}^{1}\cap R$,
$L^{2}=\mathcal{K}^{2}\cap L$, and $R^{2}=\mathcal{K}^{2}\cap R$ are the
row/column indices of $t^{1}$ and $t^{2}$, respectively.

###### Proof.

We write the matricized partially contracted tensor network as a matrix
product,

$C_{\mathcal{M}}(s,t)_{L,R}=\left(t^{1}_{L^{1},R^{1}\cup
M^{1}}\otimes\mathrm{id}_{L^{2}}\right)\left(\mathrm{id}_{R_{1}}\otimes
t^{2}_{M^{2}\cup L^{2},R^{2}}\right),$ (204)

where $\mathrm{id}_{L^{2}}$ denotes the identity matrix with row indices given
by $L^{2}$ and matching column indices and similarly for
$\mathrm{id}_{R_{1}}$; e.g., $\mathrm{id}_{\\{3,5\\}}$ has the matrix
components
$(\mathrm{id}_{\\{3,5\\}})_{(i_{3},i_{5}),(i^{\prime}_{3},i^{\prime}_{5})}=\delta_{i_{3},i^{\prime}_{3}}\delta_{i_{5},i^{\prime}_{5}}$
for $i_{j},i^{\prime}_{j}\in[n_{j}]$. Using Eqs. (189) and (191) finishes the
proof. ∎

## References

  * Chuang and Nielsen (1997) I. L. Chuang and M. A. Nielsen,  _Prescription for experimental determination of the dynamics of a quantum black box_ , J. Mod. Opt. 44, 2455 (1997).
  * Mohseni  _et al._ (2008) M. Mohseni, A. T. Rezakhani, and D. A. Lidar,  _Quantum-process tomography: Resource analysis of different strategies_ , Phys. Rev. A 77, 032322 (2008).
  * Kliesch  _et al._ (2016) M. Kliesch, R. Kueng, J. Eisert, and D. Gross,  _Improving compressed sensing with the diamond norm_ , IEEE Trans. Inf. Th. 62, 7445 (2016).
  * Brandão  _et al._ (2016a) F. G. S. L. Brandão, A. W. Harrow, and M. Horodecki,  _Efficient Quantum Pseudorandomness_ , Phys. Rev. Lett. 116, 170502 (2016a).
  * Nakata  _et al._ (2017) Y. Nakata, C. Hirche, M. Koashi, and A. Winter,  _Efficient Quantum Pseudorandomness with Nearly Time-Independent Hamiltonian Dynamics_ , Phys. Rev. X 7, 021006 (2017).
  * Onorati  _et al._ (2017) E. Onorati, O. Buerschaper, M. Kliesch, W. Brown, A. H. Werner, and J. Eisert,  _Mixing Properties of Stochastic Quantum Hamiltonians_ , Comm. Math. Phys. 355, 905 (2017).
  * Zhu  _et al._ (2016) H. Zhu, R. Kueng, M. Grassl, and D. Gross,  _The Clifford group fails gracefully to be a unitary 4-design_ , arXiv:1609.08172 [quant-ph].
  * Helsen  _et al._ (2016) J. Helsen, J. J. Wallman, and S. Wehner,  _Representations of the multi-qubit Clifford group_ , arXiv:1609.08188.
  * Cory  _et al._ (1998) D. G. Cory, M. D. Price, W. Maas, E. Knill, R. Laflamme, W. H. Zurek, T. F. Havel, and S. S. Somaroo,  _Experimental quantum error correction_ , Phys. Rev. Lett. 81, 2152 (1998).
  * Lanyon  _et al._ (2009) B. P. Lanyon, M. Barbieri, M. P. Almeida, T. Jennewein, T. C. Ralph, K. J. Resch, G. J. Pryde, J. L. O/’Brien, A. Gilchrist, and A. G. White,  _Simplifying quantum logic using higher-dimensional Hilbert spaces_ , Nature Phys. 5, 134 (2009).
  * Monz  _et al._ (2009) T. Monz, K. Kim, W. Hänsel, M. Riebe, A. S. Villar, P. Schindler, M. Chwalla, M. Hennrich, and R. Blatt,  _Realization of the Quantum Toffoli Gate with Trapped Ions_ , Phys. Rev. Lett. 102, 040501 (2009).
  * Fedorov  _et al._ (2012) A. Fedorov, L. Steffen, M. Baur, M. P. da Silva, and A. Wallraff,  _Implementation of a Toffoli gate with superconducting circuits_ , Nature 481, 170 (2012).
  * Flammia  _et al._ (2012) S. T. Flammia, D. Gross, Y.-K. Liu, and J. Eisert,  _Quantum tomography via compressed sensing: error bounds, sample complexity and efficient estimators_ , New J. Phys. 14, 095022 (2012).
  * Shabani  _et al._ (2011) A. Shabani, R. L. Kosut, M. Mohseni, H. Rabitz, M. A. Broome, M. P. Almeida, A. Fedrizzi, and A. G. White,  _Efficient Measurement of Quantum Dynamics via Compressive Sensing_ , Phys. Rev. Lett. 106, 100401 (2011).
  * Baldwin  _et al._ (2014) C. H. Baldwin, A. Kalev, and I. H. Deutsch,  _Quantum process tomography of unitary and near-unitary maps_ , Phys. Rev. A 90, 012110 (2014).
  * Kimmel and Liu (2015) S. Kimmel and Y.-K. Liu,  _Quantum compressed sensing using 2-designs_ , arXiv:1510.08887 [quant-ph].
  * Kueng  _et al._ (2017) R. Kueng, H. Rauhut, and U. Terstiege,  _Low rank matrix recovery from rank one measurements_ , Appl. Comp. Harm. Anal. 42, 88 (2017).
  * Rodionov  _et al._ (2014) A. V. Rodionov, A. Veitia, R. Barends, J. Kelly, D. Sank, J. Wenner, J. M. Martinis, R. L. Kosut, and A. N. Korotkov,  _Compressed sensing quantum process tomography for superconducting quantum gates_ , Phys. Rev. B 90, 144504 (2014).
  * Gross  _et al._ (2010) D. Gross, Y.-K. Liu, S. T. Flammia, S. Becker, and J. Eisert,  _Quantum State Tomography via Compressed Sensing_ , Phys. Rev. Lett. 105, 150401 (2010).
  * Gross (2011) D. Gross,  _Recovering Low-Rank Matrices From Few Coefficients in Any Basis_ , IEEE Trans. Inf. Th. 57, 1548 (2011).
  * Liu (2011) Y.-K. Liu,  _Universal low-rank matrix recovery from Pauli measurements_ , Adv. Neural Inf. Process. Syst. , 1638 (2011).
  * Altepeter  _et al._ (2003a) J. B. Altepeter, D. Branning, E. Jeffrey, T. C. Wei, P. G. Kwiat, R. T. Thew, J. L. O’Brien, M. A. Nielsen, and A. G. White,  _Ancilla-Assisted Quantum Process Tomography_ , Phys. Rev. Lett. 90, 193601 (2003a).
  * Kimmel  _et al._ (2014) S. Kimmel, M. P. da Silva, C. A. Ryan, B. R. Johnson, and T. Ohki,  _Robust Extraction of Tomographic Information via Randomized Benchmarking_ , Phys. Rev. X 4, 011050 (2014).
  * Candes  _et al._ (2006) E. J. Candes, J. Romberg, and T. Tao,  _Robust uncertainty principles: exact signal reconstruction from highly incomplete frequency information_ , IEEE Trans. Inform. Theor. 52, 489 (2006).
  * Donoho (2006) D. L. Donoho,  _Compressed sensing_ , IEEE Trans. Inf. Th. 52, 1289 (2006).
  * Yamamoto  _et al._ (2010) T. Yamamoto, M. Neeley, E. Lucero, R. C. Bialczak, J. Kelly, M. Lenander, M. Mariantoni, A. D. O’Connell, D. Sank, H. Wang, M. Weides, J. Wenner, Y. Yin, A. N. Cleland, and J. M. Martinis,  _Quantum process tomography of two-qubit controlled-Z and controlled-NOT gates using superconducting phase qubits_ , Phys. Rev. B 82, 184515 (2010).
  * Altepeter  _et al._ (2003b) J. B. Altepeter, D. Branning, E. Jeffrey, T. C. Wei, P. G. Kwiat, R. T. Thew, J. L. O’Brien, M. A. Nielsen, and A. G. White,  _Ancilla-assisted quantum process tomography_ , Phys. Rev. Lett. 90, 193601 (2003b).
  * Kim  _et al._ (2014) D. Kim, Z. Shi, C. B. Simmons, D. R. Ward, J. R. Prance, T. S. Koh, J. K. Gamble, D. E. Savage, M. G. Lagally, M. Friesen, S. N. Coppersmith, and M. A. Eriksson,  _Quantum control and process tomography of a semiconductor quantum dot hybrid qubit_ , Nature 511, 70 (2014).
  * Anderson  _et al._ (2015) B. E. Anderson, H. Sosa-Martinez, C. A. Riofrio, I. H. Deutsch, and P. S. Jessen,  _Accurate and robust unitary transformation of a high-dimensional quantum system_ , Phys. Rev. Lett. 114, 240401 (2015).
  * Merkel  _et al._ (2010) S. T. Merkel, C. A. Riofr$́\mathrm{$}{i}o, S. T. Flammia, and I. H. Deutsch,  _Random unitary maps for quantum state reconstruction_ , Phys. Rev. A 81, 032126 (2010).
  * Blatt and Roos (2012) R. Blatt and C. F. Roos,  _Quantum simulations with trapped ions_ , Nat. Phys. 8, 277 (2012).
  * Timoney  _et al._ (2008) N. Timoney, V. Elman, S. Glaser, C. Weiss, M. Johanning, W. Neuhauser, and C. Wunderlich,  _Error-resistant single-qubit gates with trapped ions_ , Phys. Rev. A 77, 052334 (2008).
  * Ohliger  _et al._ (2013) M. Ohliger, V. Nesme, and J. Eisert,  _Efficient and feasible state tomography of quantum many-body systems_ , New J. Phys. 15, 015024 (2013).
  * Bloch  _et al._ (2012) I. Bloch, J. Dalibard, and S. Nascimbene,  _Quantum simulations with ultracold quantum gases_ , Nat. Phys. 8, 267 (2012).
  * Kok  _et al._ (2007) P. Kok, W. J. Munro, K. Nemoto, T. C. Ralph, J. P. Dowling, and G. J. Milburn,  _Linear optical quantum computing with photonic qubits_ , Rev. Mod. Phys. 79, 135 (2007).
  * Carolan  _et al._ (2015) J. Carolan, C. Harrold, C. Sparrow, E. Mart$́\mathrm{$}{i}n-López, N. J. Russell, J. W. Silverstone, P. J. Shadbolt, N. Matsuda, M. Oguma, M. Itoh, G. D. Marshall, M. G. Thompson, J. C. F. Matthews, T. Hashimoto, J. L. O’Brien, and A. Laing,  _Universal linear optics_ , Science 349, 711 (2015).
  * Russell  _et al._ (2017) N. J. Russell, L. Chakhmakhchyan, J. L. O’Brien, and A. Laing,  _Direct dialling of Haar random unitary matrices_ , New J. Phys. 19, 033007 (2017).
  * Brandão  _et al._ (2016b) F. G. S. L. Brandão, A. W. Harrow, and M. Horodecki,  _Local Random Quantum Circuits are Approximate Polynomial-Designs_ , Comm. Math. Phys. 346, 397 (2016b).
  * Choi (1975) M.-D. Choi,  _Completely positive linear maps on complex matrices_ , Lin. Alg. App. 10, 285 (1975).
  * Jamiolkowski (1972) A. Jamiolkowski,  _Linear transformations which preserve trace and positive semidefiniteness of operators_ , Rep. Math. Phys. 3, 275 (1972).
  * Gilchrist  _et al._ (2005) A. Gilchrist, N. K. Langford, and M. A. Nielsen,  _Distance measures to compare real and ideal quantum processes_ , Phys. Rev. A 71, 062310 (2005).
  * Watrous (2009) J. Watrous,  _Semidefinite Programs for Completely Bounded Norms_ , Theory of Computing 5, 217 (2009).
  * Ben-Aroya and Ta-Shma (2009) A. Ben-Aroya and A. Ta-Shma,  _On the complexity of approximating the diamond norm_ , arXiv:0902.3397 [quant-ph].
  * Watrous (2012) J. Watrous,  _Simpler semidefinite programs for completely bounded norms_ , arXiv:1207.5726 [quant-ph].
  * Delsarte  _et al._ (1977) P. Delsarte, J. Goethals, and J. Seidel,  _Spherical codes and designs_ , Geom. Dedicata 6, 363 (1977).
  * Renes  _et al._ (2004) J. M. Renes, R. Blume-Kohout, A. J. Scott, and C. M. Caves,  _Symmetric informationally complete quantum measurements_ , J. Math. Phys. 45, 2171 (2004).
  * Ambainis and Emerson (2007) A. Ambainis and J. Emerson,  __Quantum t-designs: t-wise Independence in the Quantum World_ , _in  _Computational Complexity, 2007\. CCC ’07. Twenty-Second Annual IEEE Conference on_ (2007) pp. 129–140, quant-ph/0701126.
  * Gross  _et al._ (2007) D. Gross, K. M. R. Audenaert, and J. Eisert,  _Evenly distributed unitaries: on the structure of unitary designs_ , J. Math. Phys. 48, 052104 (2007).
  * Dankert  _et al._ (2009) C. Dankert, R. Cleve, J. Emerson, and E. Livine,  _Exact and approximate unitary 2-designs and their application to fidelity estimation_ , Phys. Rev. A 80, 012304 (2009).
  * Candès and Recht (2009) E. Candès and B. Recht,  _Exact Matrix Completion via Convex Optimization_ , Found. Comput. Math. 9, 717 (2009).
  * Recht  _et al._ (2010) B. Recht, M. Fazel, and P. A. Parrilo,  _Guaranteed Minimum-Rank Solutions of Linear Matrix Equations via Nuclear Norm Minimization_ , SIAM Rev. 52, 471 (2010).
  * Candès and Plan (2011) E. J. Candès and Y. Plan,  _Tight oracle bounds for low-rank matrix recovery from a minimal number of random measurements_ , IEEE Trans. Inform. Theory 57, 2342 (2011).
  * Kitaev  _et al._ (2002) A. Y. Kitaev, A. Shen, and M. N. Vyalyi,  _Classical and quantum computation_ , Vol. 47 (American Mathematical Society, 2002).
  * Watrous (2011) J. Watrous,  _CS 766 Theory of Quantum Information_ , Available online at https://cs.uwaterloo.ca/~watrous/LectureNotes.html (2011).
  * Kueng (2015) R. Kueng,  __Low rank matrix recovery from few orthonormal basis measurements_ , _in  _Sampling Theory and Applications (SampTA), 2015 International Conference on_ (2015) pp. 402–406.
  * Grant and Boyd (2014) M. Grant and S. Boyd,  _CVX: Matlab Software for Disciplined Convex Programming, version 2.1_ , http://cvxr.com/cvx (2014).
  * Grant and Boyd (2008) M. Grant and S. Boyd, in  _Recent advances in learning and control_ , Lecture Notes in Control and Information Sciences, edited by V. Blondel, S. Boyd, and H. Kimura (Springer-Verlag Limited, 2008) pp. 95–110, http://stanford.edu/~boyd/graph_dcp.html.
  * Kabanava  _et al._ (2015) M. Kabanava, R. Kueng, H. Rauhut, and U. Terstiege,  _Stable low-rank matrix recovery via null space properties_ , arXiv:1507.07184 [cs.IT].
  * Tropp (2015) J. A. Tropp,  _Convex recovery of a structured signal from independent random linear measurements_ , in  _Sampling Theory, a Renaissance_, edited by E. G. Pfander (Springer, 2015) pp. 67–101, arXiv:1405.1102.
  * Michel  _et al._ (2016) U. Michel, M. Kliesch, R. Kueng, and D. Gross,  _Note on the saturation of the norm inequalities between diamond and nuclear norm_ , arXiv:1612.07931 [cs.IT].
  * Note (1) $J(T_{|r})=U\Sigma_{r}V^{\dagger}$, where $J(T)$ as a singular value decomposition $J(T)=U\Sigma V^{\dagger}$ and $\Sigma_{r}$ is the diagonal matrix obtained from $\Sigma$ by setting all but the first $r$ diagonal entries to zero.
  * Steffens  _et al._ (2017) A. Steffens, C. A. Riofr$́\mathrm{$}{i}o, W. McCutcheon, I. Roth, B. A. Bell, A. McMillan, M. S. Tame, J. G. Rarity, and J. Eisert,  _Experimentally exploring compressed sensing quantum tomography_ , Quantum Sci. Technol. 2, 025005 (2017).
  * Note (2) Up to log-factors.
  * Haah  _et al._ (2017) J. Haah, A. W. Harrow, Z. Ji, X. Wu, and N. Yu,  _Sample-optimal tomography of quantum states_ , IEEE Trans Inf. Th. 63, 5628 (2017).
  * Shi (2002) Y. Shi,  _Both Toffoli and controlled-NOT need little help to do universal quantum computation_ , quant-ph/0205115.
  * Barenco  _et al._ (1995) A. Barenco, C. H. Bennett, R. Cleve, D. P. DiVincenzo, N. Margolus, P. Shor, T. Sleator, J. A. Smolin, and H. Weinfurter,  _Elementary gates for quantum computation_ , Phys. Rev. A 52, 3457 (1995).
  * Nielsen and Chuang (2010) M. A. Nielsen and I. L. Chuang,  _Quantum computation and quantum information_ (Cambridge university press, 2010).
  * Kitaev (1997) A. Y. Kitaev,  _Quantum computations: algorithms and error correction_ , Russian Math. Surv. 52, 1191 (1997).
  * Knill  _et al._ (1998) E. Knill, R. Laflamme, and W. H. Zurek,  _Resilient quantum computation: error models and thresholds_ , Proc. R. Soc. A 454, 365 (1998).
  * Aharonov and Ben-Or (1997) D. Aharonov and M. Ben-Or,  __Fault-tolerant quantum computation with constant error rate_ , _in  _29th ACM Symp. on Theory of Computing (STOC)_ (New York, 1997) pp. 176–188.
  * Flammia and Liu (2011) S. T. Flammia and Y.-K. Liu,  _Direct Fidelity Estimation from Few Pauli Measurements_ , Phys. Rev. Lett. 106, 230501 (2011).
  * Emerson  _et al._ (2005) J. Emerson, R. Alicki, and K. Życzkowski,  _Scalable noise estimation with random unitary operators_ , J. Opt. B 7, S347 (2005).
  * Wallman and Flammia (2014) J. J. Wallman and S. T. Flammia,  _Randomized benchmarking with confidence_ , New J. Phys. 16, 103032 (2014).
  * Kueng  _et al._ (2016) R. Kueng, D. M. Long, A. C. Doherty, and S. T. Flammia,  _Comparing Experiments to the Fault-Tolerance Threshold_ , Phys. Rev. Lett. 117, 170502 (2016).
  * Mendelson (2015) S. Mendelson,  _Learning Without Concentration_ , J. ACM 62, 21:1 (2015).
  * Koltchinskii and Mendelson (2015) V. Koltchinskii and S. Mendelson,  _Bounding the smallest singular value of a random matrix without concentration_ , International Mathematics Research Notices , rnv096 (2015).
  * Goodman and Wallach (2000) R. Goodman and N. R. Wallach,  _Representations and invariants of the classical groups_ , Vol. 68 (Cambridge University Press, 2000).
  * Tropp (2012) J. A. Tropp,  _User-friendly tools for random matrices: An introduction_, Tech. Rep. (DTIC Document, 2012).
  * Schollwöck (2011) U. Schollwöck,  _The density-matrix renormalization group in the age of matrix product states_ , Ann. Phys. 326, 96 (2011), January 2011 Special Issue.
  * Gharibian  _et al._ (2015) S. Gharibian, Z. Landau, S. W. Shin, and G. Wang,  _Tensor network non-zero testing_ , Quant. Inf. Comp. 15, 885 (2015).
  * Chandrasekaran  _et al._ (2012) V. Chandrasekaran, B. Recht, P. Parrilo, and A. Willsky,  _The Convex Geometry of Linear Inverse Problems_ , Found. Comput. Math. 12, 805 (2012).
  * Low (2010) R. A. Low,  _Pseudo-randomness and Learning in Quantum Computation_ , Ph.D. thesis, University of Bristol (2010), arXiv:1006.5227.
  * (83) E. Knill,  _Fermionic linear optics and matchgates_ , quant-ph/0108033.
  * Cai  _et al._ (2010) J.-F. Cai, E. J. Candes, and Z. Shen,  _A Singular Value Thresholding Algorithm for Matrix Completion_ , SIAM Journal on Optimization 20, 1956 (2010).
  * Chatterjee (2015) S. Chatterjee,  _Matrix estimation by universal singular value thresholding_ , Ann. Statist. 43, 177 (2015).
  * Boyd  _et al._ (2011) S. Boyd, N. Parikh, E. Chu, B. Peleato, and J. Eckstein,  _Distributed optimization and statistical learning via the alternating direction method of multipliers_ , Found. Trends Mach. Learn. 3, 1 (2011).
  * Voroninski (2013) V. Voroninski,  _Quantum tomography from few full-rank observables_ , arXiv:1309.7669 [math-ph].
  * Acharya  _et al._ (2016) A. Acharya, T. Kypraios, and M. Guta,  _Statistically efficient tomography of low rank states with incomplete measurements_ , New J. Phys. 18, 043018 (2016).
  * Acharya and Guta (2017) A. Acharya and M. Guta,  _Statistical analysis of compressive low rank tomography with random measurements_ , J. Phys. A 50, 195301 (2017).
  * Candès  _et al._ (2015) E. J. Candès, X. Li, and M. Soltanolkotabi,  _Phase retrieval from coded diffraction patterns_ , Appl. Comput. Harmon. Anal. 39, 277 (2015).
  * Gross  _et al._ (2016) D. Gross, F. Krahmer, and R. Kueng,  _Improved recovery guarantees for phase retrieval from coded diffraction patterns_ , Appl. Comput. Harmon. Anal. 41, 37 (2016).
  * Ziman (2008) M. Ziman,  _Process positive-operator-valued measure: A mathematical framework for the description of process tomography experiments_ , Phys. Rev. A 77, 062112 (2008).
  * Vershynin (2012) R. Vershynin,  _Introduction to the non-asymptotic analysis of random matrices_ , in  _Compressed Sensing: Theory and Applications_ (Cambridge University Press, 2012) pp. 210–268, arXiv:1011.3027 [math.PR].
  * Foucart and Rauhut (2013) S. Foucart and H. Rauhut,  _A mathematical introduction to compressive sensing_ (Springer, 2013).
  * Wik (2016a) _Symmetric group:S4_ , http://groupprops.subwiki.org/wiki/Symmetric_group:S4 (2016a), accessed: 2016-08-17.
  * Wik (2016b) _Linear representation theory of symmetric group:S4_ , http://groupprops.subwiki.org/wiki/Linear_representation_theory_of_symmetric_group:S4 (2016b), accessed: 2016-08-17.
  * Simon (1996) B. Simon,  _Representations of finite and compact groups_ , 10 (Am. Math. Soc., 1996).