New answers tagged

1 vote

Practical implementation of Shor and other factoring algorithms

I would say that it is not possible to give a proper answer to this question since the problem instances that may potentially be tractable by present-day quantum computers are too small: As ...
Martin Ekerå's user avatar
3 votes

Possible results from Shor's algorithm in practice

Shor's lower bound [Shor94] [Shor97] essentially goes as follows: Shor proves that the probability that $r$ is even and that $x^{r/2} \not\equiv -1 \:\: (\text{mod } N)$ is at least $1/2$ when $x$ is ...
Martin Ekerå's user avatar
8 votes
Accepted

(April Fools 2024) Where can we find out more details about the recent factoring of RSA-2048?

It is likely an April fools joke Factoring RSA-2048 will require billions of qubits, or thousands of very "clean" qubits in a quantum computer that operates so well that it doesn't need ...
user1271772 No more free time's user avatar
4 votes
Accepted

What is stopping FACTORING from being BQP-complete?

At a rigorous level, nothing is necessarily stopping any of these things, because no one can even prove that P≠PSPACE. If P=PSPACE, then every problem in P is BQP-complete as well as NP-complete, ...
Greg Kuperberg's user avatar

Top 50 recent answers are included