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
26
votes
2answers
1k views

Has there been any truly ground breaking advance in quantum algorithms since Grover and Shor?

(Sorry for a somewhat amateurish question) I studied quantum computing from 2004 to 2007, but I've lost track of the field since then. At the time there was a lot of hype and talk of QC potentially ...
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, ...
10
votes
3answers
452 views

Does Shor's algorithm end the search for factoring algorithms in the quantum world of computation?

In other words, will factoring research remain solely in the classical world or are there interesting research on-going in the quantum world related to factoring?
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
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 ...
8
votes
2answers
502 views

How do quantum computers prevent “quantum noise”?

On the Wikipedia page for Shor's algorithm, it is stated that Shor's algorithm is not currently feasible to use to factor RSA-sized numbers, because a quantum computer has not been built with enough ...
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 ...
8
votes
3answers
283 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 ...
8
votes
1answer
317 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 ...
8
votes
2answers
369 views

Shor's algorithm weaknesses & uniqueness of close rational

I'm working through a problem set, and am stuck on the following problem: a) What can go wrong in Shor’s algorithm if Q (the dimension of the Quantum Fourier Transform) is not taken to be ...
7
votes
2answers
393 views

Does the quantum Fourier transform have many applications beyond period finding?

(This is a somewhat soft question.) The quantum Fourier transform is formally quite similar to the fast Fourier transform, but exponentially faster. The QFT is famously at the core of Shor's ...
7
votes
1answer
737 views

Is it possible to run a general implementation Shor's algorithm on a real IBM quantum computer at least for N = 15?

I need to make a general implementation of Shor's algorithm that factors, at least, N = 15. I have been able to perform an implementation that works in simulators, with ProjectQ, but when running it ...
7
votes
0answers
59 views

What are the thermodynamic limits of Shor's algorithm

The asymptotic time complexity of Grover's algorithm is the square root of the time of a brute force algorithm. However, according to Perlner and Liu, the thermodynamic behavior (theoretical minimum ...
6
votes
1answer
182 views

What happens with first phase factor in QFT?

I'm using Mermin's Quantum Computer Science book to understand Shor's algorithm, but I can't figure out why one of the phase factors drops out of the probability for measuring a certain y. This is ...
6
votes
1answer
567 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\...
6
votes
1answer
349 views

Why is this implementation of the order finding algorithm not working?

I asked a question about this earlier, but I am still coming across problems in my algorithm implementation. I am trying to implement the order finding algorithm on Cirq finding the minimal positive $...
6
votes
0answers
113 views

Calculating power of a quantum computer — RSA

As discussed in this question, the expected security of 1024-bit RSA is 80-bits: NIST SP 800-57 §5.6.1 p.62–64 specifies a correspondence between RSA modulus size $n$ and expected security strength ...
5
votes
2answers
483 views

Is there a simple, formulaic way to construct a modular exponentiation circuit?

I'm a newcomer to quantum computing and circuit construction, and I've been struggling to understand how to make a modular exponentiation circuit. From what I know, there are several papers on the ...
5
votes
1answer
247 views

Expected repetitions of the quantum part of Shor's algorithm

Shor's algorithm to factor a number $N$ goes as follows: Pick a random value $b \in (0, N)$. Use a specific quantum computation to a sample a value $v$ that should be close to $2^{m} k/p$ where $m$ ...
5
votes
1answer
199 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 ...
5
votes
2answers
64 views

Is there a general order finding quantum algorithm for a given a and N?

I'm trying to construct a general circuit for Shor's algorithm in Qiskit. I understood the later parts of the circuit (inverse QFT and QPE), but can't really understand the order finding. For example, ...
4
votes
2answers
221 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
153 views

Why is the size of the top register for Shor's algorithm chosen as it is?

Let $N$ be the number we're trying to factor. In Shor's algorithm, the top register then has $2 \lceil\log_2(N)\rceil+1$ qubits, while the bottom register (the ancilla qubits) has $\lceil\log_2(N)\...
4
votes
1answer
297 views

Why should we use inverse QFT instead of QFT in Shor's algorithm?

Why should we use inverse QFT instead of QFT in Shor's algorithm? When I tried to simulate Shor's algorithm for small numbers, I got an answer even when I used just QFT instead of inverse QFT.
4
votes
1answer
73 views

What do empty white circles mean in a quantum circuit?

I'm studying Shor's algorithm. but I see from the beginning this empty circle. what this circle means??
4
votes
1answer
156 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 ...
4
votes
1answer
174 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 ...
4
votes
1answer
250 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 & ...
4
votes
1answer
53 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 $...
4
votes
1answer
191 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 ...
4
votes
1answer
165 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 ...
4
votes
1answer
86 views

How to write a classical version of Shor's algorithm

For learning purposes, I would like to write a classical version of Shor's algorithm. From what I have read, what makes this algorithm fast is the quantum FFT, which is used to find the period of the ...
4
votes
1answer
72 views

How to measure entanglement in an algorithm?

Entanglement in Algorithms Most algorithms in quantum computing find their strength in making use of entanglement. I am interested in evaluating the amount of entanglement generated within an ...
4
votes
1answer
130 views

Energy cost of quantum computation

A quantum computer can be modeled as a single unitary transition of a (large) effective quantum state to another. In order to get errors under control, quantum error correction is assumed. A logical ...
4
votes
0answers
46 views

Can anybody explain or suggest a good reference on how to make a modular exponentiation circuit for N=15 with any coprime base?

I have read many papers related to it but in every paper, they just show the circuit of order finding algorithm for N=15, but did not explain what is the procedure to make it. It will be great if ...
3
votes
5answers
156 views

Any other quantum algorithms than Jozsa-Deutsch decision algorithm, Grover search algorithm, Shor factorization algorithm?

I have been working on implementing Jozsa-Deutsch decision algorithm, Grover search algorithm, Shor factorization algorithm on my home-made 2 qubits device. I am wondering if there are any other ...
3
votes
2answers
132 views

What is Quantum Phase Estimation in Shor's Algorithm?

While I'm studying Algorithm, I couldn't understand what Quantum Phase Estimation is. And I heard there is relation between Phase-Kickback and Quantum Phase Estimation. I wonder what it is. Also, I'm ...
3
votes
1answer
324 views

Implementing QFT for Shor's Algorithm?

I'm studying Shor's algorithm. This diagram shows a calculation of $4^x\mod21$. I don't understand how this expresses $4^x \mod21$. Could you explain this? For example, by showing another calculation ...
3
votes
1answer
100 views

Reason for evaluating $a^x \bmod N$ from $x = 0$ to $N^2$

As per the Shor's algorithm, we need to evaluate $a^x \bmod N$ from $x = 0$ to $N^2$. What is the reason for this? Why can't we just evaluate for $N$, $2N$ or something like that?
3
votes
1answer
63 views

Eigenvectors and eigenvalues of the gate $U_a:|s\rangle\mapsto|sa \bmod N\rangle$

I'm studying Shor algorithm. This is a demostration about the eigenvectors and eigenvalues of $U_a$ gate: Can somebody explain me from the third step to the last?
3
votes
1answer
189 views

Are there any other published quantum factoring algorithms that are simpler or more efficient than Shor’s?

How many qubits and what is the minimum number of gate operations needed to factor an n-bit integer? Are there any other published algorithms that are simpler or more efficient?
3
votes
1answer
224 views

Problem with Shor's factoring algorithm [closed]

I'm trying to figure out the Shor's factoring algorithm. References i've been using wikipedia page, the book Quantum Computer Science by David Mermin and the orignal paper(1996) By Peter Shor. I ...
3
votes
0answers
70 views

Question Regarding Quantum Period-Finding Fourier Transform Approximation

I am following the 5.4.1 Period-Finding Algorithm in Nielsen and Chuang as shown below: My confusion lies with the second expression of point 3 in the procedure. Why is the second expression an ...
2
votes
2answers
480 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 ...
2
votes
2answers
123 views

Quantum computers don't try all the possible solutions, so how does the QFT really work?

Scott Aaronson is fond of saying "Quantum computers do not solve hard search problems instantaneously by simply trying all the possible solutions at once." That is, they are not non-deterministic ...
2
votes
2answers
30 views

In Shor's algorithm, how can we guarantee that each controlled-U will kickback to the same eigenvalue?

I'm studying the Shor algorithm as part of my thesis and have a question about the "measured" phases after the QPE. So, I take the controlled-U operations on the second register and in cause ...
2
votes
1answer
169 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
1answer
106 views

Lesser qubit computer doing the parts of Shor's against e.g., RSA-2048 sized prime

After posting this question to Physics, it became pretty clear I should have posted here. So: How might a (e.g.) 72-bit crypto-relevant quantum computer attack RSA-2048? Bonus: how might that be ...
2
votes
1answer
48 views

Why can I use the Sum of Eigenvectors for Phase Estimation in Shor

In phase estimation, we start by using an eigenvector $\newcommand{\ket}[1]{\lvert#1\rangle}\ket u$ to find the corresponding eigenvalue lambda. So far so good. In the order finding algorithm, we also ...
2
votes
1answer
99 views

Shor algorithm - how to obtain a period from diagram?

I'm studying shor's algorithm. I implemented in Qiskit and apriori I know that a period is 3 in my example. However, unless I know about period, how to obtain this period only according to seeing ...