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

9 questions
Filter by
Sorted by
Tagged with
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 $... 1answer 237 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$... 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 ... 1answer 109 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 ... 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 ... 2answers 445 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 ... 1answer 531 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\... 1answer 52 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$...
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 \ = \ ...