1
$\begingroup$

I'm a noob in quantum computing and I'm trying to get Shor's algorithm working on Q# (the language is unrelated). However, I'm stuck on computing $f(x)$s in the quantum circuit. Let $N\sim \log_2(n)$ be the number of qubits needed for finding the period. As far as I know, we can initialize $s=1$, and multiply it with $a,a^2,a^4 \cdots a^{2^{N-1}} \mod n$ according to the $N$ control qubits. However, all methods I can think of needs around $O(N^2)$ modulus and thus $O(N^2)$ ancillary clean qubits (for example, compute $a,a^2,a^4 \cdots a^{2^{N-1}}\mod n$ beforehand, use additions, comparing numbers and subtracting accordingly). Is there a way to implement modulus as some reversible circuit? Or, am I all wrong?

$\endgroup$
3
$\begingroup$

There is no circuit that performs the mod operation reversibly. You need to keep your numbers mod'ed the whole time. For example, instead of using an adder and then attempting to mod, use a fundamentally modular adder.

There's actually quite a lot of detail that goes into constructing these circuits. Too much for an answer here. A preprint that goes through all the details (and had working ProjectQ code at the time) is "Factoring with n+2 clean qubits and n-1 dirty qubits".

Here's a few example diagrams:

enter image description here

enter image description here

Note that the constructions are really going out of their way to avoid using ancillae, so they often have not-so-great gate counts.

And here's one to reinforce the point that it's complicated:

enter image description here

|improve this answer|||||
$\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.