Perhaps we're soon going to have decent-sized quantum computers. At that
point, if they're going to be very useful, we'll need quantum compilers
to translate ordinary code into a quantum programming language like Q-gol
(see http://rosebay.matra.com.au/~gregb/q-gol//index.html).
A note for the future: in "Quantum theory of computation and relativistic
physics" (quant-ph/9701027), Alexander Vlasov (vlasov@physics.harvard.edu)
writes "... it should be mentioned that in relativistic physics there is
no sharp division between q-gates and q-states ... This property of a QFT
has some analogy with functional style of programming in modern computer
science. In both cases there is no essential difference between data
(states) and functions (operators). A function can be used as data for
some other function."
And just out: the preprint quant-ph/9702001 says in its abstract: "We
discuss relations between decoherence and computational complexity and
show that the quantum factorization algorithm must be modified in order
to be regarded as efficient and realistic."
-mitch
http://www.thehub.com.au/~mitch/q-comp.html
Shor's Algorithm, take one
[Based on Samuel Braunstein's tutorial on quantum computation, at
http://chemphys.weizmann.ac.il/~schmuel/comp/comp.html.]
Suppose we want to factor the number N. Here's the complete procedure
that Shor follows:
A: Find a number x, coprime to N.
B: Find the least number r such that x^r - 1 is a multiple of N.
If r is odd, return to A and pick a new x; otherwise proceed to C.
C: Since r is even, we can say
x^r-1 = (x^[r/2]-1) (x^[r/2]+1) = kN (for some k)
For each of the two lefthand factors, find its greatest common divisor
with N (for example, via Euclid's algorithm). If this isn't 1 or N,
you've found a factor.
The first part of (B) is the computationally intensive part. The quantum
computer finds r, in effect, by starting with the sequence (1,2,3,...,q),
where q is some large number, then computing the sequence (x^0 mod N,
x^1 mod N,... x^q mod N), and determining the period of this second sequence
(which will be equal to r, since by hypothesis x^r mod N = 1 = x^0 mod N).
Shor's algorithm requires a quantum computer with two multi-qbit registers.
The first register is the read-out point, the second register is for an
intermediate computation. The qbits are all two-state quantum systems,
so the computer has a set of binary states of the form |0110...;1110...>,
or |i;j> for short, where i is the value of the first register (i.e., the
first set of qbits), j the value of the second register.
Since it's a quantum computer, we can have superpositions of these states,
so a general state of the computer has the form
sum[i,j] c[i,j] |i;j>,
where c[i,j] is the complex coefficient of basis state |i;j>.
This is the quantum algorithm for carrying out (B):
Step 1: Initialize the quantum computer to |0;0>.
Step 2: Place the first register into a superposition of all values.
|0;0> -> sum[m] |m;0>
Step 3: Compute f(m) = x^m mod N in the second register.
sum[m] |m;0> -> sum[m] |m;f(m)>
Step 4: Perform a quantum fourier transform on the first register.
sum[m] |m;f(m)> -> sum[m,n] exp[2i(pi).mn/q] |n;f(m)>
(q is the number of basis states for the first register; m and n
are summed only from 0 to q-1.)
You can do everything up to this point on a classical computer with
Initialize c[0..q-1,0..q'-1]
For all m,n
Let c[m,n] = 0
For m,n from 0 to q-1
Add exp[2i(pi).mn/q] to c[m,f(n)]
The quantum transformations corresponding to steps 1-4 have all been
described (just not performed, outside of simulation).
Step 5: "Read out" (measure, collapse) the first register.
... And this is where I have a lapse of understanding. The whole
point is that the quantities in Step 4 are supposed to add up to
something other than zero ("interfere constructively") only for
values of m which will allow you to infer r, the period of f(m).
So far I haven't been able to demonstrate this to my own
satisfaction, and Braunstein passes the point by in a single
sentence. I'll keep trying.