Comparing qubit values in pairs of qubits

Question

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.

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.