<p>This question continues from the <a href="https://cstheory.stackexchange.com/questions/9794/are-alice-and-bob-allowed-to-copy-qubits-in-quantum-communication-complexity-mod">previous question</a> where I mistakenly asked a question that is too general. </p>

<p>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.</p>

<p>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?</p>

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

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

<p>(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.)</p>

CC BY-SA 3.0
2012-01-20T00:11:31.750Z
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)
Tsuyoshi Ito
CC BY-SA 3.0
2012-01-20T00:11:39.473Z
(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.
Tsuyoshi Ito
CC BY-SA 3.0
2012-01-20T23:14:49.850Z
@TsuyoshiIto Thank you for the clarification of the model.
Dan
<quantum-computing><communication-complexity><quantum-information>
Do the quantum communication complexity lower bounds hold when parties can send a "duplicated" qubits?
Dan
# Do the quantum communication complexity lower bounds hold when parties can send a "duplicated" qubits?

(Asked by: username_0 on 2012-01-19)

This question continues from the [previous question](https://cstheory.stackexchange.com/questions/9794/are-alice-and-bob-allowed-to-copy-qubits-in-quantum-communication-complexity-mod) 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.)

**Tags:** quantum-computing, communication-complexity, quantum-information

> **Comments:**
> **username_1**: 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)  
> **username_1**: (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.  
> **username_0**: @TsuyoshiIto Thank you for the clarification of the model.  

---

## 0 answers

