<p>The general rule of thumb is if you have cloning (and unbounded computation!), then most things get easy. In the case of the qubit-channel communication complexity, Alice can just send her initial state with one qubit.</p>

<p>Interpret Alice's string $x$ as an integer, between $1$ and $2^n$. Given a string $x$, Alice prepares the state $|\phi_x\rangle = \sqrt{1 - x/2^n}|0\rangle + \sqrt{x/2^n}|1\rangle$. She sends state $|\phi_x\rangle$ to Bob, Bob makes an exponential number of copies of $|\phi_x\rangle$ and measures each individually in different bases to determine $x$. With $x$ in his hands, Bob can compute any function $f(x,y)$.</p>

CC BY-SA 3.0
2012-01-18T23:07:08.273Z
2012-01-18T23:07:08.273Z
Artem Kaznatcheev
<p>Let me add to Artem’s nice explanation a pedantic point about your wording “something a quantum algorithm cannot do.”</p>

<p>In the usual setting of communication complexity, each party is allowed to perform any local operations, regardless of whether it is computable or not.  This is true in both classical and quantum cases.  In this sense, each party is indeed allowed to do something a quantum <em>algorithm</em> cannot do.  However, Alice and Bob are still constrained by the law of physics, and cloning is disallowed because of this.  In short, cloning is disallowed not because there is no quantum algorithm for it, but because it is ruled out by the law of physics.</p>

CC BY-SA 3.0
2012-01-19T05:28:26.250Z
That's an interesting point. Thanks for the answer.
Dan
CC BY-SA 3.0
2018-04-04T02:17:22.260Z
@TsuyoshiIto - Please accept my invitation to: https://quantumcomputing.stackexchange.com/ .
Rob
CC BY-SA 3.0
2012-01-19T02:29:14.697Z
2012-01-19T02:29:14.697Z
Tsuyoshi Ito
<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 $\Omega(n)$ lower bounds of parity. </p>

<p>What happens if we assume that Alice and Bob can do something a quantum algorithm cannot do? One particular ability that I'm interested in is when they can copy qubits, i.e., Alice can send Bob a copy of her qubits and also keep a copy of that qubit sent to Bob. Do the lower bounds still hold in this model?</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>

<p><strong>Update:</strong> I realized after reading Artem Kaznatcheev's answer that the model I ask is too general so I　asked a new question <a href="https://cstheory.stackexchange.com/questions/9797/do-the-quantum-communication-complexity-lower-bounds-when-parties-can-send-a-du">here</a></p>

<quantum-computing><communication-complexity><quantum-information>
Are Alice and Bob allowed to copy qubits in quantum communication complexity model?
Dan
# Are Alice and Bob allowed to copy qubits in quantum communication complexity model?

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

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

What happens if we assume that Alice and Bob can do something a quantum algorithm cannot do? One particular ability that I'm interested in is when they can copy qubits, i.e., Alice can send Bob a copy of her qubits and also keep a copy of that qubit sent to Bob. Do the lower bounds still hold in this model?

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.)

**Update:** I realized after reading Artem Kaznatcheev's answer that the model I ask is too general so I　asked a new question [here](https://cstheory.stackexchange.com/questions/9797/do-the-quantum-communication-complexity-lower-bounds-when-parties-can-send-a-du)

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

---

## 2 answers

### Answer by username_1 on 2012-01-18. Score: 5 | Accepted answer

The general rule of thumb is if you have cloning (and unbounded computation!), then most things get easy. In the case of the qubit-channel communication complexity, Alice can just send her initial state with one qubit.

Interpret Alice's string $x$ as an integer, between $1$ and $2^n$. Given a string $x$, Alice prepares the state $|\phi\_x\rangle = \sqrt{1 - x/2^n}|0\rangle + \sqrt{x/2^n}|1\rangle$. She sends state $|\phi\_x\rangle$ to Bob, Bob makes an exponential number of copies of $|\phi\_x\rangle$ and measures each individually in different bases to determine $x$. With $x$ in his hands, Bob can compute any function $f(x,y)$.


---

### Answer by username_2 on 2012-01-19. Score: 6

Let me add to Artem’s nice explanation a pedantic point about your wording “something a quantum algorithm cannot do.”

In the usual setting of communication complexity, each party is allowed to perform any local operations, regardless of whether it is computable or not. This is true in both classical and quantum cases. In this sense, each party is indeed allowed to do something a quantum *algorithm* cannot do. However, Alice and Bob are still constrained by the law of physics, and cloning is disallowed because of this. In short, cloning is disallowed not because there is no quantum algorithm for it, but because it is ruled out by the law of physics.

> **Comments:**
> **username_0**: That's an interesting point. Thanks for the answer.  
> **username_3**: @TsuyoshiIto - Please accept my invitation to: https://quantumcomputing.stackexchange.com/ .  

---

