1
$\begingroup$

I recently started studying quantum algorithms, and I have a question about Shor algorithm.

I have been reading Qiskit documentation and other books and articles, I felt like it was changing the quantum circuit every time the number N to be factored to primes changed.

What is the critical difference, if any, between those quantum circuits?

Improve this question
$\endgroup$
2
  • 1
    $\begingroup$ Note that the circuit obviously has to change when $N$ changes: If the circuit is independent of $N$, its output cannot possibly aid you in factoring $N$. $\endgroup$
    – Martin Ekerå
    Commented May 14 at 19:58
  • $\begingroup$ the input of Shor's algorithm (ie quantum period finding) are $N$ and a coprime $a$. So the algorithm has to somehow encode these inputs to have an output that depends on them, and that means that the circuit itself has to depend on $a$ and $N$. $\endgroup$
    – glS ♦
    Commented Jul 22 at 8:36

1 Answer 1

Reset to default
-1
$\begingroup$

Shor's algorithm can vary based on the number you're trying to factorize. The main reason for this variation is the choice of parameters in the algorithm, particularly the choice of the integer N you want to factorize.

The critical difference in the quantum circuits lies in the size of the quantum registers and the number of qubits required to represent the factors of N adequately (I like to think this as needing more bits to represent a larger number in binary). In Shor's algorithm, you typically have two main registers: one for holding the quantum state that encodes the periodic function, and the other for storing the ancillary qubits used in the quantum Fourier transform (QFT) and other computational steps.

The number of qubits needed in these registers depends on the size of the number N you're trying to factorize. Larger N values require more qubits, and thus, the quantum circuit would need to be adjusted accordingly to accommodate these extra qubits.

Additionally, the parameters for the quantum operations, such as the number of iterations in the quantum modular exponentiation and the precision of the QFT, may also vary depending on N. These parameters are typically chosen to ensure the algorithm's success probability and efficiency.

Improve this answer
$\endgroup$
0

Your Answer

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

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