# Complexity of the quantum circuits that are needed to implement communication protocol?

Consider the following simultaneous communication problem. Alice and Bob do not share any entanglement or any common randomness, and cannot communicate directly with each other. As inputs, x is given to Alice, and y is given to Bob, where x, y ∈ {0, 1}^n. Based on their inputs Alice and Bob can each send a single message to a referee R that has to decide whether x = y or not.

My protocol : Alice and Bob get each an input $$x$$, respectively $$y$$, where $$x,y\in\{0,1\}^n$$. Based on their inputs, they can both send a single message to a referee $$\mathcal{R}$$ which decides whether their inputs are equal or not.

Any element $$x\in\{0,1\}^n$$ is a sequence $$(x_0,x_1,\ldots,x_{n-1})$$ of $$0$$'s and $$1$$'s of length $$n$$, thus defines a polynomial of degree at most $$n$$ over $$\mathbb{F}_q$$, for $$q=2^a$$, for some $$a\geq 1$$ (to be chosen later). Furthermore, let $$f$$, respectively $$h$$, denote the polynomials corresponding to $$x$$ and $$y$$; then it is immediate that $$x\neq y$$ iff $$f\neq h$$.

We propose the following protocol: both Alice and Bob compute, based on their input (polynomial), and send the referee $$\mathcal{R}$$, the quantum states $$|\phi_f\rangle^{\otimes\kappa}$$, respectively $$|\phi_h\rangle^{\otimes\kappa}$$. The referee performs $$\kappa$$ successive SWAP tests and takes the following decision: If all $$\kappa$$ measurements are $$0$$ then the referee decides that $$x=y$$; Otherwise, if at least one measurement is $$1$$, he decides that $$x\neq y$$. If $$x=y$$ then all $$\kappa$$ measurements will be $$0$$, so the referee will take the correct decision. On the other hand, if $$x\neq y$$ then the referee will make an error only if all $$\kappa$$ measurements are $$0$$; this occurs with probability $$\mathbb{P}\{\textrm{Error}\}=\left(\frac{1+|\langle\phi_f|\phi_h\rangle|^2}{2}\right)^\kappa\leq\left(\frac{1+(n/q)^2}{2}\right)^\kappa,$$ where we use the bound $$$$0\leq\langle\phi_f|\phi_h\rangle\leq\frac{n}{q}.$$$$ Letting now $$\alpha\in(0,1)$$ be fixed, we choose $$a\geq 1$$ such that $$n/q\sim\alpha$$, hence $$a\sim\log_2(n/\alpha)$$, and $$\kappa$$ large enough to guarantee that $$\left(\frac{1+\alpha^2}{2}\right)^\kappa\leq\frac{1}{100},$$ hence $$\kappa\geq\frac{2}{\log 2 - \log(1+\alpha^2)}$$, where the $$\log$$ is calculated in decimal base.

Finally, sending the quantum states $$|\phi_f\rangle^{\otimes\kappa}$$, $$|\phi_h\rangle^{\otimes\kappa}$$ to $$\mathcal{R}$$ require $$2a\kappa$$ qubits, with $$a\sim\log_2(n/\alpha)$$, hence the above protocol achieves a (probabilistic) error of at most $$0.01$$ while requiring $$O(\log n)$$ qubits to be sent.

My question is : what is the complexity of the quantum circuits that are needed for Alice, Bob,and the referee R, to implement the protocol? (In particular, if need to a apply a quantum version of a known classical algorithm please not describe the exact details of that classical algorithm. Please provide accurate complexity bounds.) Note: There is a classical randomized algorithm where Alice and Bob each send to R a message of size O(√n) and R’s error probability is at most 1/100 (This is known to be optimal).

For the referee R , I guess that each SWAP test can be represented as a quantum circuit with $$2a$$ gates, where $$2a$$ is the number of qubits of the two states to be tested. Then the complexity of a $$\kappa$$-fold SWAP test is $$\kappa\:O(\log n) = O(\log n)$$.

For Alice and Bob I have no idea ...