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 \begin{equation} 0\leq\langle\phi_f|\phi_h\rangle\leq\frac{n}{q}. \end{equation} 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 ...



Your Answer

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