Accepted

The question is about how many logical qubits it takes to implement Shor's algorithm for factoring an integer $N$ of bit-size $n$, i.e., a non-negative integer $N$ such that $1 \leq N \leq 2^n{-}1$. ...

Accepted

Have there been any truly ground breaking algorithms besides Grover's and Shor's?It depends on what you mean by "truly ground breaking". Grover's and Shor's are particularly unique because they ...

Accepted

The prime factorization of 21 (7x3) seems to be the largest done to date with Shor's algorithm; it was done in 2012 as detailed in this paper. It should be noted, however, that much larger numbers, ...

If you mean that you seek the order $r$ of $a$ modulo $N$, where $N$ is an integer and $a \in \mathbb Z_N^*$, then note that this problem can be efficiently reduced classically to the integer ...

A bit of an esoteric answer: there is a particular proposal for post-quantum cryptography called "CSI-FiSh", based on isogenies. Without getting too deep into the number theory, the ...

community wikiIt's an interesting question to pose which problems reduce to factoring (or discrete log), and whether any of those problems could be of practical value. In general I think the ...

Here's my answer, for the record.First, when we're talking about problems being $\text{NP}$-hard or $\text{NP}$-complete, we're talking about decision problems — so we need to express order finding ...

Accepted

In "Reducing the Number of Qubits in Quantum Factoring" (2024), Chevignard et al prove you can factor an $n$ bit number with $(0.5 + \epsilon)n$ logical qubits. Concretely, they estimate ...

Accepted

I assume you mean the result from this paper, where the authors (including 'our very own' Craig Gidney) have estimated that if you have $\sim20$ million noisy qubits it would take you around $8$ hours ...

Accepted

The simplest conversion is just scale the time. The cycle time increases by a factor of 1000, so it takes a decade to run instead of a week.A much better conversion is to account for the switch from ...

Accepted

Asymptotically, Shor's algorithm is really efficient. Basically it's just: superposition, modular exponentiation (the slowest step), and a fourier transform. Modular exponentiation is what you do to ...

For Shor's algorithm, it actually doesn't matter which one you use.If you apply the QFT twice, it is equivalent to a classical multiplication by -1 modulo $2^n$ where $n$ is the size of the register....

Accepted

Given that the QFT is exponentially faster than the FFT, The problem with quantum computing is that they are not actually parallel computers: One is tweaking the qubits in such a way that when ...

Accepted

I think you're right. Your idea is kind of similar to how the factoring in "How to factor 2048 bit RSA integers in 8 hours using 20 million noisy qubits" is done, except in that paper the p+...

Since Craig referenced me in his answer, I will chime in and follow up a bit on what Craig wrote.Since there are several sub-questions to your question, I will answer in parts:First, to answer your ...

Accepted

Every number with at least two odd factors has non-trivial square roots. You get the non-trivial square roots by breaking them down into $\pm 1$ square roots for each factor and applying the Chinese ...

Accepted

Factoring a 2048 bit number with Shor's algorithm involves performing one billion Toffoli gates under superposition (ref).Suppose your superposed Toffoli gate error rate is an amazing 0.01%. Note ...

Accepted

Is that correct? Is it [not] necessary to measure the ancilla qubits in Shor's algorithm?Correct, it is not necessary to measure the ancillae.This is easily seen by appealing to the no-...

You probably shouldn't be thinking of the Quantum Fourier Transform as being something where you want to extract the outcoming probability amplitudes. As you say, when you start measuring, you destroy ...

Accepted

In a nutshell, the number of qubits in the top register directly corresponds to the number of bits of precision to which $x/T$ approximates $s/r$, and we need enough precision to be able to determine $...

Accepted

In general, the number of shots does not increase the accuracy of an experiment. Rather it gives a more precise answer. Attached is a figure showing the distance (in terms of Hellinger distance) for ...

Remember that the unitary portion of any quantum algorithm is necessarily reversible. On the other hand, the map $f(x,y)\mapsto x\cdot y$ which sends two integers to their product is not. This is ...

Accepted

Shor proves in [Shor94] [Shor97] that if $N$ is a positive odd integer that has $k \ge 2$ distinct prime factors, and if $a$ is selected uniformly at random from $\mathbb Z_N^*$ as in your steps 1–2, ...

Accepted

The number of runs required is arbitrarily close to 1, using the correct post-processing. See "On the success probability of quantum order finding" by Martin Ekerå from Jan 2022:We prove a ...

Accepted

If you have a quantum state like $$|\Psi\rangle_n = a_0|0\rangle_n+a_1|1\rangle_n+...+a_n|2^n-1\rangle_n$$ and you measure it in the $\{|0\rangle_n,...,|2^{n-1}\rangle_n\}$ basis, then the probability ...

Accepted

The essential feature of this problem is that while both the quantum and classical algorithms can make use of the efficient classical function of calculating $a^k\text{ mod }N$, the issue is how many ...

Nielsen and Chuang Box 5.2 does indeed need more elaborate explanation.I’m going to describe the architecture of efficient $O(n^3)$ modular exponentiation circuit from the paper ‘Quantum Networks for ...

Accepted

If $f(x) = a^x \pmod{N}$ passes through $-1$, that value of $a$ won't work. For example, $a=2$ fails for $N=33$ because $2^5 = 32 \equiv -1 \pmod{33}$. This should have been mentioned in whatever ...

Accepted

How do we prevent quantum noise in a quantum computer?Well, technically the answer is (at least for most systems): we use ridiculously low temperatures (much colder than space), we shield everything ...