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

81 questions
Filter by
Sorted by
Tagged with
35 views

### Can I access device specifications of IBMQ paying devices?

I need to perform some tests for my thesis in real quantum computers, however, I only have access to IBM's free quantum devices (the maximum number of qubits I can use is 15, in ...
85 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, ...
52 views

### Braket and Q# Simulators

I have implemented Shor's algorithm in Qiskit, and everything works as expected within the IBM Q experience for both the IBM qasm_simulator and real hardware. However, after I've implemented Shors in ...
51 views

### How does this represent modular multiplication

How does this circuit map $|x\rangle$ to $|7x \space mod15\rangle$? Looking into Shor's and I thought that phase kickback causes the modular exponentiation part to be mapped onto the measurement ...
54 views

### Shor's implementation problem on qiskit

If q4-7 are all supposed to be eigenstates of the operation, why is it just that q7 is in $|1\rangle$? Shouldn't all qubits 4 to ...
42 views

### What is stopping FACTORING from being BQP-complete?

Classical complexity theory makes much of the study of so-called intermediate problems - that is, problems that are in $\mathsf{NP}$ but are nonetheless not knownto be in $\mathsf{P}$ and further not ...
97 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 ...
131 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 ...
33 views

### How to build an example of Shor's algorithm for the discrete log?

I have been trying to build myself an example of Shor's computations for the discrete log. I started out with this objective and I realized I should understand the factorization first, which I did ...
47 views

### How to show that amount of qubits needed to crack the RSA-2048 protocol using Shor's algorithm?

I've read that under current technology we would need around 20 million qubits to crack the RSA-2048 protocol. How would one prove this?
37 views

### Is there an example of Shor's algorithm for the discrete log problem with concrete numbers anywhere?

I understand the problem well enough and I'm trying to understand the algorithm, Shor's version. It's not easy to read the abstract descriptions available everywhere --- Shor's paper, Nielsen's book ...
111 views

### Shor's algorithm: what to do after reading the QFT's result twice?

I asked about how to identify the period looking at a Fourier transform plot. The answer seems to be to run the fourier transform multiple times getting multiple values associated to high ...
51 views

### What are the interesting spikes in this after-QFT graph (page 241) of Programming Quantum Computers?

I'm reading Programming Quantum Computers trying to understand Shor's algorithm. I learned there that we prepare a state $|x^i \bmod N\rangle$, then apply the QFT to this state. The QFT changes the ...
776 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 ...
96 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 ...
190 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 ...
101 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 ...
78 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 ...
45 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 ...
52 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 ...
97 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 ...
50 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 ...
244 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 ...
82 views

465 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 ...
44 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!