Guaranteed recovery of quantum processes from few
measurements
M. Kliesch
1,2
, R. Kueng
3,4,5
, J. Eisert
4,6,7
, and D. Gross
3,8
1
Institute for Theoretical Physics, Heinrich Heine University Düsseldorf, Germany
2
Institute of Theoretical Physics and Astrophysics, University of Gdańsk, Poland
3
Institute for Theoretical Physics, University of Cologne, Germany
4
Dahlem Center for Complex Quantum Systems, Freie Universität Berlin, Germany
5
Institute for Quantum Information and Matter, California Institute of Technology, USA
6
Department of Mathematics and Computer Science, Freie Universität Berlin, Germany
7
Helmholtz-Zentrum Berlin für Materialien und Energie, Germany
8
Centre for Engineered Quantum Systems, School of Physics, The University of Sydney, Australia
Quantum process tomography is the task of reconstructing unknown quan-
tum 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 measure-
ment model for this task: We assume that data is obtained by sending pure
states into the channel and measuring expectation values on the output. Nei-
ther 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 in-
volve ancillary systems. A priori, it is unclear whether a measurement model
tailored directly to quantum process tomography might require more measure-
ments. 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 `
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 guaran-
teed. Numerical studies demonstrate the feasibility of the approach.
Contents
1 Introduction 3
1.1 Motivation of our measurement model . . . . . . . . . . . . . . . . . . . . . 3
1.2 Our contribution . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4
1.3 Related work . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5
M. Kliesch: science@mkliesch.eu, www.mkliesch.eu
Accepted in Quantum 2019-07-16, click title to verify. Published under CC-BY 4.0. 1
arXiv:1701.03135v4 [quant-ph] 6 Aug 2019
1.4 Experimental considerations . . . . . . . . . . . . . . . . . . . . . . . . . . . 6
1.5 Notation and terminology . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7
1.5.1 Maps on operators . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7
1.5.2 Norms . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8
1.5.3 Spherical and unitary designs . . . . . . . . . . . . . . . . . . . . . . 8
1.5.4 Measurement terminology . . . . . . . . . . . . . . . . . . . . . . . . 9
2 Results 9
2.1 Measurement model . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9
2.2 Reconstructions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10
2.3 Noiseless case . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11
2.3.1 Recovery guarantees I . . . . . . . . . . . . . . . . . . . . . . . . . . 12
2.3.2 Numerical demonstration . . . . . . . . . . . . . . . . . . . . . . . . 12
2.4 Stability and robustness . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14
2.4.1 Recovery guarantees II . . . . . . . . . . . . . . . . . . . . . . . . . . 14
2.4.2 Numerical example: Reconstructing the Toffoli gate . . . . . . . . . 17
2.5 Pauli measurements . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 20
2.6 Sample complexity . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21
2.7 Applications to fault tolerant quantum computation . . . . . . . . . . . . . 21
3 Analytical details and proofs 22
3.1 Preliminaries . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 23
3.1.1 Notation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 23
3.1.2 Normalization and centralization of the observables . . . . . . . . . . 24
3.1.3 Minimum conic singular value . . . . . . . . . . . . . . . . . . . . . . 24
3.1.4 Null space property . . . . . . . . . . . . . . . . . . . . . . . . . . . 25
3.1.5 Tools from representation theory . . . . . . . . . . . . . . . . . . . . 26
3.2 Our bound on the minimum conic singular value . . . . . . . . . . . . . . . 27
3.2.1 Upper bound on the mean empirical width W
m
. . . . . . . . . . . . 29
3.2.2 Lower bound on the marginal tail function Q
ξ
. . . . . . . . . . . . . 30
3.3 General tensor network bound . . . . . . . . . . . . . . . . . . . . . . . . . . 35
3.4 Proofs of the reconstruction theorems . . . . . . . . . . . . . . . . . . . . . 36
3.4.1 Constrained trace norm minimization . . . . . . . . . . . . . . . . . 36
3.4.2 CPT-fit . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 38
3.4.3 Constrained trace and diamond norm minimization . . . . . . . . . . 39
3.5 Reconstruction from approximate 4-generic measurements . . . . . . . . . . 40
3.6 Bosonic and fermionic linear optical circuits . . . . . . . . . . . . . . . . . . 43
4 Conclusion and outlook 44
4.1 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 44
4.2 Outlook . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 44
5 Acknowledgements 46
Appendices 46
A Semidefinite programs for trace and diamond norm reconstruction . . . . . . 46
B A non-commutative Khintchine inequality . . . . . . . . . . . . . . . . . . . 47
C Linear representation of the symmetric group S
4
. . . . . . . . . . . . . . . 47
D Proof of the tensor network bound Proposition 18 . . . . . . . . . . . . . . . 49
Accepted in Quantum 2019-07-16, click title to verify. Published under CC-BY 4.0. 2
1 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 [1, 2] 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 scal-
able 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 pro-
tocols 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 ∼ n
4
ex-
pectation 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 esti-
mate channels with (approximately) low Kraus rank from significantly fewer measurements
than naively required. It is imperative to make use of this structure.
1.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
⊗m
⊗ id
n
m
— where 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 ρ
global
, and likewise performing correlated measurements on
the respective output states (T
⊗m
⊗ id
n
m
)(ρ
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 ρ
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 (ρ
loc
).
We employ the following natural measurement setup: the unknown quantum channel
T is applied to pure input states |ψ
i
ihψ
i
|. Subsequently, the expectation value of an
observable A
i
on the output is measured. Those expectation values are estimated by means
Accepted in Quantum 2019-07-16, click title to verify. Published under CC-BY 4.0. 3
of a suitably frequent repetition of the prescription choosing the same measurement setting.
Repeating this procedure m times for different input states |ψ
i
ihψ
i
| and observables A
i
results in a measurement vector of the form
y
i
≈ Tr
A
i
T (|ψ
i
ihψ
i
|)
, 1 ≤ i ≤ 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.
1.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 pro-
tocols 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:
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 algo-
rithm 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 reconstruc-
tion methods we also investigate other reconstruction protocols. Their analytical analysis
is also the basis for the recovery guarantees of the CPT-fit.
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).
iii) The third recovery algorithm closely resembles the previous one, but contains trace
preservation as an additional (linear) constraint.
iv) Otherwise similar to algorithm ii), 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. [3]
provides 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.
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 |ψ
i
i and the
Accepted in Quantum 2019-07-16, click title to verify. Published under CC-BY 4.0. 4
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 efficiently using
random quantum circuits [4–7] or fluctuating Hamiltonians [8]. Haar-random vectors have
this property, but recent results on the fourth moments of the Clifford group [9, 10] 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 measure-
ment 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 exper-
imentally implemented in various architectures [11–14]. Finally, we also comment that our
reconstruction protocols can also be applied in the setting of bosonic and fermionic linear
optical circuits.
1.3 Related work
Recent years have seen considerable advance of compressed sensing tools for the tomo-
graphic reconstruction of low-rank quantum states [15–19]. 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 [15]. With the diamond norm minimization (al-
gorithms iv) and v)) we continue a line of research that has been started in Ref. [3] and
support it with rigorous performance guarantees.
The CPT-fit has been suggested in Ref. [17] and numerically compared to full tomog-
raphy and compressed sensing in Ref. [20]. 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. Rigorous recovery guarantees for a similar
conic fitting reconstructions in (i) a low-rank matrix recovery setup and a certain class of
measurements [21] and (ii) a sparse vector recovery setup with certain binary measurements
[22] have been proven recently.
Ref. [15] presents a process tomography protocol that is based on low-rank matrix
reconstruction with random Pauli measurements [23–25]. These low rank recovery guaran-
tees 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 [26]. However, Ref. [15]
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
Accepted in Quantum 2019-07-16, click title to verify. Published under CC-BY 4.0. 5
(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 measure-
ments 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
[18, 27, 28]. Ref. [27] 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. [16] also considered process tomography via compressed sensing tech-
niques. 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 neces-
sary prerequisite for this approach. In turn, techniques from traditional compressed sensing
[29, 30] 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 assump-
tions (sparsity and knowledge of the sparsifying basis) and measurements that may be
challenging to implement in practice.
1.4 Experimental considerations
In several physically important platforms, process tomography has been experimentally
realized [26, 31, 32], both in the direct and hence ancilla-free [31, 32] and ancilla-based [26]
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 6S
1/2
ground state of
133
Cs atoms [33]. 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.
[34]. The same idea of generating Haar random unitaries using suitable time-dependent
Hamiltonians should readily apply to systems of trapped ions [35], 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 [36].
Random unitaries, albeit not Haar distributed, that allow for quantum state tomogra-
phy of quantum many-body systems have been theoretically considered [37], making use
of operations only that can be considered basically feasible in experiments with cold atoms
in optical lattices [38], such as optical super-lattices and time-of-flight measurements.
In integrated linear optical architectures [39, 40], Haar-random circuits are readily
conceivable [41]. 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
Accepted in Quantum 2019-07-16, click title to verify. Published under CC-BY 4.0. 6
M
V
∗
V
W
W
∗
7→
J
M
V
∗
V
W
W
∗
7→
Tr
W
M
V
∗
V
Figure 1: The Choi-Jamiołkowski isomorphism and partial trace in terms of tensor network diagrams
(explained in Figure 8).
Left: Order-4 tensor M ∈ L(L(V) → L(W)) as a map from L(V)
∼
=
V ⊗ V
∗
to L(W)
∼
=
W ⊗ W
∗
.
Middle: Its Choi-matrix J(M) as an operator on W
∗
⊗ V
∼
=
W ⊗ V.
Right: Partial trace Tr
1
[J(M)] of the Choi matrix J(M). This operator corresponds to the functional
ρ 7→ Tr[M(ρ)].
are feasible. This includes settings in which random circuits [6, 42] or randomly time-
fluctuating dynamics [8] can be used to generate approximate unitary designs.
1.5 Notation and terminology
In this section we introduce some basic preliminaries needed to understand our main results.
For any integer n ∈ Z
+
we use the notation [n]
:
= {1, 2, . . . , n}. The space of linear
operators on a vector space V is denoted by L(V).
If V is a Hilbert space, we often denote vectors by |ψ i ∈ V and its adjoints (conjugate
transposes) by hψ |. So the projector onto a normalized |ψ i is |ψ ihψ |. Moreover, the real
vector space of self-adjoint operators is denoted by Herm(V).
1.5.1 Maps on operators
We denote the space of linear maps taking operators to operators by L(C
n
)
:
= L(L(C
n
)).
The Choi-Jamiołkowski isomorphism [43, 44] J : L(C
n
) → L(C
n
⊗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)
J(M)
:
=
dim(V)
X
i,j=1
M(|iihj |) ⊗ |iihj | ,
(2)
where {|ii}
dim(V)
i=1
is an (arbitrary) orthonormal basis of V. Maps M ∈ L(C
n
) can have
different properties: M is called hermiticity preserving if it satisfies M(A
†
) = M(A)
†
for
all operators A ∈ L(C
n
). This is equivalent to demanding that J(M) is Hermitian, i.e.,
J(M) ∈ Herm(L(C
n
)). M is called trace preserving if Tr[M(A)] = Tr[A] for all A ∈ L(C
n
)
or, equivalently, if Tr
1
[J(M)] = 1, where Tr
1
: L(C
n
⊗ C
n
) → L(C
n
) denotes the partial
trace over the fist tensor factor. The affine subspace of hermiticity and trace preserving
maps is denoted by HT(C
n
) ⊂ L(C
n
). The identity map id
k
∈ L(C
k
) is a particularly
simple element of HT(C
n
). Moreover, M ∈ L(C
n
) is completely positive if for all k ≥ 1 one
has that (M ⊗id
k
)(A) is positive semidefinite for every positive semidefinite operator A ∈
L(C
n
⊗C
k
). We will use the shorthand notation A 0 to indicate positive-semidefiniteness
of A. In fact, a map M is completely positive if and only if (M ⊗ id
n
)(A) 0 (k = n).
This in turn is equivalent to J(M) 0.
The convex subset of completely positive and trace preserving (CPT) maps is denoted
by CPT(C
n
) ⊂ L(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.
Accepted in Quantum 2019-07-16, click title to verify. Published under CC-BY 4.0. 7
1.5.2 Norms
For q ∈ [1, ∞[, the `
q
-norm of a vector v ∈ C
n
is
kvk
`
q
:
=
n
X
j=1
|v
j
|
q
1/q
(3)
and the `
∞
-norm is kvk
`
∞
:
= max
j∈[n]
|v
j
|. The Schatten q-norm kAk
q
of an operator A
corresponds to the `
q
-norm of A’s singular values arranged in an n-dimensional vector.
Here, we will specifically encounter the following Schatten norms,
kAk
1
= Tr
√
AA
†
(trace norm), (4)
kAk
2
=
q
Tr[AA
†
] (Frobenius norm), (5)
kAk
∞
= max
|ψ i
kA |ψ ik
`
2
k|ψ ik
`
2
(spectral norm). (6)
Note that rank-one projectors |ψ ihψ | 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 gener-
alized to norms on maps M ∈ L(C
n
). In particular,
kMk
1→1
:
= max
A
kM(A)k
1
kAk
1
. (7)
is the induced trace norm. The diamond norm is a stabilized version of this norm:
kMk
:
= kM ⊗ id
n
k
1→1
. (8)
This is a particularly meaningful and widely appreciated distance measure for quantum
processes [45]. Perhaps surprisingly, it can be calculated efficiently [46–48] as a semidefinite
program. Regarding the reconstruction of structured maps, the diamond norm can serve
as a convex surrogate for low Kraus rank [3]. This is the case for channel reconstruction
and two of the five reconstruction protocols presented in this work build on this idea.
1.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 [49–51] is a probability
distribution µ on the unit sphere that reproduces the moments of the Haar measure up to
order t in both |ψi and hψ|:
E
|ψ i∼µ
(|ψ ihψ |)
⊗t
= E
|ψ i∼Haar
(|ψ ihψ |)
⊗t
. (9)
Similarly, a unitary design [52, 53] is a probability distribution ν on the unitary group
satisfying
E
U∼ν
U
⊗t
XU
†⊗t
= E
U∼Haar
U
⊗t
XU
†⊗t
(10)
for all operators X ∈ L(C
n
)
⊗t
. Typically, designs are considered to be uniform distributions
over finite sets.
Accepted in Quantum 2019-07-16, click title to verify. Published under CC-BY 4.0. 8
T
|ψ i
hψ |
U
U
∗
A
0
Figure 2: The tensorial structure of one measurement setting: T is mapped to Tr
UA
0
U
†
T (|ψ ihψ |)
.
1.5.4 Measurement terminology
In the compressed sensing literature, a single measurement is usually given by an in-
ner product, which is a Hilbert-Schmidt inner product Tr[AT(|ψ ihψ |)] in our case. In
quantum physics terminology, (|ψ i, A) corresponds to a measurement setting, whereas a
corresponding measurement would be the von-Neumann measurement of the observable
A in the state T (|ψ ihψ |) giving rise to an expectation value Tr[AT ( |ψ ihψ |)] 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 Tr[AT ( |ψ ihψ |)].
2 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.
2.1 Measurement model
We consider the task of reconstructing a quantum channel T ∈ CPT(C
n
) from measure-
ment data of the form (1): The unknown channel receives pure states |ψ
i
ihψ
i
| 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 differ-
ent measurement settings (input states and observables). Hence, the entire measurement
process leads to a measurement vector
y = A(T ) + e ∈ R
m
, (11)
with single expectation values
A(T )
i
= Tr[A
i
T (|ψ
i
ihψ
i
|)] + e
i
. (12)
The vector e ∈ R
m
denotes additive noise present in the measurement process. In contrast
to previous approaches [15, 25], no prior assumptions on the nature of this noise corruption
are required.
Throughout this work, we consider instances of random measurements {A
i
, |ψ
i
i}
m
i=1
that are independent instances of a measurement ensemble (A, |ψ i) that meets the follow-
ing requirements:
Definition 1 (4-generic measurement ensemble). We call a measurement ensemble (A, |ψ i)
with observable A and state |ψ i 4-generic if it fulfils the following criteria:
i) The distribution of |ψ i in 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.
Accepted in Quantum 2019-07-16, click title to verify. Published under CC-BY 4.0. 9
ii) A = UA
0
U
†
, where A
0
∈ Herm(C
n
) is fixed and U in 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 trace-
less and normalized in spectral norm, i.e. Tr[A
0
] = 0 and kA
0
k
∞
= 1.
Corresponding expectation values Tr[AT (|ψ ihψ |)] of a quantum channel T ∈ CPT(C
n
)
are referred to as 4-generic measurement and normalized 4-generic measurement, respec-
tively.
This definition encapsulates a variety of process measurement ensembles. In particular,
the generic measurement ensemble (|ψ i and U are Haar random states and unitaries, re-
spectively) 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 suffi-
cient. In fact, it is sufficient when the 4-designs conditions are only fulfilled approximately,
which we discuss and show in Section 3.5.
We also expect that the actual channel recovery works similarly well if |ψ i and U are
chosen from other distributions, provided that they cover the complex unit sphere and
U(n) “evenly” enough (see Section 4 for a further discussion). We confirm this expectation
with numerical simulations with Pauli-type measurements, see Section 2.5.
2.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 A. We put an emphasis on describing the
fitting method T
`
2
referred to as CPT-fit. To complement this approach, we also investigate
the reconstruction methods T
∗
η
and T
∗c
η
as versions of low-rank matrix reconstruction as
well as T
η
and T
c
η
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
T
`
2
:
= arg min{kA(T ) − yk
`
2
: T ∈ CPT(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. [17]. 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 [24, 54–56]. These recon-
structions do not only make use of the data y, but require an a-priori bound η > 0 on the
noise e,
kek
`
2
≤ η . (14)
Applied to the Choi matrix J(T ) of a quantum channel T , the usual trace norm regular-
ization leads to the reconstructions
T
∗
η
:
= arg min{kJ(T )k
1
: T ∈ L(C
n
), kA(T ) − yk
`
2
≤ η}, (15)
T
∗c
η
:
= arg min{kJ(T )k
1
: T ∈ HT(C
n
), kA(T ) − yk
`
2
≤ η}. (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 [57, Chapter 11], [58] and
Accepted in Quantum 2019-07-16, click title to verify. Published under CC-BY 4.0. 10