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

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.

Filter by
Sorted by
Tagged with
-4 votes
0 answers
27 views

How do quantum entanglement and quantum superposition contribute to the exponential speedup over classical algorithms? [closed]

To explain that about Shor’s algorithm and its components, you’ll need to cover the following information: ...
Shaminuzzaman Bhuiyan's user avatar
1 vote
1 answer
53 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 ...
momo's user avatar
  • 13
4 votes
3 answers
414 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.
Alexender Iotko's user avatar
1 vote
0 answers
43 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. ...
Bekzad Dzhanpolatov's user avatar
1 vote
0 answers
16 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 ...
Tayyab Yahya's user avatar
5 votes
1 answer
516 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
Mathias Pichler's user avatar
1 vote
2 answers
92 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 ...
tangyao's user avatar
  • 151
2 votes
1 answer
203 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 ...
HelloMan's user avatar
  • 123
8 votes
1 answer
475 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 ...
Mark Spinelli's user avatar
2 votes
1 answer
186 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 ...
ali khosravi's user avatar
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 ...
Mark Spinelli's user avatar
3 votes
0 answers
63 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 ...
Manish Kumar's user avatar
2 votes
1 answer
60 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 ...
Pablo Falegre's user avatar
4 votes
1 answer
621 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 ...
Frederik Ravn Klausen's user avatar
2 votes
3 answers
93 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 ...
Martin Vesely's user avatar
2 votes
2 answers
154 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(...
Juan Manuel Pavon's user avatar
2 votes
2 answers
303 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 ...
Avi's user avatar
  • 163
-2 votes
1 answer
133 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 ...
lousycoder's user avatar
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 ...
user27293's user avatar
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$. ...
Omeglac's user avatar
  • 155
2 votes
0 answers
124 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. ...
James Garcia's user avatar
5 votes
1 answer
236 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 ...
Adelhart's user avatar
  • 153
2 votes
0 answers
44 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 ...
Jackson Walters's user avatar
3 votes
1 answer
118 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$ ...
Jackson Walters's user avatar
11 votes
2 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 ...
Adrien Amour's user avatar
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 ...
user4676310's user avatar
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 ...
Dave R's user avatar
  • 193
4 votes
1 answer
144 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 ...
Turbo's user avatar
  • 181
0 votes
0 answers
37 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 ...
Diogo Chikhi's user avatar
4 votes
1 answer
162 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 ...
user25790's user avatar
2 votes
1 answer
49 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) &...
leonboe1's user avatar
  • 135
2 votes
2 answers
341 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 ...
Karthick Raja's user avatar
2 votes
0 answers
286 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 ...
user67105's user avatar
1 vote
1 answer
74 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,...
Andrew Baker's user avatar
6 votes
3 answers
605 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?
BootBootBoot's user avatar
2 votes
1 answer
130 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 ...
Alex's user avatar
  • 81
7 votes
1 answer
273 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 ...
Mark Spinelli's user avatar
1 vote
3 answers
541 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 ...
Maxime Desalle's user avatar
1 vote
0 answers
42 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 ...
moert4's user avatar
  • 23
4 votes
1 answer
146 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-...
user8622655's user avatar
1 vote
0 answers
110 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: ...
LittleBlue's user avatar
3 votes
1 answer
698 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)....
Taufiq Datau's user avatar
3 votes
1 answer
263 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 ...
inception's user avatar
1 vote
1 answer
82 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 ...
Daniel S's user avatar
  • 143
3 votes
1 answer
142 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 ...
user22879's user avatar
1 vote
1 answer
344 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 ...
Jonah's user avatar
  • 23
5 votes
2 answers
135 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 ...
Gadi A's user avatar
  • 437
0 votes
1 answer
133 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 ...
Philip.q.c's user avatar
2 votes
2 answers
245 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 \...
Robert Singleton's user avatar
4 votes
1 answer
439 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 ...
njoyeux's user avatar
  • 49