For $2N$ qubits $\{i_1,j_1\ldots i_N,j_N\}$ I would like to have a circuit changing the value of an ancillary register from $0$ to $1$ if $i_1=j_1$ AND $i_2=j_2$ AND ... AND $i_N=j_N$.

One way to construct such a circuit is to use a separate ancillary qubit to store the value of comparison of $i_n$ and $j_n$ and then use a multi-controlled Toffoli on all ancillas. This requires $N$ ancillas and an $N$-qubit Toffoli. Can we do better than that? (Multi-controlled gates are extremely expensive, and using a number of them linear in the input size is highly undesireable.)

One idea I had is that since comparison $|i,j,k\rangle\mapsto|i,j,k\oplus (i=j)\rangle$ is implemented as $|i,j,k\rangle\mapsto|i,j,k\oplus i\oplus j\oplus 1\rangle$ (please correct me if I'm wrong), one could probably use instead $|i,j\rangle\mapsto|i\oplus j\oplus1,j\rangle$ (and the inverse operation at the end, to restore the original values of qubits) to avoid using ancillas. This solves the problem with the number of ancillas but not with multi-controlled gates.

Another idea is to use arithmetic and calculate the product of qubits.


1 Answer 1


Yes, you can can apply a $CNOT$ from each qubit in the $i$ register (control qubit) to each qubit in the $j$ register (target qubit), followed by an $X$ gate on the target qubit. Let this operation be the unitary $U(|ij\rangle)$, then is it is pretty straightforward that:

$$U(|00\rangle) = |01\rangle$$ $$U(|01\rangle) = |00\rangle$$ $$U(|10\rangle) = |10\rangle$$ $$U(|11\rangle) = |11\rangle$$

I.e, the state of the qubit in the $j$ register (the target qubit) is $|1\rangle$ if $|i\rangle = |j\rangle$ and $|0\rangle$ otherwise.


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.