In this paper Sedrakyan and Chubukov have finally resolved the long-standing issue about the origin of the pseudogap in cuprates. This study throws light on a mystery of High-Tc superconductivity.

Figures 3 and 4 are...interesting?

To clarify in response to the above comment, our main result is that quantum theory cannot be *extended*. We consider an extension to a theory to be one that contains the original.

I'm not sure that it's fair to say that this is is an extension of Bell's result in the general case because the main theorem relies on the formalism of quantum theory (i.e. it is assumed that quantum states are represented as pure states in a Hilbert space, and that the state interacts with the measuring device via a completely positive map). Whereas Bell's theorem is just about the correlations of measurement outcomes. So I don't see that this addresses whether there could be a more complete theory which describes the results of quantum theory. Although indeed as the authors point out, in the case of many bipartite measurements on a singlet, there is no extension, since in this limit we have privacy for all no-signalling theories i.e. any eavesdropper (a.k.a. hidden variable) would have to be completely independent of Alice and Bob's measurement results.

I am not quite realizing, if it is necessary to make some comments, because most arguments already have been raised by few different people (some replies: quant-ph/0703244).

Alexander Yu. Vlasov

Hi,

First thing: it's a very interesting and beautiful result.

Unfortunately, I didn't fully understand the soundness proof given at the end of page 8. If someone is interested in explaining the proof or talking about it, please leave a comment, and I'll contact you. If you just want to give it a shot, you're welcome to call me via skype. My user name is or_sattath.

Cheers,
Or Sattath

Dear Dan,

Thank you for the nice resource paper on various mass profiles. Last year Chris Fluke and I published a paper exploring the effect of NFW, Sersic and also SIS profiles on gravitational lensing which may be of interest for your review. Our work extended previous results by also looking at the effect of these profiles on the flexion distribution (higher order weak lensing terms). We studied in detail the effect of the mass profile on observations, including the concentration factor in the NFW profile as well as the Sersic shape parameter.

The reference is Lasky, P. and Fluke, C. "Shape, shear and flexion: an analytic flexion formalism for realistic mass profiles" 2009 MNRAS 396, 2257 (arXiv:0904.1440).

Best regards,
Paul Lasky

Nice results! It is not your goal but it'd be important to know how well it behaves on social networks.

I think, Phys. Rev. A 63, 054302 (arXiv:quant-ph/0010071)
may be interesting ...

Dear Dan,

Your two new paper on Astroph look very nice and I wish a recent paper of us be of interest to you.

We published in ApJ a paper entitled "Accurate universal models for the mass accretion histories and concentrations of dark matter halos" (2009, ApJ, 707, 354, i.e., arXiv:0811.0828). In this paper, we disentangled and modeled the dependences of halo mass accretion rate (MAR) on all relevant factors and connected halo interior mass concentrations with their mass accretion histories (MAHs) in a simple way. These models can be used to predict the MAHs, the mass & redshift dependence of concentrations and the individual concentration evolution histories of dark matter halos, which significantly DISAGREE with the much-used empirical models in the literature. These models are simple, accurate and universal.

We hope it's of interest to you and any comment or suggestion from you will be appreciated much. Thanks a lot.


Best regards,
Donghai Zhao

MOdern scientific simulated article,may be used to optoelectronics devices.

This is very interesting and beautiful. One comment which I mentioned to the authors, it seems like it might be possible to "mark" this money. If the money passes through your hands (someone gives it to you in exchange for goods and you then use to to purchase goods from someone else), you can measure some other knot invariant, other than the Alexander polynomial, and then use the knowledge of that invariant later to demonstrate that you had indeed had access to the money.

Interested readers can find a bit more background here.

Thanks for the feedback. I'll be sure to tweak the intro as you suggest before it reaches publication anywhere. Feel free to email me if you have any more questions or comments. We certainly welcome the feedback.

Thanks, Joseph! This is very helpful!

Perhaps to prevent confusion in the future, you might want to add "k >= 2" to the sentence:
"More precisely, we show that for any number k of provers, QMIP[k] = MIP*[k]"
(since you do not show it for k=1)

Also, note that Theorem 1 starts with "If there exists...", and that in order to get the statement above, one probably needs to combine Theorem 1 with Theorem 2 (and perhaps some other stuff).

Regarding notation, it's purely a matter of taste, but I personally find it more logical to have the "Q" indicate quantum communication, and the "*" indicate entanglement (in analogy to MIP^*).

As regards the results we obtain, they are explicitly in the statement of Theorem 1, though I take your point that we should have echoed this in the abstract/introduction/conclusions. We obtain QMIP(k,m,c,s) contained within MIP(k,m',c,s'), where s'=max(s,2^-d) (with d being a security parameter) and m'=m*poly(n,d) where n is the problem size. The polynomial here is linear in the circuit dimensions (and so at least linear in n).

Hi Oded,



The reason that we require at least two provers is that we use the two entangled provers to implement quantum computation "blindly", meaning that they execute a quantum computation without learning anything other than an upper bound on the circuit dimensions. It is still an open question whether this can be done with a single prover, but it seems very unlikely to me and would imply BQP = IP_BQP (which is still open). Thus we can manage any number of provers greater than 1, but the case of QIP is not covered. In fact I believe we mention that whether or not this approach can work for QIP is an open problem.



As regards notation, there seems to be a lot of differing notation for the class we refer to as QMIP, and we simply went with the notation on the complexity zoo (where QMIP potentially has unbounded entanglement). That said, I am aware of at least 2 other forms of notation appearing in the literature.



As regards the number of rounds, our current proof does indeed increase the number of rounds polynomially in the size of the verifiers circuits. While I believe it may be possible to get around this, I don't yet have an explicit proof that it is possible. Even this, however, is unlikely to work in the extreme case of one-round games.

I'm curious, how do the authors use the fact that the number of provers is k>=2? Otherwise one would get (for the special case of k=1 prover) an alternative proof of QIP=IP, which would be pretty amazing.

Also, I think it should be emphasized that QMIP is the class with entanglement (I prefer the name QMIP^*); QMIP has been used before to denote the class without entanglement. Finally, the proof seems to significantly increase the number of rounds, so apparently these results do not apply to one-round games? (I wish they included a clear and precise statement of the transformation they obtain...)

it's fully of advantage

Thanks, Jonas. Good to know. Thanks very much for answering this question.

However, do you know the answer to a related question: does there exist a complete, orthonormal basis such that both the operators x and \partial_x are close (in operator norm) to diagonal in this basis? I think that this is really the basis that one wants (and the negative result for the finite dimensional case I mention is with respect to this question). This is a stronger requirement than just having bounded variance.

Thanks,
Matt

I don't know the details of what von Neumann was doing, but such bases do exist. I found a paper by Bourgain in which this was proved. (I only did so after Steve Flammia asked the question on Math Overflow.)



The paper:

Bourgain, J. A remark on the uncertainty principle for Hilbertian basis. J. Funct. Anal. 79 (1988), no. 1, 136--143

http://www.ams.org/mathscinet-getitem?mr=950087



Math Overflow link:

http://mathoverflow.net/questions/17938/simultaneous-time-frequency-concentration-of-orthonormal-sequences/17942#17942

I may be misunderstanding this paper, or may be confused about one theorem, but I think one of the claims is wrong. On the top of page 4, he states that there exists a complete orthonormal system (presumably he means a complete orthonormal basis for square-integrable functions) consisting of functions which have bounded variance and whose Fourier transforms also have bounded variance. However, I think that no such basis exists. A few cases I know of:



1)If the orthonormal basis is a Gabor basis (all functions in the basis are obtained by translates in time or frequency of a certain elementary function), then the Balian-Low theorem says that this is impossible. I think that there is a generalization of Balian-Low to arbitrary basis.



2)[This part of remark removed because I realized I misstated the result]


3)Finally, the finite dimensional case, I do know. If we have a finite dimensional Hilbert space and define the "shift" and "clock" operators as unitary matrices (shift is 1 above the main diagonal, clock is \exp(i 2pi k/N) along the main diagonal), then these matrices are discrete analogues of position and momentum and there is no way, as N gets large, to find a basis in which both operators are close to diagonal (close meaning distance from a diagonal matrix goes to zero as N gets large). This is a known result in the theory of almost commuting matrices.



Maybe I misunderstand the claim in this paper? Or maybe I am mistaken and there indeed is no version of Balian-Low for arbitrary bases?

Another brief overview provided here.

I wrote up a brief overview here.

Rezn,

If, as you say, this paper is laughable, it should not take much of your time to point to some obvious flaw. Are you asking us lesser intellects to simply accept your word that this is so -- without your saying why, or who you are?

Kris,

If you don't see what is wrong with this paper then I don't want to argue with you, this would be a waste of my time.

Rezn,

I don't see anything wrong with this paper. Can you show there is? It's easy to post denigrating comments with no substance, while hiding behind anonymity. Do you think that contributes to scientific discourse?

The claims in this paper are wrong. An epsilon-randomizing map requires >=(1-eps)*d unitaries to work even for a single input, since anything within trace distance epsilon of the maximally mixed state has to have rank at least (1-eps)*d.

This is the most entertaining and laughable paper I've read in many years ! Unfortunately for the author, I'm afraid that was not the purpose...

I'm uncomfortable saying that we've got something equivalent to a 2D lattice with polylog(L) range interactions. I think that the only way to resolve this is for us to work out an example together via skype or whatever.

Thanks for the detailed reply Ari. As I say, I really think this is great if it works. Regarding the correlation decay theorems, for any Hamiltonian H, and any operators A and B, we need to know 4 things to bound the correlation function of A and B. For definiteness, let me assume that the Hamiltonian acts on qubits on a two-dimensional lattice; I understand that you say that the lattice changes, but in fact this should just mean that the interactions change with L: as L increases, we increase the range of interactions beyond nearest neighbor.

We write the Hamiltonian H as a sum of term of sets of diameter at most R, where R is the interaction range. We need to know:
1)How does R depends on L. I believe that you are saying that R can scale as polylog(L). That is, the interactions can be embedded in this two-dimensional lattice with a range that is a polylog of L.

2)A bound, J, on the norm of these terms in the Hamiltonian. I believe that this is O(1) for your system.

3)The support of A and B. I believe that they both include at most polylog(L) sites, and that they are a distance L away from each other.

4)The spectral gap. The claim is that this is bounded below by an L-independent constant.

Given (1) and (2), we can bound the Lieb-Robinson velocity by polylog(L). Then, we can bound the correlation of A and B by ||A|| ||B|| polylog(L) exp(-L/polylog(L)), which goes to zero for large L.

So, one of those 4 claims I made about the Hamiltonian above is inconsistent with having correlation between the spins. I'd be very interested to see where I misunderstood your construction. Perhaps you require longer range interactions? If you prefer to talk over email, let me know.

If you prefer to discuss over email

I've never used Scirate before, and my experience is that it's very hard to communicate physics clearly via short text messages. But, I'm going to give it one try, and I'm happy to talk to interested folks in person or on the phone. (By the way, thanks for the comments and criticisms Matt and the mysterious anonymous RS. I welcome more comments from everybody, and even if I don't manage to respond on Scirate, I'll certainly take them into account as I try to improve the paper.)

1) On error detection/correction in GSQC:

The appendix of the paper describes a direct recipe for mapping any gate model circuit to a GSQC Hamiltonian and ground state. It discusses single qubit gates and two qubit gates. The recipe requires no creativity; you give me the circuit, I write down the Hamiltonian and ground state immediately.

There are two subtleties.

a) For fixed-gap GSQC, one should be sure that the gate model circuit includes a teleportation step after each gate. Just pretend that your gate model circuit is paranoid about leakage or something like that.

b) A subtlety arises whenever the gate model circuit includes measurements. The gate model measurement is mapped into a GSQC projection Hamiltonian; rather than simulating a measurement, GSQC performs a projection. The Bell measurement associated with teleportation becomes a Bell-state projection as described in the main text. Single qubit measurements become single qubit projections (as described in the error correction part of the appendix).

That's it. If you give me any gate model circuit, I just apply the recipe to turn it into a GSQC Hamiltonian and ground state.

The paper maintains that any GSQC Hamiltonian constructed using the recipe will have a gap that depends upon the value of Lambda in the projection Hamiltonians but not upon the number of qubits or number of gates. In order to maintain a finite gap, one needs a finite Lambda. But a finite Lambda leads to imperfect projections, and the GSQC ground state ends up simulating a _faulty_ gate model calculation.

This is when error correction comes in. To address these faulty gates, we can apply our regular GSQC recipe to translate a gate model circuit that _includes_ error correction. Including error correction won't effect the gap if we use the same Lambda, but now the errors in the ground state get cleaned up by the error correction in the circuit.

Perhaps the phrase "a GSQC version of quantum error detecting codes" was misleading. The phrase "GSQC version" was just meant to emphasize that no active measuring and pulsing is going on like in gate model error detection/correction. All we are doing is translating into GSQC, using the usual recipe, a gate model circuit that includes error detection/correction.

As an aside, it turns out that you can just use error detection rather than error correction in GSQC, as mentioned in the paper, but this is just an aside. If you'd prefer to use error correction, go ahead, but I suspect that you'll get a lower threshold. Pick your favorite code, from the surface code to the Steane code, use all the associated gate model fault tolerant circuits and simply translate them to GSQC using the recipe.

2) On correlations:

I believe that GSQC requires local operators alone whenever gate model error correction can be done with local gates alone (which is usually the case. See, for instance, D. Gottesman, "Fault-Tolerant Quantum Computation with Local Gates," J. Modern Optics 47, 333-345 (2000).) After all, we just translate our gate model circuit into GSQC using our recipe. Let me suggest the following resolution to your question, Matt, and please tell me if it sounds right to you.

To perform quantum error correction, you must encode quantum information into logical qubits. Under the encoding, the quantum information that used to be stored in physical operators is stored instead in logical operators that involve poly(log(L)) physical operators. This is true in the gate model, and therefore it's also true in GSQC.

Is there is any theorem limiting the correlations between a collection of poly(log(L)) physical operators near site 1 and a collection of poly(log(L)) physical operators near site L in the presence of local interactions between the physical operators? Before you answer, note that we use more levels of concatenated error correction as the number of steps L in the gate model calculation increases. Since the interactions in the "lattice" of GSQC qubits is determined by the gate model circuit, and the gate model circuit depends on L, the lattice changes with L. Bounding such correlations between logical operators as a function of L seems very tricky given that the number of physical operators in the logical operators, the definition of the logical operators in terms of the physical operators, and the lattice of interactions (which is determined by the gate model circuit) between logical operators all depend on L. The theorems in Hastings and Koma, Commun. Math. Phys. 265, 781 - 804 (2006), for instance, don't seem to apply to this case.

Does this sound reasonable?

Indeed, as I think about it more, I would really like to see the error correction explained better. The example I gave above shows that, if in fact it is possible to implement an arbitrary circuit with a size-independent gap, this can only be done using non-local interactions in the Hamiltonian. Again, I think this is really great if it works.

I find this paper hard to follow. In particular, I don't see how to "apply a GSQC version of quantum error detecting codes" without making the gap dependent on the size. I hope there's a better version coming soon....

This is really an amazing advance if it works. I still do not quite understand it yet, though, so I am not sure of all the details.



In particular, I don't quite understand the following: suppose I imagine my qubits arranged in, for example, 2-dimensional space on a square lattice, for example, with coordinates (x,y). Let q_i denote a qubit with coordinates (i,1). Let the first round of the quantum circuit put q_1 and q_2 in a singlet state. Then, the next round of the quantum circuit swaps qubits q_2 and q_3, so that after that round, q_1 and q_3 are in a singlet, and all others are in the |0> state. The round after that swaps q_3 and q_4, and so on. So, after L-1 rounds, q_0 and q_{L-1} are in a singlet state. So, now we translate this quantum circuit into a GSQC. Quantum error correction can be done in the gate model using local measurements and gates in two dimensions...and I think it can be done using local classical control. If this is true, that we can do all the quantum error correction using local measurements, gates, and control, then we should maybe expect that the GSQC would have local interactions. However, given local interactions and a spectral gap, we cannot have long-range correlations between two far separated qubits (q_1 and q_{L-1} in the case above). So, perhaps it is not possible to implement the quantum error correction using local gates in this GSQC model. Indeed, even if we have interactions up to a range which is L^{\alpha} for some \alpha less than unity, the same bound on correlations holds (the exact power alpha depends upon the cardinality of the support of interactions)

Cedric (cbeny above) and his co-author Ogden have indeed made impressive progress since my paper was posted by obtaining dimension-independent worst-case bounds.

Perhap's Cedric's choice of words "contrary to Jon's..." is a bit confusing. "In improvement over Jon's previously-existing arXiv post" would perhaps be more apt, although I also constructed bounds on min-entropy and state distinction and I predated him by only about 10 days.

Indeed, some months ago I updated my arXiv post to cite the subsequent worst-case bounds of both Cedric and nghk's (Hui) papers, so I see nothing significantly "contrary" in my papers.

Since it wasn't cited yet in this work, let me mention also my paper

http://arxiv.org/abs/0907.5391

Contrary to Jon's, we consider a worst-case fidelity, and contrary to Hui's, we provide dimension-independent upper and lower bounds on the optimal worst-case (entanglement) fidelity.

In addition our work is more general as it pertains to the simulation of any channel (not just the identity channel on the code). In particular this means that our bounds also work for subsystem codes.

The authors are simply mistaken in their above assertion on Scirate that the transpose channel is identical to the quadratic recovery channel in the case that P is a projection operator.

Consider the case of of the partially depolarizing channel on C^n given by

A_p(mu) = p x tr(mu) I/n + (1-p) mu,

where p is a probability, and let the projection operator be P=I, which corresponds to the maximally-mixed state rho times an irrelevant factor which disappears in the formulas for the quadratic recovery operator and for the transpose channel.

Note that the transpose channel of A_p with P=I or rho is just A_p, while the optimal reversal under just about any notion of optimality is the identity channel A_0.

For comparison, the quadratic recovery operation I defined in 0907.3386 for the map A_p and P=I is given by

R = A_f(p,n),

where f(p,n)= p^2 / (n^2(1-p)^2 + (2-p)p) is less that p for all n and p. As n->infinity it becomes dramatically less!

In particular, the quadratic recovery map is a significant
improvement over the transpose channel in the case of partially depolarizing channels with the projector P=I.

This is not at all surprising, since Barnum and Knill wrote down their reversal map (which in the case of maximally mixed states is the Transpose channel) by generalizing the pretty good measurement. As I argued using a theorem of Belavkin in my PRA article

http://arxiv.org/abs/0907.1884

the PGM tends to relatively overweight the improbable states in comparison to Holevo's measurement introduced in his 1978 paper "On asymptotically optimal hypothesis testing in quantum statistics". Note that the final section of Holevo's paper dealing with unequal probabilities was overlooked by many authors, and indeed it has some algebra mistakes. Holevo's pure-state measurement looks a lot like the PGM, except that the probabilities from the formula for the PGM are REPLACED BY THEIR SQUARES.

There is much confusion about the difference between Holevo's measurement of 1978 and the PGM. Part of the confusion is because when the states to be distinguished are all pure states with EQUAL probabilities then Holevo's measurement and the PGM are identical.

Barnum and Knill incorrectly cite Holevo's 1978 paper for invention of the PGM. This error is significant, because their reversal is no longer based on an asymptotically optimal measurement.

Furthermore, as I pointed out in the introduction of my JMP article,

http://arxiv.org/abs/0907.2094

Holevo's pure state measurement has a failure rate within a factor of two of the optimal BY CONSTRUCTION. In particular, Holevo derived his approximately optimal measurement by minimizing a cost function. But this approximate cost function was trivially within a factor of two of the failure rate.

The paper 0907.3386 referred to by jontyson deals with a different problem from the one considered in our paper. 0907.3386 discusses reversing the dynamics on a given STATE. This is the same question examined in
[Barnum, Knill, JMP43, 2097(2002)] which uses a state-dependent map as the approximate reversal map. This is different from asking what the best recovery map for a given CODE is, which must work well for ALL states in the code. In the case of quantum error correction, the recovery map cannot depend on the input state. The bounds proven in 0907.3386 apply only to the given input state used to define the reversal map, and hence do not apply to error correcting codes.

The transpose channel used in our paper comes from making the pragmatic choice of using the projector P onto the code space (or more precisely, P/d, where d = dim(code)) as the "input state" for defining the reversal map. This turns out to work well as a recovery map for all states in the code. Inserting P/d into the modified reversal map in 0907.3386 unfortunately does not yield a map different from the transpose channel.

Perhaps one can think of other ways to make use of the modified reversal map in 0907.3386, but we fail to see why this paper should be cited in our work.

That would be flame-broiled bacon.

This paper doesnot have any idea or text match with Stephen cook s description what so ever, and it is not removed from arxive. It is an original paper on medical imaging with a novel approach to identify anomaly using region grow method. Scientists must refrain from such claims.

amen to that...

Finally...

more flaming bacon...or rather, bacon flaming...

The authors fail to cite

http://arxiv.org/abs/0907.3386

The empirical evidence is a clear violation of Einsteinian relativity theory despite the claims of the authors to the contrary.In those theories c is the maximal allowed signal velocity ,period.
In contrast to Earth bound laboratories , where 120 meters
seems to be the maximal superluminal tunneling length achieved today,where the issue of relativistic causality
is hard to settle because of miniscule time periods involved.The pulsars case at hand leaves no doubt that relativistic causality has been clearly violated.An advanced civilation can no doubt send superluminal signals with the tunneling mechanism involved in this pulsar scenario. In addition ,the light boom mechanism developed (and tested) by H Ardavan et al.could be used to futher increase the signal velocity of pulsar like machines developed by those advanced civilations ,if they want.

I am a little confused about the premise of this paper. It seems to me that if entangling Hamiltonians are going to be used as dynamical decoupling pulses for preserving a single _known and specific_ state, it would be much easier to simply reset the system to say ground state, and use a similar pulse to prepare that known and specific single state, with effectively O(1) gates. However, I am not entirely sure about comparison between the errors of these two schemes but I doubt that anything could beat a single pulse preparation. Maybe the authors could kindly clarify this for me, if they come across this comment.

Although, there is a nontrivial element in the paper's construction, I am not convinced that it is actually practical in what they want to achieve. The desirable feature of dynamical decoupling lies in preserving unspecified arbitrary superpositions in the presence of unspecified weak environment. Obviously DD methods can have other applications but I remain skeptical about this paper.

Generalizing DD schemes to multi-qubit systems is not a new subject, see e.g. quant-ph/0109063 and quant-ph/0106085 but the problem in my opinion is still largely open given new DD schemes and optimization based on the error model.

Hi Robert,

You are absolutely correct that often we have prior knowledge about the state that we want to reconstruct. That's why your results are important! I just wanted to point out for the benefit of others that one has to be explicit about the inclusion of this prior information. This is the crux of the difference between our two approaches. Your approach is faster, but assumes more; our approach is slower, but is unconditional. That isn't so obvious to casual readers, I think, so I just wanted to say it clearly in public.

Regarding the positivity constraints in the tomography-as-MC setting. While it's true that we neglect positivity, one can always incorporate any convex constraints as additional information to (at least information-theoretically) improve the algorithm. We don't use positivity in the theoretical analysis because we have no need to include it -- we get the same answer regardless! In practice, we optimize using a first-order method [1] over the positive cone, so our solutions are always positive. This isn't so clear in our short paper because of page limits, but we will provide more details in a longer version soon [2]. In order to have a non-trivial objective function, we treat the trace as a slack variable and then renormalize the solution at the end. Once could also incorporate the constraint Tr(X) >= 1, and this would probably have the same effect, though I haven't explicitly tested that case. One could alternately think of the subnormalized trace that comes about in the unconstrained case as representing merely the "main support" of a density operator, with the remainder occupying some error term which could be chosen to be maximally mixed by a Jaynes principle. In the upcoming longer paper, we will also explore the effects of post-processing via debiasing together with a trace constraint to avoid this issue.

[1] Since it's a first order method, we don't have to use slow interior point solvers like CVX on large instances.

[2] In the meantime, if anyone is interested feel free to email me.

The L1-norm minimization for QPT presented in our paper (0910.5498v1)
is in a completely general setting. We show that just as in compressed
sensing (CS) theory, L1-(vector) minimization, constrained for QPT by
the CPTP conditions, returns the best almost sparse solution to a
process matrix that is almost sparse, and not necessarily
sparse. Specifically, as for CS, the estimation error for L1-norm
based QPT is bounded by the best s-sparse solution (unknown a priori)
and the noise error. If the true matrix is actually sparse and there
is no measurement noise, then perfect recovery from a few measurement
ensues.

Of course the sparsity (or almost sparsity) property depends on the
chosen basis. However that would be an issue if we treat our system as
a black-box, which usually is not the case since often we have some
prior knowledge about our physical system. That is why most of the
experiments done for QPT demonstrate a sparse process matrix in the
bases that the experimenters have assumed. Where does this priori
knowledge come from? One may have a nominal Hamiltonian model, or as
in quantum computation (QC) a primary goal is to implement a unitary
matrix, the subject of most of the QPT experiments. The ideal unitary
matrix, whatever prior motivates it, implies which basis we should
expect the most sparsity. (The examples presented here in0910.5498v1
and previously in 0812.4323v2 are based on QC goals.) Moreover,
although not shown, the elementary gates of QC have a sparse
representation not only in the SVD basis of the desired unitary, but
even in the natural basis implied by the physics of the problem,
e.g. X,Y,Z in spin systems or H,V in optical systems (a CNOT or memory
is also naturally sparse). These are all sparse without a special
basis, although often require more measurments than if estimated in
the SVD basis of the desired unitary. In addition, any knowledge
about the dominant system-bath interactions help us in choosing the
basis that almost sparsity can be safely assumed. A good example is
the transition basis in NMR. Nonetheless, general reasons why a
process matrix is (almost) sparse (and/or of low rank) is open for
investigation.

About the difference between CS and Matrix Completion (MC). Rank of a
matrix and sparsity of a vector are analogous, although not entirely
identical. The norm used in arXiv:0909.3304 and arXiv:0910:1879 for MC
(as in the MC literature) is the nuclear norm (also known by Schatten
1-norm, Ky Fan r-norm, and trace norm) and is the sum of the matrix
singular values. In standard MC, a low rank matrix can be
reconstructed efficiently by minimizing the nuclear norm with linear
constraints of the measurement outputs. In quantum state and process
tomography (QST and QPT) there are extra constraints: the matrices are
positive-semidefinite and of fixed trace. With these two constraints
the nuclear norm of a density matrix or a process matrix is also fixed
(in fact it is equal to the trace of the matrix)and therefore nuclear
norm minimization is not well formed as a constraint or an objective.
In arXiv:0909.3304 the positivity constraint is removed, thereby
permitting MC via nuclear norm min., but also permitting the
possibility of introducing errors due to data arising from an
ill-conditioned matrix (almost low rank) or from noise. Staying with
this approximation is not without merit, in fact it may be very
useful. In the ideal case of exact low rank and noise free
measurements, the MC theory predicts perfect recovery of a true
density matrix since the positivity constraint is implicit in the
data. However, in a realistic case of almost low rank and noisy
measurements, the data will not force the positivity, and so it is
possible that the resulting state or process matrix estimate will have
negative eigenvalues. How close this solution is to the true density
matrix (or process matrix) is not clear and is also an open issue. If
one is compleletly devoid of prior knowledge then perhaps iteratng
between MC and CS for QPT is a practical melding.

An important distinction for compressed sensing is between the *vector* and *matrix* L1 norms. I just want to point out that the impressive speed-ups achieved in this paper are done in the former setting of vector L1 norm minimization. What does this mean physically? It means that the authors are working in a setting where the experimentalist performing the tomography is assumed to have a priori knowledge about the basis in which the system or process is sparse. Then the sparse reconstruction is performed in that known basis, and reconstruction is achieved with only O(s polylog(d)) measurements. Thus, while this can't be used for "basis-oblivious" tomography -- where the experimenter assumes nothing -- it is still very useful for certifying that the intended state or process was indeed created.

The results of arXiv:0909.3304 and arXiv:0910:1879, by contrast, use the matrix L1 norm. Results using the matrix L1 norm do not immediately follow from results using the vector L1 norm; rather they are based on a non-commutative generalization of compressed sensing, also called matrix completion. Using this matrix norm allows the experimenter to learn a completely unknown basis, not just the expansion coefficients. The above two papers imply that quantum process tomography (QPT) of a CP map that is well approximated by r Kraus operators in some orthonormal operator basis can be done using O(r d^2 polylog(d)) measurements, plus poly(d) classical computation, where d is the dimension of the system. One can simply use the entanglement-assisted setting to do the QPT as if it were state tomography on a dxd system with a rank r state. This is unconditional, heralded (in case there is no good rank r approximation, it outputs a failure flag), and works even if the experimenter has no a priori knowledge of the process.