# Guaranteed recovery of quantum processes from few measurements

M. Kliesch  Institute of Theoretical Physics and Astrophysics, University of
Gdańsk, Poland  R. Kueng  Institute for Theoretical Physics, University of
Cologne, Germany  Dahlem Center for Complex Quantum Systems, Freie Universität
Berlin, Germany  Institute for Quantum Information and Matter, California
Institute of Technology, USA  J. Eisert  Dahlem Center for Complex Quantum
Systems, Freie Universität Berlin, Germany  D. Gross  Institute for
Theoretical Physics, University of Cologne, Germany  Centre for Engineered
Quantum Systems, School of Physics, The University of Sydney, Australia

###### Abstract

Quantum process tomography is the task of reconstructing unknown quantum
channels from measured data. In this work, we introduce compressed sensing-
based methods that facilitate the reconstruction of quantum channels of low
Kraus rank. Our main contribution is the analysis of a natural measurement
model for this task: We assume that data is obtained by sending pure states
into the channel and measuring expectation values on the output. Neither
ancillary systems nor coherent operations across multiple channel uses are
required. Most previous results on compressed process reconstruction reduce
the problem to quantum state tomography on the channel’s Choi matrix. While
this ansatz yields recovery guarantees from an essentially minimal number of
measurements, physical implementations of such schemes would typically involve
ancillary systems. A priori, it is unclear whether a measurement model
tailored directly to quantum process tomography might require more
measurements. We establish that this is not the case.

Technically, we prove recovery guarantees for three different reconstruction
algorithms. The reconstructions are based on a trace, diamond, and
$\ell_{2}$-norm minimization, respectively. Our recovery guarantees are
uniform in the sense that with one random choice of measurement settings all
quantum channels can be recovered equally well. Moreover, stability against
arbitrary measurement noise and robustness against violations of the low-rank
assumption is guaranteed. Numerical studies demonstrate the feasibility of the
approach.

###### Contents

  1. I Introduction
    1. I.1 Motivation of our measurement model
    2. I.2 Our contribution
    3. I.3 Related work
    4. I.4 Experimental considerations
    5. I.5 Notation and terminology
      1. I.5.1 Maps on operators
      2. I.5.2 Norms
      3. I.5.3 Spherical and unitary designs
      4. I.5.4 Measurement terminology
  2. II Results
    1. II.1 Measurement model
    2. II.2 Reconstructions
    3. II.3 Noiseless case
      1. II.3.1 Recovery guarantees I
      2. II.3.2 Numerical demonstration
    4. II.4 Stability and robustness
      1. II.4.1 Recovery guarantees II
      2. II.4.2 Numerical example: Reconstructing the Toffoli gate
    5. II.5 Pauli measurements
    6. II.6 Sample complexity
    7. II.7 Applications to fault tolerant quantum computation
  3. III Analytical details and proofs
    1. III.1 Preliminaries
      1. III.1.1 Notation
      2. III.1.2 Normalization and centralization of the observables
      3. III.1.3 Minimum conic singular value
      4. III.1.4 Null space property
      5. III.1.5 Tools from representation theory
    2. III.2 Our bound on the minimum conic singular value
      1. III.2.1 Upper bound on the mean empirical width $W_{m}$
      2. III.2.2 Lower bound on the marginal tail function $Q_{\xi}$
    3. III.3 General tensor network bound
    4. III.4 Proofs of the reconstruction theorems
      1. III.4.1 Constrained trace norm minimization
      2. III.4.2 CPT-fit
      3. III.4.3 Constrained trace and diamond norm minimization
    5. III.5 Reconstruction from approximate 4-generic measurements
    6. III.6 Bosonic and fermionic linear optical circuits
  4. IV Conclusion
    1. IV.1 Outlook
  5. V Acknowledgements
  6. A Semidefinite programs for trace and diamond norm reconstruction
  7. B A non-commutative Khintchine inequality
  8. C Linear representation of the symmetric group $S_{4}$
  9. D Proof of the tensor network bound Proposition 18

##  I Introduction

Recent years have seen significant advances in the precise control of quantum
systems. Complex quantum states of systems with an increasing number of
degrees of freedom can be prepared and manipulated with high accuracy. In this
development, it is important to have tools at hand that allow for a complete
characterization of state or process that are actually being realized in a
given experimental setup. The task of reconstructing quantum states or process
Chuang and Nielsen (1997); Mohseni  _et al._ (2008) from experimental data is
variously called quantum state or quantum process _tomography_ , _estimation_
, or _recovery_.

The precise characterization of processes is highly relevant, e.g., in the
quest for scalable quantum computers. The stringent requirements of the error
correction threshold – and the adverse scaling of the error correction
overhead in terms of the noise – make it necessary that implementations of
quantum gates match their specification extremely closely. We note that full
quantum process tomography is distinct from certification protocols or coarser
characterization schemes like randomized benchmarking (which reports only a
single number: a certain _error rate_). While this makes the latter type of
protocols much cheaper to implement, only process tomography allows one to
understand in precisely which way a quantum gate deviates from its
specification.

The task of quantum process tomography – important as it is – comes at a high
price: This is an unfavourable scaling of the necessary effort with the system
size. To learn an unknown unstructured process acting on an $n$-dimensional
quantum systems, $m\sim n^{4}$ expectation values are required. However,
common processes exhibit additional structure. Most importantly, quantum gates
correspond to unitary processes, which are quantum channels with Kraus rank
equal to one. Compressed sensing techniques allow one to estimate channels
with (approximately) low Kraus rank from significantly fewer measurements than
naively required. It is imperative to make use of this structure.

###  I.1 Motivation of our measurement model

The most general quantum process tomography setting allows for “coherent
measurements” of an unknown channel $T$. Here, $m$ identical copies of $T$ are
available simultaneously. At the same time, only part of the input state may
be sent through the copies of $T$, while another part potentially entangled
with the former is left unchanged. This in turn allows for performing
measurements on $T^{\otimes m}\otimes\mathrm{id}_{n^{m}}$ — where
$\mathrm{id}_{n^{m}}$ denotes the identity map on a $n^{m}$-dimensional
additional ancillary Hilbert space that may be available – rather than
“sequential” measurements on single copies of $T$. This includes the
possibility of choosing global, entangled input states
$\rho_{\textrm{global}}$, and likewise performing correlated measurements on
the respective output states $(T^{\otimes
m}\otimes\mathrm{id}_{n^{m}})(\rho_{\textrm{global}})$.

While potentially powerful, coherent measurements are arguably impractical.
This is in particular true when attempting to diagnose errors in
implementations of a quantum gates, as these are exactly the building blocks
of circuits that would be used to prepare the entangled input state in the
first place.

Avoiding this drawback, we adopt an experimentally feasible “sequential”
measurement model. What is more, we resort to the situation where the local
input states $\rho_{\textrm{loc}}$ are transmitted via individual copies of
the unknown channel $T$ in their entirety. This setting is often referred to
as “ancilla-free” or “direct” process tomography. Data acquisition is then
concluded by performing measurements on the individual output states
$T(\rho_{\textrm{loc}})$.

We employ the following natural measurement setup: the unknown quantum channel
$T$ is applied to pure input states
$\left.\left|{\psi_{i}}\right.\right\rangle\\!\\!\left.\left\langle{\psi_{i}}\right.\right|$.
Subsequently, the expectation value of an observable $A_{i}$ on the output is
measured. Those expectation values are estimated by means of a suitably
frequent repetition of the prescription choosing the same measurement setting.
Repeating this procedure $m$ times for different input states
$\left.\left|{\psi_{i}}\right.\right\rangle\\!\\!\left.\left\langle{\psi_{i}}\right.\right|$
and observables $A_{i}$ results in a _measurement vector_ of the form

$y_{i}\approx\operatorname{Tr}\bigl{[}A_{i}T(\left.\left|{\psi_{i}}\right.\right\rangle\\!\\!\left.\left\langle{\psi_{i}}\right.\right|)\bigr{]},\quad
1\leq i\leq m.$ (1)

For our theoretical recovery guarantees, the input states and observables are
assumed to be sampled independently from certain ensembles – see below for
details. We restrict attention to pure input states, as they are expected to
yield the most information about $T$, and also because the preparation of pure
input states is easily possible in most experimental setups. We expect it to
be straight-forward to generalize this work to take mixed input states into
account.

###  I.2 Our contribution

We investigate several channel reconstruction protocols that exploit the
measured channel to have an (approximately) low Kraus rank. Inspired by
compressed sensing, these protocols require considerably fewer measurements of
the form (1) than traditional process tomography schemes and contain
computationally tractable reconstruction algorithms. We provide rigorous
recovery guarantees featuring very desirable properties (uniform, stable, and
robust). This analytical work is complemented by a comprehensive numerical
analysis of the reconstruction protocols. In contrast to previous compressed
sensing results that are applicable to process tomography, our reconstruction
protocols specifically address the natural process tomography setup described
above. Our focus is on a particularly simple reconstruction:

  1. i)

A least squares fit of the observed data subject to an additional positivity
constraint. We call this approach _CPT-fit_. A distinct advantage of the CPT-
fit is that the algorithm does not depend on any parameters. In particular, no
estimate of the true rank or the noise strength is required. This stands in
contrast to most compressed sensing-based based reconstruction schemes. Also,
the CPT-fit appears to be particularly robust against violations of the
assumption of low Kraus rank.

In order to link and compare the CPT-fit to more established low-rank matrix
reconstruction methods we also investigate other reconstruction protocols.
Their analytical analysis is also the basis for the recovery guarantees of the
CPT-fit.

  1. ii)

The second reconstruction method resembles a typical low-rank matrix
reconstruction protocol: minimize the trace norm subject to convex constraints
that take into account acquired data of the form (1).

  2. iii)

The third recovery algorithm closely resembles the previous one, but contains
trace preservation as an additional (linear) constraint.

  3. iv)

Otherwise similar to algorithm iii), this reconstruction protocol replaces the
constrained trace norm minimization by a diamond norm minimization. The
constraints remain unchanged. The diamond norm is a well-motivated distance
measure for quantum channels. A priori, this does not imply in any way that
the diamond norm is also a good choice as a regularizing function for channel
estimation. However, Ref. Kliesch  _et al._ (2016) does provide strong
analytical and numerical arguments for why one should expect the diamond norm
to outperform the trace norm as a regularizer in this setting. The numerical
studies conducted in this paper lend further credence to this claim.

  4. v)

Similar to algorithm iv), but with an additional trace preservation
constraint.

We provide rigorous performance guarantees for the approaches i), iii) and v).
The guarantees are valid for measurement setups where the pure input states
$\left.\left|{\psi_{i}}\right.\right\rangle$ and the eigenbases of the
observables $A_{i}$ are drawn at random from certain ensembles. Technically,
we require the state vectors and the eigenbases to approximately form
_4-designs_ in a precise sense. Corresponding ensembles of unitaries can be
generated using random quantum circuits Brandão  _et al._ (2016a); Nakata  _et
al._ (2017) or fluctuating Hamiltonians Onorati  _et al._ (2017). Haar-random
vectors have this property, but recent results on the fourth moments of the
Clifford group Zhu  _et al._ (2016); Helsen  _et al._ (2016) suggest that
there are more structured and explicit ensembles with similar properties.

Even if a particular practical setup fails to show the (approximate) 4-design
property, our results are still a relevant proof of concept. Indeed, in
contrast to previous compressed sensing approaches, our reconstruction
guarantees show that the specific mathematical structure present in process
tomography does not imply that a larger number of measurement settings is
required.

What is more, we provide numerical simulations showing that the recovery
algorithms work well for a number of measurement models not having the
4-design property. This includes the paradigmatic case of Pauli-type
measurements.

We demonstrate our channel reconstruction procedures on generic quantum
channels of varying Kraus rank, as well as the Toffoli gate. The latter is a
three-qubit unitary quantum gate that is highly relevant in quantum
processing. Moreover, it has been experimentally implemented in various
architectures Cory  _et al._ (1998); Lanyon  _et al._ (2009); Monz  _et al._
(2009); Fedorov  _et al._ (2012).

Finally, we also comment that our reconstruction protocols can also be applied
in the setting of bosonic and fermionic linear optical circuits.

###  I.3 Related work

Recent years have seen considerable advance of compressed sensing tools for
the tomographic reconstruction of low-rank quantum states Flammia  _et al._
(2012); Shabani  _et al._ (2011); Baldwin  _et al._ (2014); Kimmel and Liu
(2015); Kueng  _et al._ (2017). To some extent, these findings have also been
adapted to cover process tomography. Such compressed sensing approaches allow
to reconstruct processes of low Kraus rank from much fewer expectation values
than a naive dimension count would suggest.

Our trace norm minimization (algorithms ii) and iii)) builds on a by now well-
established method for low-rank matrix reconstruction Flammia  _et al._
(2012). With the diamond norm minimization (algorithms iv) and v)) we continue
a line of research that has been started in Ref. Kliesch  _et al._ (2016) and
support it with rigorous performance guarantees.

The CPT-fit has been suggested in Ref. Baldwin  _et al._ (2014) and
numerically compared to full tomography and compressed sensing in Ref.
Rodionov  _et al._ (2014). These works provide numerical studies that
demonstrate the capability of such a reconstruction procedure. We expand on
these ideas by conducting additional numerical experiments. But, more
importantly, we also prove rigorous recovery guarantees for the CPT-fit.

Ref. Flammia  _et al._ (2012) presents a process tomography protocol that is
based on low-rank matrix reconstruction with random Pauli measurements Gross
_et al._ (2010); Gross (2011); Liu (2011). These low rank recovery guarantees
can be applied to the Choi-Jamiołkowski representation of a quantum channel,
since the rank of this matrix representation equals the Kraus rank of the
original channel. On first sight, such an approach requires the use of an
ancilla in order to implement the Choi-Jamiołkowski representation physically
in a concrete application Altepeter  _et al._ (2003a). However, Ref. Flammia
_et al._ (2012) also provides a more direct implementation of their protocol
that does not require any ancillas. Valid for multi-qubit processes this trick
exploits the tensor-product structure of (multi-qubit) Pauli operators. It
allows for effectively measuring the Pauli expectation value of a Choi matrix
by performing several natural channel measurements of the form (1) and
evaluating particular linear combinations thereof in a classical post-
processing step. The demerit of this approach is that the number of individual
channel measurements required to evaluate a single Pauli expectation value
scales with the dimension of the underlying Hilbert space. The measurement
model studied here does not require such a coarse-graining: every natural
measurement (1) itself already corresponds to a valid measurement instance.
This considerably reduces the number of different measurement settings that
are required in order to acquire sufficient data.

Randomized benchmarking has also been adapted to allow for process tomography
Kimmel  _et al._ (2014); Kimmel and Liu (2015). Ref. Kimmel  _et al._ (2014)
adopted randomized benchmarking techniques to obtain a process tomography
protocol that is robust towards state preparation and measurement errors
(SPAM). This is a distinct advantage over other protocols that do not share
this additional feature. However, the trade of between an increase of the
number of channel uses and the gained robustness towards SPAM errors remains
unclear.

Finally, Ref. Shabani  _et al._ (2011) also considered process tomography via
compressed sensing techniques. However, this method is somewhat different from
the other approaches presented here: Instead of assuming low Kraus rank, they
consider processes that are element-wise sparse with respect to a known basis.
Prior knowledge of this sparsifying basis is a necessary prerequisite for this
approach. In turn, techniques from traditional compressed sensing Candes  _et
al._ (2006); Donoho (2006) are applied (rather than low-rank matrix
reconstruction protocols) to reconstruct such processes from a number of
measurements that is proportional to the sparsity and depends only
logarithmically on the ambient system sizes. While requiring only very few
measurement settings, the main disadvantage of this approach are stronger
model assumptions (sparsity and knowledge of the sparsifying basis) and
measurements that may be challenging to implement in practice.

###  I.4 Experimental considerations

In several physically important platforms, process tomography has been
experimentally realized Yamamoto  _et al._ (2010); Altepeter  _et al._
(2003b); Kim  _et al._ (2014), both in the direct and hence ancilla-free Kim
_et al._ (2014); Yamamoto  _et al._ (2010) and ancilla-based Altepeter  _et
al._ (2003b) reading of the task. These works make use of different
preparations and measurements. It should be clear, however, that in several
physical architectures, random measurements of the type discussed here can
readily experimentally be implemented.

Specifically, Haar random unitary maps have been realized in a 16-dimensional
Hilbert space associated with the $6\mathrm{S}_{1/2}$ ground state of
${}^{133}\mathrm{Cs}$ atoms Anderson  _et al._ (2015). This has been achieved
by suitably exploiting a time-dependent Hamiltonian evolution giving rise to
Haar random unitaries, making use of methods of quantum control. Such random
unitaries have been put to use in a tomographic protocol, in an approach of
performing quantum tomography based on Haar random unitaries that builds upon
earlier theoretical ideas laid out in Ref. Merkel  _et al._ (2010). The same
idea of generating Haar random unitaries using suitable time-dependent
Hamiltonians should readily apply to systems of trapped ions Blatt and Roos
(2012), where a suitable type of control can be achieved with present
technology. Indeed, in a different context, methods of optimal control have
readily been applied to optimize quantum gates for trapped ions Timoney  _et
al._ (2008).

Random unitaries, albeit not Haar distributed, that allow for quantum state
tomography of quantum many-body systems have been theoretically considered
Ohliger  _et al._ (2013), making use of operations only that can be considered
basically feasible in experiments with cold atoms in optical lattices Bloch
_et al._ (2012), such as optical super-lattices and time-of-flight
measurements.

In integrated linear optical architectures Kok  _et al._ (2007); Carolan  _et
al._ (2015), Haar-random circuits are readily conceivable Russell  _et al._
(2017). It is this type of setting in which the methods presented here are
most applicable, even though they apply to any physical system in which
unitary $4$-designs are feasible. This includes settings in which random
circuits Brandão  _et al._ (2016b); Nakata  _et al._ (2017) or randomly time-
fluctuating dynamics Onorati  _et al._ (2017) can be used to generate
approximate unitary designs.

###  I.5 Notation and terminology

In this section we introduce some basic preliminaries needed to understand our
main results. For any integer $n\in\mathbb{Z}^{+}$ we use the notation
$[n]\coloneqq\\{1,2,\dots,n\\}$. The space of linear operators on a vector
space $\mathcal{V}$ is denoted by $\operatorname{\mathrm{L}}(\mathcal{V})$.

If $\mathcal{V}$ is a Hilbert space, we denote vectors by
$\left.\left|{\psi}\right.\right\rangle\in\mathcal{V}$ and its adjoints
(conjugate transposes) by $\left.\left\langle{\psi}\right.\right|$. So the
projector onto a normalized $\left.\left|{\psi}\right.\right\rangle$ is
$\left.\left|{\psi}\right.\right\rangle\\!\\!\left.\left\langle{\psi}\right.\right|$.
Moreover, the real vector space of self-adjoint operators is denoted by
$\operatorname{Herm}(\mathcal{V})$.

Figure 1: The Choi-Jamiołkowskiisomorphism and partial trace in terms of
tensor network diagrams (explained in Figure 8).
Left: Order-$4$ tensor
$M\in\operatorname{\mathrm{L}}(\operatorname{\mathrm{L}}(\mathcal{V})\to\operatorname{\mathrm{L}}(\mathcal{W}))$
as a map from
$\operatorname{\mathrm{L}}(\mathcal{V})\cong\mathcal{V}\otimes\mathcal{V}^{\ast}$
to
$\operatorname{\mathrm{L}}(\mathcal{W})\cong\mathcal{W}\otimes\mathcal{W}^{\ast}$.
Middle: Its Choi-matrix $J(M)$ as an operator on
$\mathcal{W}^{\ast}\otimes\mathcal{V}\cong\mathcal{W}\otimes\mathcal{V}$.
Right: Partial trace $\operatorname{Tr}_{1}[J(M)]$ of the Choi matrix $J(M)$.
This operator corresponds to the functional
$\rho\mapsto\operatorname{Tr}[M(\rho)]$.

####  I.5.1 Maps on operators

We denote the space of linear _maps_ taking operators to operators by
$\operatorname{\mathbb{L}}(\mathbb{C}^{n})\coloneqq\operatorname{\mathrm{L}}(\operatorname{\mathrm{L}}(\mathbb{C}^{n}))$.
The Choi-Jamiołkowski isomorphism Choi (1975); Jamiolkowski (1972)
$J:\operatorname{\mathbb{L}}(\mathbb{C}^{n})\to\operatorname{\mathrm{L}}(\mathbb{C}^{n}\otimes\mathbb{C}^{n})$
takes such maps to operators on a tensor product space and is given by (see
also Figure 1 for a tensor network description)

$\displaystyle
J(M)\coloneqq\sum_{i,j=1}^{\dim(\mathcal{V})}M(\left.\left|{i}\right.\right\rangle\\!\\!\left.\left\langle{j}\right.\right|)\otimes\left.\left|{i}\right.\right\rangle\\!\\!\left.\left\langle{j}\right.\right|\,,$
(2)

where $\left\\{|i\rangle\right\\}_{i=1}^{\mathrm{dim}(\mathcal{V})}$ is an
(arbitrary) orthonormal basis of $\mathcal{V}$. Maps
$M\in\operatorname{\mathbb{L}}(\mathbb{C}^{n})$ can have different properties:
$M$ is called _hermiticity preserving_ if it satisfies
$M(A^{\dagger})=M(A)^{\dagger}$ for all operators
$A\in\operatorname{\mathrm{L}}(\mathbb{C}^{n})$. This is equivalent to
demanding that $J(M)$ is Hermitian. $M$ is called _trace preserving_ if
$\operatorname{Tr}[M(A)]=\operatorname{Tr}[A]$ for all
$A\in\operatorname{\mathrm{L}}(\mathbb{C}^{n})$ or, equivalently, if
$\operatorname{Tr}_{1}[J(M)]=\mathds{1}$, where
$\operatorname{Tr}_{1}:\operatorname{\mathrm{L}}(\mathbb{C}^{n}\otimes\mathbb{C}^{n})\to\operatorname{\mathrm{L}}(\mathbb{C}^{n})$
denotes the partial trace over the fist tensor factor. The affine subspace of
hermiticity and trace preserving maps is denoted by
$\operatorname{HT}(\mathbb{C}^{n})\subset\operatorname{\mathbb{L}}(\mathbb{C}^{n})$.
The identity map $\mathrm{id}_{k}\in\operatorname{\mathbb{L}}(\mathbb{C}^{k})$
is a particularly simple element of $\operatorname{HT}(\mathbb{C}^{n})$.
Moreover, $M\in\operatorname{\mathbb{L}}(\mathbb{C}^{n})$ is _completely
positive_ if for all $k\geq 1$ one has that $(M\otimes\mathrm{id}_{k})(A)$ is
positive semidefinite for every positive semidefinite operator
$A\in\operatorname{\mathrm{L}}(\mathbb{C}^{n}\otimes\mathbb{C}^{k})$. We will
use the shorthand notation $A\succeq 0$ to indicate positive-semidefiniteness
of $A$. In fact, a map $M$ is completely positive if and only if
$(M\otimes\mathrm{id}_{n})(A)\succeq 0$ ($k=n$). This in turn is equivalent to
$J(M)\succeq 0$.

The convex subset of completely positive and trace preserving (CPT) maps is
denoted by
$\operatorname{CPT}(\mathbb{C}^{n})\subset\operatorname{\mathbb{L}}(\mathbb{C}^{n})$.
Importantly, these maps take density matrices to density matrices, even when
applied to subsystems. Therefore, they are also called _quantum channels_ and
are a very general description of quantum processes, e.g. dynamics.

####  I.5.2 Norms

For $q\in\left[1,\infty\right[$, the _$\ell_{q}$ -norm_ of a vector
$v\in\mathbb{C}^{n}$ is

$\left\|v\right\|_{\ell_{q}}\coloneqq\left(\sum_{j=1}^{n}|v_{j}|^{q}\right)^{1/q}$
(3)

and the $\ell_{\infty}$-norm is
$\left\|v\right\|_{\ell_{\infty}}\coloneqq\max_{j\in[n]}|v_{j}|$. The
_Schatten $q$-norm_ $\left\|A\right\|_{q}$ of an operator $A$ corresponds to
the $\ell_{q}$-norm of $A$’s singular values arranged in an $n$-dimensional
vector. Here, we will specifically encounter the following Schatten norms,

$\displaystyle\left\|A\right\|_{1}$
$\displaystyle=\operatorname{Tr}\bigl{[}\sqrt{AA^{\dagger}}\bigr{]}$ (trace
norm), (4) $\displaystyle\left\|A\right\|_{2}$
$\displaystyle=\sqrt{\operatorname{Tr}[AA^{\dagger}]}$ (Frobenius norm), (5)
$\displaystyle\left\|A\right\|_{\infty}$
$\displaystyle=\max_{\left.\left|{\psi}\right.\right\rangle}\frac{\left\|A\left.\left|{\psi}\right.\right\rangle\right\|_{\ell_{2}}}{\left\|\left.\left|{\psi}\right.\right\rangle\right\|_{\ell_{2}}}$
(spectral norm). (6)

Note that rank-one projectors
$\left.\left|{\psi}\right.\right\rangle\\!\\!\left.\left\langle{\psi}\right.\right|$
are unit normalized with respect to any Schatten-$p$ norm.

The spectral norm is also an example of an induced norm. This concept can be
generalized to norms on maps $M\in\operatorname{\mathbb{L}}(\mathbb{C}^{n})$.
In particular,

$\left\|M\right\|_{1\to
1}\coloneqq\max_{A}\frac{\left\|M(A)\right\|_{1}}{\left\|A\right\|_{1}}\,.$
(7)

is the induced trace norm. The _diamond norm_ is a stabilized version of this
norm:

$\left\|M\right\|_{\diamond}\coloneqq\left\|M\otimes\mathrm{id}_{n}\right\|_{1\to
1}\,.$ (8)

This is a particularly meaningful and widely appreciated distance measure for
quantum processes Gilchrist  _et al._ (2005). Perhaps surprisingly, it can be
calculated efficiently Watrous (2009); Ben-Aroya and Ta-Shma (2009); Watrous
(2012) as a semidefinite program. Regarding the reconstruction of structured
maps, the diamond norm can serve as a convex surrogate for low Kraus rank
Kliesch  _et al._ (2016). This is the case for channel reconstruction and two
of the five reconstruction protocols presented in this work build on this
idea.

####  I.5.3 Spherical and unitary designs

The probability measures on the unitary group, respectively, the unit complex
sphere that is invariant under multiplication with any unitary is called _Haar
measure_ and is the natural uniform measure on these sets. A _complex
projective $t$-design_ Delsarte  _et al._ (1977); Renes  _et al._ (2004);
Ambainis and Emerson (2007) is a probability distribution $\mu$ on the unit
sphere that reproduces the moments of the Haar measure up to order $t$ in both
$|\psi\rangle$ and $\langle\psi|$:

$\mathbb{E}_{\left.\left|{\psi}\right.\right\rangle\sim\mu}\bigl{[}(\left.\left|{\psi}\right.\right\rangle\\!\\!\left.\left\langle{\psi}\right.\right|)^{\otimes
t}\bigr{]}=\mathbb{E}_{\left.\left|{\psi}\right.\right\rangle\sim\mathrm{Haar}}\bigl{[}(\left.\left|{\psi}\right.\right\rangle\\!\\!\left.\left\langle{\psi}\right.\right|)^{\otimes
t}\bigr{]}\,.$ (9)

Similarly, a unitary design Gross  _et al._ (2007); Dankert  _et al._ (2009)
is a probability distribution $\nu$ on the unitary group satisfying

$\mathbb{E}_{U\sim\nu}\bigl{[}U^{\otimes t}XU^{\dagger\otimes
t}\bigr{]}=\mathbb{E}_{U\sim\mathrm{Haar}}\bigl{[}U^{\otimes
t}XU^{\dagger\otimes t}\bigr{]}$ (10)

for all operators $X\in\operatorname{\mathrm{L}}(\mathbb{C}^{n})^{\otimes t}$.
Typically, designs are considered to be uniform distributions over finite
sets.

####  I.5.4 Measurement terminology

In the compressed sensing literature, a single _measurement_ is usually given
by an inner product, which is a Hilbert-Schmidt inner product
$\operatorname{Tr}[AT(\left.\left|{\psi}\right.\right\rangle\\!\\!\left.\left\langle{\psi}\right.\right|)]$
in our case. In quantum physics terminology, a $(\psi,A)$ would correspond to
a _measurement setting_ , whereas a corresponding _measurement_ would be the
von-Neumann measurement of the observable $A$ in the state
$T(\left.\left|{\psi}\right.\right\rangle\\!\\!\left.\left\langle{\psi}\right.\right|)$
giving rise to an expectation value
$\operatorname{Tr}[AT(\left.\left|{\psi}\right.\right\rangle\\!\\!\left.\left\langle{\psi}\right.\right|)]$
in the limit of infinitely many repetitions. In order to also account for
finite sample errors we always allow for additive noise on the obtained
expectation values
$\operatorname{Tr}[AT(\left.\left|{\psi}\right.\right\rangle\\!\\!\left.\left\langle{\psi}\right.\right|)]$.

Figure 2: The tensorial structure of one measurement setting: $T$ is mapped to
$\operatorname{Tr}\bigl{[}UA_{0}U^{\dagger}T(\left.\left|{\psi}\right.\right\rangle\\!\\!\left.\left\langle{\psi}\right.\right|)\bigr{]}$.

##  II Results

In this section, we explicitly specify our measurement model of natural
measurements, explain how we computationally reconstruct the quantum channels
from the measurements, state our recovery guarantees, discuss their stability
and robustness properties, discuss our numerics on Pauli-type measurements,
and derive a sample complexity upper bound from our recovery guarantees.

###  II.1 Measurement model

We consider the task of reconstructing a quantum channel
$T\in\operatorname{CPT}(\mathbb{C}^{n})$ from measurement data of the form
(1): The unknown channel receives pure states
$\left.\left|{\psi_{i}}\right.\right\rangle\\!\\!\left.\left\langle{\psi_{i}}\right.\right|$
as input and subsequently expectation values of observables $A_{i}$ are
measured for the output state; see Figure 2 for a pictorial description. This
procedure is repeated $m$ times with different measurement settings (input
states and observables). Hence, the entire measurement process leads to a
_measurement vector_

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

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}.$
(12)

The vector $e\in\mathbb{R}^{m}$ denotes additive noise present in the
measurement process. In contrast to previous approaches Liu (2011); Flammia
_et al._ (2012), no prior assumptions on the nature of this noise corruption
are required.

Throughout this work, we consider instances of _random_ measurements
$\left\\{A_{i},\left.\left|{\psi_{i}}\right.\right\rangle\right\\}_{i=1}^{m}$
that are independent instances of a measurement _ensemble_
$\left(A,\left.\left|{\psi}\right.\right\rangle\right)$ that meets the
following requirements:

######  Definition 1 (4-generic measurement ensemble).

We call a measurement ensemble
$\left(A,\left.\left|{\psi}\right.\right\rangle\right)$ with observable $A$
and state $\left.\left|{\psi}\right.\right\rangle$ _4-generic_ if it fulfils
the following criteria:

  1. i)

The distribution of $\left.\left|{\psi}\right.\right\rangle$ in
$\mathbb{C}^{n}$ is a spherical $4$-design (9), i.e., it reproduces the first
four moments of the unitarily invariant (Haar) measure on the complex unit
sphere.

  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 chosen from a unitary $4$-design
(10), i.e., reproduces the first four moments of the Haar measure.

The measurement ensemble is called _normalized 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$.

Corresponding expectation values
$\operatorname{Tr}[AT(\left.\left|{\psi}\right.\right\rangle\\!\\!\left.\left\langle{\psi}\right.\right|)]$
of a quantum channel $T\in\operatorname{CPT}(\mathbb{C}^{n})$ are referred to
as _4-generic measurement_ and _normalized 4-generic measurement_ ,
respectively.

This definition encapsulates a variety of process measurement ensembles. In
particular, the _generic_ measurement ensemble
($\left.\left|{\psi}\right.\right\rangle$ and $U$ are Haar random states and
unitaries, respectively) meets the requirements by definition. However, our
recovery guarantees do not require such a strong notion of randomness in the
measurement design: $4$-designs are sufficient. In fact, it is sufficient when
the $4$-designs conditions are only fulfilled approximately, which we discuss
and show in Section III.5.

We also expect that the actual channel recovery works similarly well if
$\left.\left|{\psi}\right.\right\rangle$ and $U$ are chosen from other
distributions, provided that they cover the complex unit sphere and $U(n)$
“evenly” enough (see Section IV for a further discussion). We confirm this
expectation with numerical simulations with Pauli-type measurements, see
Section II.5.

###  II.2 Reconstructions

In this section, we lay out how a quantum channel $T$ can be reconstructed
from data of the form (11) for measurement settings given by $\mathcal{A}$. We
put an emphasis on describing the fitting method $T^{\ell_{2}}$ referred to as
_CPT-fit_. To complement this approach, we also investigate the reconstruction
methods $T^{\ast}_{\eta}$ and $T^{\ast c}_{\eta}$ as versions of low-rank
matrix reconstruction as well as $T^{\diamond}_{\eta}$ and $T^{\diamond
c}_{\eta}$ as reconstruction methods based on the diamond norm.

To start with the former, we minimize the square loss under the model
constrained that $T$ is a quantum process to obtain

$\displaystyle
T^{\ell_{2}}\coloneqq\operatorname*{arg\,min}\\{\left\|\mathcal{A}(T)-y\right\|_{\ell_{2}}:\,T\in\operatorname{CPT}(\mathbb{C}^{n})\\}\,.$
(13)

This minimization is essentially a fit under a CPT-constraint and we will call
it _CPT-fit_. It has been suggested and numerically investigated in Ref.
Baldwin  _et al._ (2014). This approach makes use of the measurement data $y$
alone.

More common low-rank matrix reconstruction methods in compressed sensing use
the trace norm as a so-called regularizer to favour low-rank solutions Candès
and Recht (2009); Recht  _et al._ (2010); Gross (2011); Candès and Plan
(2011). These reconstructions do not only make use of the data $y$, but
require an a-priori bound $\eta>0$ on the noise $e$,

$\left\|e\right\|_{\ell_{2}}\leq\eta\,.$ (14)

Applied to the Choi matrix $J(T)$ of a quantum channel $T$, the usual trace
norm regularization leads to the reconstructions

$\displaystyle T^{\ast}_{\eta}$
$\displaystyle\coloneqq\operatorname*{arg\,min}\\{\left\|J(T)\right\|_{1}:T\in\operatorname{\mathbb{L}}(\mathbb{C}^{n}),\
\left\|\mathcal{A}(T)-y\right\|_{\ell_{2}}\leq\eta\\}\,,$ (15) $\displaystyle
T^{\ast c}_{\eta}$
$\displaystyle\coloneqq\operatorname*{arg\,min}\\{\left\|J(T)\right\|_{1}:T\in\operatorname{HT}(\mathbb{C}^{n}),\
\left\|\mathcal{A}(T)-y\right\|_{\ell_{2}}\leq\eta\\}\,.$ (16)

These two approaches are very similar. However, the second one contains an
additional constraint that enforces hermicity and trace preservation.

The diamond norm is well-known in quantum information theory as a measure of
distinguishability of quantum channels by expectation values (Kitaev  _et al._
, 2002, Chapter 11), Watrous (2011) and can practically be calculated and
minimized using a semidefinite program Watrous (2012). For non-obvious
reasons, it can also be used as a reguralizer for the reconstruction of
certain maps on operators Kliesch  _et al._ (2016), leading to the
reconstructions

$\displaystyle T^{\diamond}_{\eta}$
$\displaystyle\coloneqq\operatorname*{arg\,min}\\{\left\|T\right\|_{\diamond}:T\in\operatorname{\mathbb{L}}(\mathbb{C}^{n}),\
\left\|\mathcal{A}(T)-y\right\|_{\ell_{2}}\leq\eta\\}\,,$ (17) $\displaystyle
T^{\diamond c}_{\eta}$
$\displaystyle\coloneqq\operatorname*{arg\,min}\\{\left\|T\right\|_{\diamond}:T\in\operatorname{HT}(\mathbb{C}^{n}),\
\left\|\mathcal{A}(T)-y\right\|_{\ell_{2}}\leq\eta\\}\,,$ (18)

where $\eta\geq 0$ is again an anticipated bound on the measurement noise.

Superior performance over simple inversion methods is expected for channels
with small Kraus rank with unitary channels being the most extreme case.
Perhaps surprisingly at first sight, the CPT-fit performs equally well as the
other reconstruction methods based on the trace (15), (16) or diamond norm
(17), (18) minimization. However, a quantum channel $T$ has a Choi matrix
$J(T)$ with constant trace norm $\left\|J(T)\right\|_{1}=n$. Hence, one can
omit the trace norm minimization in the the program (16) when the additional
constraint $J(T)\succeq 0$ is enforced, i.e.
$T\in\operatorname{CPT}(\mathbb{C}^{n})$. Minimizing the square loss
$\left\|\mathcal{A}(T)-y\right\|_{\ell_{2}}$ instead then yields the CPT-fit
(13).

(a)  (b)

Figure 3: Retrieval of random quantum channels
$T_{0}\in\operatorname{CPT}(\mathbb{C}^{4})$ for vanishing noise $e=0$. The
measurement settings $\mathcal{A}$ are drawn i.i.d. in each trial. The
parameter $\eta$ in the reconstructions (15), (16), (18) and (18) is chosen to
be ten times machine precision.

We mention once more that existing recovery guarantees for low-rank matrix
reconstruction Recht  _et al._ (2010); Gross (2011); Liu (2011); Kueng (2015)
do not apply to the measurement model considered here. Our measurement setting
(12) carries a certain product structure (see Figure 2) that is more
restrictive than the structure covered in prior works.

###  II.3 Noiseless case

For sake of clarity, we first discuss the noiseless case ($e=0$) and will
discuss stability and robustness in Section II.4.

####  II.3.1 Recovery guarantees I

We have recovery guarantees for the minimizations (16), (18), and (13), where
trace preservation features as a constraint.

######  Theorem 2 (Uniform recovery guarantees (noiseless case)).

Fix $r\leq n^{2}$ and suppose that
$\mathcal{A}:\operatorname{CPT}(\mathbb{C}^{n})\to\mathbb{R}^{m}$ contains

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

4-generic measurements which are chosen independently from the measurement
ensemble introduced in Definition 1. Then, with probability at least
$1-\mathrm{e}^{-\lambda m}$, all $T_{0}\in\operatorname{CPT}(\mathbb{C}^{n})$
with Kraus rank at most $r$ may be reconstructed exactly from noiseless
measurements $y=\mathcal{A}(T_{0})$.

This exact reconstruction is achieved by each of the minimizations (16), (18),
or (13). Here, $C$ and $\lambda$ are universal constants (which can, in
principle, be extracted explicitly from the proof).

This statement follows from more general results, namely Theorems 19, 20, and
24 below. Stability and robustness are discussed with Theorems 3 and 4.

##### Remarks

:

  1. i)

The number of real parameters required to specify a general hermiticity
preserving map $T_{0}\in\operatorname{\mathbb{L}}(\mathbb{C}^{n})$ is $n^{4}$.
If said map is also trace preserving, then $n^{4}-n^{2}$ many parameters are
required. The same holds for $T_{0}\in\operatorname{CPT}(\mathbb{C}^{n})$. If
the Kraus rank of $T_{0}$ is $\operatorname{rank}(J(T_{0}))=r$ then $T_{0}$ is
compressible in the sense that an order of $rn^{2}$ parameters suffices to
describe $T_{0}$. Therefore, up to the factor $\ln(n)$, the scaling (19) of
the number of measurements is optimal.

  2. ii)

The scaling (19) also contains a constant $C$ that we have not bounded
explicitly. Numerically, we find for $n=4,8$ that $m\geq 5\,r\,n^{2}$ generic
(Haar-random) measurements are sufficient for recovery, see Sections II.3.2
and II.4.2.

Such an approach is very common in compressed sensing: Recovery guarantees,
often with unknown constants and logarithmic factors in the scaling of the
number of measurements, ensure the functioning of the reconstruction procedure
also in the limit of large dimensions. The precise number of measurements and
the expected errors in a given setting are often determined numerically. Here,
also more special measurement settings can practically be considered. In
Section II.5, we numerically investigate Pauli-type measurements, which are
not covered by our recovery guarantees.

  3. iii)

The measurements are required to be given by exact $4$-designs. This condition
can be relaxed so that it is sufficient if the $4$-design conditions are
fulfilled only approximately. We prove that the recovery guarantees still hold
for certain $\epsilon/n^{4}$-approximate $4$-designs in Theorem 26. One can
use quantum pseudorandomness generation with random quantum circuits Brandão
_et al._ (2016b, a); Nakata  _et al._ (2017) or fluctuating Hamiltonians
Onorati  _et al._ (2017) to generate $\epsilon$-approximate designs. In both
cases, $\epsilon$ becomes exponentially small in the generation time (circuit
length/runtime), i.e., $\epsilon/n^{4}$ can be made small efficiently. In this
case, the measurement map needs to be obtained from the gate sequences or the
randomly fluctuating classical parameters of the Hamiltonian, respectively.

####  II.3.2 Numerical demonstration

Our variational reconstructions can be recast as standard convex optimization
problems (see also Appendix A). These can be solved computationally
efficiently and also practically using standard software such as CVX Grant and
Boyd (2014, 2008). For the reconstructions (13), (16), and (18) that have
trace preservation as a constraint we have proven that a number of

$m\geq m_{0}\coloneqq C\,r\,n^{2}\ln(n)$ (20)

measurement settings is sufficient to recover quantum channels of Kraus rank
$r$. We expect similar reconstruction properties for the unconstrained trace
and diamond norm reconstructions (15) and (17), although our proofs do not
directly carry over to that case. Indeed, low-rank matrices can often be
recovered via trace norm minimization from a number of measurements with such
an essentially optimal scaling Recht  _et al._ (2010); Gross (2011); Liu
(2011); Kueng  _et al._ (2017); Kabanava  _et al._ (2015).

Different reconstruction procedures with the optimal scaling (20) often have a
different constant $C$. For instance, Ref. Tropp (2015) shows that a constant
of size $C\simeq 6$ provably suffices for Gaussian measurement matrices (even
without the $ln(n)$ factor). On the other hand, the results presented in Refs.
Gross (2011); Liu (2011) are valid for more structured Pauli measurements and
require a much larger constant. Numerical studies typically highlight a
similar behaviour.

Exploiting additional prior information – such as the fact that quantum
channels preserve both hermiticity and traces – in the algorithmic
reconstructions (16), (18) can only lead to an improvement. In fact, these
constraints also facilitate the mathematical analysis. Besides being able to
prove recovery guarantees, we also observe the benefit of such additional
constraints numerically: Figure LABEL:sfig:Noiseless:a shows the _recovery
rates_ of different approaches.

This recovery rate is determined as follows. We say that a channel $T_{0}$ is
successfully reconstructed if the reconstructed channel $T^{\mathrm{rec}}$ is
close to the original one:
$\left\|T^{\mathrm{rec}}-T_{0}\right\|_{\mathrm{F}}\leq 10^{-5}$. We have
chosen $10^{-5}$ as threshold because we have observed the reconstruction
errors to be typically well separated from this value. Varying it changes the
curves in the plot only slightly. The precision of the convex optimization
software CVX Grant and Boyd (2014, 2008) in terms of the machine precision
$\mathrm{eps}=2^{-52}\approx 2.2\cdot 10^{-16}$ is $\sqrt{\mathrm{eps}}\approx
1.4\cdot 10^{-8}$. This somewhat limits the choice of thresholds. In order to
obtain the rate shown in the plots, we run $100$ independent instances and
obtain the rate as the percentage of trials with a successful reconstruction.

Our numerical studies are based on generic measurement ensembles (Haar random
input states, Haar random unitaries) and we have chosen $A_{0}$ to be a
diagonal $n\times n$ matrix whose spectrum evenly covers the interval
$[-1,1]$.

Interestingly, the unconstrained diamond norm minimization (17) performs
almost as good as its constrained counterpart (18). The heuristic reason for
this behaviour is that the diamond norm “favours” maps that satisfy a certain
trace preservation condition Kliesch  _et al._ (2016); Michel  _et al._
(2016), which is fulfilled for CPT maps. Moreover, the so-called descent cone
at CPT-maps of the diamond norm is contained in an intersection of descent
cones of nuclear norms Kliesch  _et al._ (2016). If this containment is
strict, it also leads to an improved recovery recovery guarantee.

Arguably the simplest reconstruction procedure is the fit under the CPT
constraint (13). Here, we observe that this protocol achieves a rate that is
very similar to the other constrained procedures (16), (18). Moreover, the
CPT-fit (13) clearly has the fastest computation time in our simple
implementation in CVX Grant and Boyd (2014, 2008) with Mosek 7.1 as a solver,
see Figure LABEL:sfig:Noiseless:b.

The required number of measurement settings (20) depends linearly on the Kraus
rank $r$ of the channels to be reconstructed. This dependence is confirmed for
small $r$ in our numerics for Hilbert space dimension $n=4$, see Figure 4. For
dimension $n=4$ the Kraus rank is $r\leq n^{2}=16$ and for $r=16$,
$m=\dim_{\mathbb{R}}(\operatorname{HT}(\mathbb{C}^{n}))=n^{4}-n^{2}=252$ of
measurement values are required for the reconstruction. Here,
$\dim_{\mathbb{R}}(\operatorname{HT}(\mathbb{C}^{n}))$ denotes the real
dimension of the affine space $\operatorname{HT}(\mathbb{C}^{n})$. This
observation explains the non-linear behaviour for larger $r$.

Figure 4:  Reconstruction of random quantum channels
$T_{0}\in\operatorname{CPT}(\mathbb{C}^{4})$ with different Kraus ranks
$r=\operatorname{rank}(J(T_{0}))$ from the CPT-fit (13). The white region
corresponds to $100\%$ observed recovery and the black one to $0\%$.
Parameters and measurements are as in Figure 3.

###  II.4 Stability and robustness

We consider two types of errors: i) the measurement errors $e$ already
indicated in the measurement model (12) and ii) model mismatches capturing
violations of the assumption $\operatorname{rank}(J(T_{0}))\leq r$ on the
Kraus rank.

For this purpose, we write $T\in\operatorname{CPT}(\mathbb{C}^{n})$ as
$T=T_{|r}+T_{\neg r}$ where $T_{|r}$ is defined to be a CPT map of Kraus rank
$r$ encompassing the $r$ largest eigenvalues 111
$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.  of the Choi-matrix $J(T)$ and $T_{\neg r}=T-T_{|r}$ is a
trace-annihilating map (i.e., $\operatorname{Tr}[T_{\neg r}(X)]=0$ for all
$X\in\operatorname{\mathbb{L}}(\mathbb{C}^{n})$) that is called the _model
mismatch_. In turn we relax our model assumption of low Kraus rank and allow
for small model mismatches.

A reconstruction is called _stable_ if it tolerates measurement errors and it
is called _robust_ if it tolerates model mismatches.

####  II.4.1 Recovery guarantees II

We prove all reconstructions from Theorem 2 to be stable against measurement
noise. Moreover, we prove the trace norm minimization (16) and the CPT-fit
(13) also to be robust against model mismatches.

######  Theorem 3 (Stability of the diamond norm reconstruction (18)).

Consider normalized 4-generic measurements from Definition 1. Then, under the
hypotheses of Theorem 2, reconstruction via the constrained diamond norm
minimization (18) is stable towards additive noise in the measurements
$y=\mathcal{A}(T_{0})+e$: for any $\eta\geq\left\|e\right\|_{\ell_{2}}$, the
associated reconstruction error obeys

$\left\|J(T_{0}-T^{\diamond
c}_{\eta})\right\|_{2}\leq\tilde{c}\,\frac{n^{2}}{\sqrt{m}\,\lVert
A_{0}\rVert_{2}}\,\eta\,.$ (21)

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

A more general version of this theorem – which allows for quantifying the
noise strength by any $\ell_{q}$-norm – is also true, see Corollary 24 below.

######  Theorem 4 (Stability and robustness, trace norm minimization (16) and
CPT-fit (13)).

Under the hypotheses of Theorem 2, reconstruction via the CPT-fit (13) is both
stable towards additive noise corruption and robust with respect to relaxing
the model assumption of Kraus rank $r$:

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

This performance guarantee is also valid for the constrained trace norm
minimization (16) if one replaces $\|e\|_{\ell_{2}}$ by the optimization
parameter $\eta$, provided that $\eta\geq\|e\|_{\ell_{2}}$

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

This statement summarizes two results – Theorems 19 and 20 below – that are
slightly more general: they allow for quantifying the reconstruction error
(22) and by any Schatten-$p$ norm with $p\in[1,2]$. Moreover, the noise
strength may be characterized by any $\ell_{q}$-norm:
$\eta\leavevmode\nobreak\ \geq\leavevmode\nobreak\ \|e\|_{\ell_{q}}$.

######  Corollary 5 (Normalization of the measurements).

Similar statements as in Theorems 3 and 4 hold also in the case of 4-generic
measurements, provided that $\eta$ is replaced by
$\eta/\left\|A_{0}\right\|_{\infty}$ and $\left\|A_{0}\right\|_{2}$ is
replaced by the $2$-norm of the traceless part of $A_{0}$.

##### Remarks

:

  1. i)

Theorem 4 guarantees approximate reconstructions for any quantum channel
$T_{0}\in\operatorname{CPT}(\mathbb{C}^{n})$ without requiring a prior rank
constraint. The deviation ${T_{0}}_{\neg r}$ from a channel of low Kraus rank,
i.e., the model mismatch, enters the error bound linearly. Such a robustness
is desirable for practical applications where the model assumption of low
Kraus rank is typically only approximately true.

  2. ii)

For the constrained norm minimizations (18) and (16), a prior error threshold
is required. This additional model selection task is important in actual
applications and can be a non-trivial task; see c.f., Ref. Steffens  _et al._
(2017). The CPT-fit (13) has the distinct advantage that the reconstruction
can be done without such a prior noise estimation.

  3. iii)

We emphasize that the dimensional scaling of the error bound in Eq (22) is a
consequence of the normalization we adopted. To make this precise, it is
useful to view these statements as results about stably reconstructing
(particular) Choi matrices
$J(T)\in\operatorname{\mathrm{L}}(\mathbb{C}^{n}\otimes\mathbb{C}^{n})\simeq\operatorname{\mathrm{L}}(\mathbb{C}^{n^{2}})$.
Rewriting the single expectation values (12) as

$y_{i}=\operatorname{Tr}\Bigl{[}A_{i}\otimes\left(\left.\left|{\psi_{i}}\right.\right\rangle\\!\\!\left.\left\langle{\psi_{i}}\right.\right|\right)^{T}J(T)\Bigr{]}+e_{i}$
(23)

reveals that all individual measurement matrices
$M_{i}=A_{i}\otimes\left(\left.\left|{\psi_{i}}\right.\right\rangle\\!\\!\left.\left\langle{\psi_{i}}\right.\right|\right)^{T}\in\operatorname{\mathrm{L}}(\mathbb{C}^{n^{2}})$
have constant Frobenius norm

$\left\|M_{i}\right\|_{\mathrm{F}}=\left\|A_{i}\otimes\left(\left.\left|{\psi_{i}}\right.\right\rangle\\!\\!\left.\left\langle{\psi_{i}}\right.\right|\right)^{T}\right\|_{\mathrm{F}}=\left\|A_{0}\right\|_{\mathrm{F}}\,.$
(24)

Choosing a particular normalization influences the signal-to-noise ratio (SNR)
in (23) and, in turn, the stability assertions. In order to avoid these
ambiguities, it is useful to rewrite Eq. (22) for vanishing model mismatch as

$\left\|J(T_{0}-T^{\ast
c}_{\eta})\right\|_{2}\leq\tilde{c}\frac{\sqrt{m}\,d}{\sum_{i=1}^{m}\left\|M_{i}\right\|_{\mathrm{F}}}\|e\|_{\ell_{2}}$
(25)

with $d\coloneqq\dim\bigl{(}\mathbb{C}^{n^{2}}\bigr{)}$. Note that the sum
scales like $m$. Up to our knowledge, all stable low-rank matrix
reconstruction guarantees are essentially222up to log-factors of this form!
This in particular includes Gaussian measurement ensembles (Candès and Plan,
2011, Theorem 2.3), random Pauli matrix measurements (Liu, 2011, Proposition
2.3) and outer products of standard Gaussian vectors (Kueng  _et al._ , 2017,
Theorem 2).

  4. iv)

Regarding sample complexity, an order of $rn^{5}\ln(n)/\epsilon^{2}$
independent channel evaluations (“samples”) are required to achieve a
reconstruction error of at most $\epsilon$ in Frobenius norm; see Section II.6
below. We expect this scaling to be close to optimal up to $\ln(n)$-factors
(at least for channels with very low Kraus rank $r$). Evidence for this is
provided by the discussion above: the stability guarantees in Theorem 3 and
Theorem 4 essentially match the best existing results on stable low-rank
matrix reconstruction. Among these are two that are applicable to the related
problem of quantum state tomography: random Pauli measurements Liu (2011) and
outer products of standard Gaussian vectors Kueng  _et al._ (2017).

The sample complexity of the former approach has been determined in Ref.
Flammia  _et al._ (2012). Moreover, it has been shown to be close to optimal
in the sense that it reproduces a fundamental lower bound – valid for any
tomographic procedure based on Pauli measurements – up to a single
$\ln(n)$-factor.

Fundamental lower bounds on the sample complexity achievable by any
tomographic procedure have been derived in Ref. Haah  _et al._ (2017). Said
work also determines the sample complexity associated with measuring outer
products of standard Gaussian vectors. Interestingly, this sample complexity
matches the fundamental lower bound up to a factor of $r\ln(n)$, where $r$
denotes the rank of the density operator in question. Thus, state tomography
via low-rank matrix recovery from outer products of Gaussian vectors is close
to optimal, at least for states that have very low rank.

We expect that similar results are true for quantum process tomography via
low-rank matrix reconstruction of Choi matrices. However, while conceptually
similar, the results regarding sample complexities of state tomography
procedures Flammia  _et al._ (2012); Haah  _et al._ (2017) are not directly
applicable to process tomography. We intend to address such an extension in
future work.

####  II.4.2 Numerical example: Reconstructing the Toffoli gate

The Toffoli gate is a three qubit gate that has drawn a lot of attention from
theorists as well as experimentalists. It is universal for classical
computation and, together with the Hadamard gate, also for quantum computation
Shi (2002). Moreover, it has played an important role in the theory of gate
sets Barenco  _et al._ (1995) and can help to significantly reduce the number
of gates in quantum algorithms, such as in quantum error correction. It also
has been implemented experimentally in nuclear magnetic resonance Cory  _et
al._ (1998), linear optics Lanyon  _et al._ (2009), trapped ions Monz  _et
al._ (2009), and in superconducting circuits Fedorov  _et al._ (2012).
Moreover, the reconstruction using the CPT-fit (13) has already been compared
to full tomography Rodionov  _et al._ (2014). Hence, the Toffoli gate is a
good candidate to benchmark our process tomography schemes.

We demonstrate uniform recovery, i.e., we draw a fixed number of measurement
settings at random and keep them fixed throughout the simulation in Figure
II.4.2. Then, we always use the first $m$ of them for reconstructions with $m$
settings.

Since reconstruction via the unconstrained trace norm minimization (15) is
numerically inferior to the other reconstructions (Figure 3) we will not
investigate it in all simulations.

There are two types of error sources: (i) imperfect measurements give rise to
measurement noise $e\in\mathbb{R}^{m}$ in our model (12) and (ii) the
implemented channel $T_{0}\in\operatorname{CPT}(\mathbb{C}^{n})$ could have
violated the model assumption of a low Kraus rank. Here, we confirm our
analytic stability result towards both error sources numerically.

Our theorems put minimal assumptions on the potential noise corruption
$e\in\mathbb{R}^{m}$. In particular, it does not need to follow a specific
statistical model. For our numerical analysis, however, we draw the
measurement noise $e$ i.i.d. from a zero-mean Gaussian distribution and scale
it so that the noise strength $\left\|e\right\|_{\ell_{2}}$ has the desired
value (Figure II.4.2, left). A Gaussian error model frequently occurs in
practice: When estimating expectation values from observed frequencies such an
error model arises naturally in the limit of many measurements per setting. In
practice, the parameter $\eta$ needs to be estimated for the reconstructions
(15), (16), (18) and (18). Here, one could take the smallest $\eta$ so that
the reconstructions succeeds. The CPT-fit (13) has the advantage of not
requiring such an estimation.

We reconstruct $T_{\mathrm{Toff}}$ from $m=320$ _noisy_ measurements with
different values of $\left\|e\right\|_{\ell_{2}}$ without model mismatch
($\lambda=0$), see Figure II.4.2(left). For the trace and diamond norm
reconstructions (16), (17), and (18) we set the error parameter
$\eta=\left\|e\right\|_{\ell_{2}}+10\,\mathrm{eps}$, where
$\mathrm{eps}=2^{-52}\approx 2\cdot 10^{-16}$ is the machine precision. As
predicted by Theorems 3 and 4, the reconstruction error
$\left\|T^{\mathrm{rec}}-T_{0}\right\|_{\mathrm{F}}$ scales linearly in the
noise strength $\left\|e\right\|_{\ell_{2}}$, see Figure II.4.2. Here, the
CPT-fit (13) has the smallest reconstruction error. If one further increases
the number of measurements, then the reconstruction error
$\left\|T^{\mathrm{rec}}-T_{0}\right\|_{\mathrm{F}}$ decreases further, as
guaranteed by Theorems 3 and 4.

In order to demonstrate robustness of our reconstructions, we set $T_{0}$ to
be a convex combination of the Toffoli gate $T_{\mathrm{Toff}}$ and a
completely depolarizing channel
$T_{\mathrm{dep}}(\rho)=n^{-1}{\operatorname{Tr}(\rho)}\mathds{1}$,

$T_{0}=(1-\lambda)T_{\mathrm{Toff}}+\lambda\,T_{\mathrm{dep}}\,,$ (26)

where $\lambda\in[0,1]$. The depolarizing channel corresponds to a physically
relevant error model that maximally violates our model assumption of low Kraus
rank; see, e.g., Ref. (Nielsen and Chuang, 2010, Chapter 8.3.4).

We test the reconstruction of $T_{0}$ for different values of
$\lambda\in[0,1]$. For the sake of clarity, we completely suppress additive
noise ($e=0$) and set the error threshold $\eta=10\,\mathrm{eps}$. The results
are presented in Figure II.4.2(right) and demonstrate the robustness
guaranteed by Theorem 4. The reconstruction error
$\left\|T^{\mathrm{rec}}-T_{0}\right\|_{\mathrm{F}}$ depends roughly linearly
$\lambda$. Here, the diamond norm minimizations (17) and (18), perform worse
than the constrained trace norm minimization (16) and the CPT-fit (13).

In the case of measurement noise, the reconstruction error
$\left\|T^{\mathrm{rec}}-T_{0}\right\|_{\mathrm{F}}$ approaches the optimal
value $\left\|e\right\|_{\ell_{2}}$ in the limit of large $m$, see Figure
II.4.2(left). In the case of a model mismatch, the reconstruction error
decreases below the mismatch parameter $\lambda$ and vanishes if $m$
approaches the full dimension of $\operatorname{CPT}(\mathbb{C}^{n})$, see
Figure II.4.2(right).

We find it worthwhile to share one interesting numerical observation on the
unconstrained diamond norm reconstruction (17): The optimal value
$\left\|T^{\mathrm{rec}}\right\|_{\diamond}$ of the reconstruction seems to
decrease with the reconstruction error
$\left\|T^{\mathrm{rec}}-T_{0}\right\|_{\mathrm{F}}$, see Figure II.4.2.
Hence, this reconstruction procedure does not only yield good approximations
to the measured channel $T_{0}$, but its optimal value also provides some
indication of the reconstruction error’s size.

One can exploit this observation by using both the CPT-fit (13) and the
unconstrained diamond norm reconstruction (17). The CPT-fit is the fastest
reconstruction procedure and yields the smallest error. Complementing this,
the diamond norm minimization provides an indication of what the error might
be. In the CPT-fit, the reconstructed map $T^{\mathrm{rec}}$ is always a
quantum channel, i.e.,
$T^{\mathrm{rec}}\in\operatorname{CPT}(\mathbb{C}^{n})$. In contrast, the
solution of the diamond norm minimization can, in principle, be any map in
$\operatorname{\mathbb{L}}(\mathbb{C}^{n})$. The latter also holds true for
the unconstrained trace norm reconstruction (15), but we could not observe a
similar feature of its minimum value.

|  |
---|---|---

(a) The reconstruction error over the number of measurement settings $m$ for
fixed measurement noise $\left\|e\right\|_{\ell_{2}}=0.05$ (left) and fixed
model mismatch $\lambda=0.05$ (right), respectively, in a uniform recovery
setting.
(b) The reconstruction error over the measurement noise
$\left\|e\right\|_{\ell_{2}}$ and model mismatch $\lambda$, respectively, for
$m=320$ fixed measurement settings.
(c) The optimal value $\left\|T^{\diamond}_{\eta}\right\|_{\diamond}$ from the
minimization (17) over the reconstruction error
$\left\|T^{\diamond}_{\eta}-T_{0}\right\|_{\mathrm{F}}$ achieved by the
unconstrained diamond norm minimization (17) used in (b).
Figure 5. Uniform recovery of the three qubit Toffoli gate
$T_{0}\in\operatorname{CPT}(\mathbb{C}^{8})$ in imperfect settings. In the
perfect setting $m=320$ measurement settings are sufficient for reconstruction
w.h.p. while the total dimension is
$\dim(\operatorname{CPT}(\mathbb{C}^{8}))=4032$.
Left: Reconstruction of $T_{0}=T_{\mathrm{Toff}}$ from
$y=\mathcal{A}(T_{0})+e$ and $\mathcal{A}$ with measurement noise
$e\in\mathbb{R}^{m}$ being drawn uniformly from a scaled sphere and without
model mismatch ($\lambda=0$). The parameter $\eta$ is chosen to be ten times
machine precision plus the chosen noise strength
$\left\|e\right\|_{\ell_{2}}$.
Right: Reconstruction of $T_{0}$ from $y=\mathcal{A}(T)$ and $\mathcal{A}$
with $T_{0}=(1-\lambda)\,T_{\mathrm{Toff}}+\lambda\,T_{\mathrm{dep}}$, where
the model mismatch is given by the completely depolarizing channel
$T_{\mathrm{dep}}$.

The error bounds from Theorem 4 suggest that observables with larger Frobenius
norm have a better noise suppression, as $\left\|A_{0}\right\|_{\mathrm{F}}$
appears in the denominator in the error bound (22). We also tested this
behaviour numerically in order to demonstrate that it is not just a proof
artifact, but an actual feature. We choose $A_{0}$ to have $r_{A}$ many non-
zero eigenvalues, which we evenly distribute in the interval $[-1,1]$. These
$A_{0}$ have a Frobenius norm in the interval $[1,2]$. Figure 6 shows the
average reconstruction error of the Toffoli gate for non-uniform measurements
in dependence of $\left\|A_{0}\right\|_{\mathrm{F}}$ and noise strength
$\left\|e\right\|_{\ell_{2}}=0.1$. This numerical analysis demonstrates that
the reconstruction error can indeed be reduced with increasing
$\left\|A_{0}\right\|_{\mathrm{F}}$.

Figure 6: The plot shows the average reconstruction error
$\left\|J(T^{\ell_{2}}-T_{0})\right\|_{1}$ for observables with different
rank. The observables’ non-zero eigenvalues cover evenly the interval
$[-1,1]$, giving rise to a Frobenius norm increasing monotonically with the
rank. Plotted are CPT-fit (13) reconstructions of the Toffoli gate from
$m=320$ i.i.d. measurements. The noise is scaled to
$\left\|e\right\|_{\ell_{2}}=0.1$.
The plot highlights advantageous stability properties of non-degenerate – and
thus high rank – observables.

###  II.5 Pauli measurements

Our recovery guarantees hold for 4-generic measurements. However, these
measurements can be challenging to implement in many experimental situations.
So, how do our recovery schemes perform for more more restricted measurement
ensembles? In this section we numerically investigate two practically relevant
measurement scenario of Pauli-type measurements.

For quantum state tomography Flammia  _et al._ (2012), Pauli measurements are
proven to satisfy the so-called _restricted isometry property_ for rank-$r$
matrices in $\operatorname{\mathrm{L}}(\mathbb{C}^{d})$ for a number of
measurement settings scaling as $r\,d\,\log(d)^{6}$ Liu (2011).

Motivated by this strong statement, we numerically investigate process
measurements that are inspired by a Pauli setting. We denote the set of Pauli
strings by $\mathcal{P}\subset\operatorname{U}(2^{L})$, i.e., the set of
operators $P=\sigma^{(1)}\otimes\sigma^{(2)}\otimes\dots\otimes\sigma^{(L)}$
with Pauli matrices
$\sigma^{(i)}\in\\{\mathds{1},\sigma_{x},\sigma_{y},\sigma_{z}\\}$ for
$i\in[L]$. We write $P\sim\mathcal{P}$ for a Pauli string that is drawn
uniformly at random from $\mathcal{P}$. Then we choose the measurements as

$y_{j}\coloneqq\operatorname{Tr}[P_{j}T_{0}(\left.\left|{\psi_{j}}\right.\right\rangle\\!\\!\left.\left\langle{\psi_{j}}\right.\right|)]\,,$
(27)

where observables $P_{j}$ and input states
$\left.\left|{\psi_{j}}\right.\right\rangle$ are i.i.d. selected as follows.
Each $P_{j}\sim\mathcal{P}$ is a uniformly drawn Pauli string and each state
vector $\left.\left|{\psi}\right.\right\rangle_{j}$ is a tensor product of
uniformly i.i.d. drawn eigenvectors of random Pauli operators
$\\{\sigma_{x},\sigma_{y},\sigma_{z}\\}$ (hence, an eigenvector of the
corresponding Pauli string).

Numerically, we observe that for random unitary quantum channels our
reconstructions perform very similar for these Pauli measurements and the
generic (Haar-random) measurements (not shown in the plots). However, for non-
generic channels we observe that the two types of measurements lead to
different reconstruction behaviours, see Figure 7: For the reconstruction of
the Toffoli gate, more Pauli-type-measurements than generic measurements are
required in the case of unconstrained trace norm regularization (15). In
contrast, fewer Pauli-measurements are required for the other regularizations.

We have also observed that reconstructions from Pauli-measurements have
similar stability properties as the ones in the generic case (not shown in the
plots).

The identity quantum channel $T_{0}=\mathrm{id}$ is an extreme case in the
sense that it is sparse in any basis and commutes with all transformations.
For generic measurements we have observed that it has the same reconstruction
behaviour as Haar-random unitary $T$ channels. In comparison, in case of Pauli
measurements, the unconstrained trace norm reconstruction works worse and the
other reconstructions better (not shown in the plots).

|  |
---|---|---
Figure 7:  Pauli-type measurements: Comparison of the reconstruction errors of
generic (Haar-random) unitary quantum channels (left) and the Toffoli gate
(right).

###  II.6 Sample complexity

The expectation values in our measurements need to be estimated from finite
samples leading to a reconstruction error $e$. Assume we want to estimate the
measured channel $T_{0}\in\operatorname{CPT}(\mathbb{C}^{n})$ in Frobenius
norm up to an error $\left\|e\right\|_{\ell_{2}}\leq\epsilon$. Then the
_sample complexity_ is the scaling of the optimal number of measurements in
the ideal setting, i.e., without model mismatch or measurement errors.

We use the Landau symbols $\operatorname{\mathrm{O}}$ and
$\operatorname{\Omega}$ to denote the usual asymptotic upper and lower bounds,
respectively. The Landau symbol $\operatorname{\tilde{\mathrm{O}}}$ denotes
the same scaling as $\operatorname{\mathrm{O}}$ up to log-factors.

The error of an empirical mean of
$\operatorname{Tr}[A_{i}T_{0}(\left.\left|{\psi_{i}}\right.\right\rangle\\!\\!\left.\left\langle{\psi_{i}}\right.\right|)]$
form $\ell$ samples scales as $\operatorname{\mathrm{O}}(1/\sqrt{\ell})$
w.h.p. (due to, e.g., Chebyshev’s inequality). This gives rise to an error
vector $e$ bounded as

$\left\|e\right\|_{\ell_{2}}\in\operatorname{\mathrm{O}}(\sqrt{m/\ell})\,.$
(28)

Hence, the total estimation error bounded as

$\epsilon\leq\frac{n^{2}\left\|e\right\|_{\ell_{2}}}{\sqrt{m}\bigl{\|}A_{0}\bigr{\|}_{2}}$
(29)

is small w.h.p. for $\ell\geq\ell_{0}$ with some $\ell_{0}$ being bounded as
$\ell_{0}\in\operatorname{\mathrm{O}}\Bigl{(}\frac{n^{4}}{\lVert
A_{0}\rVert_{2}^{2}}\epsilon^{2}\Bigr{)}$. For
$\bigl{\|}A_{0}\bigr{\|}_{2}\in\operatorname{\Omega}(\sqrt{n})$ this yields a
total sample complexity scaling as
$\operatorname{\tilde{\mathrm{O}}}(rn^{2})\operatorname{\mathrm{O}}(n^{3}/\epsilon^{2})=\operatorname{\tilde{\mathrm{O}}}(rn^{5}/\epsilon^{2})$.

###  II.7 Applications to fault tolerant quantum computation

The techniques presented here also have applications for fault tolerant
quantum computation. Threshold theorems Kitaev (1997); Knill  _et al._ (1998);
Aharonov and Ben-Or (1997) give a theoretical guarantee that that quantum
computers can be built in principle if the noise strength are below some
threshold value. The strength of the errors needs to be quantified in diamond
norm distance which is not directly accessible. Instead one typically
evaluates average error rates using direct fidelity estimation Flammia and Liu
(2011), or randomized benchmarking, see e.g. Emerson  _et al._ (2005).
However, these two error measures can differ by orders of magnitude Wallman
and Flammia (2014). This, in particular, is the case for coherent error
sources, such as unitary over/under-rotations Kueng  _et al._ (2016), where
the diamond distance is proportional to the square root of the average error
rate. Thus, achieving fault-tolerance thresholds in the presence of unitary
noise requires an exceedingly high error control (around $10^{-8}$ for typical
threshold levels of a few times $10^{-4}$). In contrast, other noise sources
typically imply a much more favourable (linear) relation between both error
measures.

From a practical perspective, these results are encouraging: Unlike incoherent
noise, coherent noise effects can typically be corrected. A necessary
subroutine for achieving this goal is to accurately estimate these error
channels. Our results considerably simplify this task, in particular for
unitary errors which have Kraus rank one. They provide estimation techniques
that require considerably fewer measurements than traditional process
tomography protocols.

##  III Analytical details and proofs

Our analytical results build on by now well-established mathematical proof
techniques for low-rank matrix reconstruction Tropp (2015); Kueng  _et al._
(2017); Kabanava  _et al._ (2015). The main technical contribution of this
work is to extend these techniques to natural measurements whose structure
deviates from less structured measurement matrices common in low-rank matrix
reconstruction.

Starting point of our analysis is a geometric approach to low-rank matrix
recovery presented in Tropp (2015). It relates the reconstruction error from a
constrained trace norm minimization to a certain quantity associated with the
measurement map $\mathcal{A}$: the _minimum conic singular value_ ; see
Definition 8 below. We bound this quantity by invoking Mendelson’s small ball
method Mendelson (2015); Koltchinskii and Mendelson (2015) – a strong
probabilistic tool that depends on certain concentration properties of the
measurement ensemble. For 4-generic measurements these are derived using
representation theory of the unitary group and general bounds on tensor
network contractions besides probabilistic bounds commonly used on low-rank
matrix reconstruction.

This geometric analysis results in a reconstruction guarantee for the
constrained trace norm minimization (16) that is stable towards additive noise
corruption. In turn, the geometric arguments provided in Ref. Kliesch  _et
al._ (2016) suggest a strengthening of the obtained error bounds, if one
replaces the trace norm by the diamond norm. Theorem 3 – or, more generally:
Theorem 23 and Corollary 24 – are consequences of such an approach.

Our second main result – Theorem 4 – assures stability towards noise
corruption as well as robustness with respect to violating the model
assumption of low Kraus rank. This further improvement is achieved via
establishing a robust version of the _null space property_ for 4-generic
measurements. We refer to Section III.1.4 for a brief introduction. The
technical prerequisites for such an approach are largely identical to the ones
associated with the more geometric framework outlined above. Mendelson’s small
ball method, in particular, is again applicable. Hence, relatively little
additional effort is required for this approach which has the added benefit of
ensuring robustness towards model mismatches.

The remainder of this section is organized as follows: After some
preliminaries, we prove a bound on the minimum conic singular value for the
case of our measurement setting in Section III.2. The proof used a general
bound on tensor networks, which we state and prove in Section III.3. In
Section III.4, we state and prove general versions of our main theorems.
Finally, in Section III.6, we show that our results also hold for a quantum
linear optical setting.

###  III.1 Preliminaries

Before we come the to proofs we introduce some helpful notation, discuss the
minimum conic singular value and a useful bound to it, introduce the null
space property and a subsequent recovery guarantee, and explain the use of
representation theory for bounding certain moments.

####  III.1.1 Notation

A _vectorization_ of a tensor is a vector containing all its elements. The
_Frobenius norm_ $\left\|T\right\|_{\mathrm{F}}$ of a tensor $T$ is defined to
be the $\ell_{2}$-norm of some vectorization of $T$. Importantly, for an
operator $A\in\operatorname{\mathrm{L}}(\mathbb{C}^{n})$ it holds that
$\left\|A\right\|_{\mathrm{F}}=\left\|A\right\|_{2}$.

The permutation group on $k$ elements is denoted by $S_{k}$ and the unitary
group by
$\operatorname{U}(n)\subset\operatorname{\mathrm{L}}(\mathbb{C}^{n})$. Its
representation on $(\mathbb{C}^{n})^{\otimes k}$ is denoted by $R$, so that
for $\sigma\in S_{k}$ the representation $R(\sigma)\in U(n^{k})$ acts on
$(\mathbb{C}^{n})^{\otimes k}$ by permuting the $k$ tensor copies according to
$\sigma$.

##### Affine spaces

: In order to deal with the constraint that the reconstructed maps are trace
preserving we need the affine version of the usual reconstruction problem
Tropp (2015) in compressed sensing.

It is helpful to extend the basic algebraic operations to sets: E.g., we
denote the Minkowski sum of subsets $S$ and $R$ of some vector space by
$S+R\coloneqq\\{s+r:s\in S,r\in R\\}$. Similarly, we define $-R$ and $s+R$ for
some $s\in S$.

An _affine space_ $\mathcal{V}$ over the field $\mathbb{R}$ is a subset of a
vector space over $\mathbb{R}$ such that for all $\lambda\in\mathbb{R}$ and
$x,y\in\mathcal{V}$ one has $(1-\lambda)x+\lambda y\in\mathcal{V}$. Then
$\mathcal{V}_{0}\coloneqq\mathcal{V}-\mathcal{V}$ is a vector space and
$\mathcal{V}=x+\mathcal{V}_{0}$ for any $x\in\mathcal{V}$. The linear span
$\operatorname{\operatorname{lin}}(\mathcal{V})$ of $\mathcal{V}$ is another
vector space containing both $\mathcal{V}$ and $\mathcal{V}_{0}$.

A map $A:\mathcal{V}\to\mathcal{W}$ between affine spaces $\mathcal{V}$ and
$\mathcal{W}$ is called _affine_ if for all $\lambda\in\mathbb{R}$ and
$x,y\in\mathcal{V}$ one has $A((1-\lambda)x+\lambda y)=(1-\lambda)Ax+\lambda
Ay$.

Given an affine map $\mathcal{A}:\mathcal{V}\to\mathbb{R}^{m}$ (such as the
measurement map defined in (11)) one can extend it linearly to
$\operatorname{\operatorname{lin}}(\mathcal{V})$. This extension will also be
denoted by $\mathcal{A}$.

##### Maps and operators

: Any map $M\in\operatorname{\mathbb{L}}(\mathbb{C}^{n})$ and operators
$A,\rho\in\operatorname{\mathrm{L}}(\mathbb{C}^{n})$ satisfy the identity

$\operatorname{Tr}[A\,M(\rho)]=\operatorname{Tr}[A\otimes\rho^{T}J(M)]\,.$
(30)

We will use this identity to write expectation values of the type
$\operatorname{Tr}[AT(\rho)]$ in terms of the Choi matrix $J(T)$.

By $M^{\dagger}$ we denote the Hilbert-Schmidt adjoint of
$M\in\operatorname{\mathbb{L}}(\mathbb{C}^{n})$ and by $M^{\star}$ the map
which obeys $M(X)^{\dagger}=M^{\star}(X^{\dagger})$ for all
$X\in\operatorname{\mathrm{L}}(\mathbb{C}^{n})$. These two involutions satisfy
$M^{\dagger\star}=M^{\star\dagger}$. Moreover, we use the notation

$M^{k,l}\coloneqq M^{\otimes k}\otimes M^{\star\otimes l}.$ (31)

We note in passing that CPT maps $T\in\operatorname{CPT}(\mathbb{C}^{n})$ have
diamond norm $\left\|T\right\|_{\diamond}=1$ and Choi matrices are normalized
as $\left\|J(T)\right\|_{1}=n$.

##### Truncating Choi matrices

: It will be helpful to define the set containing all Choi matrices
$J\operatorname{HT}(\mathbb{C}^{n})=\\{X\in\operatorname{Herm}(\mathbb{C}^{n}\otimes\mathbb{C}^{n}):\
\operatorname{Tr}_{1}(X)=n\,\mathds{1}_{n}\\}$, where $\operatorname{Tr}_{1}$
denotes the partial trace over the first tensor factor. Consistently with the
truncation of maps in $\operatorname{\mathbb{L}}(\mathbb{C}^{n})$, the
_truncation_ $X_{|r}\in J\operatorname{HT}(\mathbb{C}^{n})$ of $X\in
J\operatorname{HT}(\mathbb{C}^{n})$ to rank $r$ is given by setting all but
the largest $r$ singular values of $X$ to zero. The corresponding _tail_ is
defined to be $X_{\neg r}\coloneqq X-X_{|r}\in
J\operatorname{HT}(\mathbb{C}^{n})_{0}$.

####  III.1.2 Normalization and centralization of the observables

We assume the fixed observable $A_{0}$ to be normalized
($\left\|A_{0}\right\|_{\infty}=1$) and centered (traceless):
$\operatorname{Tr}[A_{0}]=0$. Such restrictions somewhat simplify the
technical analysis; the following observations highlight that little
generalization is lost by imposing them:

######  Observation 6 (Uncentered observables).

Fix $A_{0}\in\mathrm{Herm}(\mathbb{C}^{n})$ and let

$\tilde{A}_{0}\coloneqq A_{0}-\operatorname{Tr}[A_{0}]\mathds{1}/n$ (32)

be the traceless part of $A_{0}$. Then, the associated 4-generic measurement
maps $\mathcal{A}$ and $\tilde{\mathcal{A}}$ introduced in Definition 1 do not
necessarily coincide. However, the algorithmic reconstructions
$T^{\mathrm{rec}}$ and $\tilde{T}^{\mathrm{rec}}$ of any trace-preserving map
$T$ nonetheless coincide for all reconstruction procedures (15), (16), (17),
(18), or (13).

###### Proof.

Since any $T\in\operatorname{CPT}(\mathbb{C}^{n})$ is trace preserving, we
have that

$\displaystyle\tilde{\mathcal{A}}(T)_{j}$
$\displaystyle=\operatorname{Tr}[\tilde{A}_{j}T(\left.\left|{\psi_{j}}\right.\right\rangle\\!\\!\left.\left\langle{\psi_{j}}\right.\right|)]$
$\displaystyle=\operatorname{Tr}[A_{j}T(\left.\left|{\psi_{j}}\right.\right\rangle\\!\\!\left.\left\langle{\psi_{j}}\right.\right|)]-\operatorname{Tr}[A_{j}]/n$
(33) $\displaystyle=\mathcal{A}(T)_{j}-\operatorname{Tr}[A_{j}]/n.$ (34)

Together with the definition of $y$ and $\tilde{y}$ this implies

$\mathcal{A}(T)-y=\tilde{\mathcal{A}}(T)-\tilde{y}\,.$ (35)

But this means that the corresponding minimizations are the same. ∎

The following observation says that the observable’s spectral norm suppresses
the noise.

######  Observation 7 (Unnormalized observables).

Let $\mathcal{A}$ be a 4-generic measurement and define
$\hat{\mathcal{A}}:=\left\|A_{0}\right\|_{\infty}^{-1}\mathcal{A}$. Then the
algorithmic reconstructions associated with measurements

$y=\mathcal{A}(T_{0})+e\quad\textrm{and}\quad\hat{y}=\hat{\mathcal{A}}(T_{0})+\frac{e}{\left\|A_{0}\right\|_{\infty}}$
(36)

coincide for all five reconstruction procedures: (15), (16), (17), (18) and
(13).

####  III.1.3 Minimum conic singular value

The usual minimum conic singular value of a map $\mathcal{A}$ can be written
variationally as the right hand side (RHS) of Eq. (37) with $K$ being the full
space and $q=2$. In order for $\mathcal{A}$ to be invertible, the minimum
conic singular value needs to be positive. Moreover, for fixed spectral norm
of $\mathcal{A}$, the larger the minimum conic singular of $\mathcal{A}$ the
more stable $\mathcal{A}$ can be inverted. An extension of these basic
concepts can be extended to realm of convex analysis, which motivates the
following Definition.

######  Definition 8 ($\ell_{q}$-minimum conic singular value).

Consider an affine space $\mathcal{V}$ where
$\operatorname{\operatorname{lin}}(\mathcal{V})$ is equipped with a norm
$\left\|{\,\cdot\,}\right\|$. Let $\mathcal{A}:\mathcal{V}\to\mathbb{R}^{m}$
be an affine linear map and $K\subset\mathcal{V}_{0}$ be a cone. The minimum
singular value of $\mathcal{A}$ w.r.t. $K$, measured in $\ell_{q}$-norm with
$q\geq 1$, is

$\lambda_{\min{}}(\mathcal{A};K;\ell_{q})\coloneqq\inf_{u\in
K}\frac{\left\|\mathcal{A}u\right\|_{\ell_{q}}}{\left\|u\right\|}\,,$ (37)

where $\mathcal{A}$ has been extended to
$\operatorname{\operatorname{lin}}(\mathcal{V})$.

Typically, one chooses $q=2$ in order to define the minimum conic singular
value Tropp (2015). Here, we opt for a more general definition that allows for
adjusting stability guarantees towards noise to different types of noise
models. For instance one may choose $q=2$ for Gaussian noise and $q=1$ for
Poissonian noise.

The conic singular value of our measurement map $\mathcal{A}$ (see Eq. (12))
w.r.t. a cone $K\subset\operatorname{\mathbb{L}}(\mathbb{C}^{n})$ can be
written as

$\lambda_{\min{}}(\mathcal{A};K;\ell_{q})=\inf_{M\in
E}\left(\sum_{i=1}^{m}\operatorname{Tr}[A_{i}M(\left.\left|{\psi_{i}}\right.\right\rangle\\!\\!\left.\left\langle{\psi_{i}}\right.\right|)]^{q}\right)^{\frac{1}{q}}$
(38)

with $E=\\{M\in K:\left\|M\right\|_{\mathrm{F}}=1\\}$.

We use a method established by Mendelson Mendelson (2015); Koltchinskii and
Mendelson (2015) in order to bound the minimum conic singular value. As
suggested in Ref. (Kabanava  _et al._ , 2015, Remark 5.1), we use a
generalization of Tropp’s version (Tropp, 2015, Proposition 5.1).

######  Lemma 9 (Bound on $\lambda_{\min{}}$).

Let $E\subset\operatorname{HT}(\mathbb{C}^{n})$ be a cone of maps and
$(\left.\left|{\psi_{i}}\right.\right\rangle,A_{i})_{i\in[m]}$ be an i.i.d.
measurement settings. Define the _marginal tail function_

$Q_{\xi}\coloneqq\inf_{M\in
E}\operatorname{\mathbb{P}}\bigl{[}\bigl{|}\operatorname{Tr}[A_{i}M(\left.\left|{\psi_{i}}\right.\right\rangle\\!\\!\left.\left\langle{\psi_{i}}\right.\right|)]\bigr{|}\geq\xi\bigr{]}$
(39)

(the same for all $i$) and _mean empirical width_

$W_{m}(E)\coloneqq\operatorname{\mathbb{E}}\sup_{M\in
E}\frac{1}{\sqrt{m}}\sum_{i=1}^{m}\epsilon_{i}\operatorname{Tr}[A_{i}M(\left.\left|{\psi_{i}}\right.\right\rangle\\!\\!\left.\left\langle{\psi_{i}}\right.\right|)]\,,$
(40)

where $\epsilon_{i}\in\\{-1,1\\}$ are independent uniformly random signs.
Then, for any $\xi>0$, $\lambda>0$, and $q\geq 1$

$\begin{split}\inf_{M\in
E}&\left(\sum_{i=1}^{m}\left|\operatorname{Tr}[A_{i}M(\left.\left|{\psi_{i}}\right.\right\rangle\\!\\!\left.\left\langle{\psi_{i}}\right.\right|)]\right|^{q}\right)^{\frac{1}{q}}\\\
&\geq
m^{\frac{1}{q}-\frac{1}{2}}\left(\xi\sqrt{m}Q_{2\xi}-2W_{m}-\xi\lambda\right)\end{split}$
(41)

with probability at least $1-e^{-\lambda^{2}/2}$.

###### Proof.

Following Ref. (Kabanava  _et al._ , 2015, Remark 5.1), we point out that the
proof of Ref. (Tropp, 2015, Proposition 5.1) actually implies the stronger
statement

$\begin{split}\frac{1}{\sqrt{m}}\inf_{M\in
E}&\sum_{i=1}^{m}\left|\operatorname{Tr}[A_{i}M(\left.\left|{\psi_{i}}\right.\right\rangle\\!\\!\left.\left\langle{\psi_{i}}\right.\right|)]\right|\\\
&\geq\xi\sqrt{m}Q_{2\xi}-2W_{m}-\xi\lambda\,.\end{split}$ (42)

Using that $\left\|v\right\|_{\ell_{1}}\leq
m^{1/q}\left\|v\right\|_{\ell_{q}}$ for any $v\in\mathbb{C}^{m}$ results in
(41) for any $q\geq 1$. ∎

####  III.1.4 Null space property

If an operator $X$ is of rank $r$ one has
$\left\|X\right\|_{1}\leq\sqrt{r}\left\|X\right\|_{2}$. Here, we rely on the
idea to take a similar inequality to define the notion of effectively rank-$r$
elements. This notion of effective low rank is often enough for low-rank
matrix reconstruction. Additionally, one can take into account violations of
$X$ being of low rank. This idea is formalized with the _null space property_
(NSP).

######  Definition 10 (NSP).

For $q\geq 1$, a linear map
$\mathcal{A}:J\operatorname{HT}(\mathbb{C}^{n})\to\mathbb{R}^{m}$ satisfies
the _$\ell_{q}$ -null space property_ for rank $r$ with constants
$\mu\in\left]0,1\right[$ and $\tau>0$ if for all
$X\in\operatorname{HT}(\mathbb{C}^{n})_{0}$

$\left\|X_{|r}\right\|_{2}\leq\frac{\mu}{\sqrt{r}}\left\|X_{\neg
r}\right\|_{1}+\tau\left\|\mathcal{A}(X)\right\|_{\ell_{q}}.$ (43)

We will use the following result from Ref. Kabanava  _et al._ (2015) in our
setting. It yields recovery guarantees from the NSP.

######  Theorem 11 (Recovery guarantee (Kabanava  _et al._ , 2015, Theorem
12)).

Fix $1\leq p\leq 2$ and let
$\mathcal{A}:J\operatorname{HT}(\mathbb{C}^{n})\to\mathbb{R}^{m}$ satisfy the
NSP for rank $r$ with constants $\mu\in\left]0,1\right[$ and $\tau>0$. Then,
for all $X,Y\in J\operatorname{HT}(\mathbb{C}^{n})$,

$\begin{split}\left\|X-Y\right\|_{p}\leq&\frac{(1+\mu)^{2}}{1-\mu}\Bigl{(}\left\|Y\right\|_{1}-\left\|X\right\|_{1}+2\left\|X_{\neg
r}\right\|_{1}\Bigr{)}\\\
&\quad+\tau\,r^{1/p-1/2}\,\frac{3+\mu}{1-\mu}\left\|\mathcal{A}(X-Y)\right\|_{\ell_{q}}\,.\end{split}$
(44)

####  III.1.5 Tools from representation theory

In this section we simplify the $k$-th moments of the random variables
$UAU^{\dagger}$ and
$\left.\left|{\psi}\right.\right\rangle\\!\\!\left.\left\langle{\psi}\right.\right|$,
where $U$ and $\left.\left|{\psi}\right.\right\rangle$ are drawn independently
from the Haar measures. These derivations will be used when we bound the
moments of
$\operatorname{Tr}[UA\,U^{\dagger}\,M(\left.\left|{\psi}\right.\right\rangle\\!\\!\left.\left\langle{\psi}\right.\right|)]$
for maps $M\in\operatorname{\mathbb{L}}(\mathbb{C}^{n})$.

In order to compute expectation values over the unitary group of the type

$E\coloneqq\operatorname{\mathbb{E}}_{U\sim\mathrm{Haar}}[(UAU^{\dagger})^{\otimes
k}]$ (45)

we will use some basic facts from representation theory. Specifically, we use
the decomposition from Schur Weyl duality

$(\mathbb{C}^{n})^{\otimes
k}\cong\bigoplus_{\lambda}\pi^{k}_{\lambda}\otimes\rho^{n}_{\lambda}$ (46)

into irreducible representations (irreps) $\rho^{n}_{\lambda}$ and
$\pi^{k}_{\lambda}$ of the unitary group $\operatorname{U}(n)$ and the
symmetric group $S_{k}$, respectively. The irreps are labelled by Young
diagrams $\lambda$ with $k$ boxes and at most $n$ rows. Since $[U^{\otimes
k},E]=0$ for all $U\in\operatorname{U}(d)$, a famous theorem due to Schur
(see, e.g., (Goodman and Wallach, 2000, Theorem 4.2.10)) implies that $E$ can
be written as $E=\bigoplus_{\lambda}\mathds{1}\otimes Y_{\lambda}$, where
$Y_{\lambda}\in\rho^{n}_{\lambda}$. But we also have that $[\sigma,E]=0$ for
all $\sigma\in S_{k}$ and Schur’s Lemma implies that

$\operatorname{\mathbb{E}}_{U\sim\mathrm{Haar}}[(UAU^{\dagger})^{\otimes
k}]=\sum_{\lambda}a_{\lambda}P_{\lambda}\,,$ (47)

where each $a_{\lambda}\in\mathbb{C}$ and each $P_{\lambda}$ is the projection
onto $\pi^{k}_{\lambda}\otimes\rho^{n}_{\lambda}$. The coefficients can be
calculated as the expansion coefficients

$\displaystyle a_{\lambda}=\frac{\operatorname{Tr}[A^{\otimes
k}P_{\lambda}]}{\operatorname{Tr}[P_{\lambda}]}\,.$ (48)

This argument also yields that

$\displaystyle
F\coloneqq\operatorname{\mathbb{E}}_{\left.\left|{\psi}\right.\right\rangle\sim\mathrm{Haar}}[\left.\left|{\psi}\right.\right\rangle\\!\\!\left.\left\langle{\psi}\right.\right|^{\otimes
k}]=\sum_{\lambda}b_{\lambda}P_{\lambda}\,.$ (49)

The coefficients are $b_{\lambda}\propto\operatorname{Tr}[P_{\lambda}F]$ and
we have
$\left.\left|{\psi}\right.\right\rangle\\!\\!\left.\left\langle{\psi}\right.\right|^{\otimes
k}P_{\mathrm{Sym}^{k}}=\left.\left|{\psi}\right.\right\rangle\\!\\!\left.\left\langle{\psi}\right.\right|^{\otimes
k}$ and $P_{\lambda}P_{\lambda^{\prime}}=0$ for $\lambda\neq\lambda^{\prime}$.
Together with $\operatorname{Tr}[F]=1$ we obtain that

$\displaystyle\operatorname{\mathbb{E}}_{\left.\left|{\psi}\right.\right\rangle\sim\mathrm{Haar}}[\left.\left|{\psi}\right.\right\rangle\\!\\!\left.\left\langle{\psi}\right.\right|^{\otimes
k}]=\frac{1}{\operatorname{Tr}[P_{\mathrm{Sym}^{k}}]}\,P_{\mathrm{Sym}^{k}}\,,$
(50)

where $P_{\mathrm{Sym}^{k}}$ is the projector onto the fully symmetric
subspace in $(\mathbb{C}^{n})^{\otimes k}$.

##### First moments

: Setting $k=1$ and using that
$\operatorname{Tr}[A^{2}]=\left\|A\right\|_{2}^{2}$ and
$\left.\left|{\psi}\right.\right\rangle\\!\\!\left.\left\langle{\psi}\right.\right|^{2}=\left.\left|{\psi}\right.\right\rangle\\!\\!\left.\left\langle{\psi}\right.\right|$
yields that

$\operatorname{\mathbb{E}}_{U\sim\mathrm{Haar}}[UAU^{\dagger}]=\frac{\operatorname{Tr}[A]}{n}\,\mathds{1}.$
(51)

and

$\displaystyle\operatorname{\mathbb{E}}_{\left.\left|{\psi}\right.\right\rangle\sim\mathrm{Haar}}[(\left.\left|{\psi}\right.\right\rangle\\!\\!\left.\left\langle{\psi}\right.\right|)^{2}]=\frac{1}{n}\,\mathds{1}\,.$
(52)

##### Second moments

: The _flip operator_
$\mathbb{F}\in\operatorname{\mathrm{L}}(\mathbb{C}^{n}\otimes\mathbb{C}^{n})$
is given by the linear extension of

$\mathbb{F}\left.\left|{\psi}\right.\right\rangle\otimes\left.\left|{\phi}\right.\right\rangle\coloneqq\left.\left|{\phi}\right.\right\rangle\otimes\left.\left|{\psi}\right.\right\rangle\,.$
(53)

The projector onto the symmetric subspace of
$\mathbb{C}^{n}\otimes\mathbb{C}^{n}$ can be written as
$P_{\mathrm{Sym}^{2}}=\frac{1}{2}\left(\mathds{1}+\mathbb{F}\right)$. The
dimension of the fully symmetric subspace in
$\mathbb{C}^{n}\otimes\mathbb{C}^{n}$ is

$\displaystyle\operatorname{Tr}[P_{\mathrm{Sym}^{2}}]$
$\displaystyle=\operatorname{Tr}[\mathds{1}]/2+\operatorname{Tr}[\mathbb{F}]/2$
(54) $\displaystyle=n^{2}/2+n/2$ (55) $\displaystyle=n(n+1)/2\,.$ (56)

Together we obtain

$\operatorname{\mathbb{E}}\left[\left(|\psi\rangle\langle\psi|\right)^{\otimes
2}\right]=\frac{2}{n(n+1)}P_{\mathrm{Sym}^{2}}=\frac{1}{n(n+1)}\left(\mathds{1}+\mathbb{F}\right)\,.$
(57)

In order to derive the second moment of $UAU^{\dagger}$ we also need the
projector onto the anti-symmetric subspace
$P_{\wedge^{2}}=\frac{1}{2}\left(\mathds{1}-\mathbb{F}\right)$. From Eq. (47)
and $\operatorname{Tr}[\mathds{1}]=n^{2}$ and
$\operatorname{Tr}[\mathbb{F}]=n$ we obtain

$E=\frac{2\operatorname{Tr}\bigl{[}P_{\mathrm{Sym}^{2}}A\bigr{]}}{n(n+1)}P_{\mathrm{Sym}^{2}}+\frac{2\operatorname{Tr}\bigl{[}P_{\wedge^{2}}A\bigr{]})}{n(n-1)}P_{\wedge^{2}}\,.$
(58)

Evaluating the remaining traces in a basis or using tensor network diagrams
yields

$\operatorname{\mathbb{E}}\left[\left(UAU^{\dagger}\right)^{\otimes
2}\right]=\frac{\operatorname{Tr}(A)^{2}+\|A\|_{2}^{2}}{n(n+1)}P_{\mathrm{Sym}^{2}}+\frac{\operatorname{Tr}(A)^{2}-\|A\|_{2}^{2}}{n(n-1)}P_{\wedge^{2}}\,.$
(59)

###  III.2 Our bound on the minimum conic singular value

The following theorem is the main technical result of this work.

######  Theorem 12 (Minimum conic singular value bound).

Let $(A_{i},\left.\left|{\psi_{i}}\right.\right\rangle)_{i\in[m]}$ be a
normalized 4-generic measurement ensemble (Definition 1). Denote by
$\mathcal{A}:\operatorname{HT}(\mathbb{C}^{n})\to\mathbb{R}^{m}$ the linear
map given by the components

$\mathcal{A}(M)_{i}\coloneqq\operatorname{Tr}\bigl{[}A_{i}M(\left.\left|{\psi_{i}}\right.\right\rangle\\!\\!\left.\left\langle{\psi_{i}}\right.\right|)\bigr{]}\,.$
(60)

Moreover, for $c_{\mu}>0$ denote by

$K\coloneqq\Bigl{\\{}M\in\operatorname{HT}(\mathbb{C}^{n})_{0}:\left\|J(M)\right\|_{1}\leq
c_{\mu}\sqrt{r}\left\|J(M)\right\|_{2}\Bigr{\\}},$ (61)

the cone of trace-annihilating maps of “effective Kraus-rank” at most $r$.
Then, for the constant $c$ from Lemma 14, for any $c_{\lambda}\in{}]0,c[$,
$q\geq 1$ and any

$m>m_{0}\coloneqq
125\,\mathrm{e}\left(\frac{c_{\mu}}{c-c_{\lambda}}\right)^{2}\,r\ln(n)n(n+1)$
(62)

the $\ell_{q}$-minimum conic singular value of $\mathcal{A}$ is lower bounded
as

$\inf_{M\in
K}\frac{\left\|\mathcal{A}(M)\right\|_{\ell_{q}}}{\left\|M\right\|_{\mathrm{F}}}\geq\frac{c-c_{\lambda}}{5}\left\|A\right\|_{2}\frac{m^{\frac{1}{q}}\left(1-\sqrt{\frac{m_{0}}{m}}\right)}{n(n+1)}$
(63)

with probability at least $1-\mathrm{e}^{-c_{\lambda}^{2}m/5}$ over
$\mathcal{A}$.

###### Proof of Theorem 12.

We choose $E$ in Lemma 9 to be $E_{\nu}$ from Lemma 13. Inserting the bounds
from Lemmas 14 and 13 into Eq. (41) implies

$\begin{split}\inf_{M\in
E_{\nu}}&m^{\frac{1}{2}-\frac{1}{q}}\left\|\mathcal{A}(M)\right\|_{\ell_{q}}\geq\\\
&\qquad
c\sqrt{m}\,\xi\left(1-\frac{(2\xi)^{2}(n-1)\,n\,(n+1)^{2}}{2\left\|A\right\|_{2}^{2}\nu^{2}}\right)^{2}\\\
&\qquad\qquad-2\frac{c_{\mu}\sqrt{6\,\mathrm{e}\ln(n)r}}{n}\,\nu\left\|A\right\|_{2}-\xi\lambda\end{split}$
(64)

with probability at least $1-\mathrm{e}^{-\lambda^{2}/2}$ over $\mathcal{A}$.
Choosing $\nu=\nu_{0}\coloneqq n\sqrt{n(n+1)}/\left\|A\right\|_{2}$ and using
that $(n+1)(n-1)/n^{2}\leq 1$ yields

$\begin{split}\inf_{M\in
E_{\nu_{0}}}&m^{\frac{1}{2}-\frac{1}{q}}\left\|\mathcal{A}(M)\right\|_{\ell_{q}}\geq{}\\\
&c\sqrt{m}\,\xi\left(1-2\xi^{2}\right)^{2}-c_{\mu}\sqrt{6\,\mathrm{e}\ln(n)n(n+1)\,r}-\xi\lambda\,.\end{split}$
(65)

Next, choosing $\xi=1/\sqrt{10}$ yields a maximum value greater than $1/5$ for
$\xi\left(1-2\xi^{2}\right)^{2}$. This choice yields the bound

$\begin{split}\inf_{M\in
E_{\nu_{0}}}&m^{\frac{1}{2}-\frac{1}{q}}\left\|\mathcal{A}(M)\right\|_{\ell_{q}}\geq\\\
&\frac{c}{5}\sqrt{m}-c_{\mu}\sqrt{6\,\mathrm{e}\ln(n)n(n+1)\,r}-\frac{\lambda}{\sqrt{10}}\,.\end{split}$
(66)

Furthermore, we set $\lambda=\frac{c_{\lambda}\sqrt{10}}{5}\sqrt{m}$ with some
constant $0<c_{\lambda}<c$ to obtain

$\begin{split}\inf_{M\in
E_{\nu_{0}}}&m^{\frac{1}{2}-\frac{1}{q}}\left\|\mathcal{A}(M)\right\|_{\ell_{q}}\geq\\\
&\frac{c-c_{\lambda}}{5}\sqrt{m}-c_{\mu}\sqrt{6\,\mathrm{e}\ln(n)n(n+1)\,r}\,.\end{split}$
(67)

So, we choose $m>m_{0}$ with

$\sqrt{m_{0}}\coloneqq\frac{5\sqrt{6\,e}\,c_{\mu}}{c-c_{\lambda}}\sqrt{\ln(n)n(n+1)\,r}$
(68)

in order guarantee that the infimum yields a positive value. This choice leads
to

$\displaystyle\inf_{M\in E_{\nu_{0}}}\left\|\mathcal{A}(M)\right\|_{\ell_{q}}$
$\displaystyle\geq\frac{c-c_{\lambda}}{5}m^{\frac{1}{q}}\left(1-\sqrt{\frac{m_{0}}{m}}\right)\,.$
(69)

As the infimum over $E_{\nu}$ is homogeneous in $\nu$ (i.e., “proportional” to
all $\nu\geq 0$), we obtain for the cone $E=\bigcup_{\nu\geq 0}E_{\nu}$
generated by $E_{\nu_{0}}$ that

$\displaystyle\inf_{M\in
E}\frac{\left\|\mathcal{A}(M)\right\|_{\ell_{q}}}{\left\|M\right\|_{\mathrm{F}}}$
$\displaystyle=\inf_{M\in
E_{\nu_{0}}}\left\|\mathcal{A}(M)\right\|_{\ell_{q}}/\nu_{0}$ (70)
$\displaystyle=\inf_{M\in
E_{\nu_{0}}}\left\|\mathcal{A}(M)\right\|_{\ell_{q}}\frac{\left\|A\right\|_{2}}{n(n+1)}$
(71)
$\displaystyle\geq\frac{c-c_{\lambda}}{5}\left\|A\right\|_{2}\frac{m^{\frac{1}{q}}\left(1-\sqrt{\frac{m_{0}}{m}}\right)}{n(n+1)}\,,$
(72)

where we have remembered the choice of $\nu_{0}$ form the beginning of the
proof. This bound holds with probability at least
$1-\mathrm{e}^{-\lambda^{2}/2}=1-\mathrm{e}^{-c_{\lambda}^{2}m/5}$ over
$\mathcal{A}$ for any $c_{\lambda}\in{}]0,c[$. ∎

####  III.2.1 Upper bound on the mean empirical width $W_{m}$

We prove an upper bound on $W_{m}$ defined in Eq. (40) for $E$ being a slice
of the cone of effectively rank-$r$ maps.

######  Lemma 13 (Bound on $W_{m}$).

For $r\in\mathbb{Z}^{+}$, $\nu>0$, and $c_{\mu}>0$ let

$K\coloneqq\Bigl{\\{}M\in\operatorname{HT}(\mathbb{C}^{n})_{0}:\left\|J(M)\right\|_{1}\leq
c_{\mu}\sqrt{r}\left\|J(M)\right\|_{2}\Bigr{\\}}$ (73)

and

$E_{\nu}\coloneqq\\{M\in K:\left\|M\right\|_{\mathrm{F}}=\nu\\}.$ (74)

For $m\geq 2n^{2}\ln(n)$ let
$(A_{i},\left.\left|{\psi_{i}}\right.\right\rangle)_{i\in[m]}$ be a normalized
4-generic measurement ensemble (Definition 1). Then the mean empirical width
(40) is bounded as

$W_{m}(E_{\nu})\leq\frac{c_{\mu}\sqrt{6\,\mathrm{e}\ln(n)\,r}}{n}\,\nu\left\|A\right\|_{2}\,.$
(75)

###### Proof.

By definition (40), $W_{m}$ reads as

$\displaystyle W_{m}(E_{\nu})$
$\displaystyle=\operatorname{\mathbb{E}}\sup_{M\in
E_{\nu}}\frac{1}{\sqrt{m}}\sum_{i=1}^{m}\epsilon_{i}\operatorname{Tr}[U_{i}A\,U_{i}^{\dagger}M(\left.\left|{\psi_{i}}\right.\right\rangle\\!\\!\left.\left\langle{\psi_{i}}\right.\right|)].$
(76)

Since $W_{m}(E_{\nu})=\nu W_{m}(E)$ with $E\coloneqq E_{1}$, it is enough to
prove the lemma for $\nu=1$.

With

$H_{i}\coloneqq(U_{i}A\,U_{i}^{\dagger})\otimes(\left.\left|{\psi_{i}}\right.\right\rangle\\!\\!\left.\left\langle{\psi_{i}}\right.\right|^{T})\in\operatorname{\mathrm{L}}(\mathbb{C}^{n}\otimes\mathbb{C}^{n})$
(77)

and using the identity (30), the “expectation value” can also be written as

$\operatorname{Tr}[U_{i}A\,U_{i}^{\dagger}M(\left.\left|{\psi_{i}}\right.\right\rangle\\!\\!\left.\left\langle{\psi_{i}}\right.\right|)]=\operatorname{Tr}[H_{i}\,J(M)]\,.$
(78)

We define

$H\coloneqq\frac{1}{\sqrt{m}}\sum_{i=1}^{m}\epsilon_{i}H_{i}$ (79)

to arrive at the compact form

$W_{m}(E)=\operatorname{\mathbb{E}}\sup_{M\in E}\operatorname{Tr}[HJ(M)]\,.$
(80)

The application of Hölder’s inequality yields

$W_{m}(E)\leq\operatorname{\mathbb{E}}\sup_{M\in
E}\left\|H\right\|_{\infty}\left\|J(M)\right\|_{1}\,.$ (81)

Using the definition (73) of $K$ and that
$\left\|J(M)\right\|_{2}=\left\|M\right\|_{\mathrm{F}}=\nu=1$ we obtain

$W_{m}(E)\leq
c_{\mu}\sqrt{r}\operatorname{\mathbb{E}}\left\|H\right\|_{\infty}\,.$ (82)

In order to bound $\operatorname{\mathbb{E}}\left\|H\right\|_{\infty}$ we
proceed similarly as in the proof of (Kueng  _et al._ , 2017, Proposition 13).
By applying a non-commutative Khintchine inequality (see Theorem 29 in
Appendix B) to (79) we obtain

$\operatorname{\mathbb{E}}_{\epsilon_{i}}[\left\|H\right\|_{\infty}]\leq\sqrt{\frac{2\ln(2n^{2})}{m}}\operatorname{\mathbb{E}}\,\Bigl{\|}\left(\sum_{i=1}^{m}H_{i}^{2}\right)^{1/2}\Bigr{\|}_{\infty}.$
(83)

Thanks to Jensen’s inequality,
$\operatorname{\mathbb{E}}\bigl{\|}\sqrt{X}\bigr{\|}_{\infty}\leq\operatorname{\mathbb{E}}\sqrt{\left\|X\right\|_{\infty}}\leq\sqrt{\operatorname{\mathbb{E}}\left\|X\right\|_{\infty}}$
and, hence,

$\operatorname{\mathbb{E}}_{\epsilon_{i}}[\left\|H\right\|_{\infty}]\leq\sqrt{\frac{2\ln(2n^{2})}{m}}\left(\operatorname{\mathbb{E}}\,\Bigl{\|}\sum_{i=1}^{m}H_{i}^{2}\Bigr{\|}_{\infty}\right)^{1/2}.$
(84)

The Matrix Chernoff Bound (Tropp, 2012, Theorem 5.1.1) implies that

$\operatorname{\mathbb{E}}\,\Bigl{\|}\sum_{i=1}^{m}H_{i}^{2}\Bigr{\|}_{\infty}\leq\frac{\mathrm{e}^{\theta}-1}{\theta}\,m\,\bigl{\|}\operatorname{\mathbb{E}}\bigl{[}H_{1}^{2}\bigr{]}\bigr{\|}_{\infty}+\sup_{H_{1}}\left\|H_{1}\right\|_{\infty}\frac{\ln(n^{2})}{\theta}\,,$
(85)

where we have already used that $\\{H_{i}\\}$ are i.i.d. operators. With the
averages (51) and (52) we find that $H_{1}$ (defined in Eq. (77)) satisfies

$\displaystyle\bigl{\|}\operatorname{\mathbb{E}}\bigl{[}H_{1}^{2}\bigr{]}\bigr{\|}_{\infty}=$
$\displaystyle\Bigl{\|}\frac{\operatorname{Tr}[A^{2}]}{n}\mathds{1}\Bigr{\|}_{\infty}\;\Bigl{\|}\frac{1}{n}\,\mathds{1}\Bigr{\|}_{\infty}=\frac{\left\|A\right\|_{2}^{2}}{n^{2}}.$
(86)

Moreover, $H_{1}$ always satisfies

$\left\|H_{1}\right\|_{\infty}=\left\|A\right\|_{\infty}\bigl{\|}\left.\left|{\psi}\right.\right\rangle\\!\\!\left.\left\langle{\psi}\right.\right|^{T}\bigr{\|}_{\infty}=1\,,$
(87)

as $A$ and $\left.\left|{\psi}\right.\right\rangle$ are both normalized.
Hence,

$\operatorname{\mathbb{E}}\,\Bigl{\|}\sum_{i=1}^{m}H_{i}^{2}\Bigr{\|}_{\infty}\leq\frac{\mathrm{e}^{\theta}-1}{\theta}\,m\,\,\frac{\left\|A\right\|_{2}^{2}}{n^{2}}+\frac{\ln(n^{2})}{\theta}\,.$
(88)

Choosing $\theta=1$ and proceeding from Eq. (84) we obtain

$\operatorname{\mathbb{E}}[\left\|H\right\|_{\infty}]\leq\sqrt{\frac{2\ln(2n^{2})}{m}}\left((\mathrm{e}-1)\,m\,\frac{\left\|A\right\|_{2}^{2}}{n^{2}}+2\ln(n)\right)^{1/2}.$
(89)

With $\left\|A\right\|_{2}\geq\left\|A\right\|_{\infty}=1$ and the assumptions
$m\geq 2n^{2}\ln(n)$ and $\ln\bigl{(}\sqrt{2}n\bigr{)}\leq\frac{3}{2}\ln(n)$
we obtain

$\displaystyle\operatorname{\mathbb{E}}[\left\|H\right\|_{\infty}]$
$\displaystyle\leq\sqrt{4\ln\bigl{(}\sqrt{2}\,n\bigr{)}}\,\frac{\left\|A\right\|_{2}}{n}\left((\mathrm{e}-1)+\frac{2n^{2}\ln(n)}{m}\right)^{1/2}$
(90)
$\displaystyle\leq\frac{\sqrt{6\,\mathrm{e}\ln(n)}}{n}\,\left\|A\right\|_{2}\,.$
(91)

Finally, with Eq. (82),

$W_{m}(E)\leq\frac{c_{\mu}\sqrt{6\,\mathrm{e}\ln(n)\,r\,}}{n}\,\left\|A\right\|_{2}\,,$
(92)

which proves Lemma 13. ∎

####  III.2.2 Lower bound on the marginal tail function $Q_{\xi}$

In this section, we prove a lower bound on the marginal tail function (39).

######  Lemma 14 (Lower tail bound).

Let $(A_{i},\left.\left|{\psi_{i}}\right.\right\rangle)_{i\in[m]}$ be a
normalized 4-generic measurement ensemble (Definition 1). For some trace
annihilating $M\in\operatorname{TP}(\mathbb{C}^{n})_{0}$ define the random
variable

$S\coloneqq\operatorname{Tr}[UA\,U^{\dagger}\,M(\left.\left|{\psi}\right.\right\rangle\\!\\!\left.\left\langle{\psi}\right.\right|)]\,.$
(93)

Then $S$ satisfies

$\displaystyle\operatorname{\mathbb{P}}\bigl{[}|S|\geq\xi\bigr{]}$
$\displaystyle\geq
c\left(1-\frac{\xi^{2}(n-1)\,n\,(n+1)^{2}}{2\left\|A\right\|_{2}^{2}\Bigl{(}\left\|M(\mathds{1})\right\|_{2}^{2}+\left\|M\right\|_{\mathrm{F}}^{2}\Bigr{)}}\right)^{2}$
(94)

for all $\xi>0$, where $c$ is an absolute constant.

We will prove this lemma using the Paley-Zygmund inequality. This inequality
states that for every non-negative random variable $Z\geq 0$ and parameter
$\theta\in[0,1]$

$\operatorname{\mathbb{P}}\bigl{[}Z>\theta\operatorname{\mathbb{E}}[Z]\bigr{]}\geq(1-\theta)^{2}\frac{\operatorname{\mathbb{E}}[Z]^{2}}{\operatorname{\mathbb{E}}\bigl{[}Z^{2}\bigr{]}}\,.$
(95)

We will choose $Z=|S|^{2}$ so that we can use a lower bound on the second
moment and an upper bound on the fourth moment of $S$.

###### Proof of Lemma 14.

As typically done Tropp (2015), we use the Paley-Zygmund inequality (95) to
establish the lower tail bound,

$\displaystyle\operatorname{\mathbb{P}}\bigl{[}|S|\geq\xi\bigr{]}$
$\displaystyle=\operatorname{\mathbb{P}}\bigl{[}|S|^{2}\geq\xi^{2}\bigr{]}$
(96)
$\displaystyle\geq\left(1-\frac{\xi^{2}}{\operatorname{\mathbb{E}}[|S|^{2}]}\right)^{2}\,\frac{\operatorname{\mathbb{E}}[|S|^{2}]^{2}}{\operatorname{\mathbb{E}}[|S|^{4}]}\,.$
(97)

Inserting the fourth moment bound (117) and the second moment (99) into (97)
we obtain for another absolute constant $c>0$ that

$\displaystyle\\!\\!\\!\\!\operatorname{\mathbb{P}}\bigl{[}|S|\geq\xi\bigr{]}$
(98) $\displaystyle\geq
c\left(1-\frac{\xi^{2}}{\operatorname{\mathbb{E}}[|S|^{2}]}\right)^{2}\frac{(n-1)^{2}n^{2}(n+1)^{2}(n+2)(n+3)}{(n-1)^{2}n^{2}(n+1)^{4}}$
$\displaystyle\geq
c\left(1-\frac{\xi^{2}(n-1)\,n\,(n+1)^{2}}{2\left\|A\right\|_{2}^{2}\Bigl{(}\left\|M(\mathds{1})\right\|_{2}^{2}+\left\|M\right\|_{\mathrm{F}}^{2}\Bigr{)}}\right)^{2},$

where (99) has been used again in the second step. This bound proves Lemma 14.
∎

Actually, we can fully calculate the second moment without any assumptions on
$\operatorname{Tr}[A]$.

######  Lemma 15 (Second moment).

Let $(A_{i},\left.\left|{\psi_{i}}\right.\right\rangle)_{i\in[m]}$ be a
4-generic measurement ensemble (Definition 1) and
$M\in\operatorname{HT}(\mathbb{C}^{n})_{0}$ be a trace annihilating map.

Then
$S\coloneqq\operatorname{Tr}[UA\,U^{\dagger}\,M(\left.\left|{\psi}\right.\right\rangle\\!\\!\left.\left\langle{\psi}\right.\right|)]$
has the second moment

$\operatorname{\mathbb{E}}\bigl{[}|S|^{2}\bigr{]}=\frac{2\left\|A\right\|_{2}^{2}\,n-2\operatorname{Tr}[A]^{2}}{(n-1)\,n^{2}\,(n+1)^{2}}\Bigl{(}\left\|M(\mathds{1})\right\|_{2}^{2}+\left\|M\right\|_{\mathrm{F}}^{2}\Bigr{)}\,.$
(99)

Figure 8: Tensor network diagrams: tensors are denoted by boxes with one line
for each index. Contraction of two indices corresponds to connection of the
corresponding lines. Examples: A vector
$\left.\left|{\psi}\right.\right\rangle$, vectorization of an operator $A$,
$M\in\operatorname{\mathbb{L}}(\mathbb{C}^{n})$ applied to that vectorization,
the non-vectorized version of the flip operator $\mathbb{F}$, and
$M^{1,1}=M\otimes M^{\star}$.

###### Proof.

First, we will derive some identities for certain traces containing
$\mathds{1}$, $\mathbb{F}$, and $M$. As $M$ is trace annihilating, i.e.,
$M^{\dagger}(\mathds{1})=0$, we obtain

$\operatorname{Tr}[\mathds{1}M^{1,1}(\mathds{1})]=\operatorname{Tr}[M^{1,1\dagger}(\mathds{1})]=0$
(100)

and

$\operatorname{Tr}[\mathds{1}M^{1,1}(\mathbb{F})]=\operatorname{Tr}[M^{1,1\dagger}(\mathds{1})\mathbb{F}]=0\,.$
(101)

Moreover, using “the swap-trick” $\operatorname{Tr}[\mathbb{F}(A\otimes
B)]=\operatorname{Tr}[AB]$ we obtain

$\displaystyle\operatorname{Tr}[\mathbb{F}M^{1,1}(\mathds{1})]$
$\displaystyle=\operatorname{Tr}[\mathbb{F}M(\mathds{1})\otimes
M^{\star}(\mathds{1})]$ (102)
$\displaystyle=\operatorname{Tr}[M(\mathds{1})M^{\star}(\mathds{1})]$ (103)
$\displaystyle=\operatorname{Tr}[|M(\mathds{1})|^{2}]$ (104)
$\displaystyle=\left\|M(\mathds{1})\right\|_{2}^{2}\,.$ (105)

The last of these identities is

$\displaystyle\operatorname{Tr}[\mathbb{F}M^{1,1}(\mathbb{F})]$
$\displaystyle=\operatorname{Tr}[\mathbb{F}(M\otimes M^{\ast})(\mathbb{F})]$
(106)
$\displaystyle=\begin{matrix}\mathord{\includegraphics{figProofLemma15}}\end{matrix}$
(107) $\displaystyle=\operatorname{Tr}[J(M)J(M^{\star})]$ (108)
$\displaystyle=\operatorname{Tr}[J(M)J(M)^{\dagger}]=\operatorname{Tr}[|J(M)|^{2}]$
(109)
$\displaystyle=\left\|J(M)\right\|_{2}^{2}=\left\|M\right\|_{\mathrm{F}}^{2}\,,$
(110)

see Figure 8 for an explanation of the tensor network diagram.

Next, using the expressions for the second moments of
$\left.\left|{\psi}\right.\right\rangle\\!\\!\left.\left\langle{\psi}\right.\right|$
and $UAU^{\dagger}$, (57) and (59), we obtain

$\displaystyle\operatorname{\mathbb{E}}[|S|^{2}]$
$\displaystyle=\operatorname{Tr}\bigl{[}\bigl{(}UA\,U^{\dagger}M(\left.\left|{\psi}\right.\right\rangle\\!\\!\left.\left\langle{\psi}\right.\right|)\bigr{)}\otimes\bigl{(}UA\,U^{\dagger}M^{\star}(\left.\left|{\psi}\right.\right\rangle\\!\\!\left.\left\langle{\psi}\right.\right|)\bigr{)}\bigr{]}$
(111)
$\displaystyle=\operatorname{Tr}\Bigl{[}\operatorname{\mathbb{E}}\bigr{[}(UAU^{\dagger})^{\otimes
2}\bigl{]}M^{1,1}\Bigl{(}\operatorname{\mathbb{E}}\bigl{[}\left.\left|{\psi}\right.\right\rangle\\!\\!\left.\left\langle{\psi}\right.\right|^{\otimes
2}\bigr{]}\Bigr{)}\Bigr{]}$ (112)
$\displaystyle=\frac{1}{2n^{2}(n+1)}\sum_{\pm}\frac{\operatorname{Tr}(A)^{2}\pm\operatorname{Tr}(A^{2})}{n\pm
1}\operatorname{Tr}\Bigl{[}(\mathds{1}\pm\mathbb{F})M^{1,1}(\mathds{1}+\mathbb{F})\Bigr{]}$
(113)
$\displaystyle=\frac{1}{2n^{2}(n+1)}\sum_{\pm}\frac{\pm\operatorname{Tr}(A)^{2}+\operatorname{Tr}(A^{2})}{n\pm
1}\operatorname{Tr}\Bigl{[}\mathbb{F}M^{1,1}(\mathds{1}+\mathbb{F})\Bigr{]}\,.$
(114)

We finish the proof by using the traces containing $M$ from the beginning and
that $\operatorname{Tr}[A^{2}]=\left\|A\right\|_{2}^{2}$,

$\displaystyle\operatorname{\mathbb{E}}[|S|^{2}]$
$\displaystyle=\frac{1}{\,n^{2}\,(n+1)}\Bigl{(}\frac{\operatorname{Tr}[A]^{2}+\operatorname{Tr}[A^{2}]}{n+1}+\frac{-\operatorname{Tr}[A]^{2}+\operatorname{Tr}[A^{2}]}{n-1}\Bigr{)}\Bigl{(}\left\|M(\mathds{1})\right\|_{2}^{2}+\left\|M\right\|_{\mathrm{F}}^{2}\Bigr{)}$
(115)
$\displaystyle=\frac{2\left\|A\right\|_{2}^{2}\,n-2\operatorname{Tr}[A]^{2}}{(n-1)\,n^{2}\,(n+1)^{2}}\Bigl{(}\left\|M(\mathds{1})\right\|_{2}^{2}+\left\|M\right\|_{\mathrm{F}}^{2}\Bigr{)}\,.$
(116)

∎

######  Lemma 16 (Upper bound on the fourth moment).

The random variable $S$ form Lemma 14 has a fourth moment bounded as

$\operatorname{\mathbb{E}}[|S|^{4}]\leq
c_{3}\frac{\left\|A\right\|_{2}^{4}\Bigl{(}\left\|M(\mathds{1})\right\|_{2}^{2}+\left\|M\right\|_{\mathrm{F}}^{2}\Bigr{)}^{2}}{(n-1)^{2}n^{2}(n+1)^{2}(n+2)(n+3)}\,,$
(117)

where $c_{3}$ is an absolute constant.

The proof of this lemma uses facts about the symmetric group $S_{4}$ all of
which are stated in Appendix C.

###### Proof.

The fourth moment is

$\displaystyle\phantom{=i}\operatorname{\mathbb{E}}[|S|^{4}]$ (118)
$\displaystyle=\operatorname{Tr}\bigl{[}\bigl{(}UAU^{\dagger}M(\left.\left|{\psi}\right.\right\rangle\\!\\!\left.\left\langle{\psi}\right.\right|)\bigr{)}^{\otimes
2}\otimes\bigl{(}UAU^{\dagger}M^{\star}(\left.\left|{\psi}\right.\right\rangle\\!\\!\left.\left\langle{\psi}\right.\right|)\bigr{)}^{\otimes
2}\bigr{]}$
$\displaystyle=\operatorname{Tr}\Bigl{[}\operatorname{\mathbb{E}}\bigr{[}(UA\,U^{\dagger})^{\otimes
4}\bigl{]}M^{\otimes
2,2}\Bigl{(}\operatorname{\mathbb{E}}\bigl{[}\left.\left|{\psi}\right.\right\rangle\\!\\!\left.\left\langle{\psi}\right.\right|^{\otimes
4}\bigr{]}\Bigr{)}\Bigr{]}\,.$ (119)

According to Eq. (50) the average over
$\left.\left|{\psi}\right.\right\rangle$ yields

$\operatorname{\mathbb{E}}\bigl{[}\left.\left|{\psi}\right.\right\rangle\\!\\!\left.\left\langle{\psi}\right.\right|^{\otimes
4}\bigr{]}=\frac{1}{d_{1}(n)}P_{\mathrm{Sym}^{4}},$ (120)

where we have used that $\operatorname{Tr}(P_{\mathrm{Sym}^{4}})=d_{1}(n)$
with $d_{1}(n)=n\,(n+1)(n+2)(n+3)/24$ from Eq. (188) being the dimension
$\operatorname{Tr}(P_{\mathrm{Sym}^{4}})$ corresponding to the trivial
representation $\mathrm{Sym}^{4}$.

According to Eq. (47) we have

$\displaystyle\operatorname{\mathbb{E}}\bigr{[}(UA\,U^{\dagger})^{\otimes
4}\bigl{]}=\sum_{i=1}^{5}a_{i}\,P_{i}\,.$ (121)

By taking the trace, we obtain the corresponding expansion coefficients

$a_{i}=\frac{\operatorname{Tr}[A^{\otimes 4}\,P_{i}]}{d_{i}(n)}$ (122)

where $d_{i}(n)=\operatorname{Tr}[P_{i}]$ is also given in (188) and each
$P_{i}$ is the representation of the central minimal projection $p_{i}$ of
$S_{4}$ (see (185)) on $(\mathbb{C}^{n})^{\otimes 4}$. Inserting everything
into (119), we obtain

$\operatorname{\mathbb{E}}[|S|^{4}]=\sum_{i=1}^{5}a_{i}\,\frac{\operatorname{Tr}\Bigl{[}P_{i}M^{\otimes
2,2}(P_{1})\Bigr{]}}{d_{1}(n)}\,.$ (123)

For a permutation $\sigma\in S_{4}$ with representation
$R(\sigma)\in\operatorname{\mathrm{L}}((\mathbb{C}^{n})^{\otimes 4})$ the
Hilbert-Schmidt overlap $\operatorname{Tr}[A^{\otimes 4}R(\sigma)]$ only
depends on the conjugacy class of $\sigma$. We denote the conjugacy class
containing permutations composed of each $j_{i}$ disjoint cycles of sizes
$\\{k_{i}\\}_{i\in[l]}$ by $k_{1}^{j_{1}}k_{2}^{j_{2}}\dots k_{l}^{j_{l}}$,
e.g., $2^{1}\subset S_{4}$ are the transpositions. One can conclude, e.g.,
from tensor network diagrams that

$\displaystyle\operatorname{Tr}[\mathds{1}\,A^{\otimes 4}]$
$\displaystyle=\operatorname{Tr}[A]^{4}=0\,,$ (124)
$\displaystyle\operatorname{Tr}[2^{2}A^{\otimes 4}]$
$\displaystyle=\operatorname{Tr}[A^{2}]^{2},$
$\displaystyle\operatorname{Tr}[2^{1}A^{\otimes 4}]$
$\displaystyle=\operatorname{Tr}[A^{2}]\operatorname{Tr}[A]^{2}=0\,,$
$\displaystyle\operatorname{Tr}[4^{1}A^{\otimes 4}]$
$\displaystyle=\operatorname{Tr}[A^{4}]\,,$
$\displaystyle\operatorname{Tr}[3^{1}A^{\otimes 4}]$
$\displaystyle=\operatorname{Tr}[A^{3}]\operatorname{Tr}[A]=0\,.$

With the sizes of the conjugacy classes (181), the minimal projections (185),
and the dimensional factors (188)

$\displaystyle a_{1}$
$\displaystyle=\frac{3\operatorname{Tr}[A^{2}]^{2}+6\operatorname{Tr}[A^{4}]}{n\,(n+1)(n+2)(n+3)}\,,$
(125) $\displaystyle a_{2}$
$\displaystyle=\frac{3\operatorname{Tr}[A^{2}]^{2}-6\operatorname{Tr}[A^{4}]}{(n-3)(n-2)(n-1)\,n}\,,$
$\displaystyle a_{3}$
$\displaystyle=\frac{6\operatorname{Tr}[A^{2}]^{2}}{(n-1)\,n^{2}\,(n+1)}\,,$
$\displaystyle a_{4}$
$\displaystyle=\frac{-3\operatorname{Tr}[A^{2}]^{2}-6\operatorname{Tr}[A^{4}]}{(n-1)\,n\,(n+1)(n+2)}\,,$
$\displaystyle a_{5}$
$\displaystyle=\frac{-3\operatorname{Tr}[A^{2}]^{2}+6\operatorname{Tr}[A^{4}]}{(n-2)(n-1)\,n\,(n+1)}\,,\,$

for $n\geq 4$. For $n=3$ we have $P_{2}=0$ and, hence $a_{2}=0$. For $n=2$ we
have $P_{2}=0$ and $P_{5}=0$ and, hence, $a_{2}=a_{5}=0$. In both cases, the
remaining $a_{i}$ are as stated above.

From the submultiplicativity of the Schatten $2$-norm follows that
$\left\|A^{j}\right\|_{2}\leq\left\|A\right\|_{2}^{j}$ for
$j\in\mathbb{Z}^{+}$. Also using the bound

$\frac{1}{n-j}\leq\frac{j+1}{n}\qquad\text{for integers}\ n>j\geq 0$ (126)

we obtain

$|a_{i}|\leq\frac{c_{1}\left\|A\right\|_{2}^{4}}{(n-1)^{2}\,n\,(n+1)}$ (127)

for all $i\in[5]$, where $c_{1}$ is an absolute constant.

In order to bound $\operatorname{Tr}[P_{i}M^{\otimes 2,2}(P_{1})]$ in Eq.
(123) we observe that each projection $P_{i}$ is a linear combination of
permutation matrices $\\{R(\sigma)\\}_{\sigma\in S_{4}}$, see (185), where
only the permutation matrices $R(\sigma)$ depend on $n$. Hence, it is enough
to bound $\operatorname{Tr}[R(\sigma)M^{2,2}(R(\tau))]$ for all permutations
$\sigma,\tau\in S_{4}$.

Combining (117) from Lemma 17 below, (127), and (123) yields

$\operatorname{\mathbb{E}}[|S|^{4}]\leq
c_{3}\frac{\left\|A\right\|_{2}^{4}\Bigl{(}\left\|M(\mathds{1})\right\|_{2}^{2}+\left\|M\right\|_{\mathrm{F}}^{2}\Bigr{)}^{2}}{(n-1)^{2}n^{2}(n+1)^{2}(n+2)(n+3)}$
(128)

for some absolute constant $c_{3}$. ∎

######  Lemma 17.

For any $M\in\operatorname{HT}(\mathbb{C}^{n})_{0}$ and $\sigma,\tau\in S_{4}$

$\bigl{|}\operatorname{Tr}[R(\sigma)M^{2,2}(R(\tau))]\bigr{|}\leq
c_{2}\Bigl{(}\left\|M(\mathds{1})\right\|_{2}^{2}+\left\|M\right\|_{\mathrm{F}}^{2}\Bigr{)}^{2}$
(129)

for some absolute constant $c_{2}$.

###### Proof.

We will conclude from Proposition 18 that

$\bigl{|}\operatorname{Tr}[R(\sigma)M^{2,2}(R(\tau))]\bigr{|}\leq
c_{2}^{\prime}\max\bigl{\\{}\left\|M(\mathds{1})\right\|_{2}^{4},\left\|M\right\|_{\mathrm{F}}^{4}\Bigr{\\}}$
(130)

for some absolute constant $c_{2}^{\prime}$, which implies the lemma.

We consider
$\operatorname{HT}(\mathbb{C}^{n})_{0}\subset\operatorname{\mathrm{L}}(\operatorname{\mathrm{L}}(\mathcal{X})\to\operatorname{\mathrm{L}}(\mathcal{Y}))$
as a subspace, where $\mathcal{X}=\mathbb{C}^{n}=\mathcal{Y}$ are labels for
the input and output Hilbert space. The permutation operator $R(\tau)$
permutes and contracts the indices of $M^{2,2}$ in
$\operatorname{Tr}[R(\sigma)M^{2,2}(R(\tau))]$ that correspond to
$\mathcal{X}$. Similarly, the permutation operator $R(\sigma)$ permutes the
indices of $M^{2,2}$ in $\operatorname{Tr}[R(\sigma)M^{2,2}(R(\tau))]$ that
correspond to $\mathcal{Y}$, which are contracted subsequently by
$\operatorname{Tr}$. So, no $\mathcal{X}$-index is contracted with a
$\mathcal{Y}$-index. Hence, $\operatorname{Tr}[R(\sigma)M^{2,2}(R(\tau))]$ is
a contraction without self-contractions of the tensors
$\\{M,M^{\star},M(\mathds{1}),M^{\star}(\mathds{1}),\operatorname{Tr}\circ
M,\operatorname{Tr}\circ M^{\star}\\}$. The tensors $\operatorname{Tr}\circ
M^{\star}$ and $\operatorname{Tr}\circ M$ vanish due to maps in
$\operatorname{HT}(\mathbb{C}^{n})_{0}$ being trace annihilating. Moreover,
$\left\|M\right\|_{\mathrm{F}}=\left\|M^{\star}\right\|_{\mathrm{F}}$ and
$\left\|M(\mathds{1})\right\|_{2}=\left\|M^{\star}(\mathds{1})\right\|_{2}$.
Proposition 18 tells us that arbitrary closed tensor networks without self-
contractions are bounded by the product of the Frobenius norms of the single
tensors and implies the bound (130). ∎

###  III.3 General tensor network bound

In this section, we prove a simple bound on a fully contracted tensor network,
which we used to prove Lemma 17. A _tensor_ is a vector in
$\mathbb{C}^{n_{1}}\otimes\mathbb{C}^{n_{2}}\otimes\dots\otimes\mathbb{C}^{n_{K}}$,
where $\mathcal{X}\otimes\mathcal{Y}$ denotes the tensor product of vector
spaces $\mathcal{X}$ and $\mathcal{Y}$. It is often helpful to identify a
tensor with its representation $t$ in terms of a product basis of the
canonical bases of $\mathbb{C}^{n_{i}}$. Then $t$ is given as an array of
numbers, i.e., $t\in\mathbb{C}^{n_{1}\times n_{2}\times\dots\times n_{K}}$.

A _tensor network_ is a set of tensors together with a contraction
corresponding to pairs of indices where both indices have the same dimension
$n_{i}$. Instances of such tensor networks are, e.g., the workhorse of
powerful simulation techniques for strongly correlated quantum systems
Schollwöck (2011).

We present a general version of such tensor networks and then prove our bound.
For this purpose, we use a notation that is completely disjoint from the other
sections. E.g., $C$ will be a contraction instead of a constant.

A _pointer_ to an index of a tensor in
$\mathbb{C}^{n_{1}}\otimes\mathbb{C}^{n_{2}}\otimes\dots\otimes\mathbb{C}^{n_{K}}$
is just a number $k\in[K]$ used to identify the $k$-th index. A _contraction_
is a linear map

$C:\mathbb{C}^{n_{1}}\otimes\mathbb{C}^{n_{2}}\otimes\dots\otimes\mathbb{C}^{n_{K}}\to\mathbb{C}^{n_{i_{1}}}\otimes\mathbb{C}^{n_{i_{2}}}\otimes\dots\otimes\mathbb{C}^{n_{I}}$

given by a set of pairs of pointers $P=(\\{k_{l},k^{\prime}_{l}\\})_{l\in[L]}$
with even $K-I=2L$ so that each number $k\in[K]$ occurs at most once in at
most one of the pairs. In particular, $k_{l}\neq k^{\prime}_{l}$ for all
$l\in[L]$. Moreover, the consistency condition $n_{k_{l}}=n_{k^{\prime}_{l}}$
is required to hold for all $l\in[L]$ (in many relevant cases the dimensions
$n_{k}$ assume only a very few different values). Let
$\mathcal{P}=\\{k_{l},k^{\prime}_{l}\\}_{l\in[L]}$ be the set of pointers
occurring in the pairs $P$ and $\mathcal{I}\coloneqq[K]\setminus\mathcal{P}$
the other pointers. Then the contraction $C(t)$ of a tensor
$t\in\mathbb{C}^{n_{1}}\otimes\mathbb{C}^{n_{2}}\otimes\dots\otimes\mathbb{C}^{n_{K}}$
is given by the components

$\begin{split}C(t)_{\alpha^{\prime}_{i_{1}},\alpha^{\prime}_{i_{2}},\dots,\alpha^{\prime}_{i_{I}}}\coloneqq&\sum_{\alpha_{k}\in[n_{k}],\
k\in[K]}t_{\alpha_{1},\alpha_{2},\dots,\alpha_{K}}\\\
&\qquad\quad\times\prod_{l\in\mathcal{P}}\delta_{\alpha_{k_{l}},\alpha_{k^{\prime}_{l}}}\prod_{m\in\mathcal{I}}\delta_{\alpha_{m},\alpha^{\prime}_{m}}\,,\end{split}$

i.e., all index pairs $\\{k_{l},k^{\prime}_{l}\\}$ are summed over and the
remaining indices are the indices of $C(t)$.

A _tensor network_ is a set of tensors $T=(t^{j})_{j\in J}$ with
$t^{j}\in\mathbb{C}^{n_{1}^{j}\times n_{2}^{j}\times\dots\times
n_{K^{j}}^{j}}$ together with a contraction $C$ of their tensor product
$t^{1}\otimes t^{2}\otimes\dots\otimes t^{J}$, where we use the convention

$\begin{split}(t^{1}&\otimes t^{2}\otimes\dots\otimes
t^{J})_{i_{1},i_{2},\dots,i^{K}}=\\\
&t^{1}_{i_{1},i_{2},\dots,i_{K^{1}}}t^{2}_{i_{K^{1}+1},\dots,i_{K^{1}+K^{2}}}\dots
t^{J}_{i_{K-K^{J}+1},\dots,i_{K}}\end{split}$ (131)

with $K\coloneqq\sum_{j=1}^{J}K^{j}$. For short, we write $C(T)\coloneqq
C(t^{1}\otimes t^{2}\otimes\dots\otimes t^{J})$. We say that a tensor network
$(T,C)$ with tensors $T=(t^{j})_{j\in J}$ has a _self-contraction_ if there is
a tensor $t^{j}$ such that both pointers of one of the pairs
$\\{k_{l},k^{\prime}_{l}\\}$ defining $C$ point to indices of $t^{j}$. We call
a tensor network $(T,C)$ _closed_ if $C(T)$ is a number, i.e., if
$\mathcal{I}$ is empty.

The relevance of tensor networks comes from the fact that contractions of
_certain_ tensor networks (such as Matrix Product States) can be calculated
efficiently, while only to store general tensors requires exponentially many
parameters in the total number of indices. In general, estimating the outcome
of a contraction is a #$\mathsf{P}$-hard problem Gharibian  _et al._ (2015).
However, there is a simple and natural upper bound, which might already be
known. At least for sake of a self-contained presentation we provide a proof
below.

######  Proposition 18 (Bound on tensor network contractions).

Let $(T,C)$ be a tensor network with $J\geq 2$ tensors $T=(t^{j})_{j\in[J]}$
and contraction $C$ without self-contractions. Then

$\left\|C(T)\right\|_{\mathrm{F}}\leq\prod_{j=1}^{J}\left\|t^{j}\right\|_{\mathrm{F}}.$
(132)

If a tensor network has a self-contraction this statement can fail to hold.
Such an example can be easily constructed by taking the tensors so that the
trace of an identity matrix occurs.

Here we briefly sktech the proof of the tensor network bound and provide a
full proof in Appendix D.

###### Proof idea of Proposition 18.

Reshaping $t^{j}$ suitably into matrices $\tilde{t}^{j}$, the tensor network
$C(T)$ can be rewritten as a matrix product of
$\tilde{t}^{j}\otimes\mathds{1}$ sandwiched between vectorizations
$\left.\left\langle{t^{1}}\right.\right|$ and
$\left.\left|{t^{J}}\right.\right\rangle$ of $t^{1}$ and $t^{J}$,

$C(T)=\left\langle
t^{1}\right|\tilde{t}^{2}\otimes\mathds{1}\dots\tilde{t}^{J-1}\otimes\mathds{1}\left|t^{J}\right\rangle\,.$
(133)

Hence,

$\displaystyle|C(T)|$
$\displaystyle\leq\left\|\left.\left\langle{t^{1}}\right.\right|\right\|_{\ell_{2}}\left\|\tilde{t}^{2}\otimes\mathds{1}\right\|_{\infty}\dots\left\|\tilde{t}^{J-1}\otimes\mathds{1}\right\|_{\infty}\left\|\left.\left|{t^{J}}\right.\right\rangle\right\|_{\ell_{2}}$
(134)
$\displaystyle=\left\|t^{1}\right\|_{\mathrm{F}}\left\|\tilde{t}^{2}\right\|_{\infty}\dots\left\|\tilde{t}^{J-1}\right\|_{\infty}\left\|t^{J}\right\|_{\mathrm{F}}\,,$
(135)

where we have used that $\left\|A\otimes
B\right\|_{\infty}=\left\|A\right\|_{\infty}\left\|B\right\|_{\infty}$,
$\left\|\mathds{1}\right\|_{\infty}=1$, and that the Frobenius norm is the
$\ell_{2}$-norm of a vectorization. Then the bound
$\left\|\tilde{t}^{j}\right\|_{\infty}\leq\left\|\tilde{t}^{j}\right\|_{2}=\left\|t^{j}\right\|_{\mathrm{F}}$
between the Schatten norms finishes the proof. ∎

###  III.4 Proofs of the reconstruction theorems

In this section we prove generalized versions of the theorems presented in
Section II providing recovery guarantees for the constrained trace and diamond
norm regularization (16) and (17) and the CPT-fit (13).

####  III.4.1 Constrained trace norm minimization

In this section we prove a stable and robust reconstruction guarantee for:

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

with $q\geq 1$. The reconstruction procedure $T^{\ast c}_{\eta}$ introduced in
(16) is a special case, namely $q=2$, of this class of minimization problems.

######  Theorem 19 (Stable and robust reconstruction from trace norm
minimization).

Let $\mathcal{A}:\operatorname{CPT}(\mathbb{C}^{n})\to\mathbb{R}^{m}$ given by
$\mathcal{A}(T)_{j}=\operatorname{Tr}[A_{j}T(\left.\left|{\psi_{j}}\right.\right\rangle\\!\\!\left.\left\langle{\psi_{j}}\right.\right|)]$,
where $(A_{i},\left.\left|{\psi_{i}}\right.\right\rangle)_{i\in[m]}$ is a
4-generic measurement ensemble (Definition 1) and the observables’ traceless
part is $\tilde{A}_{0}\coloneqq A_{0}-\operatorname{Tr}[A_{0}]\mathds{1}/n\neq
0$.

Then there are constants $C$ and $\lambda$ such that the following holds. Fix
$q\geq 1$, some Kraus rank $r$, a number of measurement settings

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

and let $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_{\eta,q}^{\ast c}$ 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{\|}_{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}\bigr{\|}_{2}}\,\frac{\eta}{\left\|A_{0}\right\|_{\infty}}$
(138)

provided that $\left\|e\right\|_{\ell_{q}}\leq\eta$. The constants $C$,
$\lambda$, and $\tilde{c}$ only depend 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$.

We prove this statement by establishing a strong notion of the NSP (43) for
Choi matrices of channel differences. The main technical ingredient to prove
the NSP is the bound on the minimum conic singular value from Theorem 12. Then
Theorem 11 will give the desired result.

When proving the NSP it is helpful to consider two cases. First, operators
$X\in J\operatorname{HT}(\mathbb{C}^{n})$ satisfying
$\left\|X_{|r}\right\|_{\mathrm{F}}\leq\frac{\mu}{\sqrt{r}}\left\|X_{\neg
r}\right\|_{1}$ are effectively of high rank and satisfy the NSP by default.
Thus, it suffices to consider the case where
$\left\|X_{|r}\right\|_{2}\geq\frac{\mu}{\sqrt{r}}\left\|X_{\neg
r}\right\|_{1}$. Every such matrix satisfies

$\displaystyle\left\|X\right\|_{1}$ $\displaystyle\leq\left\|X_{\neg
r}\right\|_{1}+\left\|X_{|r}\right\|_{1}$ (139)
$\displaystyle<\frac{1+\mu}{\mu}\sqrt{r}\,\left\|X_{|r}\right\|_{2}$ (140)
$\displaystyle\leq\frac{1+\mu}{\mu}\sqrt{r}\,\left\|X\right\|_{2}\,.$ (141)

Hence $M=J^{-1}(X)$ is contained in the cone $K$ from Eq. (61) with
$c_{\mu}=\frac{1+\mu}{\mu}$. For any $q\geq 1$, Theorem 12 yields the bound

$\inf_{M\in
K}\frac{\left\|\mathcal{A}(M)\right\|_{\ell_{q}}}{\left\|M\right\|_{\mathrm{F}}}\geq\frac{1}{\tau}$
(142)

with probability over $\mathcal{A}$ at least $1-\mathrm{e}^{-\lambda m}$,
where

$1/\tau\geq\tilde{C}\left\|A\right\|_{2}\frac{m^{\frac{1}{q}}}{n^{2}}\,,$
(143)

and where $\tilde{C}$ is a constant only depending on $\lambda$ and $\mu$.
Hence, Theorem 11 yields

$\begin{split}\|J(T_{0}&-T^{\ast c}_{\eta,q})\|_{p}\\\
&\leq\frac{(1+\mu)^{2}}{1-\mu}\Bigl{(}\left\|J(T^{\ast
c}_{\eta,q})\right\|_{1}-\left\|J(T_{0})\right\|_{1}+2\left\|J(T_{0})_{\neg
r}\right\|_{1}\Bigr{)}\\\ &\phantom{\leq i}+\tau
r^{1/p-1/2}\,\frac{3+\mu}{1-\mu}\left\|\mathcal{A}(T_{0}-T^{\ast
c}_{\eta,q})\right\|_{\ell_{q}}\end{split}$ (144)

for any $\mu\in\left]0,1\right[\,$. The minimization in (136) assures
$\left\|J(T^{\ast c}_{\eta,q})\right\|_{1}\leq\left\|J(T_{0})\right\|_{1}$ by
construction, because $J(T_{0})$ is a feasible point of this optimization
problem. Moreover,

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

since $\mathcal{A}(T_{0})-y=e$ with $\left\|e\right\|_{\ell_{q}}\leq\eta$ and
$\left\|y-\mathcal{A}(T^{\ast c}_{\eta})\right\|_{\ell_{q}}\leq\eta$ due to a
constraint in the minimization (16). Choosing $\mu=\sqrt{5}-2$ leads to
$(1+\mu)^{2}/(1-\mu)=2$. Simplifying the bound (144) with these observations
completes the proof. ∎

####  III.4.2 CPT-fit

In this section, we prove a stable and robust reconstruction guarantee for the
following generalization of the CPT-fit (13):

$T^{\ell_{q}}\coloneqq\operatorname*{arg\,min}\\{\left\|\mathcal{A}(T)-y\right\|_{\ell_{q}}:\,T\in\operatorname{CPT}(\mathbb{C}^{n})\\}\,,$
(146)

where $q\geq 1$ arbitrary. Similar to before, the CPT-fit discussed in the
introductory section arises from fixing $q=2$.

######  Theorem 20 (Stable and robust reconstruction from CPT-fit).