Addition modulo 2 notation (Quantum Computing)

Question

I am studying Quantum Computing using the book Quantum Computation and Quantum Information of Michael Nielsen and Isaac Chuang. I am confused by the meaning of the $\oplus$ (addition modulo 2) symbol in the notation.

Given a starting state $|\psi\rangle|\phi\rangle$ and a unitary gate $U$ such that $U|\psi\rangle|\phi\rangle = |\psi\rangle|\phi \oplus f(\psi)\rangle$. What does in this case $\oplus$ mean, in the general case for $|f(\psi)\rangle = \alpha_0 |0\rangle + \alpha_1|1\rangle$ and $|\phi\rangle = \beta_1 |0\rangle + \beta_2 |1\rangle$?

Answer 1

The question is about the general case, but the purpose of U can be explained more clearly with an example. You can find in the book Quantum Computation and Quantum Information of Michael Nielsen and Isaac Chuang an example about period finding. Then the Unitary gate with the same definition $ U|\psi\rangle|\phi\rangle = |\psi\rangle|\phi \oplus f(\psi)\rangle $ is used in an algorithm with output r or repetition rate with f(x) = x + r. In this case and for the most algorithms in quantum computers, the addition modulo addition is used for the purpose its name implies. It is a binary operation for adding two numbers with a XOR operation or with the CNOT quantum gate.

It is used in the period finding algorithms for its property to recognize the same output value with two different input values. Suppose we have a function $ f(x) = f(x \oplus s) $ with s is an fixed binary string 101. For x = 000 and x = 101 the result is the same in both cases. So you can find similar values in a periodic function

Answer 2

The definition shows how $U$ is defined on the standard basis (that is, when $\psi$ and $\phi$ are pure states). You can extend it to general states in a linear way.

Two more comments:

• $\psi$ could be one qubit, but it could also be longer.
• $f$ is probably a deterministic function.