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
8 votes
2 answers
2k views

Why doesn't Shor's algorithm output a solution for some numbers?

I've been trying to mess around with Qiskit's implementation of Shor's algorithm, and while trying I've noticed that Shor(33), for example, would not output a solution (even with an absurd number of ...
user avatar
1 vote
1 answer
33 views

I have question about cost of 'modular multiplication unitary' in Shor's algorithm

Here modular multiplication unitary means $U_a : |s\rangle \to|as\mod N\rangle$. My main question is, can the modular multiplication unitary $U_a$ can be constructed in time polynomial in the number ...
user avatar
2 votes
2 answers
54 views

Is it possible to turn modular multiplication into in-place operation?

I began to work on the implementation of Shor's algorithm with a custom value for the modulo. Despite some questions have already been asked about it here, I don't manage to get a complete example or ...
user avatar
  • 21
6 votes
1 answer
386 views

How accurate must QM be for applications of quantum computing?

The Tale of One-Way Functions (section 2.4) claims that quantum mechanics would have to be accurate to an remarkable (absurd?) degree for an application such as factoring large numbers. So, ...
user avatar
  • 161
0 votes
1 answer
36 views

How to run Quantum Instance into ibmq_qasm_simulator

I have tried to run Shor's algorithm using IBM high performance simulator. I am currently using QuantumInstance to factorize a number. The code is provided below: <...
user avatar
  • 33
4 votes
1 answer
92 views

Cost of Modular Exponentiation in Shor's algorithm

In the Shor's algorithm, we need to compute the sequence of controlled $U^{2^j}$ operations used by the phase estimation procedure, where $U$ is defined as $$ U|y\rangle=|xy\;(\mod N)\rangle\text{ ...
user avatar
  • 277
3 votes
1 answer
183 views

Modular exponentiation quantum circuit design for Shor's algorithm

I'm studying Shor's algorithm and I'm wondering how to build the quantum circuit for the modular exponentiation calculation in the Shor's algorithm. Is the circuit found classically (using ...
user avatar
  • 55
6 votes
2 answers
95 views

Chronology of discovery of quantum phase estimation algorithm

I'm a bit confused about exactly when the phase estimation algorithm was discovered. The Wiki article, as well as various textbooks and papers, says that it was introduced in 1995 by Alexei Kitaev, ...
user avatar
1 vote
1 answer
167 views

Would the interest in building quantum computers decrease if a classical algorithm for factoring all integers in polynomial time is discovered?

Quoting Wikipedia: No algorithm has been published that can factor all integers in polynomial time, that is, that can factor a $b$-bit number $n$ in time $O(b^k)$ for some constant $k$. Neither the ...
user avatar
  • 119
2 votes
1 answer
148 views

Prove that applying the QFT twice is equivalent to classical multiplication by $-1$ modulo $2^n$

While going through the answer given on this post, I came across the sentence: If you apply the $QFT$ twice, it is equivalent to a classical multiplication by -1 modulo $2^n$ where $n$ is the size of ...
user avatar
  • 33
9 votes
0 answers
97 views

Calculate the period (like in Shor's algorithm) from the factors?

One of the fundamental elements of Shor's algorithm is the calculation of the function: $$ f_a(r) = a^r (mod \ N) $$ where $N$ is the number to be factored and $a$ is a number chosen with some ...
user avatar
1 vote
1 answer
35 views

Confusion with denotations and potentially other things as well

In the article article there is an optimized circuit for Shor's algorithm: and I'm not sure if $x=11$ is the random number $1<x<N$ I can choose to calculate $f(r)= x^r\bmod N$ for $r=1,2,3,4\...
user avatar
2 votes
1 answer
96 views

Shor's Algorithm Results - Qiskit

I have been trying to build a Shor's Algorithm simulation for N = 15 on Qiskit's framework. Having referenced the Qiskit textbook, I built a circuit that largely resembles what they have done, with a ...
user avatar
3 votes
0 answers
60 views

Implementing Shor's algorithm on IBM Quantum Composer

I'm trying to recreate from this paper in the IBM Quantum Composer. However, this circuit isn't enough understandable for me to do so. I have tried to recreate the above circuit in the composer as ...
user avatar
4 votes
1 answer
85 views

Difference between semiclassical QFT and QFT

In papers, one of them being An Experimental Study of Shor's Factoring Algorithm on IBM Q is stated that replacing QFT with the semiclassical QFT (Kitaev's approach) reduces the needed number of ...
user avatar
1 vote
1 answer
71 views

Measurement of the second quantum register in the Shor's algorithm [duplicate]

I've read that the measurement of the ancilla qubits is not fundamental for Shor's algorithm, but I don't understand how the algorithm works if I remove it. Without those measurements, do I have $r$ ...
user avatar
  • 141
3 votes
1 answer
130 views

Implementation of Unitary in Shor's Algorithm in PennyLane

I've been working on implementing Shor's Algorithm in PennyLane, but am struggling to understand how the circuit for 'U' has been constructed according to Qiskit. In the Qiskit textbook, they seek to ...
user avatar
1 vote
0 answers
42 views

How to create this feature map?

In this paper, the following feature map is used: $$x \to \vert\phi(x)\rangle = \frac{1}{\sqrt{2^k}}\sum_{i=0}^{2^k-1}\vert x\cdot g^i\rangle$$ But no circuit is provided. A theoretical description of ...
user avatar
  • 31
5 votes
1 answer
131 views

Register size in factoring 15 using Shor's algorithm

In Nielsen and Chuang's book: Quantum computation and quantum information (2016), there is an example in Box 5.4 which shows how to factor $15$ using Shor's algorithm. I am confused about a ...
user avatar
  • 51
1 vote
0 answers
41 views

What will be the most useful quantum algorithms in the fault-tolerant quantum computers era?

When we'll have fault tolerant quantum computers with a lot of qubits, what will be the most useful algorithms (studied so far)? I know about Shor, Grover and quantum phase estimation but I'm pretty ...
user avatar
  • 141
1 vote
0 answers
24 views

State of the art values for Shor algorithm depth and number of qubits on Clifford+T basis with arbitrary connectivity

I am trying to find the state of the art results in term of number of logical qubits and depth for the Shor factoring algorithm on the Clifford+T basis. I don't want to assume anything about the error ...
user avatar
1 vote
1 answer
125 views

Integer factorization using Shor's Alorithm

I have question about Shor's algorithm, from I know it's for factorize an integer and can factorize big number with ease. I using Qiskit to try make a simple factorization program (with local ...
user avatar
  • 33
3 votes
1 answer
46 views

Where is the extra qubit after QFT$^{-1}$ coming from in Shor’s algorithm?

Hello sorry if this is a stupid question arising from my ignorance but I have been looking at the modular adder for Shor's algorithm according to this website. Here is what the gate looks like: The ...
user avatar
  • 65
1 vote
1 answer
180 views

"Classical" phase estimation versus iterative phase estimation

In the article Arbitrary accuracy iterative phase estimation algorithm as a two qubit benchmark, the authors introduced implementation of phase estimation with two qubits only. The trick that bits ...
user avatar
0 votes
1 answer
143 views

Question about the Result Analysis of Ekera's Method in Short DLP

In section 4.4 of the paper "Quantum algorithms for computing short discrete logarithms and factoring RSA integers", for an arbitrary set $\left\{ (j_i, k_i):1\le i\le s \right\}$ chosen ...
user avatar
2 votes
1 answer
86 views

Why don't we use exact QFT in Shor's algorithm?

In DLP ($g \equiv x^r$ (mod $p$) with known order of $x$ as $p$), Shor algorithm applies QFT to the state $$\frac{1}{p}\sum_{a, b}^{p-1}|a, b, g^ax^b⟩$$ Here QFT is of size $q$ that satisfies $(p-1)\...
user avatar
2 votes
0 answers
92 views

Two possible ways how to implement Shor's Algorithm

Among many paper describing circuit solving period finding problem and discrete logarithm problem (DLP) (for simplity, let's say $g \equiv x^r$ (mod n) and try to find $r$), there are two variants ...
user avatar
1 vote
0 answers
77 views

Matrix for $U^{2^j}$ from Shor's algorithm for any $a$ and $N$

I'm implementing Shor's algorithm from scratch and therefore want to implement a unitary gate $U$ such that $U^{2^j}|y\rangle = |a^{2^j}y \: \text{mod} \: N\rangle$. I know that an efficient way of ...
user avatar
  • 2,576
4 votes
1 answer
60 views

In Shor's algorithm, how is ${\rm QFT}_n|x\rangle$ split into its even and odd components?

I am auditing a course on quantum computing. Since this is not paid, I dont have any staff support to ask questions. Therefore I am asking the stackoverflow community to help me with it. This is ...
user avatar
0 votes
1 answer
51 views

Is the final state in the quantum period finding algorithm entangled?

In the period finding algorithm (see the picture), through the standard procedure in quantum computing algorithms, we have $$U_f|\Psi\rangle|0^n\rangle=\frac{1}{\sqrt{2^n}}\left(\sum_{x=0}^{2^n-1}|x\...
user avatar
  • 207
2 votes
2 answers
95 views

Who is responsible for implementing quantum error correction?

There are various options for error correction. For example, the Shore code or a whole class of surface codes. But I don't really understand at what level they should be implemented. For example, I ...
user avatar
  • 431
4 votes
1 answer
162 views

What is the quantum query complexity of the period finding routine of Shor's algorithm?

It seems like it should be a function of N - O(log N), to minimise probability of getting a multiple of the period. However, Prof Preskill's lec notes mention: Thus we solve Period Finding if the ...
user avatar
  • 73
1 vote
1 answer
51 views

Does Toffoli AND conjugate affect superposition if used in Shor's algorithm?

I have come across several papers that use Toffoli AND conjugate to minimize the T-depth. But since it contains a measurement, does it affect Shor's algorithm (in terms of interference, entanglement, ...
user avatar
3 votes
1 answer
219 views

Logical bit-flip and Phase-flip operators of Shor’s 9-qubit code

The logical basis states of the Shor’s 9-qubit code are given by $|0_L\rangle = \frac{(|000\rangle+|111\rangle)(|000\rangle+|111\rangle)(|000\rangle+|111\rangle)}{2\sqrt{2}}, |1_L\rangle = \frac{(|000\...
user avatar
  • 465
1 vote
1 answer
158 views

What is the largest number factored by the IBM Quantum simulators?

Though a lot of papers talk about the largest factored number by Shor's Algorithm, I want to know the largest one factored by the IBM Quantum, for example, the simulator_mps. I am able to use it to ...
user avatar
7 votes
2 answers
126 views

Continued fractions with Shor's algorithm: which convergent?

Suppose I am using Shor's order finding algorithm to calculate the order $r$ of $x\leq N$ with respect to $N$. After some run of the QPE subroutine, I obtain a good, $L$-bit approximation to $s/r$ for ...
user avatar
  • 73
0 votes
1 answer
110 views

Quantum Fourier Transform in the Period Finding Problem

I am trying to prove that when applying the inverse QFT to the following state: we get the following result: However, I get a wrong prefactor. Can anyone tell me where I went wrong? Here my ...
user avatar
  • 11
3 votes
0 answers
55 views

Shor vs Schnorr: A classical algorithm for breaking RSA? [duplicate]

I am not sure why I haven't heard much chatter about this paper by Dr. Claus Peter Schnorr where he claims to have come up with a classical algorithm to break the RSA protocol. The construction is ...
user avatar
  • 221
7 votes
1 answer
481 views

Classical algorithm with complexity similar to Shor's discovered: Are there more efficient quantum algorithms than Shor's?

In the article Fast Factoring Integers by SVP Algorithms the author claims that he discovered classical algorithm for factoring integers in polynomial time. The Quantum Report mentioned here that it ...
user avatar
-4 votes
1 answer
106 views

Can I have access to break my Windows BitLocker key [closed]

Is it possible to have access to a quantum computer to break a BitLocker key (maybe with Shor's algorithm) and have access to my data? Here what happened to me: after I've changed my LENOVO X270 ...
user avatar
6 votes
1 answer
66 views

How does the subtraction gate work in Fourier space

I am currently reading Shor's algorithm on my own and I come across a paper via this link. It shows the circuit for implementing Shor's alogrithm. Here it depicts that taking a QFT circuit on the ...
user avatar
  • 61
4 votes
1 answer
211 views

Shor's algorithm - modular exponentiation and Quantum Fourier transform and quantum phase estimation method

I have a question about Shor's algorithm with respect to the eigenvector representation of the second (lower) register. In the following I use the notation of Nielsen, M., Chuang, I., 2016, Quantum ...
user avatar
  • 181
4 votes
1 answer
193 views

Why is the superposition of all states an eigenvector, with eigenvalue 1, of the QFT?

In many descriptions of order finding, but also in this answer here, it is shown that the superposition of all states is an eigenvector for eigenvalue 1.0. To cite: Having found the eigenvalues, we ...
user avatar
  • 197
3 votes
1 answer
256 views

Can I access device specifications of IBMQ paying devices?

I need to perform some tests for my thesis in real quantum computers, however, I only have access to IBM's free quantum devices (the maximum number of qubits I can use is 15, in ...
user avatar
  • 79
2 votes
1 answer
66 views

Unitary Operator impact on both - the Control Qubit and the Target Register in Shor's Algorithm

I read the details of Shor's algorithm implementation at the link https://qiskit.org/textbook/ch-algorithms/shor.html#2.-The-Solution and had a question. As a concept, when Unitary is applied with a ...
user avatar
1 vote
1 answer
101 views

Braket and Q# Simulators

I have implemented Shor's algorithm in Qiskit, and everything works as expected within the IBM Q experience for both the IBM qasm_simulator and real hardware. However, after I've implemented Shors in ...
user avatar
9 votes
0 answers
201 views

What is stopping FACTORING from being BQP-complete?

Classical complexity theory makes much of the study of so-called intermediate problems - that is, problems that are in $\mathsf{NP}$ but are nonetheless not known to be in $\mathsf{P}$ and further not ...
user avatar
  • 6,777
2 votes
1 answer
232 views

How does this represent modular multiplication

How does this circuit map $|x\rangle$ to $|7x \space mod15\rangle$? Looking into Shor's and I thought that phase kickback causes the modular exponentiation part to be mapped onto the measurement ...
user avatar
2 votes
3 answers
148 views

Shor's implementation problem on qiskit

If q4-7 are all supposed to be eigenstates of the operation, why is it just that q7 is in $|1\rangle$? Shouldn't all qubits 4 to ...
user avatar
2 votes
1 answer
182 views

How to show that amount of qubits needed to crack the RSA-2048 protocol using Shor's algorithm?

I've read that under current technology we would need around 20 million qubits to crack the RSA-2048 protocol. How would one prove this?
user avatar
  • 257