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
2 votes
2 answers
55 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
136 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
1 vote
2 answers
274 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
  • 153
-1 votes
1 answer
120 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
  • 89
2 votes
0 answers
91 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
4 votes
1 answer
185 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
  • 143
2 votes
0 answers
39 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
104 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
57 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
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 ...
Dave R's user avatar
  • 183
4 votes
1 answer
134 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
  • 141
0 votes
0 answers
35 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
144 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
46 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
242 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
216 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
68 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
585 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
0 votes
1 answer
152 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 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 indicate that I'm on a 24-hour ...
bburd's user avatar
  • 53
2 votes
1 answer
121 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
263 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
502 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
3 votes
1 answer
133 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
99 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
561 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
189 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
78 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
  • 133
3 votes
1 answer
133 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
311 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
113 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
130 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
220 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
433 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
2 votes
0 answers
52 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 ...
Martin Vesely's user avatar
1 vote
0 answers
250 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 (...
Kay's user avatar
  • 11
0 votes
0 answers
57 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 ...
Philip.q.c's user avatar
2 votes
1 answer
350 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 ...
tulapia's user avatar
  • 23
1 vote
1 answer
101 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 ...
Martin Spinoza's user avatar
3 votes
1 answer
94 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 ...
Gustavo Mirapalheta's user avatar
2 votes
1 answer
307 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-...
antonantal's user avatar
1 vote
1 answer
163 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) ...
antonantal's user avatar
3 votes
1 answer
222 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 ...
Alex's user avatar
  • 81
2 votes
1 answer
405 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 ...
Sam_QC's user avatar
  • 109
1 vote
1 answer
137 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 ...
Sooraj S's user avatar
  • 791
2 votes
1 answer
221 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....
Gabe Richardson's user avatar
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 ...
Dexter Mandark's user avatar