We’re rewarding the question askers & reputations are being recalculated! Read more.

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
1
vote
0answers
33 views

Suggestions for hybrid factoring algorithm on DWave and Qiskit

I was wondering if the multi-prime factoring problem can be solved in a hybrid approach using DWave (to factor) and Shor's algorithm (in Qiskit)? Please let me know your thoughts. Thanks!
4
votes
1answer
50 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
0answers
166 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 ...
5
votes
2answers
121 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 ...
4
votes
0answers
41 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
1answer
101 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.
3
votes
1answer
115 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
89 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?
0
votes
1answer
43 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 \...
1
vote
1answer
42 views

Confusion regarding probability of period resulting in factoring

This is a sequel to 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 ...
4
votes
1answer
39 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
129 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 ...
10
votes
3answers
234 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?
5
votes
1answer
262 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\...
2
votes
0answers
249 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
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 ...
6
votes
1answer
142 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 ...
4
votes
1answer
120 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 ...
6
votes
1answer
567 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 ...
2
votes
2answers
449 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
115 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 ...
5
votes
1answer
132 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$ ...
2
votes
1answer
100 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 \ = ...
6
votes
1answer
218 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 $...
2
votes
0answers
84 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 \ = \ ...
2
votes
1answer
91 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 ...
7
votes
1answer
166 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 ...
4
votes
2answers
156 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 + ...
1
vote
1answer
153 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
1answer
166 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 & ...
25
votes
2answers
968 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 ...
8
votes
2answers
1k 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 ...
4
votes
1answer
125 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 ...
8
votes
1answer
215 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 ...
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, ...
5
votes
1answer
145 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 ...
8
votes
3answers
218 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
2answers
462 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 ...