# Quantum tomography under prior information

Last week, I was at Texas A&M for David Larson’s 70th birthday conferenceBernhard Bodmann was also there, and we talked a little about phase retrieval.  He pointed me to this fantastic paper:

Quantum tomography under prior information

Teiko Heinosaari, Luca Mazzarella, Michael M. Wolf

It’s all about determining a positive semidefinite matrix $A$ from measurements of the form $\mathrm{Tr}[AS_n]$, where $S_n$ is a positive semidefinite matrix corresponding to some physical measurement process.   In the quantum setting, $A$ is called a mixed state, and its trace is $1$.  If a given collection of $S_n$‘s sum to the identity matrix, then the ensemble is known as a positive operator-valued measure (POVM); frame theorists might identify this as a Parseval “generalized” frame.  Furthermore, if $A$ and $S_n$ both have rank $1$, then we have the decompositions $A=xx^*$ and $S_n=f_nf_n^*$, and so the corresponding measurement has the form

$\mathrm{Tr}[AS_n]=\mathrm{Tr}[xx^*f_nf_n^*]=\mathrm{Tr}[f_n^*xx^*f_n^*]=|\langle x,f_n\rangle|^2.$

In this case, the rank-$1$ mixed state $A=xx^*$ is called as a pure state, and the unit-trace condition equivalently means $\|x\|^2=1$; recall that pure states were the subject of my previous post.  As such, mixed states form a natural generalization of pure states, and the trace-based measurement process corresponds nicely.

The main point of the paper is to find necessary and sufficient conditions for an ensemble of $S_n$’s to be informationally complete (IC) with respect to pure states.  For the reader’s sake, IC is just physics-speak for injective; $\{S_n\}$ is IC with respect to pure states if the measurements $\{\mathrm{Tr}[xx^*S_n]\}$ completely determine the pure state $xx^*$ (or $x$ up to a global phase factor).  As such, the results of this paper would be immediately applicable to the phase retrieval problem if it weren’t for two main differences:  the unknown mixed state necessarily has unit trace, and the $S_n$’s don’t necessarily have rank $1$.  But there are still implications for phase retrieval, and I detail some of them below.

The paper has two main sections (Sections 3 and 4).  Section 3 gives sufficient conditions for IC, while Section 4 gives necessary conditions.  As far as sufficient conditions are concerned, the authors start by using a construction from Cubitt, Montanaro and Winter to demonstrate that rank-$r$ mixed states can be distinguished with only $4r(d-r)-1$ measurements.  This corresponds nicely to a compressed sensing result of Gross, Liu, Flammia, Becker and Eisert, which gives a reconstruction procedure based on only $\mathcal{O}(rd\log^2d)$ measurements, meaning a mere log penalty is paid to achieve efficiency and stability in reconstruction.  Later, the authors completely characterize POVMs which are IC with respect to $2$– and $3$-dimensional pure states, although the characterization doesn’t appear to admit a useful generalization to larger dimensions.  Next, the authors use constructions from James and Milgram to produce ensembles of self adjoint matrices which are IC with respect to pure states.  In particular, the construction of Milgram manages to distinguish $d$-dimensional pure states with less than $4d-\alpha(d-1)$ measurements, where $\alpha(d-1)$ is the number of $1$’s in the binary representation of $d-1$.  The authors conclude the section by leveraging Minkowski dimension to show that almost every ensemble of $4d-3$ self adjoint matrices is IC with respect to $d$-dimensional pure states.

Unfortunately, the constructions in Section 3 are not immediately applicable to the phase retrieval problem, as the measurement matrices $S_n$ do not have rank $1$.  In fact, even the Minkowski-dimension-based argument fails to say anything about phase retrieval, as rank-$1$ matrices form a measure-zero subset of the set of self adjoint matrices; by comparison, Balan, Casazza and Edidin used an algebro-geometric approach to show that almost every ensemble of $4d-2$ vectors produce injective phaseless measurements.

Section 4, however, is immediately applicable to the phase retrieval problem.  In this section, the authors view the mapping $xx^*\mapsto\{\mathrm{Tr}[xx^*S_n]\}$ from the standpoint of topology.  First, they show that pure-state-IC measurements form a topological embedding of the set of pure states into euclidean space; this is proved using the facts that the mapping is linear and the set of pure states is compact.  However, this homeomorphic structure doesn’t appear to be strong enough to impose substantial necessary conditions for injectivity (see their Corollaries 2 and 3).  By contrast, diffeomorphic structure appears to be particularly telling.  The authors show that pure-state-IC measurements necessarily form a smooth embedding of the set of pure states into euclidean space, and then they use a well-known result about embedding complex projective space to conclude that $4d-2\alpha(d-1)-4$ measurements are necessary for injectivity.

Since injective phaseless measurements are necessarily IC with respect to pure states, this means that $4d-2\alpha(d-1)-4$ measurements are, in fact, necessary.  I alluded to this fact in a previous post, but now we have a paper we can actually cite.  Unbeknownst to the authors, this result actually disproves a conjecture of Ron Wright from 1978 (found in this paper).  The conjecture states that $d$-dimensional pure states are completely determined by their distributions with respect to three observables, implying that $3d$ measurements suffice to be pure-state-IC.  Interestingly, the main result they used about embedding complex projective space was first proved by Atiyah and Hirzebruch in 1959, almost 20 years before Ron Wright first posed his conjecture.

It remains to be determined how many phaseless measurements are necessary for injectivity.  Finkelstein’s work led some to believe that $3d-2$ was the minimum number, and now this paper shows that $4d-o(d)$ measurements are actually required.  In fact, we know that similar topological arguments cannot substantially improve this bound since they must also apply to $S_n$’s of arbitrary rank, with which $4d-\alpha(d-1)$ measurements suffice.  As such, an improvement to this lower bound must somehow account for how rank-$1$ measurements differ from general measurements.