Questions tagged [shors-algorithm]

Shor's algorithm, named after American mathematician Peter Shor, is a quantum algorithm for integer factorization, formulated in 1994. Informally, it solves the following problem: given an integer N, find its prime factors.

Filter by
Sorted by
Tagged with
0
votes
1answer
74 views

Why do we search for square roots of 1 in Shor's algorithm unlike the qudratic sieve?

In the quadratic sieve algorithm, the idea is to find $a$ and $a$ such that $a^2 \equiv b^2 \bmod n$. We need that $a\not\equiv \pm b \bmod n$. However, there the $c$ is not necessarily $1$. $\gcd(b \...
8
votes
3answers
284 views

Shor's algorithm caveats when $a^{r/2} =-1 \mod N$

For an integer, $N$, to be factorised, with $a$ (uniformly) chosen at random between $1$ and $N$, with $r$ the order of $a\mod N$ (that is, the smallest $r$ with $a^r\equiv 1\mod N$): Why is that in ...
4
votes
1answer
54 views

How does $x^{\frac{r}{2}} \equiv -1 \pmod {p_i^{a_i}}$ follow from “if all these powers of $2$ agree”?

Polynomial-Time Algorithms for Prime Factorization and Discrete Logarithms on a Quantum Computer (Shor, 1995) [p. 15] To find a factor of an odd number $n$, given a method for computing the order $...
6
votes
1answer
601 views

How exactly does modular exponentiation in Shor's algorithm work?

Consider the modular exponentiation part of Shor's algorithm which in many works is just referred to as $$U_{f}\sum^{N-1}_{x = 0}\vert x\rangle\vert 0\rangle = \vert x\rangle\vert a^{x}\text{ mod }N\...
4
votes
1answer
196 views

Why do we use the quantum superposition for a period instead of factors in Shor's algorithm?

I understand in Shor's algorithm we use quantum computers to find the period of a function which can then be used to find N, and we increase the probability of observing the state with the correct ...
8
votes
2answers
2k views

Why is quantum Fourier transform required in Shor's algorithm?

I’m currently studying the Shor’s algorithm and am confused about the matter of complexity. From what I have read, the Shor’s algorithm reduces the factorization problem to the order-finding problem ...
2
votes
0answers
438 views

Possible results from Shor's algorithm in practice

After reading through Shor's algorithm, I have a few questions about the probability of factoring semiprime number out. Here is some background of the question. To factor a semiprime number $N$ such ...
8
votes
1answer
1k views

How many logical qubits are needed to run Shor's algorithm efficiently on large integers ($n > 2^{1024}$)?

First, I know there are differences in logical qubits and physical qubits. It takes more physical qubits for each logical qubit due to quantum error. Wikipedia states that it takes quantum gates of ...
4
votes
1answer
158 views

Shor's algorithm effectiveness

In Shor's algorithm we require the period to be even. If the period is not even or $x^{r/2}+1 \equiv 0 \bmod N$ then we have to restart the process and pick a new random $x$. Why do we know that the ...
2
votes
2answers
483 views

Shor's algorithm beginning

This may be a silly question but at the start of Shor's algorithm to factorise a number $N$ we need to find a number $n$ such that $N^{2} \leq 2^{n} \leq 2N^{2}$ Why does such a number $n$ exist for ...
4
votes
1answer
170 views

Understanding why the modular function part of Shor's algorithm is unitary

I've been struggling to understand the modular exponent bit of Shor's algorithm. My understanding is that it takes a register in the state $\frac{1}{\sqrt{Q}}\sum_{k=1}^{Q-1} |k\rangle |0\rangle$ to ...
19
votes
3answers
3k views

What integers have been factored with Shor's algorithm?

Shor's algorithm is expected to enable us to factor integers far larger than could be feasibly done on modern classical computers. At current, only smaller integers have been factored. For example, ...
4
votes
1answer
181 views

Measuring ancillas in Shor's algorithm

When considering Shor's algorithm, we use ancilla qubits to effectively obtain the state $$\sum_x \left|x,f(x)\right>$$ for the function $f(x) = a^x \mod N$. As I have learned it, we then measure ...
2
votes
1answer
172 views

Is this the correct quantum circuit for the order-finding algorithm?

The algorithm is being implemented on Cirq, with the goal of finding the smallest $r$ for cooprime numbers $x$ and $N$ satisfying the equation $x^r \ = \ 1($mod $N)$. I have set $x \ = \ 2$ and $N \ = ...
2
votes
0answers
90 views

Would this quantum algorithm implementation work?

I am trying to implement the order finding algorithm on Cirq finding the minimal positive $r$ for coprime $x$ and $N$ satisfying the equation $x^r \ = \ 1$(mod$ \ N$). In my case, I have set $x \ = \ ...
1
vote
1answer
232 views

How can Shor's algorithm be used to crack 32 bit RSA Encryption? [closed]

I have this as my minor project and plan to use Shor' Algorithm for factorization to figure out the $p$ and $q$ factors for cracking. Although I understand the theoretical part, I am having some ...
4
votes
2answers
229 views

Do the probability amplitudes of the superposition state produced by the QFT transform convey useful information?

I have been studying on Quantum Fourier Transform (QFT) by myself, and I am little bit confused about how could QFT be used. For example, if the QFT of three quantum bits is $a_1|000\rangle + ...
4
votes
1answer
257 views

How many qubits does it take to break a 10 characters password?

Let's assume we developed a hashcat-like programs for quantum computer. How many qubits we need to find the correct hash (WPA, MD5,...) from a 10 characters password make from upper, lower & ...
9
votes
2answers
2k views

Simplified explanation of Shor/QFT transformation as thumbtack

As a non-mathematician/software programmer I'm trying to grasp how QFT (Quantum Fourier Transformation) works. Following this YouTube video: https://www.youtube.com/watch?v=wUwZZaI5u0c And this ...
8
votes
1answer
328 views

Entanglement in Shor's algorithm

One deals with the notion of superposition when studying Shor's algorithm, but how about entanglement? Where exactly does it appear in this particular circuit? I assume it is not yet present in the ...
5
votes
1answer
200 views

Confusion about random sampling of integers in Shor's algorithm

My understanding of Shor's algorithm is that you have to carry out the following steps if you are trying to factor $N$: Chose a random number less than $N$. Let's call it $a$. Calculate the period ...

1
2