SciRate Papers: 7/18 to 7/25

In attempt to keep my reading more current, I’m going to try to post the top rated arXiv papers on SciRate each week and hopefully add about the papers. Let’s see how long I can keep it up (bets?)

0807.2668 (7 scites) “Mixing doubly stochastic quantum channels with the completely depolarizing channel” by John Watrous.

QP says: A large variety of open quantum system evolutions are describable using the superoperator formalism. A superoperator is a linear map from a space of linear operators to another space of linear operators. The ones we care most about in quantum computing are the superoperators which correspond to a evolving a system and its intially environment, when these two subsystem start out separable. Such admissible superoperators are trace preserving and are also completely positive. Within the class of superoperators there are some other classes which are also of use. One is unital superoperators. Unital superoperators map the identity operator to the identity operator. In other words unital superoperators fix maximally mixed density matrices. Admissible superoperators which are unital are called doubly stochastic superoperators. Another class of superoperators are those which can be expressed as a probabilistic sum of unitaries. These are a subclass of the doubly stochastic superoperators and are called mixed unitary superoperators. For qubits, all doubly stochastic superoperators are mixed unitary superoperators, but for three dimensional and higher system this is not true. Mixed unitary operators, I think, are of even more interest nowadays, since as was shown in arXiv:0804.1936, by Rosgen that the additivity conjecture for minimum output entropy can be resolved without loss of generality by referring to mixed unitary superoperators.
Lots of cool things are known about mixed unitary superoperators. For example, they correspond exactly to the channels that can be corrected using classical information obtained by measuring the environment of the channel (Gregoratti and Werner.) Here Watrous adds to what we know about these superoperators by showing that it is always possible to take a doubly stochastic superoperator and mix it with a completely depolarizing channel such that this new superoperator is a mixed unitary operator. The mixing procedure can be thought of as, with probability p performing the depolarizing channel and with probability 1-p performing the original channel.

0807.2758 (7 scites) “Simultaneous Communication Protocols with Quantum and Classical Messages” by Oded Regev, and Ronald de Wolf.

QP says: Suppose Alice has x and Bob has y and they wish to compute a joint function of x and y, f(x,y). Communication complexity studies how much the parties need to communicate in order to achieve this. There are a variety of different models for this setting, sometimes Alice and Bob communicate back and forth. Here the authors consider the simultaneous communication setting where both Alice and Bob send their communication to a referee, Rob, and Rob has to calculate f(x,y) with high probability. For example, if f(x,y)=1 iff x=y, then assuming Alice and Bob do not share prior randomness, then classical one requires O(sqrt(n)) bits to calculate f where n is the number of bits used to express the inputs x and y (this is also sufficient.) However, if Alice and Bob are able to use qubits for communication instead of classical bits, then using quantum fingerprinting, one can use only O(log(n)) qubits to calculate f. This is an exponential separation between quantum and classical communication complexity for this setting. Here the authors investigate a case apparently raised as a question by Wim van Dam: what if one of the parties communicates to the referee classically while the other communicates quantumly? (A side note: Apparently Dmitry Gavinsky had considered this problem earlier and obtained similar results but declined to be author on the current version of this paper.)
Here the authors show that for computing Boolean functions the quantum classical simulatenous message passing can be only polynomially better than the classical simulatenous message passing case. Interestingly, there are cases where a relational problem admits an exponential separation between these two models. The proofs here use a lot of earlier work due to Aaronson.

Other papers receiving lots of scites:
0807.3616 (5 scites) “Protecting Quantum Information with Entanglement and Noisy Optical Modes” by Mark M. Wilde and Todd A. Brun.
0807.3566 (5 scites) “Stabilizer Quantum Codes: A Unified View based on Forney-style Factor Graphs” by Pascal O. Vontobel
0807.2876 (4 scites) “Stabilizer states and local realism” by Matthew B. Elliott (this is a Ph.D. thesis.)
0807.3811 (4 scites) “Entanglement-redistribution boxes” by Andrzej Grudka, Michal Horodecki, Pawel Horodecki, Ryszard Horodecki, and Marco Piani
0807.3286 (4 scites) “The Strong Free Will Theorem” by John Conway and Simon Kochen