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.
192
questions
4
votes
0
answers
90
views
Why doesn't Shor's algorithm suggest a fast classical algorithm?
I am reading (and quoting) Andrew Child's notes, and I'm trying to understand the HSP for abelian groups, and in particular why the quantum algorithm doesn't shed any light on a potential classical ...
- 351
1
vote
1
answer
78
views
Why when using Shor's Algorithm to factor 33 am I getting 5 as a period half of the time?
When using Shor's algorithm to try to factor 33 I expect the period found to be 10, however when I run it using qiskit and qasm simulator I keep getting 5 and 10 appearing as the most common periods ...
- 19
1
vote
0
answers
57
views
How to run Shor's algorithm on real quantum hardware with Qiskit?
I am trying to factor 15 with Shor's algorithm and want to find the period for $a^x$ mod $15$ on real quantum hardware with Qiskit. I took the code from the Qiskit Textbook and managed to run it on ...
2
votes
1
answer
54
views
General number of classical bits: recycles qubits
I am trying to write a Qiskit routine to perform qubit recycling for Shor's algorithm. This is a procedure by which the M-bit control register is replaced by a single quantum register, and the ...
- 145
1
vote
1
answer
117
views
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 ...
- 21
4
votes
3
answers
585
views
Where to find a generic implementation of Shor's algorithm with Qiskit?
Since Shor's algorithm was deprecated in Qiskit, I'm wondering where to find a generic implementation.
There are some examples over the Internet but factoring of 15 is just hardcoded.
1
vote
0
answers
112
views
Shor’s / qiskit.circuit.exceptions.CircuitError: 'duplicate qubit arguments' [closed]
All code for Quantum Realiazition Shor's algoritm
P.S. I hope all operation almost correct.
...
1
vote
0
answers
17
views
Why we do SWAP operations for applying a mode N function in Shor algorithms and How we do this swapping? [duplicate]
I am working on implementing shor algorithm for finding prime factors of N = 15. I am trying to understand a code of qiskit, but i am confused how and why the code editor is using swap codes to define ...
- 11
5
votes
1
answer
578
views
How to read the result of quantum shor circuit for N=15
I found many circuits for the Shor algorithm for N=15, but i don't understand how to read the result 3 or 5.
Where can i find the result e.g. for this circuit
I found it here
2
votes
2
answers
129
views
What are the ambient group $G$ and the hidden subgroup $H$ in Shor's order finding algorithm?
It is widely believed that Shor's order-finding algorithm is an example of hidden subgroup problem. However, there is a little trick here. The problem is what is the hidden subgroup in Shor's order ...
- 171
2
votes
1
answer
218
views
Classical computation required in Shor's algorithm: are they heavy?
A quantum computer also requires to perform classical computations.
I would like to know if to implement Shor's algorithm, there is a heavy classical computation cost (i.e. that would require a ...
- 123
8
votes
1
answer
531
views
Happy 30th Anniversary to Shor's Algorithm! How challenging was the review process when it was first announced?
Shor's algorithm dropped 30 years ago sometime in April, 1994. Peter Shor has given many wonderful accounts of the early history of the field and of what sparked his particular interest.
Shor has been ...
- 13.6k
2
votes
1
answer
207
views
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 ...
- 51
11
votes
1
answer
1k
views
(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 ...
- 13.6k
3
votes
0
answers
74
views
Why FACTORING is in second level of Fourier hierarchy?
As per comlexityzoo web, the definition of the k-th level of Fourier Hierarchy (FH) is:
$FH_k$ is the class of problems solvable by a uniform family of polynomial-size quantum circuits, with k levels ...
- 827
2
votes
1
answer
73
views
Transpile and run don't use GPU device
I'm trying to run an implementation of Shor's algorithm using a GPU device. While running with $N<1023$ works (23 qubits), when running with a higher number of qubits, the program ends before ...
4
votes
1
answer
663
views
Why is it not a good idea to run Shor's algorithm on a big noisy quantum computer?
Suppose I try to run Shor's algorithm on a big noisy quantum computer.
For a given input I repeat the circuit many times and collect statistics for the measurements of each qubit.
Now based on the ...
2
votes
3
answers
135
views
Shor: Modular exponentiation vs modular multiplication
In his original article Polynomial-Time Algorithms for Prime Factorization
and Discrete Logarithms on a Quantum Computer, Peter Shor constructed an algorithm for finding a period $r$ of the modular ...
- 14.8k
2
votes
1
answer
175
views
Is there a way to implement Smolin's variant of Shor's algorithm?
I'm currently investigating Shor's algorithm and especially Smolin's variant, that he described in his article: https://arxiv.org/abs/1301.7007
My applied changes according to Smolin's variant are ...
- 135
3
votes
2
answers
171
views
How to implement the modular exponentiation implementation in Shor's algorithm?
I am trying to implement Shor's algorithm using modular exponentiation as described in this paper: https://arxiv.org/abs/quant-ph/0205095
The issue is found when trying to implement CMULT($a^{-1}$)mod(...
2
votes
2
answers
327
views
Why does solving integer factorization by using Shor’s algorithm surpass the conventional computation
What is the reason that solving integer factorization by using Shor’s algorithm surpass the conventional computation? Can these quantum characteristics be used for different problems? I would like to ...
- 163
-2
votes
1
answer
145
views
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 ...
- 131
1
vote
0
answers
36
views
Eigenvalues of a unitary U that implements a periodic function [closed]
What can be said about the eigenvalues of a unitary quantum gate $U$ which implements $f(x)=f(x+r) \forall x$, as in $U|x\rangle|0\rangle\rightarrow|x\rangle|f(x)\rangle$ ?
The reason I'm asking is ...
- 19
4
votes
2
answers
1k
views
A necessary and sufficient condition for the existence of a nontrivial square root in Shor's algorithm
A nontrivial square root of $N$ is a number $x$ such that $x^2 = 1\pmod{N}$ where $x$ isn't $1$ or $-1$.
Shor's algorithm consists of finding such a number in order to find a nontrivial factor of $N$. ...
- 155
2
votes
0
answers
167
views
How to do modular exponentiation in qiskit with gates?
I understand the following code on why the specific swaps take place, but when I try to replicate it with $N=35$, I get confused.
...
- 21
6
votes
1
answer
285
views
Why do current large-scale QCs fail to run Shor's algorithm?
Quantum noob here. Apologies if my question is trivial.
According to google, IBM has a quantum computer with 433 qubits.
Based on this (How many logical qubits are needed to run Shor's algorithm ...
- 163
2
votes
1
answer
58
views
Does this measurement for quantum phase estimation look correct?
I have implemented Shor's algorithm for $N=15$ from this tutorial. I understand the algorithm pretty well, but I'm a little confused at the output I'm getting from running the circuit. It appears to ...
- 351
3
votes
1
answer
135
views
What is the initial state in the second register in Shor's algorithm?
Following up on this question, can someone help me clear up the notation we're using for states in Shor's algorithm? It's very unclear what the sentence "where the second register is $|1\rangle$ ...
- 351
11
votes
2
answers
3k
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 ...
- 391
2
votes
1
answer
58
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
9
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 ...
- 193
4
votes
1
answer
153
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 ...
- 181
0
votes
0
answers
39
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
171
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
65
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
1
vote
2
answers
476
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
356
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
80
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,...
- 279
6
votes
3
answers
620
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?
- 93
2
votes
1
answer
134
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
8
votes
1
answer
289
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 ...
- 13.6k
1
vote
3
answers
575
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
1
answer
81
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
4
votes
1
answer
158
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-...
- 101
1
vote
0
answers
114
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:
...
- 71
3
votes
1
answer
816
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)....
- 61
3
votes
1
answer
357
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
2
votes
1
answer
89
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 ...
- 153
3
votes
1
answer
149
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
374
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