I want to perform constant-quantum modular addition: $|x\rangle \mapsto |x + K \bmod R \rangle$ where the input $x$ can be greater than $R$. E.g. For $K=1, R=10$ the input $|11 \rangle$ should map to $|(11+1) \bmod 10 \rangle = |2\rangle$. When I try this in quirk, the input remains unchanged because it is greater than the modulus $R$. Is there an easy pre-processing trick to perform this operation?
1 Answer
$\begingroup$
$\endgroup$
1
If the number is a classical constant, you should just preprocess it to be smaller than the modulus. If it's stored in a quantum register, you can perform long division under superposition to split it into the remainder and the quotient.
Long division is done by computing if the target is larger than $\text{modulus} \cdot 2^n$ for the largest possible $n$ (given the number of qubits being used to store the integer) then subtracting that value from the target conditioned on the result of the comparison. As this is iterated, the comparison qubits form the quotient and the qubits in the target form the remainder.
-
$\begingroup$ Any thoughts on how to do a 1-step subtraction with 1 dirty ancilla? (I realised my modulus is always between $2^{n-1}$ and $2^n$. So I only need to do 1 step of long division.) $\endgroup$V. Patel– V. Patel2025-08-08 06:10:54 +00:00Commented Aug 8 at 6:10