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
1
vote
1answer
44 views

Integer factorization using Shor's Alorithm

I have question about Shor's algorithm, from I know it's for factorize an integer and can factorize big number with ease. I using Qiskit to try make a simple factorization program (with local ...
2
votes
1answer
28 views

Where is the extra qubit after QFT$^{-1}$ coming from in Shor’s algorithm?

Hello sorry if this is a stupid question arising from my ignorance but I have been looking at the modular adder for Shor's algorithm according to this website. Here is what the gate looks like: The ...
1
vote
1answer
55 views

"Classical" phase estimation versus iterative phase estimation

In the article Arbitrary accuracy iterative phase estimation algorithm as a two qubit benchmark, the authors introduced implementation of phase estimation with two qubits only. The trick that bits ...
0
votes
1answer
132 views

Question about the Result Analysis of Ekera's Method in Short DLP

In section 4.4 of the paper "Quantum algorithms for computing short discrete logarithms and factoring RSA integers", for an arbitrary set $\left\{ (j_i, k_i):1\le i\le s \right\}$ chosen ...
2
votes
1answer
55 views

Why don't we use exact QFT in Shor's algorithm?

In DLP ($g \equiv x^r$ (mod $p$) with known order of $x$ as $p$), Shor algorithm applies QFT to the state $$\frac{1}{p}\sum_{a, b}^{p-1}|a, b, g^ax^b⟩$$ Here QFT is of size $q$ that satisfies $(p-1)\...
2
votes
0answers
76 views

Two possible ways how to implement Shor's Algorithm

Among many paper describing circuit solving period finding problem and discrete logarithm problem (DLP) (for simplity, let's say $g \equiv x^r$ (mod n) and try to find $r$), there are two variants ...
1
vote
0answers
47 views

Matrix for $U^{2^j}$ from Shor's algorithm for any $a$ and $N$

I'm implementing Shor's algorithm from scratch and therefore want to implement a unitary gate $U$ such that $U^{2^j}|y\rangle = |a^{2^j}y \: \text{mod} \: N\rangle$. I know that an efficient way of ...
4
votes
1answer
49 views

In Shor's algorithm, how is ${\rm QFT}_n|x\rangle$ split into its even and odd components?

I am auditing a course on quantum computing. Since this is not paid, I dont have any staff support to ask questions. Therefore I am asking the stackoverflow community to help me with it. This is ...
0
votes
1answer
49 views

Is the final state in the quantum period finding algorithm entangled?

In the period finding algorithm (see the picture), through the standard procedure in quantum computing algorithms, we have $$U_f|\Psi\rangle|0^n\rangle=\frac{1}{\sqrt{2^n}}\left(\sum_{x=0}^{2^n-1}|x\...
2
votes
2answers
58 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 ...
4
votes
1answer
94 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 ...
1
vote
1answer
39 views

Does Toffoli AND conjugate affect superposition if used in Shor's algorithm?

I have come across several papers that use Toffoli AND conjugate to minimize the T-depth. But since it contains a measurement, does it affect Shor's algorithm (in terms of interference, entanglement, ...
3
votes
1answer
108 views

Logical bit-flip and Phase-flip operators of Shor’s 9-qubit code

The logical basis states of the Shor’s 9-qubit code are given by $|0_L\rangle = \frac{(|000\rangle+|111\rangle)(|000\rangle+|111\rangle)(|000\rangle+|111\rangle)}{2\sqrt{2}}, |1_L\rangle = \frac{(|000\...
1
vote
1answer
98 views

What is the largest number factored by the IBM Quantum simulators?

Though a lot of papers talk about the largest factored number by Shor's Algorithm, I want to know the largest one factored by the IBM Quantum, for example, the simulator_mps. I am able to use it to ...
6
votes
1answer
82 views

Continued fractions with Shor's algorithm: which convergent?

Suppose I am using Shor's order finding algorithm to calculate the order $r$ of $x\leq N$ with respect to $N$. After some run of the QPE subroutine, I obtain a good, $L$-bit approximation to $s/r$ for ...
0
votes
1answer
73 views

Quantum Fourier Transform in the Period Finding Problem

I am trying to prove that when applying the inverse QFT to the following state: we get the following result: However, I get a wrong prefactor. Can anyone tell me where I went wrong? Here my ...
3
votes
0answers
48 views

Shor vs Schnorr: A classical algorithm for breaking RSA? [duplicate]

I am not sure why I haven't heard much chatter about this paper by Dr. Claus Peter Schnorr where he claims to have come up with a classical algorithm to break the RSA protocol. The construction is ...
7
votes
1answer
353 views

Classical algorithm with complexity similar to Shor's discovered: Are there more efficient quantum algorithms than Shor's?

In the article Fast Factoring Integers by SVP Algorithms the author claims that he discovered classical algorithm for factoring integers in polynomial time. The Quantum Report mentioned here that it ...
-4
votes
1answer
73 views

Can I have access to break my Windows BitLocker key [closed]

Is it possible to have access to a quantum computer to break a BitLocker key (maybe with Shor's algorithm) and have access to my data? Here what happened to me: after I've changed my LENOVO X270 ...
6
votes
1answer
58 views

How does the subtraction gate work in Fourier space

I am currently reading Shor's algorithm on my own and I come across a paper via this link. It shows the circuit for implementing Shor's alogrithm. Here it depicts that taking a QFT circuit on the ...
4
votes
1answer
160 views

Shor's algorithm - modular exponentiation and Quantum Fourier transform and quantum phase estimation method

I have a question about Shor's algorithm with respect to the eigenvector representation of the second (lower) register. In the following I use the notation of Nielsen, M., Chuang, I., 2016, Quantum ...
4
votes
1answer
152 views

Why is the superposition of all states an eigenvector, with eigenvalue 1, of the QFT?

In many descriptions of order finding, but also in this answer here, it is shown that the superposition of all states is an eigenvector for eigenvalue 1.0. To cite: Having found the eigenvalues, we ...
2
votes
1answer
162 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 ...
2
votes
1answer
56 views

Unitary Operator impact on both - the Control Qubit and the Target Register in Shor's Algorithm

I read the details of Shor's algorithm implementation at the link https://qiskit.org/textbook/ch-algorithms/shor.html#2.-The-Solution and had a question. As a concept, when Unitary is applied with a ...
1
vote
1answer
95 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 ...
9
votes
0answers
154 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 known to be in $\mathsf{P}$ and further not ...
2
votes
1answer
117 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 ...
2
votes
3answers
101 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 ...
2
votes
1answer
87 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?
2
votes
1answer
55 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 ...
4
votes
1answer
149 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 ...
4
votes
1answer
78 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 ...
3
votes
0answers
46 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 ...
1
vote
1answer
329 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 ...
7
votes
2answers
341 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 ...
6
votes
1answer
142 views

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

With reference to a 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 a ...
3
votes
0answers
65 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 ...
4
votes
1answer
133 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 ...
3
votes
1answer
262 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 ...
2
votes
2answers
97 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 ...
3
votes
1answer
127 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 ...
3
votes
1answer
71 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?
3
votes
1answer
90 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}[1]{\lvert#1\rangle}\ket u$ to find the corresponding eigenvalue lambda. So far so good. In the order finding algorithm, we also ...
6
votes
2answers
138 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, ...
2
votes
1answer
180 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 ...
4
votes
1answer
174 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 ...
2
votes
2answers
155 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 ...
7
votes
1answer
108 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 ...
1
vote
1answer
144 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 ...
5
votes
1answer
155 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 ...