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
6
votes
1answer
349 views

Why is this implementation of the order finding algorithm not working?

I asked a question about this earlier, but I am still coming across problems in my algorithm implementation. I am trying to implement the order finding algorithm on Cirq finding the minimal positive $...
5
votes
1answer
247 views

Expected repetitions of the quantum part of Shor's algorithm

Shor's algorithm to factor a number $N$ goes as follows: Pick a random value $b \in (0, N)$. Use a specific quantum computation to a sample a value $v$ that should be close to $2^{m} k/p$ where $m$ ...
8
votes
3answers
283 views

Shor's algorithm caveats when $a^{r/2} =-1 \mod N$

For an integer, $N$, to be factorised, with $a$ (uniformly) chosen at random between $1$ and $N$, with $r$ the order of $a\mod N$ (that is, the smallest $r$ with $a^r\equiv 1\mod N$): Why is that in ...
1
vote
1answer
115 views

When increase the shot, why the result is different?

when I measure the shot = 1024 when I measure the shot = 8192 I want to derive result value 011(=3) However, I know if measure the more shots, increase the accuracy. why this result derive??? why ...
8
votes
1answer
1k views

How many logical qubits are needed to run Shor's algorithm efficiently on large integers ($n > 2^{1024}$)?

First, I know there are differences in logical qubits and physical qubits. It takes more physical qubits for each logical qubit due to quantum error. Wikipedia states that it takes quantum gates of ...
6
votes
1answer
567 views

How exactly does modular exponentiation in Shor's algorithm work?

Consider the modular exponentiation part of Shor's algorithm which in many works is just referred to as $$U_{f}\sum^{N-1}_{x = 0}\vert x\rangle\vert 0\rangle = \vert x\rangle\vert a^{x}\text{ mod }N\...
5
votes
2answers
483 views

Is there a simple, formulaic way to construct a modular exponentiation circuit?

I'm a newcomer to quantum computing and circuit construction, and I've been struggling to understand how to make a modular exponentiation circuit. From what I know, there are several papers on the ...
4
votes
1answer
53 views

How does $x^{\frac{r}{2}} \equiv -1 \pmod {p_i^{a_i}}$ follow from “if all these powers of $2$ agree”?

Polynomial-Time Algorithms for Prime Factorization and Discrete Logarithms on a Quantum Computer (Shor, 1995) [p. 15] To find a factor of an odd number $n$, given a method for computing the order $...
2
votes
0answers
90 views

Would this quantum algorithm implementation work?

I am trying to implement the order finding algorithm on Cirq finding the minimal positive $r$ for coprime $x$ and $N$ satisfying the equation $x^r \ = \ 1$(mod$ \ N$). In my case, I have set $x \ = \ ...