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

71 questions
Filter by
Sorted by
Tagged with
34 views

### Simplifying Qiskit circuit with c_if()

I'm trying to simplify the inner for loop of this implementation of the Mosca-Ekert semi-classical variant of Shor's algorithm. The inner for loop should have only linear length, but this ...
142 views

### Shor's algorithm: initialization of second register

I am trying to understand Shor's algorithm. I am not quite sure why the initialization, indicated as $|1\rangle$ in the below image at the bottom left is chosen as it is? I understand the modular ...
41 views

### What is a maximal number factored by Shor's algorithm so far?

With reference to similar question here I would like to know what is the maximal number which has been factored with Shor's algorithm so far on actual quantum hardware. The reason I am asking similar ...
46 views

### Abelian Hidden Subgroup Problem for arbitrary cyclic p-Groups

I had asked a question similar to this one here regarding how to handle the HSP for groups whose cyclic decomposition contains factors whose order is not a power of two. I also had some prior ...
91 views

### How to write a classical version of Shor's algorithm

For learning purposes, I would like to write a classical version of Shor's algorithm. From what I have read, what makes this algorithm fast is the quantum FFT, which is used to find the period of the ...
236 views

### Problem with Shor's factoring algorithm [closed]

I'm trying to figure out the Shor's factoring algorithm. References i've been using wikipedia page, the book Quantum Computer Science by David Mermin and the orignal paper(1996) By Peter Shor. I ...
45 views

### In Shor's algorithm, how can we guarantee that each controlled-U will kickback to the same eigenvalue?

I'm studying the Shor algorithm as part of my thesis and have a question about the "measured" phases after the QPE. So, I take the controlled-U operations on the second register and in cause ...
98 views

### Constructing arbitrary functions for the Abelian HSP

My question might be similar to Hidden subgroup problem. However, I'm not exactly sure though. In addition, that question doesn't have an answer. I'm trying to create some simple instances of the ...
65 views

### Eigenvectors and eigenvalues of the gate $U_a:|s\rangle\mapsto|sa \bmod N\rangle$

I'm studying Shor algorithm. This is a demostration about the eigenvectors and eigenvalues of $U_a$ gate: Can somebody explain me from the third step to the last?
54 views

### Why can I use the Sum of Eigenvectors for Phase Estimation in Shor

In phase estimation, we start by using an eigenvector $\newcommand{\ket}{\lvert#1\rangle}\ket u$ to find the corresponding eigenvalue lambda. So far so good. In the order finding algorithm, we also ...
69 views

### Is there a general order finding quantum algorithm for a given a and N?

I'm trying to construct a general circuit for Shor's algorithm in Qiskit. I understood the later parts of the circuit (inverse QFT and QPE), but can't really understand the order finding. For example, ...
103 views

### How to implement Cx mod N unitary

The following links provides circuts for $a\in\{2,7,8,11,13\}$ and $N=15$: https://qiskit.org/textbook/ch-algorithms/shor.html#3.-Qiskit-Implementation https://arxiv.org/abs/1202.6614v3. I am ...
134 views

### Energy cost of quantum computation

A quantum computer can be modeled as a single unitary transition of a (large) effective quantum state to another. In order to get errors under control, quantum error correction is assumed. A logical ...
112 views

### Shor's Discrete Logarithm Algorithm with a QFT with a small prime base

Suppose you replace both QFTs in Shor's discrete logarithm algorithm with simpler QFTs with small prime base w. Does this algorithm extract the discrete logarithm modulo w? It seems it does, provided ...
76 views

### What are the thermodynamic limits of Shor's algorithm

The asymptotic time complexity of Grover's algorithm is the square root of the time of a brute force algorithm. However, according to Perlner and Liu, the thermodynamic behavior (theoretical minimum ...
20 views

### Questions on May & Schlieper's “Quantum Period Finding is Compression Robust”

https://arxiv.org/abs/1905.10074 https://crypto.stanford.edu/~dabo/pubs/abstracts/quantum.html Below are a few questions about May and Schlieper's paper "Quantum Period Finding is Compression Robust"...
86 views

### Building the period-finding circuit for Shor's Algorithm & the classical complexity of finding the period

I've been trying to learn about Shor's algorithm by writing out implementations of the circuit for modular exponentiation, ${ a }^{ x }\; ({ mod }\; N)$, to find the period $r$ for small numbers such ...
101 views

### Question Regarding Quantum Period-Finding Fourier Transform Approximation

I am following the 5.4.1 Period-Finding Algorithm in Nielsen and Chuang as shown below: My confusion lies with the second expression of point 3 in the procedure. Why is the second expression an ...
77 views

433 views

### How to make a Shor's algorithm for an arbitrary number of qubits with Qiskit on a IBM machine?

So suppose you want to do a Shor algorithm on an arbitrary number of qubits using an arbitrary $a$ (the base number in the periodic function $a^x \mod c$) and $c$ ( the factored number). Making the ...
265 views

### Implementing QFT for Shor's Algorithm

I’m trying to get a Quantum Fourier Transform working with the rest of a compiled version of Shor’s algorithm, attempting to factor $N=21$. In the following image, there’s an initialization phase (...
42 views

### Suggestions for hybrid factoring algorithm on DWave and Qiskit

I was wondering if the multi-prime factoring problem can be solved in a hybrid approach using DWave (to factor) and Shor's algorithm (in Qiskit)? Please let me know your thoughts. Thanks!
79 views

### How to measure entanglement in an algorithm?

Entanglement in Algorithms Most algorithms in quantum computing find their strength in making use of entanglement. I am interested in evaluating the amount of entanglement generated within an ...
769 views

### Is it possible to run a general implementation Shor's algorithm on a real IBM quantum computer at least for N = 15?

I need to make a general implementation of Shor's algorithm that factors, at least, N = 15. I have been able to perform an implementation that works in simulators, with ProjectQ, but when running it ...
640 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 ...
116 views

### Calculating power of a quantum computer — RSA

As discussed in this question, the expected security of 1024-bit RSA is 80-bits: NIST SP 800-57 §5.6.1 p.62–64 specifies a correspondence between RSA modulus size $n$ and expected security strength ...
49 views

### Can anybody explain or suggest a good reference on how to make a modular exponentiation circuit for N=15 with any coprime base?

I have read many papers related to it but in every paper, they just show the circuit of order finding algorithm for N=15, but did not explain what is the procedure to make it. It will be great if ...
304 views

### Why should we use inverse QFT instead of QFT in Shor's algorithm?

Why should we use inverse QFT instead of QFT in Shor's algorithm? When I tried to simulate Shor's algorithm for small numbers, I got an answer even when I used just QFT instead of inverse QFT.
195 views

### Are there any other published quantum factoring algorithms that are simpler or more efficient than Shor’s?

How many qubits and what is the minimum number of gate operations needed to factor an n-bit integer? Are there any other published algorithms that are simpler or more efficient?
102 views

### Reason for evaluating $a^x \bmod N$ from $x = 0$ to $N^2$

As per the Shor's algorithm, we need to evaluate $a^x \bmod N$ from $x = 0$ to $N^2$. What is the reason for this? Why can't we just evaluate for $N$, $2N$ or something like that?
75 views

197 views

### Why do we use the quantum superposition for a period instead of factors in Shor's algorithm?

I understand in Shor's algorithm we use quantum computers to find the period of a function which can then be used to find N, and we increase the probability of observing the state with the correct ...
463 views

### Does Shor's algorithm end the search for factoring algorithms in the quantum world of computation?

In other words, will factoring research remain solely in the classical world or are there interesting research on-going in the quantum world related to factoring?
608 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\...
440 views

### Possible results from Shor's algorithm in practice

After reading through Shor's algorithm, I have a few questions about the probability of factoring semiprime number out. Here is some background of the question. To factor a semiprime number $N$ such ...