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
0 votes
0 answers
24 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 ...
1 vote
1 answer
57 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 ...
  • 13
1 vote
1 answer
67 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 ...
3 votes
1 answer
73 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 ...
1 vote
1 answer
59 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-...
1 vote
1 answer
44 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) ...
3 votes
1 answer
98 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 ...
  • 31
1 vote
1 answer
79 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 ...
  • 89
1 vote
1 answer
72 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 ...
  • 383
2 votes
1 answer
60 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....
1 vote
1 answer
42 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 ...
0 votes
0 answers
15 views

determine degree of boolean polynomial given as black box

I searched a lot but couldn't find a good resource that addresses this question. Given a boolean polynomial with $n$ boolean variables as a black box, what is the most efficient way to compute its ...
0 votes
0 answers
46 views

Mathematical reasoning of Repeating the Phase Estimation in the Order Finding Algorithm

Repeating the order-finding algorithm of quantum computing twice obtains $\dfrac{s_1'}{r_1'}$ the first time, and $\dfrac{s_2'}{r_2'}$ the second time, where $\dfrac{s_i'}{r_i'}$ is $\dfrac{s_i}{r}$ ...
  • 383
1 vote
0 answers
44 views

Probability of the case when $r'\neq r$ and $r'$ is a factor $r$ in the order finding algorithm

In the Order-Finding algorithm it is stated that it might be that $s$ and $r$ have a common factor, in which case the number $r'$ returned by the continued fractions algorithm be a factor of $r$, and ...
  • 383
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 ...
2 votes
1 answer
43 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 ...
2 votes
2 answers
87 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 ...
  • 63
6 votes
1 answer
412 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, ...
  • 161
0 votes
1 answer
96 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: <...
  • 43
4 votes
1 answer
135 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{ ...
  • 383
3 votes
1 answer
248 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 ...
  • 101
6 votes
2 answers
137 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, ...
1 vote
1 answer
186 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 ...
  • 205
2 votes
1 answer
170 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 ...
  • 33
9 votes
0 answers
123 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 ...
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\...
2 votes
1 answer
109 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 ...
3 votes
0 answers
91 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 ...
4 votes
1 answer
118 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 ...
1 vote
1 answer
85 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$ ...
  • 335
4 votes
1 answer
183 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 ...
2 votes
0 answers
47 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 ...
  • 41
6 votes
1 answer
157 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 ...
  • 61
1 vote
0 answers
44 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 ...
  • 335
1 vote
0 answers
27 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 ...
2 votes
1 answer
159 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 ...
  • 43
3 votes
1 answer
51 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 ...
  • 165
1 vote
1 answer
265 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 ...
0 votes
1 answer
146 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 ...
2 votes
1 answer
102 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)\...
2 votes
0 answers
100 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 ...
1 vote
0 answers
96 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 ...
  • 2,655
4 votes
1 answer
68 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 ...
0 votes
1 answer
53 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\...
  • 207
2 votes
2 answers
111 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 ...
  • 441
4 votes
1 answer
198 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 ...
  • 73
2 votes
1 answer
53 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, ...
3 votes
1 answer
294 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\...
  • 495
1 vote
1 answer
206 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 ...
7 votes
2 answers
149 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 ...
  • 332