# 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
Filter by
Sorted by
Tagged with
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 ...
1 vote
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
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 ...
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 ...
1 vote
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
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
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
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 ...
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
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
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
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
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 ...
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
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
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 ...
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 ...
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
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
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(...
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
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
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 ...
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
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. ...
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
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 ...
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$ ...
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
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
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
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
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 ...
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 ...
65 views

• 23