Questions tagged [shors-algorithm]
Shor's algorithm, named after American mathematician Peter Shor, is a quantum algorithm for integer factorization, formulated in 1994. Informally, it solves the following problem: given an integer N, find its prime factors.
165
questions
11
votes
3
answers
2k
views
Are there any uses for Shor's algorithm other than breaking public key cryptography
This question may be slightly opinion based, so I apologise if this is the incorrect place to ask.
My question is, is there any use for Shor's integer factorisation algorithm other than for breaking ...
- 329
2
votes
1
answer
45
views
Why is the following exponential ignored (or equals 1) in the probability amplitude?
I'm reading Ronald de Wolf's lecture notes and when explaining Shor's algorithm on page 40 after applying a QFT to
$$
\frac{1}{\sqrt{m}} \sum_{j=0}^{m-1} |jr+s\rangle
$$
the following expression is ...
- 123
8
votes
2
answers
1k
views
Can we avoid repetition in Shor's algorithm by using the quadratic formula?
Shor's algorithm is a quantum algorithm to find a non-trivial factor of a composite integer $N$. It is assumed that $N$ is odd and not a perfect power.
The first step is to find the multiplicative ...
- 183
4
votes
1
answer
121
views
Quantum algorithm to get $d$ (private exponent) directly without factoring first
Shor's algorithm is for finding period $r$ such that $a^r\equiv 1\bmod N$. Knowing period we can factor $N$.
In RSA we encrypt message $m$ by $m^e\bmod N$ ($e$ and $N$ are public keys).
Let us pick ...
- 141
0
votes
0
answers
34
views
Exponential modulation on qiskit, Shor algorithm [duplicate]
I´m trying to code the shor algorithm for any N and any a but i always find examples of code for the N=15. My first question is how is this funtion( provided by qiskit ) does the exponential ...
4
votes
1
answer
108
views
In Shor's algorithm, what is the exact analysis of its time and probability complexity?
Generally exact complexities aren't interesting, but I couldn't find any info on it for this case at all.
Specifically my question, is let's say I have a polynomial p(n) and I want to have a quantum ...
- 49
2
votes
1
answer
37
views
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) &...
- 135
2
votes
2
answers
83
views
What is period finding useful for in Shor's algorithm?
Could someone help me to understand the concept behind period finding in Shor algorithm?. I'm a beginner in quantum computing.
I want to know why we use Shor's algorithm to find the period and what is ...
2
votes
0
answers
92
views
Shor's algorithm in Python with qiskit - How to implement the modular exponentiation step?
I found this code for Shor's algorithm but it always was failing at the end of the modular_exponentiation routine because the keyvalue of ...
- 21
1
vote
1
answer
62
views
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,...
- 237
6
votes
3
answers
556
views
Can Shor's algorithm be done with the same efficiency on an adiabatic quantum computer as on a circuit-based one?
Unfortunately, I cannot find any information on this, so I am asking in this forum if anyone knows, and if so, why this is the case?
- 73
0
votes
1
answer
120
views
In Aaronson's Shor's algorithm sealed room analogy, what happens if I wake up only every 48 hours?
I've been reading Aronson's https://scottaaronson.blog/?p=208 blog post about Shor's algorithm. In his sealed room analogy, what happens if I wake up only every 48 hours? Won't this procedure wrongly ...
- 53
2
votes
1
answer
110
views
What is the relationship between recycling time and success probability of finding the right period, in iterative Shor's algorithm?
I'm studying Shor's algorithm using an iterative approach where only one single qubit is used on the upper register and it is recycled $2\log_2(N)$ times ($N$ is the number to factorize).
I have a ...
- 81
7
votes
1
answer
241
views
Were quantum computers conjectured to factor large numbers before Shor developed his algorithm?
Peter Shor has given wonderful accounts of the development of his algorithm, with a lot of detail on the activity in the field at around the early-mid 90's. He's been very free about emphasizing that ...
- 10.1k
1
vote
3
answers
405
views
Does Shor's algorithm imply the existence of the multiverse?
In The Fabric of Reality, David Deutsch argues the following:
To those who still cling to a single-universe world-view, I issue this challenge: explain how Shor's algorithm works. I do not merely ...
- 164
1
vote
0
answers
41
views
modify Shor’s quantum order finding algorithm in such a way that it uses as few qubits as possible
I am supposed to modify Shor’s quantum order finding algorithm in such a way that it uses as few qubits as possible.
Beforehand, I already did an exercise where I showed that the inverse Quantum ...
- 23
3
votes
1
answer
88
views
Is the phase-estimation a specific case of the Hidden Subgroup Problem?
I read Nielsen & Chuang and I have difficulties understanding the links between the Hidden Subgroup Problem and the Phase Estimation.
In Exercise 5.14 (Section 5.3.1 "Application: order-...
- 81
1
vote
0
answers
75
views
Having trouble trying to program the shor 9 qubit code
I am trying to program in python the following quantum circuit but for some reason when I write the matrix after the z gate, M8, the resultant matrix is zero.
The code is:
...
- 51
3
votes
1
answer
333
views
Trying to construct modular exponentiation gate in Qiskit
https://qiskit.org/textbook/ch-algorithms/shor.html in this tutorial I don't understand especially in how they define for the modular exponentiation gate with only swap gate (inside c_amod15 function)....
- 41
3
votes
1
answer
90
views
Is there a way to access the value of a classical bit after measurement and store it as a variable (qiskit)?
I am trying to implement the one-qubit Approximate QFT for Shor's Algorithm in qiskit as described in this paper, which requires the gate
$$
R_j^{\prime}=\left(\begin{array}{c}
1 \hspace{0.5em} 0 \\
0 ...
- 31
1
vote
1
answer
60
views
Physical qubit estimates when using surface codes
I've been trying to recreate physical qubit requirements to attack elliptic curve cryptography for the good people over at cryptography stack exchange. I don't want to get too deep into the arcana of ...
- 133
3
votes
1
answer
122
views
Why does Shor suggest to take $q$ such that $n^2 \leq q < 2n^2$? Isn't that a bit too much? [duplicate]
We would like to find the order of $x \bmod{n}$. Shor --- on page 318 of his 1999 paper --- instructs:
First, we find $q$, the power of 2 with $n^2 \leq q < 2n^2$. [...] Next, we put the first ...
- 33
1
vote
1
answer
227
views
7*4 mod(15) qiskit explanation
I don't understand this circuit's output from Qiskit's doc : .
Indeed, the result should be 13, but output, I think I don't have the right method to read the result. I should have $|1101\rangle$ but ...
- 23
4
votes
2
answers
89
views
$QFT^{-1}$ at the end of Shor's algorithm and $QFT$ at the end of Hidden Subgroup algorithm
In the usual presentations (e.g. Nielsen and Chuang) Shor's algorithm (in its quantum part) is presented as a special case of phase estimation, meaning it uses a circuit of the form "generate ...
- 427
0
votes
1
answer
119
views
Is Shor demonstration wrong?
in Polynomial-Time Algorithms for Prime Factorization and Discrete Logarithms on a Quantum Computer by Peter W. Shor (also in Algorithms for quantum computation: discrete logarithms and factoring).
In ...
2
votes
2
answers
187
views
How to factor $N=14$ with Shor's algorithm?
As a practice exercise, I am trying to factor $N=14$ using Shor's algorithm. My initial guess is $a = 5$, and I need a quantum circuit $U$ for:
$U\vert y \rangle = \vert 5 \cdot y ~{\rm mod}~ 14 \...
- 123
4
votes
1
answer
429
views
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 ...
- 49
2
votes
0
answers
39
views
Simulation of algorithms with QFT on a classical computer
In paper The Quantum Fourier Transform Has Small Entanglement the authors showed that strong entanglement of qubits caused by QFT comes mainly from ordering the qubits. QFT itself prepares only weak ...
- 13.4k
1
vote
0
answers
164
views
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 (...
- 11
0
votes
0
answers
48
views
Understanding Shor algorithm fo Elliptic Curves Demonstration
I was reading Shor's discrete logarithm quantum algorithm for elliptic curves. And i have two questions.
In page 7 they say that $x = (x0 - dy) mod q$, where $x0$ is between 0 and q-1, but then they ...
2
votes
1
answer
251
views
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 ...
- 23
1
vote
1
answer
89
views
Shor's Algorithm and Permutations
I read some articles about Shor's algorithm but I can't understand how it works. From my point of view it makes the problem even more complex from O(2^n) to O(n!). How does the oracle that is suppose ...
3
votes
1
answer
90
views
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 ...
2
votes
1
answer
213
views
Qiskit textbook: Shor's algorithm
The Qiskit textbook shows the following circuit for implementing the phase $(\frac{s}{r})$ estimation stage of Shor's algorithm for factorizing 15:
My understanding is that the register of qubits 8-...
- 35
1
vote
1
answer
139
views
Qiskit textbook: mod 15 multiplication circuit
The Qiskit textbook shows a circuit for mod 15 multiplication by "a", which for a==2 does the following operations:
U.swap(0,1)
U.swap(1,2)
U.swap(2,3)
...
- 35
3
votes
1
answer
202
views
Can the paper by Monz et al. (2015) be regarded as a real implementation of Shor's algorithm?
I'm studying about the Shor algorithm and I wonder whether the paper below can be regarded as a real implementation of the Shor algorithm:
https://arxiv.org/abs/1507.08852
In this paper, they tried to ...
- 81
2
votes
1
answer
290
views
When factoring N=21 on IBMQ Devices with Shor's algorithm, does the quantum subroutine require modular exponentiation?
I am currently working on Qiskit code implementing Shor algorithm in the form of a quantum circuit. I am factoring $N = 21$ (into 3 and 7) using 5 qubits, with 3 qubits in the work register and 2 in ...
- 99
1
vote
1
answer
122
views
DFT like operation in the third step of Period finding and Discrete Logarithm algorithm
In the third step of the algorithm for discrete logarithm, the state
$$
|\hat{f}(l_1,l_2)\rangle=\frac{1}{\sqrt{r}}\sum_{j=0}^{r-1}e^{-2\pi il_2j/r}|{f}(0,j)\rangle
$$
is introduced which is stated to ...
- 761
2
votes
1
answer
166
views
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....
1
vote
1
answer
50
views
ValueError: Operation doesn't satisfy the given `keep` but can't be decomposed
I was going through Cirq tutorial on Shor's algorithm and was able to implement it successfully using cirq. But it takes forever to run for any n > 21; so I ...
1
vote
0
answers
49
views
Probability of the case when $r'\neq r$ and $r'$ is a factor $r$ in the order finding algorithm
In the Order-Finding algorithm it is stated that it might be that $s$ and $r$ have a common factor, in which case the number $r'$ returned by the continued fractions algorithm be a factor of $r$, and ...
- 761
8
votes
2
answers
2k
views
Why doesn't Shor's algorithm output a solution for some numbers?
I've been trying to mess around with Qiskit's implementation of Shor's algorithm, and while trying I've noticed that Shor(33), for example, would not output a solution (even with an absurd number of ...
- 83
2
votes
1
answer
62
views
I have question about cost of 'modular multiplication unitary' in Shor's algorithm
Here modular multiplication unitary means $U_a : |s\rangle \to|as\mod N\rangle$.
My main question is, can the modular multiplication unitary $U_a$ can be constructed in time polynomial in the number ...
- 21
2
votes
2
answers
147
views
Is it possible to turn modular multiplication into in-place operation?
I began to work on the implementation of Shor's algorithm with a custom value for the modulo. Despite some questions have already been asked about it here, I don't manage to get a complete example or ...
- 63
6
votes
1
answer
487
views
How accurate must QM be for applications of quantum computing?
The Tale of One-Way Functions (section 2.4) claims that quantum mechanics would have to be accurate to an remarkable (absurd?) degree for an application such as factoring large numbers. So, ...
- 161
0
votes
1
answer
371
views
How to run Quantum Instance into ibmq_qasm_simulator
I have tried to run Shor's algorithm using IBM high performance simulator. I
am currently using QuantumInstance to factorize a number. The code is provided below:
<...
- 43
4
votes
1
answer
191
views
Cost of Modular Exponentiation in Shor's algorithm
In the Shor's algorithm, we need to compute the sequence of controlled $U^{2^j}$ operations used by the phase estimation procedure, where $U$ is defined as
$$
U|y\rangle=|xy\;(\mod N)\rangle\text{ ...
- 761
3
votes
2
answers
474
views
Modular exponentiation quantum circuit design for Shor's algorithm
I'm studying Shor's algorithm and I'm wondering how to build the quantum circuit for the modular exponentiation calculation in the Shor's algorithm.
Is the circuit found classically (using ...
- 141
6
votes
2
answers
239
views
Chronology of discovery of quantum phase estimation algorithm
I'm a bit confused about exactly when the phase estimation algorithm was discovered. The Wiki article, as well as various textbooks and papers, says that it was introduced in 1995 by Alexei Kitaev, ...
- 199
1
vote
1
answer
219
views
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 ...
- 201