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
0answers
24 views
+50

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
62 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?
2
votes
1answer
42 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 ...
5
votes
2answers
59 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
92 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
125 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 ...
1
vote
2answers
107 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
0answers
55 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 ...
0
votes
0answers
16 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"...
1
vote
1answer
71 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 ...
3
votes
0answers
68 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 ...
1
vote
1answer
59 views

Quantum Phase Estimation Circuit and Modular Exponentiaton

In Nielsen and Chuang, it is stated that the effect of phase estimation circuit is mapping state $|j\rangle |u\rangle$ to $|j\rangle U^j |u\rangle$. Here is my solution: Consider the first $CU^{2^0}...
2
votes
2answers
122 views

Quantum computers don't try all the possible solutions, so how does the QFT really work?

Scott Aaronson is fond of saying "Quantum computers do not solve hard search problems instantaneously by simply trying all the possible solutions at once." That is, they are not non-deterministic ...
3
votes
5answers
153 views

Any other quantum algorithms than Jozsa-Deutsch decision algorithm, Grover search algorithm, Shor factorization algorithm?

I have been working on implementing Jozsa-Deutsch decision algorithm, Grover search algorithm, Shor factorization algorithm on my home-made 2 qubits device. I am wondering if there are any other ...
3
votes
2answers
122 views

What is Quantum Phase Estimation in Shor's Algorithm?

While I'm studying Algorithm, I couldn't understand what Quantum Phase Estimation is. And I heard there is relation between Phase-Kickback and Quantum Phase Estimation. I wonder what it is. Also, I'm ...
7
votes
2answers
365 views

Does the quantum Fourier transform have many applications beyond period finding?

(This is a somewhat soft question.) The quantum Fourier transform is formally quite similar to the fast Fourier transform, but exponentially faster. The QFT is famously at the core of Shor's ...
2
votes
1answer
92 views

Shor algorithm - how to obtain a period from diagram?

I'm studying shor's algorithm. I implemented in Qiskit and apriori I know that a period is 3 in my example. However, unless I know about period, how to obtain this period only according to seeing ...
1
vote
1answer
110 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 ...
4
votes
1answer
68 views

What do empty white circles mean in a quantum circuit?

I'm studying Shor's algorithm. but I see from the beginning this empty circle. what this circle means??
3
votes
1answer
309 views

Implementing QFT for Shor's Algorithm?

I'm studying Shor's algorithm. This diagram shows a calculation of $4^x\mod21$. I don't understand how this expresses $4^x \mod21$. Could you explain this? For example, by showing another calculation ...
1
vote
1answer
76 views

How to implement modular exponentiation efficiently in Shor's algorithm?

I'm a noob in quantum computing and I'm trying to get Shor's algorithm working on Q# (the language is unrelated). However, I'm stuck on computing $f(x)$s in the quantum circuit. Let $N\sim \log_2(n)$ ...
2
votes
1answer
93 views

Quantum computing w.r.t. the many-worlds theory [duplicate]

Quantum algorithms are inherently probabilistic. Let's say I run Shor's factoring algorithm on some number. There's a chance that the output I observe is incorrect. Does the many-worlds theory suggest ...
4
votes
1answer
153 views

Why is the size of the top register for Shor's algorithm chosen as it is?

Let $N$ be the number we're trying to factor. In Shor's algorithm, the top register then has $2 \lceil\log_2(N)\rceil+1$ qubits, while the bottom register (the ancilla qubits) has $\lceil\log_2(N)\...
2
votes
1answer
386 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 ...
2
votes
1answer
240 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 (...
1
vote
0answers
40 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!
4
votes
1answer
71 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 ...
6
votes
1answer
726 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 ...
5
votes
2answers
456 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 ...
6
votes
0answers
111 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 ...
4
votes
0answers
46 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 ...
4
votes
1answer
289 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.
3
votes
1answer
181 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?
3
votes
1answer
98 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?
0
votes
1answer
70 views

Why do we search for square roots of 1 in Shor's algorithm unlike the qudratic sieve?

In the quadratic sieve algorithm, the idea is to find $a$ and $a$ such that $a^2 \equiv b^2 \bmod n$. We need that $a\not\equiv \pm b \bmod n$. However, there the $c$ is not necessarily $1$. $\gcd(b \...
1
vote
1answer
60 views

Confusion regarding probability of period resulting in factoring

This is a sequel to 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 ...
4
votes
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 $...
4
votes
1answer
183 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 ...
10
votes
3answers
448 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?
6
votes
1answer
538 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\...
2
votes
0answers
426 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 ...
8
votes
2answers
2k views

Why is quantum Fourier transform required in Shor's algorithm?

I’m currently studying the Shor’s algorithm and am confused about the matter of complexity. From what I have read, the Shor’s algorithm reduces the factorization problem to the order-finding problem ...
6
votes
1answer
180 views

What happens with first phase factor in QFT?

I'm using Mermin's Quantum Computer Science book to understand Shor's algorithm, but I can't figure out why one of the phase factors drops out of the probability for measuring a certain y. This is ...
4
votes
1answer
154 views

Shor's algorithm effectiveness

In Shor's algorithm we require the period to be even. If the period is not even or $x^{r/2}+1 \equiv 0 \bmod N$ then we have to restart the process and pick a new random $x$. Why do we know that the ...
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 ...
2
votes
2answers
478 views

Shor's algorithm beginning

This may be a silly question but at the start of Shor's algorithm to factorise a number $N$ we need to find a number $n$ such that $N^{2} \leq 2^{n} \leq 2N^{2}$ Why does such a number $n$ exist for ...
4
votes
1answer
162 views

Understanding why the modular function part of Shor's algorithm is unitary

I've been struggling to understand the modular exponent bit of Shor's algorithm. My understanding is that it takes a register in the state $\frac{1}{\sqrt{Q}}\sum_{k=1}^{Q-1} |k\rangle |0\rangle$ to ...
5
votes
1answer
239 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$ ...
2
votes
1answer
166 views

Is this the correct quantum circuit for the order-finding algorithm?

The algorithm is being implemented on Cirq, with the goal of finding the smallest $r$ for cooprime numbers $x$ and $N$ satisfying the equation $x^r \ = \ 1($mod $N)$. I have set $x \ = \ 2$ and $N \ = ...
6
votes
1answer
343 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 $...