For the following Quantum parallelism algorithm: enter image description here

Why does the output for $y$ have to be $y ⊕ f(x)$ for the algorithm to work? Why can't it be anything else, such as $f(x)$ only or $f(y)$ etc?


1 Answer 1


Recall that the operations that one applies on a quantum state are actually unitary matrices. In particular, these operations are reversible, since these matrices can be inverted.

Now, let us consider the map: $$|x\rangle|y\rangle\mapsto|x\rangle|y\oplus f(x)\rangle$$ If you were to write the matrix corresponding to this mapping, you would end up with a permutation matrix, that is, a matrix filled with zeros except for a single $1$ in each row and in each column. It is easy to check that such a matrix is unitary and is, as such, a permitted operation, no matter what $f$ is.

Now, let us consider the map: $$|x\rangle\mapsto|f(x)\rangle$$ which is called in the literature an erasing oracle, or a minimal oracle. This is a perfectly valid mapping, as long as $f$ is one-to-one. Indeed, in that case, the associated matrix is once again a permutation matrix, which is easily seen by the fact that each basis state is mapped to an unique basis state. If $f$ is not bijective however, say, constant to $0$, then the operation is no longer invertible, since it is not possible anymore to recover $|x\rangle$ from $|f(x)\rangle=|0\rangle$.

Note that another type of mapping may be encountered, for instance when studying Grover's algorithm, which is the phase mapping: $$|x\rangle\mapsto(-1)^{f(x)}|x\rangle$$ The associated matrix is this time not a permutation one, but a diagonal one, with a $-1$ on the index where $f$ is equal to 1. This matrix being unitary, we can apply it.

All in all, the mapping you choose depends on your needs, but it has to be unitary to be valid, which is why we can't always simply apply $f$ to the input register. Note that it is often desirable to apply the first mapping or the phase one instead of the minimal one. For instance, Simon's algorithm uses the first mapping, while Grover's algorithm uses the phase one.


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.