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


2 Answers 2


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


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.

  • $\begingroup$ That's an interesting point. Thanks for the answer. $\endgroup$
    – Danu
    Commented Jan 19, 2012 at 5:28
  • $\begingroup$ @TsuyoshiIto - Please accept my invitation to: quantumcomputing.stackexchange.com . $\endgroup$
    – Rob
    Commented Apr 4, 2018 at 2:17

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.