# Tag Info

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 ...
• 47.1k
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$. ...
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, ...
• 3,331
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 ...
• 1,661

### 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....
• 22.4k

### 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 ...
• 47.1k
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 ...
• 2,159
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 ...
• 4,728
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 ...
• 22.4k
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 ...
• 226
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-...
• 22.4k

### 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 ...
• 12k
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 ...
• 8,091
Accepted

### Simplified explanation of Shor/QFT transformation as thumbtack

Let me attempt to give a rather unconventional answer to this question: ...
• 551
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 ...
• 47.1k
Accepted

• 12k

### What integers have been factored with Shor's algorithm?

The size of the number factored is not a good measure for the complexity of the factorization problem, and correspondingly the power of a quantum algorithm. The relevant measure should rather be the ...
• 4,997
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 ...
• 47.1k
Here's, surely, a very non-optimal way of doing it. Imagine we have a unitary $V$ which performs the operation $$V|x\rangle|y\rangle=|x\rangle|xy\text{ mod }N\rangle.$$ We can deal with how $V$ ...