# 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.

138 questions
Filter by
Sorted by
Tagged with
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
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
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 ...
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
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
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) ...
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
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
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
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
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 ...
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 ...
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
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
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 ...
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 ...
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
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
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
135 views

• 207
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
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