Low rank matrix recovery from rank one measurements

Introduction

As Balan et al. pointed out in , this apparent obstacle of having nonlinear measurements can be overcome by noting that the measurement process – while quadratic in $x$ – is linear in the outer product $xx^{*}$:

This “lifts” the problem to a matrix space of dimension $n^{2}$, where it becomes linear and can be solved explicitly, provided that the number of measurements $m$ is at least $n^{2}$ . However, there is additional structure present, namely the matrix $X=xx^{*}$ is guaranteed to have rank one. This connects the phase retrieval problem to the young but already extensive field of low-rank matrix recovery. Indeed, it is just a special case of low-rank matrix recovery, where both the signal $X=xx^{*}$ and the measurement matrices $A_{j}=a_{j}a_{j}^{*}$ are constrained to be proportional to rank-one projectors.

It should be noted, however, that such a reduction to a low rank matrix recovery problem is just one possibility to retrieve phases. Other approaches use polarization identities or alternate projections . Yet another recent method is phase retrieval via Wirtinger flow .

2. Low rank matrix recovery

This is a convex optimization problem which can be solved computationally efficiently with various strategies [33, Chapter 15], . We note that several alternatives to nuclear norm minimization may also be applied including iteratively reweighted least squares , iterative hard thresholding , greedy approaches and algorithms specialized to certain measurement maps ${\mathcal{A}}$ , but our analysis is geared towards nuclear norm minimization and does not provide guarantees for these other algorithms.

While unstructured Gaussian measurements provide optimal guarantees, which are comparably easy to derive, many applications demand for more structure in the measurement process. A particular instance is the matrix completion problem , which aims at recovering missing entries of a matrix which is known to be of low rank. Here, the source of randomness is in the selection of the known entries. In contrast to the unstructured measurements, additional incoherence properties of the matrix to be recovered are required and the bounds on the number of measurements are slightly worse , namely $m\geq Crn\log^{2}(n)$. The matrix completion setup generalizes to measurements with respect to an arbitrary operator basis. The incoherence assumption on the matrix to be recovered can be dropped if in turn the operator basis is incoherent, which is the case for the particular example of Pauli measurements arising in quantum tomography . Here, a sufficient and necessary number of measurements scales like $m\geq Crn\log(n)$.

Rank-one measurements, however, in general fail to be sufficiently incoherent for directly applying proof techniques of the same type. For the particular case of phase retrieval (where the matrix of interest is by construction a rank-one projector) this obstacle could be overcome by providing problem specific recovery guarantees that either manifestly rely on (rank one) Gaussian measurements or result in a non-optimal sampling rate .

3. Weighted complex projective designs

The concept of real spherical designs was introduced by Delsarte Goethals and Seidel in a seminal paper and has been studied in algebraic combinatorics and coding theory . Recently, complex projective designs – the natural extension of real spherical designs to the complex unit sphere – have been of considerable interest in quantum information theory .

A simple application of Schur’s Lemma – see e.g. [65, Lemma 1] – reveals that the integral on the right hand side of (5) amounts to

In accordance with , we call a $t$-design proper, if all the weights are equal, i.e., $p_{i}=1/N$ for all $i=1,\ldots,N$.

By introducing weights, it becomes simpler to obtain designs with a number of elements that scales polynomially in the dimension $n$. Some existence results can be found in , where weighted $t$-designs appear under the notion of cubatures of strength $t$. It seems that one can construct weighted $t$-designs by drawing sufficiently many vectors at random and afterwards solving a linear system for the weights. Further note, that generalizations of cubatures to higher dimensional projections were used in in the context of a generalized phase retrieval problem, where the measurements are given as norms of projections onto higher dimensional subspaces.

Main results

Our first main result gives a uniform and stable guarantee for recovering rank-$r$ matrices with $\mathcal{O}(rn)$ rank one measurements that are proportional to projectors onto standard Gaussian random vectors.

Here, $C_{1},C_{2}$ and $C_{3}$ denote universal positive constants. (In particular, for $\eta=0$ one has exact reconstruction.)

For the rank one case $r=1$, Theorem 2 essentialy reproduces the main result in which uses completely different proof techniques. (More precisely, for $X$ of rank $1$ the estimate in loc. cit. is $\|X-X^{\#}\|_{2}\leq\frac{C\|\epsilon\|_{1}}{{m}}$ with high probability.) A variant of the above statement was shown in to hold (in the real case) for a fixed matrix $X$ of rank one. (More precisely, in loc. cit. it is assumed that $X$ is positive semidefinite and the optimization is performed wrt. the function $f$ given by (9) below.) In fact, our proof reorganizes and extends the arguments of [74, Section 8] in such a way, that Theorem 8.1 of loc. cit. is shown to hold even uniformly (that is simultaneously for all $X$) and for arbitrary rank. On the contrary to , we will not need $\varepsilon$-nets to show uniformity.

2. Recovery with 4-designs

Here, $C_{4},C_{5},C_{6}>0$ again denote universal positive constants.

The normalization factor $\sqrt{n(n+1)}$ leads to approximately the same normalization of the $A_{j}$ (wrt. the Frobenius norm) as in expectation in the Gauss case. The theorem is a stable, uniform guarantee for recovering arbitrary Hermitian matrices of rank at most $r$ with high probability using the convex optimization problem (4) and $m=\mathcal{O}\left(nr\log(n)\right)$ measurements drawn independently (according to the design’s weights) from a weighted 4-design. It obviously covers sampling from proper 4-designs as a special case.

Also, Theorem 3 is close to optimal in terms of the design order $t$ required. In the context of the phase retrieval problemi.e., recovering unknown Hermitian matrices of rank one it was shown in [38, Theorem 2], that choosing measurements uniformly from a proper 2-design does not allow for a sub-quadratic sampling rate $m$ without additional structural assumptions on the measurement ensemble. It is presently open whether Theorem 3 also holds for $3$-designs.

Finally, note that the results for Gaussian measurement vectors and 4-designs are remarkably similar. They only differ by a logarithmic factor. This underlines the usefulness of complex projective designs as a general-purpose tool for de-randomization – see e.g. [38, Section 1.1.] for further reading on this topic. Also, Theorem 3 resembles insights in the context of distinguishing quantum states , where it was pointed out that (approximate) $4$-designs “perform almost as good” as uniform measurements (projectors onto random Gaussian vectors). Note that we will generalize Theorem 3 to approximate $4$-designs in Theorem 5 below.

3. Extensions

In this section we state variants of the main theorems which can be proved in a similar way.

Theorem 2 is also valid in the real case, i.e., assuming that the $a_{j}$ are real standard Gaussian distributed and ${\mathcal{H}}_{n}$ is replaced by the space ${\mathcal{S}}_{n}$ of real symmetric $n\times n$-matrices. The proof of the corresponding statement is very similar to the one of Theorem 2 and we sketch the necessary adaptations in Subsection 4.3.

3.2. Recovery of positive semidefinite matrices

The matrix $X$ to be recovered may be known to be positive semidefinite ($X\succcurlyeq 0$) in advance. In this case, one can enforce the reconstructed matrix to be positive semidefinite by considering the optimization program

instead of the nuclear norm minimization program (4). Then analog versions of Theorems 2, 3 and 5 hold. In particular, the error bounds (7), (8) remain valid. In the noisy case $\eta>0$, this does not follow directly from these theorems, since the minimizer of the nuclear norm minimization (4) is not guaranteed to be positive semidefinite in the noisy case. The proof proceeds similarly as the ones for the case $X\in{\mathcal{H}}_{n}$. Instead of the nuclear norm one has to consider (as in ) the function

Applications to quantum state tomography

A particular instance of matrix recovery is the task of reconstructing a finite $n$-dimensional quantum mechanical system which is fully characterized by its density operator $\rho$ – an $n\times n$-dimensional positive semidefinite matrix with trace one. Estimating the density operator of an actual (finite dimensional) quantum system is an important task in quantum physics known as quantum state tomography.

While Theorem 3 is a substantial derandomization of Theorem 2 and therefore interesting from a theoretical point of view, its usefulness hinges on the availability of constructions of exact weighted 4-designs. Unfortunately, such constructions are notoriously difficult to find unless one relies on randomness, for which, however, the resulting designs are not efficient in the sense described in the previous section. One way to circumvent these difficulties is to relax the defining property (5) of a $t$-design. This approach was – up to our knowledge – introduced by A. Ambainis and J. Emerson and resulted in the notion of approximate designs which is by now well established in quantum information science.

We call a weighted set $\left\{p_{i},w_{i}\right\}_{i=1}^{N}$ of normalized vectors an approximate $t$-design of $p$-norm accuracy $\theta_{p}$, if

While accuracy measured in arbitrary Schatten-$p$-norms is conceivable, the ones measured in operator norm ($p=\infty$) and nuclear norm ($p=1$) are the ones most commonly used – at least in quantum information theory. For these two accuracies, the definition in particular assures that every approximate $t$-design is in particular also a $k$-design for any $1\leq k\leq t$ with the same $p$-norm accuracy $\theta_{p}$ . For the sake of being self-contained we provide a proof of this statement in the appendix – see Lemma 16.

A slightly refined analysis reveals that Theorem 3 also holds for sufficiently accurate approximate 4-designs.

Fix $1\leq r\leq n$ arbitrary and let $\left\{p_{i},w_{i}\right\}_{i=1}^{N}$ be an approximate 4-design satisfying

2. Protocols for efficient low rank matrix recovery

Up to now, efficient recovery of low rank density operators by means of the convex optimization problem (4) has been established for random measurements of (generalized) Pauli observables . For this type of measurements, the statistical issues are well understood and Y.K. Liu managed to prove a uniform recovery guarantee which is comparable to the results presented here. Also, this procedure has been tested in experiments .

Theorem 5 is similar in spirit and we show here that it permits efficient low rank quantum state tomography for different types of measurements. Indeed, in the field of quantum information theory, various ways of constructing approximate $t$-designs are known. Most of these methods are inspired by “realistic” quantum mechanical setups (e.g. the circuit model [61, Chapter 4]) and can therefore be – in principle – implemented efficiently in an actual experiment.

Introducing these constructions in full detail would go beyond the scope of this work and we content ourselves with sketching two possible ways of generating approximate 4-design measurements which meet the requirements of Theorem 5. For further clarification on the concepts used here, we refer directly to the stated references.

From now on we shall assume that the dimension $n=2^{d}$ is a power of two ($d$-qubit density operators).

where $C_{7}$ is a sufficiently small absolute constant. The additional rank requirement stems from the fact that the resulting design only has limited accuracy.

(where $C_{8}$ is again a sufficiently small absolute constant) in order to assure that the design’s operator-norm accuracy obeys $\theta_{\infty}\leq 1/(16r^{2})$.

2.2. Approximate unitary designs

One should note that the approximate unitary designs of are not of a finite nature, because the set of all local random unitaries is continuous. Nevertheless, assuming that such local random unitaries are available as “basic building blocks”, local random circuits are efficiently implementable in terms of circuit length. Replacing the atomic expectation values $\sum_{i=1}^{N}p_{i}\left(w_{i}w_{i}\right)^{\otimes t}$ by their continuous counterparts does not change the argument and Theorem 5 remains valid.

It is worthwhile to point out that the two possible applications of Theorem 5 to the problem of low rank quantum state tomography, as presented here, are not yet optimal. The implementation using the Ambainis-Emerson POVM – presented in 3.2.1 – suffers from the drawback that it demands either a very strong criterion on the density operator’s rank – condition (12) – or generating the design in a much larger space and projecting it down. The latter construction is highly unlikely to be optimal and it is furthermore a priori not clear where the corresponding POVM-measurements can be implemented efficiently.

The second approach, on the other hand, suffers from the drawback that carrying out each of the $Crn\log n$ random measurements requires terminating with a very coarse two-outcome POVM measurement. It is very likely that a more fine grained-output statistics could be obtained with comparable effort. The recovery protocol stated here, however, does not allow for advantageously taking into account such refined information about the unknown state.

However, we still feel that mentioning these protocols is worthwhile, as they substantially narrow down the gap between what can be proved (Theorem 5 and the protocols presented in subsection 3.2) and what can be implemented efficiently in an actual quantum state tomography experiment. Next, we provide ideas for further narrowing this gap and finding more protocols that allow for efficient low rank quantum state tomography.

3. Outlook

The construction of approximate $t$-designs in Section 3.2.1 via projections from higher-dimensional designs would be much stronger if an efficient protocol for the corresponding POVM measurements could be provided. We leave this for future work. Alternatively, the authors of mention results by Kuperberg who managed to construct exact $t$-designs containing only ${\mathcal{O}}\left(n^{2t}\right)$ vectors. They furthermore conjecture that their method of efficiently implementing the corresponding POVM measurement also works for Kuperberg’s exact construction. Trying to find such an implementation and combining it with Theorem 3 also does constitute an intriguing follow up-project.

A quick calculation reveals that this orbit forms a normalized tight frame. Unfortunately, the trace-norm accuracy (14) is too weak for a direct application of Theorem 5. However, in [58, Theorem 1] it is shown that the union of all $3$-qubit phase-random circuits forms an exact diagonal-unitary 4-design. Similar to local random circuits, such $3$-qubit phase-random circuits can in principle be implemented efficiently [58, Proposition 3] in an actual quantum mechanical setup. Furthermore, comparing (14) with the accuracy relation $\theta_{\infty}\leq\theta_{1}\leq n^{t}\theta_{\infty}$ – see Lemma 16 in the appendix – suggests that particular orbits of diagonal-unitary designs might possess a much tighter operator-norm accuracy, if the spectrum of their ($t$-fold tensored) average were sufficiently flat. Such a result, combined with Theorem 5, would lead to a tomography procedure that is similar to the one of Section 3.2.2, but uses random 3-qubit phase gates instead of local random circuits.

Proofs

Here, proper convex means that $f$ is convex and attains at least one finite value.

With these notions, the success of the convex program (15) can be estimated as follows.

The crucial point for us is that in the situation that $\Phi$ is a random matrix with i.i.d. rows, the following theorem can be applied to estimate $\lambda_{\min}(\Phi;{\mathcal{D}}(f,x_{0}))$ (see also ).

with $(\varepsilon_{j})$ being a Rademacher sequenceA Rademacher vector $\epsilon=(\epsilon_{j})_{j=1}^{m}$ is a vector of independent Rademacher random variables, taking the values $\pm 1$ with equal probability.. Then for any $\xi>0$ and any $t\geq 0$ with probability at least $1-e^{-2t^{2}}$

We note that the above theorem is stated in to hold with probability $1-e^{-t^{2}/2}$. Inspecting the proof, however, reveals that the probability estimate can actually be improved to $1-e^{-2t^{2}}$.

We will apply the notions in these results in the context of Theorems 2 and 3 as follows:

where the union runs over all $X\in{\mathcal{H}}_{n}\setminus\{0\}$ of rank at most $r$. We further define

A crucial ingredient for Theorems 2 and 3 is the following lemma.

Let $A\in{\mathcal{H}}_{n}$ be a Hermitian $n\times n$-matrix. Then

By duality and the matrix Hölder inequality this statement is equivalent to

The following proof is inspired by [74, Section 8], where similar arguments are used.

It is enough to show that, for any $X\in{\mathcal{H}}_{n}\setminus\{0\}$ of rank at most $r$, we have

where $S_{2}\in{\mathcal{H}}_{n}$ has the property that $S_{2}x_{i}=0$ for all $i\in\{1,\ldots,r\}$ and $\|S_{2}\|_{\infty}\leq 1$. (See for example , where the real analogue is shown.) Consider now

since $\tau=\|{A}_{4}\|_{\infty}\leq\|A\|_{\infty}=\lambda$. ∎

In order to prove both statements of Theorem 2, it is enough by Proposition 7 to show that for $m\geq cnr$ with probability at least $1-e^{-\gamma m}$

for suitable positive constants $c,c_{1},\gamma$. For $\xi>0$ let

where the $\varepsilon_{j}$ form a Rademacher sequence independent of everything else, and introduce

By Theorem 8, for any $\xi>0$ and any $t\geq 0$ with probability at least $1-e^{-2t^{2}},$

Following Tropp’s bowling scheme, we first estimate $Q_{2\xi}$ for a suitable $\xi$. As in , we conclude from the Payley-Zygmund inequality (see e.g. [33, Lemma 7.16]) that

Combining this with (19) and (20), we obtain

Thus we choose $\xi=\frac{1}{2\sqrt{2}}$.

In order to estimate $W_{m}$, we use Lemma 10 to obtain

In , a uniform result for phase retrieval in the Gaussian case is proved using an inexact dual certificate. One can write down a generalization of this dual certificate for the rank $r$-case, but following the arguments of loc. cit., the resulting number of required measurements then seems to depend significantly worse than linearly on $r$. It might be possible to rather adapt the arguments in based on a different construction of a dual certificate in order to derive linear scaling of $m$ in $r$, but the resulting proof would be more complicated than ours (and likely lead to more logarithmic factors).

2. Proof of Theorem 3

Let us now turn to proving the analogous result for complex projective 4-designs. It is convenient to rescale the (normalized) 4-design vectors as

Assume that $a$ is drawn at random from a super-normalized weighted $4$-design. Then

The desired statement follows, if we can show that

The remaining right hand sides are standard expressions in multilinear algebra and can for instance be calculated using wiring calculus. Indeed, Lemma 17 in the appendix implies that

Let $H$ be the matrix defined in (18), where the $a_{j}$’s are chosen independently at random from a super-normalized weighted 1-design. Then it holds that

Since the $\epsilon_{j}$’s in the definition of $H$ form a Rademacher sequence, the non-commutative Khintchine inequality [75, p. 19], see also [33, Exercise 8.6(d)], is applicable and yields

where we once more have taken into account super-normalization and used the 1-design property. Theorem 15 together with the assumption $m\geq 2n\log n$ implies that, for any $\tau>0$,

The choice $\tau=1.27$ approximately minimizes the above expression and yields

Combining this estimate with (27) yields the desired statement with $c_{4}=2^{3/4}\sqrt{c_{5}}=3.1049$. ∎

Now we are ready to prove the second main theorem of this work.

3. Proof of Theorem 2 for real Gaussian vectors

4. Proof for recovery of positive semidefinite matrices

The only part in the proof of the recovery result for positive semidefinite matrices stated in Section 2.3.2 that slightly differs from the one for arbitrary Hermitian matrices, is the proof of a corresponding version of Lemma 10. The subdifferential of the function $f$ introduced in (9) slightly differs from the subdifferential of the nuclear norm. For $X=\sum_{i=1}^{r}\lambda_{i}x_{i}x_{i}^{*}$, where all $\lambda_{i}$ are nonzero, $\partial f(X)$ consists of all matrices of the form

where $S_{2}\in{\mathcal{H}}_{n}$ has the property that $S_{2}x_{i}=0$ for all $i\in\{1,\ldots,r\}$ and all eigenvalues of $S_{2}$ do not exceed $1$. Hence we choose (in the notation of the proof of Lemma 10)

Then the remainder of the proof of Lemma 10 is the same.

5. Proof of Theorem 5

The proof of this generalized statement proceeds along the same lines as the one of Theorem 3. However, Propositions 12 and 13 – as well as their respective proofs – have to be slightly altered due to the weaker requirements imposed by Theorem 5.

Under the assumptions of Theorem 5, a weaker version of (23), namely

yields the same lower bound (32) due to $\|Z^{\otimes 2}\|_{\infty}=\|Z\|_{\infty}^{2}\leq\|Z\|_{2}^{2}=1$ (where the last equality follows from $Z\in E_{r}$). Applying Lemma 17 then yields

which is the (slightly weaker) analogue of (25). Likewise we derive a fourth moment bound:

compare the proof of Proposition 12. Having these bounds at hand, allows for applying the Payley Zygmund inequality to obtain

5.2. Generalized version of Proposition 13

The assumptions in Theorem 5 assure that (26) is still valid, possibly with a larger absolute constant $c_{4}$. Again, the proof of this generalized statement is very similar to the proof of Proposition 13. Indeed, only the bound (29) for the matrix Chernoff inequality needs to be slightly altered. The assumption (11) implies that

Consequently, applying the matrix Chernoff inequality yields (26) with a slightly larger absolute constant $c_{4}$.

Appendix

Recall from Section 1.2 that for $1\leq p<\infty$ , the Schatten-$p$-norm on ${\mathcal{H}}_{n}$ is defined as

where $\lambda_{1},\ldots,\lambda_{n}$ denote the $n$ eigenvalues of $Z\in{\mathcal{H}}_{n}$. For $p=\infty$ one defines similarly

i.e., $\|Z\|_{\infty}$ is the spectral norm of $Z$. The Frobenius norm $\|\cdot\|_{F}=\|\cdot\|_{2}$ is induced by the the Hilbert-Schmitt (or Frobenius) scalar product

which makes ${\mathcal{H}}_{n}$ a Hilbert space. The Schatten-$p$ norms are non-increasing in $p$, i.e. for any $0<p\leq p^{\prime}\leq\infty$

holds for all $Z\in{\mathcal{H}}_{n}$. The following relations provide converse inequalities for particular instances of Schatten $p$-norms that are used frequently in our work:

In addition, we often use a particular instance of the matrix Hölder inequality, namely

2. Matrix Chernoff inequality

The matrix version of the classical Chernoff inequality for the expection of a sum of independent random matrices shown in [73, Theorem 5.1.1] (see also ) reads as follows.

Let $X_{1},\ldots,X_{m}$ be a sequence of independent random positive definite matrices in ${\mathcal{H}}_{n}$ satisfying

3. Multilinear algebra

We briefly repeat some standard concepts in multilinear algebra which are convenient for our proof of Proposition 12. They can be found in any textbook on multilinear algebra – e.g. – but we nonetheless include them here for the sake of being self-contained.

and we call the elementary elements $z_{1}\otimes\cdots\otimes z_{k}$ the tensor product of the vectors $z_{1},\ldots,z_{k}\in V$.

With this notation, the space of linear maps $V\to V$ ($n\times n$-matrices) corresponds to the tensor product ${\mathcal{M}}_{n}:=V\otimes V^{*}$ which is spanned by $\left\{x\otimes y^{*}:\;x,y\in V\right\}$ – the set of all rank-1 matrices. Using this tensor product description of ${\mathcal{M}}_{n}$ allows for defining the (matrix) tensor product ${\mathcal{M}}_{n}^{\otimes k}$ in complete analogy to above. We refer to its elements $Z_{1}\otimes\cdots\otimes Z_{k}$ as the tensor product of the matrices $Z_{1},\ldots,Z_{k}\in{\mathcal{M}}_{n}$.

On this tensor space, we define the partial trace (over the $i$-th tensor system) to be the natural contraction

The partial trace over multiple systems can then be obtained by concatenating individual traces of this form, e.g.

This implies that the nuclear norm is multiplicative with respect to the tensor structure, i.e.,

for $Z_{1},\ldots,Z_{k}\in{\mathcal{M}}$ arbitrary. A singular value decomposition – see e.g. [77, Lecture 2] – reveals that the same is true for the operator norm, i.e.

Using these basic concepts of multilinear algebra and (6), we can show that every approximate $t$-design is also an approximate design of lower order.

Every approximate $t$-design of accuracy measured either in operator- or trace-norm is also an approximate $k$-design of the same accuracy for any $1\leq k\leq t$. Furthermore the accuracies $\theta_{\infty}$ and $\theta_{1}$ are related via

This statement is implicitly proved in , where the authors use an equivalent definition of approximate $t$-designs as averaging sets of complex polynomials of degree at most $(t,t)$. With this alternative definition, Lemma 16 follows naturally from the fact that every polynomial of degree at most $(k,k)$ with $1\leq k\leq t$ is a particular instance of a degree-$(t,t)$-polynomial. Here we provide an alternative proof that uses concepts from multilinear algebra and accesses Definition 4 directly. Such a proof idea is mentioned in [54, Section 2.2.3] and we include the full argument here for the sake of being self-contained.

Let us start with proving the statement for the accuracy measured in operator norm. In this case, Definition 4 is equivalent to demanding

The desired statement follows if we can show that (43) implies a corresponding inequality for smaller tensor powers $k$. Fix $1\leq k\leq t$ and note that the inequality chain (43) is preserved under taking arbitrary partial traces, because partial traces respect the positive semidefinite ordering. This in particular implies that

Finally, inequality (42) directly follows from comparing trace and operator norm on ${\mathcal{M}}_{n}^{\otimes t}$ which is isomorphic to the space of all $n^{t}\times n^{t}$-dimensional matrices.

4. Wiring calculus in multilinear algebra

The defining properties (5), (10) of exact and approximate complex projective $t$-designs are phrased in terms of tensor spaces. For calculations in multilinear algebra – particularly if they involve (partial) traces– wiring diagrams [49, Chapter 2.11] are very useful, as they provide a way of computing contractions of tensors pictorially. Here we give a brief introduction that should suffice for our calculations and defer the interested reader to and references therein for further reading.

In wiring calculus matrix multiplication is therefore represented by

Tensor products of matrices are arranged in parallel, i.e.,

just corresponds to contracting parallel matrix indices and therefore

But for higher tensor systems more permutations can occur. In wiring calculus, permutations therefore act by interchanging different input and output lines.

We are now ready to prove the statements required in Proposition 12.

For an abritrary Hermitian matrix $Z\in\mathcal{H}_{n}$ and a positive integer $m$, it holds

We start with the case $m=2$ and then extend the argument to the general case.

and its pictorial counterpart is therefore

Applying the graphical calculus introduced above then yields

which is the desired statement for $m=2$.

Acknowledgements

RK is glad to acknowledge inspiring discussions with D. Gross and helpful comments from J. Aaberg.

The work of RK is supported by scholarship funds from the State Graduate Funding Program of Baden-Württemberg, the Excellence Initiative of the German Federal and State Governments (Grant ZUK 43), the ARO under contracts, W911NF-14-1-0098 and W911NF-14-1-0133 (Quantum Characterization, Verification, and Validation), the Freiburg Research Innovation Fund, and the DFG. HR and UT acknowledge funding by the European Research Council through the Starting Grant StG 258926 (SPALORA). RK and HR would like to thank the Mathematisches Forschungsinstitut Oberwolfach and the organizers of the Oberwolfach workshop Mathematical Physics meets Sparse Recovery (April 2014, Workshop ID: 1416a), where discussions on the topic of this article have started.

References