21
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 were really the first instances that showed particularly valuable types of speed-up with a quantum computer (e.g. the presumed exponential improvement for Shor) ...
16
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, such as 56,153 in 2014, have been factored using a minimization algorithm, as detailed here. For a convenient reference, see Table 5 of this paper:
$$
\begin{...
15
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$. The question is a poignant one and not easy to answer as there are various tradeoffs possible (e.g., between number of qubits and circuit size).
Executive ...
9
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 actually use the RSA cryptosystem. That means to a quantum computer, encrypting/decrypting RSA legitimately would be about the same speed as using Shor's ...
9
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. That is to say, it reverses the order of all of the computational basis states except for $|0\rangle$ which stays where it started. $|k\rangle$ becomes $|-k\...
8
The answer to noise (and any source of error, really) in quantum computations is quantum error correction: You choose an encoding such that discretized errors correspond not only to invalid encodings but also uniquely determine what kind of error must have occured. This is not possible for all errors but with reasonable error models (such as single qubit ...
7
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 the superposition. The only way to extract the amplitudes is to make the same state many, many times, and keep repeating your measurements until you get enough ...
7
Let's represent $N^2$ as $2^a+b$, where $a$ is the greatest power of 2 that not exceeds $N^2$, and $b \ge 0$ (which is always possible to do - $a$ is just the number of bits in binary representation of $N^2$). Then $n = a+1$:
$N^2 \le 2^{a+1}$, because otherwise $a$ would not be the greatest power of 2 that not exceeds $N^2$.
$2^{a+1} \le 2N^2 = 2(2^a+b) = ...
7
Let me attempt to give a rather unconventional answer to this question:
As a non-mathematician/software programmer I'm trying to grasp
how QFT (Quantum Fourier Transformation) works.
Suppose that we have a quantum computer which is able to manipulate $n$ qubits. The quantum state of such a quantum computer precisely describes the current state of this ...
7
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 times does each have to evaluate the function.
For the classical algorithm you're suggesting, you'd calculate $a\text{ mod }N$, and $a^2\text{ mod }N$, and $a^...
7
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 $s$ and $r$ given $x/T$. For example, if $s=1$ and $r$ is large, then we cannot afford to confuse $1/r$ with $1/(r+1)$, say.
In more detail, think about any ...
6
You skipped a step in the algorithm.
First check if $N$ is even. $35$ is not even.
Next determine if $N=a^b$ for $a \geq 1$ and $b \geq 2$. It's not.
Randomly choose $x$ in the range $1$ to $N-1$. If $\text{gcd}(x,N) > 1$ then return the factor $\text{gcd}(x,N)$. This is what you missed. $\text{gcd}(10,35) = 5$ There's no reason to perform order finding ...
6
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 (or at least as much as possible) out, that might introduce any noise (radio waves, such as phone signals or light, magnetic fields, ...), we do everything to ...
6
For Shor's algorthm:
State of the art is still 15. In order to "factor" 21 in the paper Heather mentions, they had to use the fact that $21=7\times 3$ to choose their base $a$. This was explained in 2013 in the paper Pretending to factor numbers on a quantum computer, later published by Nature with a slightly friendlier title. The quantum computer did not ...
6
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 $p(y)$ of getting the state $|y\rangle_n$ is $|a_y|^2$ where $a_y \in \Bbb C$ (i.e it's a complex number).
In your example, $$a_y = e^{2\pi i x_0 y/2^n} \...
6
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 a Bell state run on the IBM Quantum Boeblingen device from the theoretical answer as a function of the number of shots taken. For each value of the shots, the ...
6
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 qubit it would take you around $8$ hours to 'run' Shor's algorithm for a $2048$ bit key.
For a 'proof' you can read the paper, but there are a few important things to realize here:
This is an estimate
...
6
Perhaps a simpler example will help. Let the unitary $U$ permute $\vert 0\rangle$ and $\vert 1 \rangle$. That means $U\vert 0\rangle = \vert 1\rangle$ and $U\vert 1\rangle = \vert 0\rangle$.
Then clearly, $$U\left(\frac{\vert 0\rangle +\vert 1 \rangle}{\sqrt{2}}\right) = \frac{U\vert 0\rangle + U\vert 1\rangle}{\sqrt{2}} = \frac{\vert 1\rangle + \vert 0\...
5
Check out Thoerem 5.3 in Nielsen and Chuang. It conveys that we are almost guaranteed to get a good value of $x$ (the probability is stated to be at least $1-\frac{1}{2^m}$ where there are $m$ unique prime factors of $N$). The expected number of repetitions of the algorithm (due to this effect) is only just more than 1. At worst, it's 2. There's no absolute ...
5
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-communication theorem. If measuring the ancillae could affect the success of the algorithm, you could communicate faster-than-light by starting the algorithm many times, ...
5
Your question contains the answer, as you mention the controlled-U gate which is an entangling gate. You will see in the page I linked, that the action of c-U on $|+\rangle|0\rangle$ for example can turn the state into one which cannot be written as a product:
$|+\rangle|0\rangle = \left( \frac{|0\rangle+|1\rangle}{\sqrt{2}} \right)\otimes |0\rangle = \...
5
The size of the number factored is not a good measure for the complexity of the factorization problem, and correspondingly the power of a quantum algorithm. The relevant measure should rather be the periodicity of the resulting function which appears in the algorithm.
This is discussed in J. Smolin, G. Smith, A. Vargo: Pretending to factor large numbers on ...
5
This self-answer gives a not-very-good worst case analysis. I'd really rather have a proper distribution of repetition counts.
Probability of a period resulting in factoring
In Shor's original paper, you can find the following statement:
The multiplicative group (mod $p^α$) for any odd prime power $p^α$ is cyclic [Knuth 1981], so for any odd prime power ...
5
A QFT can't arbitrarily raise the probability of any state you want to any value you want. Once you create a superposition, you need to find some way to make destructive interference occur between the states you don't want, and construct interference between the states you do want. Finding ways to do this is essentially the entire field of quantum algorithms....
5
It is a "negative" control.
In other terms, the gate in your circuit will apply a NOT on the last qubit if and only if the following conditions are both met:
$\vert x_3\rangle = \vert 0 \rangle$
the first ancilla qubit is in the state $\vert 1 \rangle$.
A "normal" control (i.e. not an empty circle) would change the first condition to $\vert x_3 \rangle =...
5
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 reading out the result, the desired result gets a high probability.
The power of quantum computing comes from the vast phase-space that grows exponentially with ...
5
Shor's algorithm is often quoted as having a cost of $\mathcal{O}(\log^3 n)$ quantum operations, though it's actually a bit smaller than that: $\mathcal{O}\left((\log n)^{2} (\log \log n) (\log \log \log n) \right)$, but since $\log \log n < \log n$ we know that the "verbose" cost is less than the often quoted cost of $\mathcal{O}(\log^3 n)$.
...
4
$$
\log_2 604,661,760,000,000,000 \approx 59.07
$$
So use $60$ qubits for the data lines where you will put a uniform superposition. This gives a total of $61$ qubits to run Grover's.
$2^{59} = 5.764607523034e+17$ so if you can throw away about $2.8e+16$ possibilities first, you would be able to do it $60$.
Edit: As cautioned this is for logical qubits.
4
There are a number of questions here.
Regarding your first question:
So does measurement matter or not?
I learned a lot about quantum computing/quantum mechanics by figuring out why measuring the second register is optional. If it weren't optional, then we can send superluminal messages.
For example, suppose Alice runs Shor's algorithm. After ...
4
Shor's algorithm relies on determining the period of $a^x\bmod N$. If you only evaluate up to $N$, then you are undersampling, in much the same way that you would classically be below the Nyquist criteria.
For example, if you measure the second register and get $y$, the first register collapses to all $x$ such that $a^x\bmod N =y$. These $x$ collide at $...
Only top voted, non community-wiki answers of a minimum length are eligible