2
$\begingroup$

I am currently working on Qiskit code implementing Shor algorithm in the form of a quantum circuit. I am factoring $N = 21$ (into 3 and 7) using 5 qubits, with 3 qubits in the work register and 2 in the control. The purpose is that a random integer between 2 and 20 (inclusive) will be input and the program will either use classical or quantum+classical computing to derive the factors. One thing I noticed as I was creating the circuit was that if a random number is input into the quantum subroutine, say the number 4, and there is no modular exponentiation function, just an inverse QFT on the work register, it still works and finds the period $r$, which is 6. I originally assumed this was a bug or a coding mistake, but it also made me wonder if the modular exponentiation is the same for each input.

Due to this, I have two questions: Is there a universal series of gates that can transform $x$ into $a^x \mod N$, the control register output? I was under the impression it was different depending on what $x$ was, but the results I am getting are seemingly disproving that. Similarly, for numbers as small as $N=21$, does the control register output even matter? The work register output from the inverse QFT appears to be doing all of the work, no matter if the mod. exp. function is included or not?

Picture below, approx. same for every input that reaches the quantum subroutine of Shor's algorithm in my code:

Data from a=4, with mod. exp. function commented out

Improve this question
$\endgroup$

1 Answer 1

Reset to default
3
$\begingroup$

Period finding for N=21 requires a 5 qubit work register, not 3. You need at least $\lceil \log_2 N \rceil$ work qubits. Otherwise you can't actually store intermediate values during the modular exponentiation.

You also need at least $10$ controls, not 2. If you use fewer than $\lceil 2 \log_2 N \rceil$ controls, the result doesn't actually have the necessary resolution to distinguish between different periods. That being said, you can use the standard trick of recycling the control qubits so there's only one alive at a time. But you should be expecting 10 recycling steps, not 2 recycling steps.

Using fewer than 5 work qubits, or fewer than 10 steps, or making the steps not do actual multiplications, is a clear sign that you are not running Shor's algorithm and are instead using knowledge of the factors to optimize the circuit (aka cheating). In which case you might as well just solve the problem classically and have the quantum computer flip coins so it can get a participation award.

Improve this answer
$\endgroup$
2
  • 1
    $\begingroup$ Thank you for responding so quickly. If I may slightly rephrase my question, I was wondering if the controlled U gates that are part of the quantum implementation of Shor's algorithm change based on the input. So assuming I did have the proper amount of qubits for the algorithm, the controlled U gates are, correct me if I am wrong, made up of other, simpler quantum gates. Does this series of gates change depending on the input x, from the control register? I had assumed that they were, but my (inherently flawed) testing has suggested otherwise. $\endgroup$
    – Sam_QC
    Jun 24, 2022 at 18:17
  • 1
    $\begingroup$ @Sam_QC Yes the circuit depends on the randomly chosen base and the number being factored. It doesn't technically have to but the alternative uses way more qubits and way more gates. $\endgroup$
    – Craig Gidney
    Jun 24, 2022 at 19:04

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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