Skip to main content
Share Your Experience: Take the 2024 Developer Survey

Questions tagged [factorization]

Questions regarding quantum algorithms that factorize numbers, finding smaller integer factors or prime factors such as in Shor algorithm.

Filter by
Sorted by
Tagged with
1 vote
1 answer

Why circuit in Shor algorithm differs for different factorized numbers?

I recently started studying quantum algorithms, and I have a question about Shor algorithm. I have been reading Qiskit documentation and other books and articles, I felt like it was changing the ...
momo's user avatar
  • 13
3 votes
1 answer

Benefits of using quantum encrypted keys

Considering, in a perfect world everyone has the capability to create a quantum key. What would the benefits of using quantum encrypted keys instead of using classically encrypted keys? Besides the ...
Snarz's user avatar
  • 31
2 votes
1 answer

Practical implementation of Shor and other factoring algorithms

I explore the realm of open-source quantum computers, particularly those available in the current or near-term future. My goal is to implement the largest possible integer factorizations. I would ...
ali khosravi's user avatar
3 votes
1 answer

Bound on success Probability for Regev's factoring algorithm

Theorem 4.1 in Regev's paper talks about a theorem due to Pomerance as follows: Theorem 4.1: Suppose G is a finite abelian group with minimal number of generators $r$. Then, when choosing elements ...
Manish Kumar's user avatar
11 votes
1 answer

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

[Note that this was originally asked on April 1, 2024, also known as April Fool's day in many Western nations] I'm hearing some rumors that a combination of neutral atoms (Lukin's group?), in ...
Mark Spinelli's user avatar
6 votes
1 answer

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

Background Phase estimation circuits prepare $n$ qubits $Q_0, \dots, Q_{n-1}$ in the $|+\rangle$ state, then apply $U^{2^q}$ controlled by $Q_q$ for each $q$, then apply a quantum Fourier transform, ...
Craig Gidney's user avatar
  • 37.6k
-2 votes
1 answer

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

I neither have a background in QC, higher mathematics (calculus) and nor have I gone through the literature about the field. As a layman what catches my attention is that people say that quantum ...
lousycoder's user avatar
2 votes
1 answer

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

I'm struggling to understand the last part of Shor's algorithm, to be exact the point when we found $x-1$, $x+1$ with $x-1 ≠ 0\mod N$, $x+1 ≠ 0 \mod N$ and $(x+1)(x-1) = 0 \mod N$. Then, $gcd(x-1, N) &...
leonboe1's user avatar
  • 135
2 votes
0 answers

Does a solution to SAT solve the HSP for $S_N$, $D_{2N}$, or even the general case?

I often hear about the graph isomorphism problem reducing to the HSP with the symmetric group and a mapping $f \colon \pi \in S_N \mapsto \pi(G)$ with $G$ being some graph (the union of the graphs we’...
Andrew Baker's user avatar
1 vote
1 answer

Implementing a HSP for Graph Isomorphism in the Quantum Circuit Model

The HSP (Hidden Subgroup Problem) links many NP-intermediate problems, such as factoring, graph isomorphism, and shortest vector. The brief problem statement is presented like so: Given some group, G,...
Andrew Baker's user avatar
4 votes
1 answer

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

We know that it is possible to factor large numbers on a quantum computer using Shor's algorithm. But how about simply using a multiplication circuit in reverse? The idea is to build a multiplication ...
njoyeux's user avatar
  • 49
1 vote
0 answers

How to factorize a big number using Shor's algorithm with Qiskit

There is codes for only modulus 15 in textbook. (function c_amod15) So I tried to use the function Shor in library (...
Kay's user avatar
  • 11
2 votes
1 answer

Speed versus number of qubits for RSA factorization

I'm trying to gain a better understanding of the requirements for successful 2048-bit RSA key factorization in relation to time needed versus qubits available. For this I have some questions that ...
tulapia's user avatar
  • 23
3 votes
1 answer

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

I know about the answer of a similar question here: Reason for evaluating $a^x \bmod N$ from $x = 0$ to $N^2$. But the answer there seems to explain the reason in terms of real qubits (chance of them ...
Gustavo Mirapalheta's user avatar
3 votes
1 answer

Probability of success proof for Shor's algorithm

In the book "Quantum Computation and Information" by Nielsen and Chuang, Shor's algorithm is presented with a related probability of success theorem and proof found on page 634, Theorem A4....
Gabe Richardson's user avatar
1 vote
1 answer

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

Quoting Wikipedia: No algorithm has been published that can factor all integers in polynomial time, that is, that can factor a $b$-bit number $n$ in time $O(b^k)$ for some constant $k$. Neither the ...
blunova's user avatar
  • 201
9 votes
2 answers

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

One of the fundamental elements of Shor's algorithm is the calculation of the function: $$ f_a(r) = a^r (mod \ N) $$ where $N$ is the number to be factored and $a$ is a number chosen with some ...
Doriano Brogioli's user avatar