Skip to main content
Share Your Experience: Take the 2024 Developer Survey
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
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
  • 22.9k
6 votes
Accepted

Speed versus number of qubits for RSA factorization

[Are] a minimum of 6152 (logical) qubits is required to achieve the capacity of factoring 2048 bit long integers[..]? No, we intentionally used more logical qubits than needed because that reduced ...
Craig Gidney's user avatar
  • 37.8k
4 votes

Is QFT qubit recycling compatible with Zeckendorf's Fibonacci representation of integers?

My spontaneous off-the-bat reply would be no — and even if control qubits can be recycled, then it would be towards the end of the quantum algorithm, and the advantage would then not be that great. ...
Martin Ekerå's user avatar
4 votes

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
Accepted

Bound on success Probability for Regev's factoring algorithm

This is just Markov's inequality that states that for a positive random variable $X$ and $a > 0$ then $$ P( X \geq a ) \leq \frac{E(X)}{a}. $$ see the wikipedia: https://en.wikipedia.org/wiki/...
Frederik Ravn Klausen's user avatar
3 votes
Accepted

In Shor's algorithm, why do we have ${\rm gcd}(x\pm 1, N) > 1$?

The assumptions $x\pm1\neq0\bmod N$ mean that neither of them is a multiple of (or equal to) $N$. That is, you cannot write $x+1=kN$ for some $k\in\mathbb{Z}$, and same for $x-1$. At the same time, $(...
glS's user avatar
  • 25.4k
3 votes

Probability of success proof for Shor's algorithm

TL;DR This is a consequence of the Chinese Remainder theorem and the fact that in any group if $g^k$ is the identity then the order of $g$ divides $k$. Setup We are factoring an odd composite ...
Adam Zalcman's user avatar
  • 22.9k
3 votes
Accepted

Would the interest in building quantum computers decrease if a classical algorithm for factoring all integers in polynomial time is discovered?

This depends on a few factors, excuse the pun. This is already an unlikely scenario, with several associated unlikely variants. Even if Integer Factorization is in P and said algorithm is discovered ...
Joseph Geipel's user avatar
2 votes

Calculate the period (like in Shor's algorithm) from the factors?

I would have written a comment to extend on Sam's answer, but since I am seemingly not able to do this since I seldom use this forum, I will write a follow-up answer here instead: If you wish to ...
Martin Ekerå's user avatar
2 votes

Calculate the period (like in Shor's algorithm) from the factors?

I second the comment that this would be a straightforward exercise in an introductory number theory course, and if you're thinking about Shor's algorithm in this way, an introductory number theory ...
Sam Jaques's user avatar
  • 2,066
2 votes
Accepted

Do quantum computing principles have a theoretical or hypothetical potential to solve factorial time problems?

There are problems for which quantum computing provides an exponential speedup. As you correctly stated, a prominent example is factorization. However, the speedup heavily depends on the kind of ...
Lars's user avatar
  • 36
2 votes

Benefits of using quantum encrypted keys

A classical asymetric cipher is based on computationaly hard problems (assumed to be as so far we have not found an efficient algorithm). This means that classical computer is believed to be incapable ...
Martin Vesely's user avatar
1 vote
Accepted

Why circuit in Shor algorithm differs for different factorized numbers?

Shor's algorithm is indeed fascinating, but its implementation can vary based on the number you're trying to factorize. The main reason for this variation is the choice of parameters in the algorithm, ...
Shravan Patel's user avatar
1 vote
Accepted

Implementing a HSP for Graph Isomorphism in the Quantum Circuit Model

What do you mean that we cannot "represent an input to this oracle as a bitstring"? For example we could have the basis states in our Hilbert space be the adjacency matrices over $N$ ...
Mark Spinelli's user avatar
1 vote

Why to evaluate a N period function we need to go up to N^2 and not just up to 2N

It's because the difference between fractions with denominators $\leq N$ can be as small as $1/N^2$, and the closest fractions always have different denominators, and your goal is to learn the ...
Craig Gidney's user avatar
  • 37.8k

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