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
5 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
  • 34.9k
-1 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
2 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