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) ...
14
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 ...
13
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{...
8
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 ...
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 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 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
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^...
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
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) = ...
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
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\...
6
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
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 ...
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
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
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
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 ...
5
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 ...
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 =...
4
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 ...
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
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 $...
4
It seems that you are trying to make sense of compiled circuits from this paper. All Sections, Tables and Figures noted below are in reference to this paper. The short answers are in bold in case you are not looking for explanation.
WHY?
The circuit in your question is a "compiled" quantum circuit, which uses known information about the solution to a ...
3
The Fourier transform part (everything from the swaps onward) looks correct. The initialization (column of Hadamards) looks correct. But the part where you do controlled modular multiplications doesn't, because there's no operations controlled on the 2nd through fifth qubits that you are QFT-ing.
You also seem to expect the output to be the period, when ...
3
You can test stand alone the a modular multiplication circuit. In this case $\text{base} = 2$ and $N = 3$. However the smallest useful composite $N = 15 = 3 \times 5$.
Let's take a well known Multiplication by 7 modulo 15 circuit
We start with input $$\ |1\rangle \text{ gives } |7\rangle$$
$$\ |7\rangle \text{ gives } |4\rangle$$
$$\ |4\rangle \text{ gives ...
3
The critical thing, in this case, about a unitary operator is that it maps orthogonal states to orthogonal states (if $\langle i|j\rangle=0$, then $\langle i|U^\dagger U|j\rangle=0$, so the transformed vectors $U|i\rangle$ and $U|j\rangle$ are orthogonal). Now, you've defined what it must do for a set of states:
$$
|k\rangle|0\rangle\mapsto |k\rangle|f(k)\...
3
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 = \...
3
Given that there is an efficient way to create the sequence
classically, can we not just add a little check for whether we have
encountered $x^{r} = 1 \ \text{mod} N$? During the creation process,
it should not increase complexity to exponential-time, right?
Why bother with quantum Fourier transform at all? Did I misunderstand
it in some way?
...
Only top voted, non community-wiki answers of a minimum length are eligible
