24 votes
Accepted

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

The question is about how many logical qubits it takes to implement Shor's algorithm for factoring an integer $N$ of bit-size $n$, i.e., a non-negative integer $N$ such that $1 \leq N \leq 2^n{-}1$. ...
MartinQuantum's user avatar
22 votes
Accepted

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

Have there been any truly ground breaking algorithms besides Grover's and Shor's? It depends on what you mean by "truly ground breaking". Grover's and Shor's are particularly unique because they ...
DaftWullie's user avatar
  • 55.7k
15 votes
Accepted

What integers have been factored with Shor's algorithm?

The prime factorization of 21 (7x3) seems to be the largest done to date with Shor's algorithm; it was done in 2012 as detailed in this paper. It should be noted, however, that much larger numbers, ...
auden's user avatar
  • 3,399
13 votes

Are there any uses for Shor's algorithm other than breaking public key cryptography

A bit of an esoteric answer: there is a particular proposal for post-quantum cryptography called "CSI-FiSh", based on isogenies. Without getting too deep into the number theory, the ...
Sam Jaques's user avatar
  • 1,994
12 votes

Are there any uses for Shor's algorithm other than breaking public key cryptography

community wiki It's an interesting question to pose which problems reduce to factoring (or discrete log), and whether any of those problems could be of practical value. In general I think the ...
10 votes
Accepted

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

Asymptotically, Shor's algorithm is really efficient. Basically it's just: superposition, modular exponentiation (the slowest step), and a fourier transform. Modular exponentiation is what you do to ...
Sam Jaques's user avatar
  • 1,994
10 votes
Accepted

How to show that amount of qubits needed to crack the RSA-2048 protocol using Shor's algorithm?

I assume you mean the result from this paper, where the authors (including 'our very own' Craig Gidney) have estimated that if you have $\sim20$ million noisy qubits it would take you around $8$ hours ...
JSdJ's user avatar
  • 5,369
10 votes
Accepted

A necessary and sufficient condition for the existence of a nontrivial square root in Shor's algorithm

Every number with at least two odd factors has non-trivial square roots. You get the non-trivial square roots by breaking them down into $\pm 1$ square roots for each factor and applying the Chinese ...
Craig Gidney's user avatar
  • 33.3k
9 votes

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

You probably shouldn't be thinking of the Quantum Fourier Transform as being something where you want to extract the outcoming probability amplitudes. As you say, when you start measuring, you destroy ...
DaftWullie's user avatar
  • 55.7k
9 votes

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

For Shor's algorithm, it actually doesn't matter which one you use. If you apply the QFT twice, it is equivalent to a classical multiplication by -1 modulo $2^n$ where $n$ is the size of the register....
Craig Gidney's user avatar
  • 33.3k
9 votes
Accepted

When increase the shot, why the result is different?

In general, the number of shots does not increase the accuracy of an experiment. Rather it gives a more precise answer. Attached is a figure showing the distance (in terms of Hellinger distance) for ...
Paul Nation's user avatar
  • 2,239
9 votes
Accepted

Can we avoid repetition in Shor's algorithm by using the quadratic formula?

I think you're right. Your idea is kind of similar to how the factoring in "How to factor 2048 bit RSA integers in 8 hours using 20 million noisy qubits" is done, except in that paper the p+...
Craig Gidney's user avatar
  • 33.3k
9 votes

Can we avoid repetition in Shor's algorithm by using the quadratic formula?

Since Craig referenced me in his answer, I will chime in and follow up a bit on what Craig wrote. Since there are several sub-questions to your question, I will answer in parts: First, to answer your ...
Martin Ekerå's user avatar
8 votes
Accepted

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

In a nutshell, the number of qubits in the top register directly corresponds to the number of bits of precision to which $x/T$ approximates $s/r$, and we need enough precision to be able to determine $...
John Watrous's user avatar
  • 5,158
8 votes
Accepted

Why doesn't Shor's algorithm output a solution for some numbers?

If $f(x) = a^x \pmod{N}$ passes through $-1$, that value of $a$ won't work. For example, $a=2$ fails for $N=33$ because $2^5 = 32 \equiv -1 \pmod{33}$. This should have been mentioned in whatever ...
Craig Gidney's user avatar
  • 33.3k
8 votes

Can numbers be factored by using a reverse multiplication circuit on a quantum computer?

Remember that the unitary portion of any quantum algorithm is necessarily reversible. On the other hand, the map $f(x,y)\mapsto x\cdot y$ which sends two integers to their product is not. This is ...
Adam Zalcman's user avatar
  • 20.8k
7 votes
Accepted

Simplified explanation of Shor/QFT transformation as thumbtack

Let me attempt to give a rather unconventional answer to this question: ...
arriopolis's user avatar
7 votes
Accepted

Measuring ancillas in Shor's algorithm

Is that correct? Is it [not] necessary to measure the ancilla qubits in Shor's algorithm? Correct, it is not necessary to measure the ancillae. This is easily seen by appealing to the no-...
Craig Gidney's user avatar
  • 33.3k
7 votes

Where exactly does entanglement appear in Shor's algorithm?

Your question contains the answer, as you mention the controlled-U gate which is an entangling gate. You will see in the page I linked, that the action of c-U on $|+\rangle|0\rangle$ for example can ...
user1271772's user avatar
  • 13.5k
7 votes
Accepted

How do quantum computers prevent "quantum noise"?

How do we prevent quantum noise in a quantum computer? Well, technically the answer is (at least for most systems): we use ridiculously low temperatures (much colder than space), we shield everything ...
3244611user's user avatar
7 votes
Accepted

Expected repetitions of the quantum part of Shor's algorithm

The number of runs required is arbitrarily close to 1, using the correct post-processing. See "On the success probability of quantum order finding" by Martin Ekerå from Jan 2022: We prove a ...
Craig Gidney's user avatar
  • 33.3k
7 votes

Expected repetitions of the quantum part of Shor's algorithm

This self-answer gives a not-very-good worst case analysis. I'd really rather have a proper distribution of repetition counts. Probability of a period resulting in factoring In Shor's original paper,...
Craig Gidney's user avatar
  • 33.3k
7 votes
Accepted

In Shor's factorization algorithm for $N$, why can we always find $n$ such that $N^2\le 2^n\le 2N^2$?

Let's represent $N^2$ as $2^a+b$, where $a$ is the greatest power of 2 that not exceeds $N^2$, and $b \ge 0$ (which is always possible to do - $a$ is just the number of bits in binary representation ...
Mariia Mykhailova's user avatar
7 votes
Accepted

What happens with first phase factor in QFT?

If you have a quantum state like $$|\Psi\rangle_n = a_0|0\rangle_n+a_1|1\rangle_n+...+a_n|2^n-1\rangle_n$$ and you measure it in the $\{|0\rangle_n,...,|2^{n-1}\rangle_n\}$ basis, then the probability ...
Sanchayan Dutta's user avatar
7 votes
Accepted

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

The essential feature of this problem is that while both the quantum and classical algorithms can make use of the efficient classical function of calculating $a^k\text{ mod }N$, the issue is how many ...
DaftWullie's user avatar
  • 55.7k
7 votes
Accepted

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

Given that the QFT is exponentially faster than the FFT, The problem with quantum computing is that they are not actually parallel computers: One is tweaking the qubits in such a way that when ...
emacs drives me nuts's user avatar
6 votes
Accepted

Shor's algorithm effectiveness

Check out Thoerem 5.3 in Nielsen and Chuang. It conveys that we are almost guaranteed to get a good value of $x$ (the probability is stated to be at least $1-\frac{1}{2^m}$ where there are $m$ unique ...
DaftWullie's user avatar
  • 55.7k
6 votes
Accepted

Confusion about random sampling of integers in Shor's algorithm

You skipped a step in the algorithm. First check if $N$ is even. $35$ is not even. Next determine if $N=a^b$ for $a \geq 1$ and $b \geq 2$. It's not. Randomly choose $x$ in the range $1$ to $N-1$. If ...
Andrew O's user avatar
  • 1,729
6 votes

What integers have been factored with Shor's algorithm?

For Shor's algorthm: State of the art is still 15. In order to "factor" 21 in the paper Heather mentions, they had to use the fact that $21=7\times 3$ to choose their base $a$. This was explained in ...
user1271772's user avatar
  • 13.5k

Only top scored, non community-wiki answers of a minimum length are eligible