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
82
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 ...
1
vote
1
answer
66
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 ...
1
vote
0
answers
38
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
51
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 ...
0
votes
1
answer
76
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 ...
4
votes
3
answers
484
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
79
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 ...
5
votes
1
answer
560
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
116
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 ...
2
votes
1
answer
210
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 ...
8
votes
1
answer
503
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 ...
2
votes
1
answer
201
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 ...
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 ...
3
votes
0
answers
68
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 ...