Complexity of quantum circuits in a specific protocol

Question

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.

I suggested the following protocol:

Associate each $x ∈ \{0, 1\}^n$ with a short quantum state $|φ_x\rangle$, called the quantum fingerprint of $x$. We can choose an error-correcting code $C: \{0, 1\}^n → \{0, 1\}^N$ where $m = log(N) ≈ log(n)$. There exist codes where $N = O(n)$ and any two codewords $C(x)$ and $C(y)$ have Hamming distance close to $N/2$, say $d(C(x), C(y)) ∈ [0.5N-\epsilon, 0.5N+\epsilon]$ (for instance, a random linear code will work). Define the quantum fingerprint of $x$ as follows:

$|φ_x\rangle = \frac{1}{\sqrt{N}}\sum_{j=1}^{N}(-1)^{C(x)_j}|j\rangle$

This is a unit vector in an $N$-dimensional space, so it corresponds to only $\lceil{log(N)}\rceil = log n + O(1)$ qubits. For distinct $x$ and $y$, the corresponding fingerprints will have a small inner product:

$\langle\varphi_x|φ_y\rangle=\frac{1}{N}\sum_{j=1}^{N}(-1)^{C(x)_j+C(y)_j}=\frac{N-2d(C(x),C(y))}{N}\in[-\epsilon,\epsilon]$

The quantum protocol will be as follows: Alice and Bob send quantum fingerprints of $x$ and $y$ to the Referee, respectively. The referee now has to determine whether $x = y$ (which corresponds to $\langle\varphi_x|φ_y\rangle=1$) or $x=y$ (which corresponds to $\langle\varphi_x|φ_y\rangle\in[-\epsilon,\epsilon]$). The SWAP-test accomplishes this with a small error probability. This circuit first applies a Hadamard transform to a qubit that is initially $|0\rangle$, then SWAPs the other two registers conditioned on the value of the first qubit being $|1\rangle$, then applies another Hadamard transform to the first qubit and measures it. SWAP is the operation that swaps the two registers: $|φ_x\rangle|φ_y\rangle→|φ_y\rangle|φ_x\rangle$. The Referee receives $|φ_x\rangle$ from Alice and $|φ_y\rangle$ from Bob and applies the test to these two states. An easy calculation reveals that the outcome of the measurement is $1$ with probability $\frac{1-|\langle\varphi_x|φ_y\rangle|^2}{2}$. Hence if $|φ_x\rangle=|φ_y\rangle$ then we observe a $1$ with probability $0$, but if $|\langle\varphi_x|φ_y\rangle|$ is close to $0$ then we observe a $1$ with probability close to $1/2$. Repeating this procedure with several individual fingerprints can make the error probability arbitrarily close to $0$.

Now, my question is what is the complexity of the quantum circuits that are needed for Alice, Bob, and referee R, to implement this protocol?

Thanks so much for helping!

Answer 1

There are two different complexity considerations that you might be interested in in this scenario.

The one that most people think about is the communication complexity, i.e. how many qubits Alice and Bob have to send to the referee. This is relatively simple to calculate - it's just $mk$ where $k$ is the number of times you have to repeat the controlled-swap test. If we want a failure probability $\epsilon$, then we need $$ \frac{1}{2^k}\leq\epsilon $$ because that's the probability that, given the two states are approximately orthogonal, you get the 0 measurement result every time and therefore misinterpret them as being the same. Hence, the communication complexity is $$ O(m\log(1/\epsilon)). $$

What your question actually asked about was the circuit complexity. For Alice and Bob, this is the question of how hard it is to prepare the state $|\varphi_x\rangle$. In the worst case, there is no pattern to the $(-1)^C(x)_j$ phases, and you have to compute them all separately. (Strictly, there's some pattern because of the encoding.) This suggests a complexity $O(n)$. On the other hand, imagine there's a circuit that requires less than $O(n)$ running time to encode the state. Each $|\varphi_x\rangle$ is unique, so we could consider the specification of the circuit as a substitute for $x$. Hence we have losslessly compressed $n$ bits of information into something less than $O(n)$, which must be impossible. In other words, you cannot do any better.

As for the referee, they have a relatively easy time. They just need to apply the swap test, the main element of which is controlled-swap, swapping two $m$-qubit states. But this is just $m$ controlled-swap gates where you swap a pair of qubits. So the complexity is $O(m)$.