2
$\begingroup$

How does this circuit map $|x\rangle$ to $|7x \space mod15\rangle$? Looking into Shor's and I thought that phase kickback causes the modular exponentiation part to be mapped onto the measurement qubits through the Fourier basis. enter image description here

$\endgroup$
3
$\begingroup$

Applying a NOT gate to every qubit in an $n$ bit register performs the transformation $f(x) = 2^n - 1 - x$. In this case that's $f(x) = 16-1-x = -x \pmod{15}$. So the NOT gates are equivalent to negating.

The triplets of CNOTs are performing swaps and the swaps implement a right-rotate:

enter image description here

An $n$ bit right-rotate is equivalent to multiplying by the multiplicative inverse of 2 mod $2^n-1$, which is $8$ in our case.

Together these two multiplications multiply by $-1 \cdot 8 = -8 = -8 + 15 = 7 \pmod{15}$.

Note that the circuit isn't quite correct. There is a degeneracy where $|0\rangle$ is mapped to $|15\rangle$ instead of $|0\rangle$. In the general case, unexpected information could leak into this degeneracy and decohere when the register is measured. But in the context of Shor's algorithm you know the register has no overlap with $|0\rangle$ so it's fine.

Also note that if your qubits are not restricted to linear connectivity, you can make the circuit shallower by running two of the swaps in parallel:

enter image description here

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.