16
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) ...
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{...
12
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 ...
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
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
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
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 ...
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} \...
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 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\...
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
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 ...
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 $...
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
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
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?
...
3
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....
3
If $r$ is the least common multiple of the $r_i$, then for each $r_i$ there is an integer $s_i$ such that $r=r_is_i$. If at least one of the $r_i$ is even, then so is $r$, which we need.
Moreover, if all the $r_i$ agree on the powers of 2 dividing the $r_i$, then $r$ contains the same number of powers of 2, and $s_i$ must be odd. Hence, for each $i$,
$$
x^{...
3
Shor's algorithm is based on the gate model of quantum computation. However, there are alternatives to the gate model, such as quantum walks, etc. See all of the answers to this question for a nice summary of the different models of computation.
As to what I believe to be the implicit question "is Shor's the only known quantum factoring algorithm, or are ...
2
If $a^{r/2} \equiv -1$, then $a^{r/2}$ is a trivial square root of $1$ instead of an interesting square root. We already knew that $-1$ is a square root of $1$. We need a square root we didn't already know.
Suppose I give you a number $x$ such that $x^2 = 1 \pmod{N}$. You can rewrite this equation as:
$$\begin{align}
x^2 &= 1 + k \cdot N
\\
x^2 - 1 &...
2
The requirement that $a^r\equiv 1\mod N$ is equivalent to requiring that $a^r - 1\equiv 0\mod N$.
We want a number, $b$, such that the greatest common denominator of $b$ and $N$ is a proper factor of $N$ (i.e. is a factor $\neq 1, N$).
We also have that $a^r-1 = \left(a^{r/2}-1\right)\left(a^{r/2}+1\right)$.
So, we take $b = a^{r/2}-1$. We know that $r$ ...
Only top voted, non community-wiki answers of a minimum length are eligible
