View articles by...
Feed of this discussionCan quantum mechanics help distributed computing?
quantalk.org/09-08-003
Posted: 28 August 2009, 11:03

Abstract: We present a brief survey of results where quantum information processing is useful to solve distributed computation tasks. We describe problems that are impossible to solve using classical resources but that become feasible with the help of quantum mechanics. We also give examples where the use of quantum information significantly reduces the need for communication. The main focus of the survey is on communication complexity but we also address other distributed tasks.
Simon Benjamin
Editor, Operator
posted
11:03
28/08/09
View only replies to this postFor review
This paper has been submitted for consideration for an upcoming Special Issue of the International Journal of Quantum Information with the theme 'Distributed Quantum Computing'.
In due course the reviewers will post their reports into this thread, at which point the author can enter into an exchange with them and/or revise the manuscript.
Third parties are also welcome to contribute to this thread, however the eventual decision of the editors (Dan Browne and Simon Benjamin) will normally be based principally on the reviewer and author postings.
Anonymous α
Reviewer
posted
10:44
10/09/09
View only replies to this postReview
4/Acceptable with revision, no need to see a revised version.

--------------------------
General remarks.
--------------------------

The goal of this article is a overview about some problems of distributed computing in the light of quantum information.
The main focus is on communication complexity problems. This paper is well written and gives an idea about the different results in this subject.
One of the things that I like about this paper is that it gives an overview of a lot of problems which we are not used to seeing together in the same place.

The authors use intuition instead of the technical aspects to introduce these problems, making it pleasant to read.

Sometimes it is little bit too informal, and some references are given with very few details about the main idea of the results within.
In other words, there are some problems where more intuition about the result will be useful for the reader.

The logic of the paper between the different parts ( Quantum computation and entanglement / Pseudo-telepathy / Communication complexity / Other communication games / Conclusion) is not clear.
One suggestion would be to have a short introduction to explain the structure of the paper and after introduce "Quantum computation and entanglement" and "communication complexity", and after "pseudo-telepathy" and "communication games". An other suggestion could be to have a general introduction and split the paper in two parts: "non-communication games" (pseudo telepathy...) with a little introduction for this part and an other part "Communication games" with the paragraph called "communication complexity" inside this part.

--------------------------------------------------------------
Part 1/ Quantum computation and entanglement.
--------------------------------------------------------------

The second paragraph (between "In classical.... ... from an n-qubit state") could be reduced significantly, since it is a very general introduction and could be more focus to introduce the subject of the article: distributed computing.

Paragraph 3.
The difference between entanglement and quantum correlations is not clear. Sometimes entanglement is used instead of quantum correlation, which suggests to reader that is the same thing.
For example:
line 5 : "In the absence of quantum correlations (if two players do not share entanglement)...."
The bracket suggests that the absence of quantum correlation implies no entanglement, but in the general case this is not true: there are some states which are entangled but with no quantum correlations (that is, the correlations can be explained with a local hidden variable model).

line 7: "when the players share quantum correlations..." It's could be useful to make this more precise.

paragraph 5.
There is no logical link between paragraph 4 and paragraph 5. Why this paragraph about QKD arrives at this moment is not clear, it would be better after paragraph 6 (before the sentence " We will not discuss quantum computer ...")
In general, this paragraph 6 could be reduced significantly because it not clearly related with the subject of the article (pseudo-telepathy, and communication game...), and/or it will be useful for the reader to explain more clearly the link.

----------------------------------------------
Part 2/ Pseudo-telepathy
----------------------------------------------

line 2: "It involves the study of a physical phenomenon that was previously studied by physicists" The meaning of this sentence is strange...

-------------------------------------------------------
Part 3/ communication complexity
-------------------------------------------------------

paragraph 3, line 3:
"We have decided to concentrate on this model since it is natural to compare it to quantum case."
It could helpful to make precise why this model is natural.

-------------------------------------------------------
Part 4/ Other communication games
-------------------------------------------------------

4.1 / Fingerprinting.
It could be interesting to exhibit the link with communication games.

4.3 / Quantum proofs.
The same remark as above, the link with communication games is not clear.

4.4 / Classical simulation of entanglement
"The distant players are assumed to share continuous random variables; otherwise it is know to be impossible."
The meaning of this sentence is not clear. If we suppose that the parties cannot use communication, it is trivial.
If we suppose that they can use classical communication, it's not clear that "otherwise" is related to "continuous" and they suppose the communication is taken as the worst case.
It could be helpful to make this sentence precise . For example, (...) it's impossible to simulate quantum correlations with worst case communication if the parties don't share a infinite amount of random variables (or just share continuous random variables). It could be nice to give refer to [42] (Classical simulation of quantum entanglement without local hidden variables) for this result.
Anne Broadbent
posted
23:04
23/11/09
View only replies to this postReply
We thank the referee for the very pertinent comments that have
allowed us to improve the paper. Please find below our responses.
Attached is the modified submission.

The logic of the paper between the different parts ( Quantum
computation and entanglement / Pseudo-telepathy / Communication
complexity / Other communication games / Conclusion) is not clear.
One suggestion would be to have a short introduction to explain the
structure of the paper and after introduce "Quantum computation and
entanglement" and "communication complexity", and after
"pseudo-telepathy" and "communication games". An other suggestion
could be to have a general introduction and split the paper in two
parts: "non-communication games" (pseudo telepathy...) with a little
introduction for this part and an other part "Communication games"
with the paragraph called "communication complexity" inside this
part.

*Our Answer:* We have clarified the structure of the paper in the
paragraph before the section entitled "pseudo-telepathy". We have
renamed the section "Other communication games" to "More distributed
quantum tasks"

--------------------------------------------------------------
Part 1/ Quantum computation and entanglement.
--------------------------------------------------------------

The second paragraph (between "In classical.... ... from an n-qubit
state") could be reduced significantly, since it is a very general
introduction and could be more focus to introduce the subject of the
article: distributed computing.

*Our Answer:* because the survey is "aimed at researchers having very
limited knowledge of quantum computation", we think that the short
introduction to quantum information is appropriate.

Paragraph 3.
The difference between entanglement and quantum correlations is not
clear. Sometimes entanglement is used instead of quantum correlation,
which suggests to reader that is the same thing.
For example:
line 5 : "In the absence of quantum correlations (if two players do
not share entanglement)...."
The bracket suggests that the absence of quantum correlation implies
no entanglement, but in the general case this is not true: there are
some states which are entangled but with no quantum correlations
(that is, the correlations can be explained with a local hidden
variable model).

line 7: "when the players share quantum correlations..." It's could
be useful to make this more precise.

*Our Answer:* We have replaced "quantum correlations" we
"entanglement" in two pertinent places.

paragraph 5.
There is no logical link between paragraph 4 and paragraph 5. Why
this paragraph about QKD arrives at this moment is not clear, it
would be better after paragraph 6 (before the sentence " We will not
discuss quantum computer ...")
In general, this paragraph 6 could be reduced significantly because
it not clearly related with the subject of the article
(pseudo-telepathy, and communication game...), and/or it will be
useful for the reader to explain more clearly the link.

*Our Answer:* We have made the suggested modifications to the order
of the text. We left the text of paragraph 6 intact because we want
to give an overview of the area before going into details.

----------------------------------------------
Part 2/ Pseudo-telepathy
----------------------------------------------

line 2: "It involves the study of a physical phenomenon that was
previously studied by physicists" The meaning of this sentence is
strange...

*Our Answer:* New sentence: "It involves the study of a phenomenon
that previously appeared in physics literature"

-------------------------------------------------------
Part 3/ communication complexity
-------------------------------------------------------

paragraph 3, line 3:
"We have decided to concentrate on this model since it is natural to
compare it to quantum case."
It could helpful to make precise why this model is natural.

*Our Answer:* we have added "where players also have access to shared
entanglement"

-------------------------------------------------------
Part 4/ Other communication games
-------------------------------------------------------

4.1 / Fingerprinting.
It could be interesting to exhibit the link with communication
games.

*Our Answer:* We changed the title of the section to "More
distributed quantum tasks"

4.3 / Quantum proofs.
The same remark as above, the link with communication games is not
clear.

*Our Answer:* Same as above.

4.4 / Classical simulation of entanglement
"The distant players are assumed to share continuous random
variables; otherwise it is know to be impossible."
The meaning of this sentence is not clear. If we suppose that the
parties cannot use communication, it is trivial.
If we suppose that they can use classical communication, it's not
clear that "otherwise" is related to "continuous" and they suppose
the communication is taken as the worst case.
It could be helpful to make this sentence precise . For example,
(...) it's impossible to simulate quantum correlations with worst
case communication if the parties don't share a infinite amount of
random variables (or just share continuous random variables). It
could be nice to give refer to [42] (Classical simulation of quantum
entanglement without local hidden variables) for this result.

*Our Answer:* New text: "We assume in what follows that the distant
parties share an infinite amount of random variables, because
otherwise it is impossible to simulate quantum correlations with
worst case communication~\cite{MBCC01}."

Simon Benjamin
Editor, Operator
posted
15:23
24/11/09
View only replies to this postAcceptance
This paper is now accepted for publication in the IJQI Special Issue on Distributed QIP.

The thread will remain open for any interested researcher to post questions, observations etc.
Simon Benjamin
Editor, Operator
posted
22:33
24/11/09
View only replies to this postAUTOMATED POST: Change to thread
I have made a change to the article this thread is about. The reason for the change was:

Upload of new article file
 (all posts shown)
5 posts