5
$\begingroup$

This question continues from the previous question where I mistakenly asked a question that is too general.

In quantum communication complexity, we always assume that Alice and Bob have unlimited computational power and are still prove lower bounds such as the Ω(n) lower bounds of parity.

What happens if we assume that Alice and Bob can do something that they cannot do due to the the law of physics? One particular ability that I'm interested in is when each party can send a qubit to the other party without losing their own qubit. In other words, before sending their qubits to the other party, they can make ONE copy of it. (Note that this is allowed only when they are about to send a qubit.) Do the known lower bounds hold in this case?

A particular result that I'm interested in is the lower bound in Razborov's paper "Quantum communication complexity of symmetric predicates".

Also, is this ability already included in the formal definition, e.g., as defined in Razborov's paper?

(As you can guess, my understanding in quantum algorithm is very limited. So, besides the full answers, I would appreciate any pointer to anything in the literature as well.)

Improve this question
$\endgroup$
3
  • 3
    $\begingroup$ I think that this question is interesting, but there are subtle issues with “cloning” part of an entangled state—it is not well-defined! So I would define the model as follows. (more) $\endgroup$
    – Tsuyoshi Ito
    Commented Jan 20, 2012 at 0:11
  • 2
    $\begingroup$ (cont’d) Alice and Bob have the usual quantum channel, and also each party has a “cloning device” which clones an arbitrary-size pure state. If either party tries to clone a non-pure state, the device magically detects it and explode, which as the same effect as giving a wrong answer. Sending one qubit costs 1, and also cloning a k-qubit pure state costs k. Can we still show some nontrivial lower bound in this model? I do not know if a model like this has been ever studied. $\endgroup$
    – Tsuyoshi Ito
    Commented Jan 20, 2012 at 0:11
  • $\begingroup$ @TsuyoshiIto Thank you for the clarification of the model. $\endgroup$
    – Dan
    Commented Jan 20, 2012 at 23:14

0

Reset to default

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.