Subject: quantum computers - summary [rather long]

From: Oleg Goldshmidt <[email-masked]>
Date: 08 Apr 2002 22:37:35 +0300

Hi everybody,

A while ago, in the "Concrete and Abstract Stuff" thread, the
discussion of complexity theory drifted (but of course! happens in
every thread here...) to the realm of quantum computers. The drift was
prompted by a question of mine, more questions were asked, some were
answered (correctly or incorrectly), some weren't. In the end, I wrote:

> So it's back to the literature for me. As soon as I find
> this very last bug in the program, that is...

I will leave you wondering as to whether or not I have found that very
last bug, but I did dig out a couple of papers on quantum computers,
and I'll try to summarize briefly what I learned and give answers to
(some of) the questions raised in the above-mentioned thread. I will
try to give brief quotes from the thread, to provide enough context,
and then offer answers. I may cite several messages at once, so I'll
fix attribution lines (but not the contents) by hand.

It all started from the following exchange:

Oleg Goldshmidt <[email-masked]> writes:

>  "Nadav Har'El" <[email-masked]> writes:
>  
>  > Oleg Goldshmidt <[email-masked]> writes:
>  >
>  > > Are the latest 5-7 qubit quantum computers not Turing machines?
>  > 
>  > Of course they aren't, that's their whole point!
>  
>  Well, I am not so sure about "of course", I still have not made up my
>  mind regarding whether or not it is some massive parallelization
>  technique (the machine crunching various components of a mixed quantum
>  state in parallel).

It turns out that this is a rare case where I was right and Nadav
wasn't. Quantum computers are in fact Turing machines. Similarly to
the representation of classical computers as a series of universal
"gates", there is a set of universal "quantum gates" that can be used
to perform any quantum computation (cf. [1]). An important point is
that quantum systems (and hence quantum gates) are fundamentally
reversible, whereas only the classical NOT is reversible (a == ~~a),
and AND, OR, and NAND are not (see [1] for some fun with
reversibility). Therefore it is not obvious that a quantum computer
can perform any classical computation. Proving this possible was the
great contribution of David Deutsch [2]. In fact, it is possible to
create a Universal Quantum Turing Machine [3].

The advantage of a quantum computer is, indeed, in massive parallelism
of computation that stems from the existence of so-called mixed, or
entangled states. Without going into physics, I'll try to say a couple
of words using maths, which is more likely to be spoken by this list's
subscribers. 

A system of N (classical) bits can be in 2N states. Mathematically,
the state space of such a system is a *cartesian* product of
2-dimensional state spaces of the individual bits, and one of its
bases is a union of the {0,1} bases of the original single-bit spaces.

A state of a qubit-size system can be represented by a vector in a
2-dimensional vector space spanned by a basis of {|0>,|1>} [I am using
Dirac's bra/ket notation, but if it's Chinese to you, it is simply
ASCII for (contravariant) vectors]. The state space of an N-qubit
system is a *tensor* product of the single-qubit spaces, and its
dimension is 2^N.

This is where winnings in parallelization come from. Potentially,
a linear increase in space (e.g. number of processors) can lead to
exponential decrease in computation time [4].

This is not all, however. There was yet another question that I raised
based solely on my physical intuition, without any deep understanding 
of what is going on

Oleg Goldshmidt <[email-masked]> writes:

>  Another thing I never understood was how the result would be obtained
>  from a quantum computer without collapsing the system's wavefunction
>  (on an intuitive level, this looks like defeating the purpose: saying
>  that the result is somewhere in the complex superposition of states
>  and actually getting to it are two different things). I must be
>  missing a few basic things in the whole picture, since (intensely
>  practical) minds like Feynman would certainly have caught basic flaws
>  in the argumentation early on.

That is a fundamental problem indeed. From the quantum point of view,
a measurement (a read on the memory register that contains the result,
if you will) amounts to projections onto the basis vectors of the
state space (I am translating physics into math as I am typing,
loosely at that), and the state of the resulting system is actually
*changed* by the measurement into one of the states represented by the
basis vectors.  Moreover, the final state will be chosen
probabilistically, the probability of each basis state determined by
the co-ordinates of the final state *of the computation* (before the
measurement) with respect to the basis.

Think of it in terms of a gedanken parallelized Monte Carlo
simulation: we have computed - in parallel - an enormous number of
realizations, but we can only access one of them, chosen at random at
that. What have we gained?

It turns out that *in some cases* there are clever tricks that allow
one to finess the measurement problem because the original problem has
some symmetry or other property. One such case (the most famous,
probably, due to its ramifications for cryptography) is Shor's
factoring algorithm ([5], also [4]). There, the trick is based on a
connection between factors and periodicity (thus Fourier transforms),
together with linearity of quantum systems (no interference), and,
most importantly, that it does not really matter which factor we find
first.

Another trick is used by Grover's O(sqrt(N)) search algorithm [6].
There, again, an important property of the problem is that we do
not care which of the set members that satisfy the test conditions 
we find. Details in [6] or [4].

This difficulty leaves the question of whether quantum computers can
be used for a wide variety of applications open. In particular, it is
not known whether a quantum computer can solve NP-complete problems in
polynomial time [4].

If you are interested in this stuff, but not too much, I suggest you
start with a rather non-technical review [4], which gives enough
details for those who do not like pure hand-waving.
 
I warned you it was long...

References.

[1] Feynman Lectures on Computation,
    http://www.amazon.com/exec/obidos/ASIN/0738202967/qid=1018288920/sr=1-1/ref=sr_1_1/104-9138356-8545501

[2] D. Deutsch, 1985, Quantum theory, the Church-Turing principle and 
    the universal quantum computer,
    http://www.qubit.org/resource/deutsch85.pdf
    (I am not through this paper yet - it's very technical - OG)

[3] E. Bernstein, U. Vazirani, 1997, Quantum Complexity theory,
    http://epubs.siam.org/sam-bin/getfile/SICOMP/articles/30092.pdf
    (Unfortunately, one needs a SIAM account to get this, so I
     have not read the paper - OG)

[4] E. Rieffel, W. Polak, 2000 An Introduction to Quantum Computing
    for Non-Physicists 
    http://xxx.lanl.gov/abs/quant-ph/9809016
    (A nice, not very technical review - OG)

[5] P. Shor, 1994, Algorithms for Quantum Computation: Discrete
    Logarithms and Factoring,
    http://www.research.att.com/~shor/papers/QCalgs.pdf
    (Technical, there is a useful outline in [4] - OG)

[6] L. Grover, 1996, A fast quantum mechanical algorithm for database search,
    http://xxx.lanl.gov/abs/quant-ph/9605043

-- 
Oleg Goldshmidt | [email-masked] 
If it aint't broken it hasn't got enough features yet.

---

From: "Nadav Har'El" <[email-masked]>
Date: Tue, 9 Apr 2002 00:28:00 +0300

On Mon, Apr 08, 2002, Oleg Goldshmidt wrote about "[hackers-il] quantum computers - summary [rather long]":
>...
>...

What you explained is why Quantum computers are *at least stronger* than
a Turing machine, not why they are the same thing as Turing machines. Using
a quantum machine you can do some things in polynomial time that you we
don't know how to do in polynomial time in a deterministic Turing machine -
hence they may be really stronger. (Note: I'm saying "don't know how to do"
instead of "can't do", because nobody even knows if P!=NP, for example).

What I meant by "that's their whole point" is that quantum machines can
do things that on a normal computer (or Turing machine) we cannot (or at
least don't know how to) do (efficently). Otherwise, no-one would have been
interested in them.

Your [3] (see link below) seems to some weird results where in some weird
sense the quantum Turing machine is shown to be stronger (and not equal)
than BPP (which is itself stronger or equal to P, if I remember correctly),
but since it involves some Oracle, I'm still not sure what this result
really means.

So I guess we were both right in some sense, we just misunderstood each
other ;) But I think I better shut-up on this issue after this posting,
because I am really not a quantum computing expert (I think we have 2 other
people on this list who are!), to say an understatement. And as they say,
it's better to be thought a fool than to open your mouth and remove all doubt -
I think I opened my mouth too much on this subject :)

> A system of N (classical) bits can be in 2N states. Mathematically,

Ah? why 2N and not 2^N? But it's a bit late, so I guess my brain is a
little tired... Never mind..

> not known whether a quantum computer can solve NP-complete problems in

But it can solve an NP problem that is not known to be in P (such as the
factoring problem).

After reading [3]'s abstract, there's something I don't understand:
If we ever prove P!=NP, is it possible that we might still find that quantum
computers (without oracles) can't calculate in polynomial time anything more
than P? That would be unfortunate, and make quantum computers absolutely
useless...

>      have not read the paper - OG)

I put a copy of this in http://nadav.harel.org.il/pub/30092.pdf
(I hope nobody comes after me for copyright violation... Please don't
redistribute it further.)

-- 
Nadav Har'El                        |        Monday, Apr 8 2002, 27 Nisan 5762
[email-masked]             |-----------------------------------------
Phone: +972-53-245868, ICQ 13349191 |An error? Impossible! My modem is error
http://nadav.harel.org.il           |correcting.

---

From: Eran Tromer <[email-masked]>
Date: Tue, 09 Apr 2002 01:43:23 +0300

Howdy,

It's a nice review, and kudos for identifying the central papers.
Here's some nitpicking.

> create a Universal Quantum Turing Machine [3].

A quantum computer is definitely not a Turing machine. First, "Turing 
machine" is a very specific formalism -- a Pentium (with infinite 
memory) isn't a Turing machine either. I assume it's equivalence 
(polynomial-overhead simulation) rather than "similarity" that you're 
interested in.

There are several different formalisms for representing quantum 
computer. Obviously the quantum *circuit* formalism is not very similar 
to a Turing machine, nor is it equivalent, for the same reason that a 
the classical circuit formalism is not equivalent to the classical TM 
formalism (namely, issues of non-uniformity).

There *is* a formalism of "quantum Turing machines" which is rather 
similar to classical TMs, but there are some very subtle issues in the 
definitions. As you suggest, quantum TMs are indeed at least as powerful 
as classical TMs. The converse is an open problem, (assuming we're only 
concerned with the ability to compute functions or decide languages, as 
opposed, for instance, to communication complexity)

"Universal Quantum Turing Machine" usually refers to a quantum Turing 
machine that can simulate any *quantum* Turing machine, not every 
classical Turing machine as you suggest.

> entangled states. 

"Mixed" and "entangled" are two well-defined concepts and are not 
equivalent. An entangled state is a quantum superposition of several 
state, with complex amplitudes. A mixed state means just classical 
probabilism, i.e., lack of knowledge. The two can be distinguished 
experimentally.

> system is a *tensor* product of the single-qubit spaces, and its

A classical N-bit system can assume 2^N distinct states, and the state 
space has degree N. A state is characterized by N boolean values.

A quantum N-qubit system can assume infinitely many distinct states. The 
*dimension* of the state space is indeed 2^N, but each state is 
characterized by 2^N-1 complex values (for pure states; many more for 
general mixed states). You can't obtain an infinite amount of storage of 
parallelism, though, because of the limitations implied by quantum 
mechanics on the way these values can be manipulated and measured.

By the way, for those interested in a concise yet clear and 
comprehensive introduction to quantum computation, I would recommend the 
review paper by Dorit Aharonov:
http://xxx.lanl.gov/abs/quant-ph/9812037

   Regards,
     Eran Tromer

---

From: Eran Tromer <[email-masked]>
Date: Tue, 09 Apr 2002 01:57:28 +0300

Hi,

> than P? That would be unfortunate, and make quantum computers absolutely

AFAIK, such implication is not known to hold for bounded-error 
computation. That is, quite plausibly P!=NP and BPP!=BQP. Whether we'll 
be able to prove either inequality is a different matter...

I'm not sure about the zero-error classes (P and EQP); if I recall 
correctly, their strict equivalence is open but if you add an 
arbitrarily small amounts of noise then they become equivalent.

   Regards,
     Eran

---

From: Oleg Goldshmidt <[email-masked]>
Date: 09 Apr 2002 22:41:31 +0300

Eran Tromer <[email-masked]> writes:

> memory) isn't a Turing machine either. 

Of course it isn't.

> I assume it's equivalence (polynomial-overhead simulation) rather
> than "similarity" that you're interested in.

As I wrote in the follow-up to Nadav's message, I started from the
point of view that Turing-equivalency was about computability, not
practicality/complexity.

Maybe this starting point is wrong from the point of view of modern
CS. Please someone let me know (there are enough experts on the list)
and I'll apologize and shut up - again ;-).

Extra gratitude to the kind soul who will point me to a discussion of 
"optimal" Turing machines - a notion that must make sense if
complexity is in the picture.

> probabilism, i.e., lack of knowledge. The two can be distinguished 

I didn't mean lack of knowledge in the classical sense. I must admit
that a) my quantum mechanics is rusty - I don't work in the field, b)
I originally studied it in a different language (in which "mixed" and
"entangled" would be the same - or very similar - word). In any case,
I meant a superposition of states.

> A classical N-bit system can assume 2^N distinct states, 

The dimension of the state space is not determined by how many
possible states a system can have, but how many numbers (co-ordinates)
are needed to describe any single state. Maybe I was unclear - it
confused Nadav, too.

> http://xxx.lanl.gov/abs/quant-ph/9812037

Thanks! I'll make more sense to myself after I read it.

---

From: Oleg Goldshmidt <[email-masked]>
Date: 09 Apr 2002 22:19:06 +0300

> instead of "can't do", because nobody even knows if P!=NP, for

I am missing something conceptual here. I thought that the idea of
Turing machines was to separate computable problems from
non-computable ones. The question of efficiency or complexity is that
of an algorithm used, and is quite separate in my mind.

In particular, the usual statement is that having multiple Turing
machines (a finite number of those) working in parallel makes no
difference in principle, since the computation can be performed
sequentially by a single Turing machine. Since - OK, let me be
cautious - I have not seen anything that would contradict the
statement that there is nothing in any single thread of parallel
quantum computation that is not computable by a classical Turing
machine, I conclude that anything a quantum computer can do, a
classical computer can also do. It may take the classical computer
more than Hubble time, but that's immaterial as far as
Turing-equivalency is concerned.

I am a bit (a qubit?) confused (and need to do much more reading) with
the universal quantum gate representation as well. It seems that a set of
1-bit rotations plus a 2-bit XOR can perform any quantum computation
(phase shifts are irrelevant) - cf.

http://xxx.lanl.gov/abs/quant-ph/9503016

- I have not yet read it, just glanced through very quickly.

I suspect that each of those individually can be performed by a
(probably exponential but) finite number of classical gates. This will
prove that any quantum computation can be performed by a set of
classical gates, albeit much less efficiently. What bothers me here is
that rotations for arbitrary angles are needed, and there is an
infinite number of those, seemingly, which is problematic. On the
other hand, a quantum computation of a finite number of operations
will need a finite number of rotations to perform. Yet another angle
is the data which is also quantum. On top of that, we are familiar
with computational models that do not distinguish between programs and
data... Forget it, it's silly to apply common sense to technical
aspects of the quantum world. I need more time to read and think.

> other ;) 

I suspect that the mutual misunderstanding stems from the different
understanding of the definition of Turing machine - stopping or
complexity.

> But I think I better shut-up on this issue after this posting,
> because I am really not a quantum computing expert 

And I even lack the benefit of formal CS education, so my email
account should be revoked ;-) My understanding of turing machines
might differ from what is taught in a modern CS course at the
Technion, and I should certainly defer to that authority.

> (I think we have 2 other people on this list who are!),

I guess Eran Tromer is one - why didn't he (and the other one) stop me
in time? ;-)

> it's better to be thought a fool than to open your mouth 
> and remove all doubt

Too late for me... ;-)

Is that the difference between mathematicians and physicists? The
latter consider only one question stupid, "May I ask a stupid question?"

> than P? That would be unfortunate, and make quantum computers absolutely

Not necessarily. Grover's search is considered pretty useful,
apparently. ;-)

> I put a copy of this in http://nadav.harel.org.il/pub/30092.pdf

Thanks! More stuff to study...

---

From: Dan Kenigsberg <[email-masked]>
Date: Wed, 10 Apr 2002 18:11:17 +0300 (IDT)

> of an algorithm used, and is quite separate in my mind.

The two questions are indeed separate, but voth can be discussed with the help
of Turing machines. Turing machine is a computation model, it is a 
specification of the concept of executing an algorithm.
Using this realization of computation, one way ask what can be done and what
cannot, or the other questions like what can be done within Poly(n) steps.
In fact, one cannot discuss the complexity of an algorithm without defining the
basic operations.

Using other models of computation may render different answers. Indeed, many
believe that supplying a TM with randomness would allow it to solve some
problems more efficiently. Furthurmore, many people believe that quantum gate
array is even more efficient in solving some (other) questions.
Anyway, as you suspected, the "quantum speedup" is exponential *at most*, which
means for example that a quantum computer could not solve the halting problems -
if it could, there would be a classical TM that would do it too, only
explonentialy slower.  All it needs is to calculate the probability of each and
every outcome and select one of them appropriately.
 
To sum things up: 
* R=QR (probelms solvable by Turing machine are exaclty those solvable by quantum turing machine)
* BPP<=BQP (probabilistic TM are not stronger than quantum machine), yet it is
  not known by now whether BPP<BQP sharply
* BQP<=EXP (and even BQP<=PSPACE). Again, the sharpness question is still open.

I hope that clears things a bit for you, call any of the "experts" to correct me
any time, and glad that we can talk about nonsense while war is fought all
arround.

Dan.

---

From: Adeyemo oluseyi <[email-masked]>
Date: Wed, 10 Apr 2002 17:15:01 -0700 (PDT)

Hi dan,
      I want to have full understanding on how to
hack.
E.G CREDIT CARD, SITES, PASSWORD AND BANK.
   Thaat was my main purpose of joining you site and i
want to tell you that someone Hack my password and
deleated all my confidential message even he even
clear off my credit card information.If there is any
way you can use to help me to get another card and
also to strike back,i will be very glad to read from
you.
Thanks
Richard oluseyi
  Hi dan,
--- Dan Kenigsberg <[email-masked]> wrote:
> * R=QR (probelms solvable by Turing machine are
> exaclty those solvable by quantum turing machine)

__________________________________________________
Do You Yahoo!?
Yahoo! Tax Center - online filing with TurboTax
http://taxes.yahoo.com/

---

From: "Nadav Har'El" <[email-masked]>
Date: Thu, 11 Apr 2002 11:47:43 +0300

> want to tell you that someone Hack my password and

It's customary to read a mailing list for a few days (or browse
its archives) before posting to it, to get a feel for the kind of
discussion that goes on in it.

Obviously, you didn't bother to do that, or you'd have known that
this list is *not* about cracking (what you call "hack"). It's
about doing inteligent and fun things with computers, not about how
to steal from others.

-- 
Nadav Har'El                        |     Thursday, Apr 11 2002, 29 Nisan 5762
[email-masked]             |-----------------------------------------
Phone: +972-53-245868, ICQ 13349191 |Energizer Bunny arrested - charged with
http://nadav.harel.org.il           |battery.

---

From: Eran Tromer <[email-masked]>
Date: Mon, 15 Apr 2002 00:59:50 +0300

Howdy,

 > point of view that Turing-equivalency was about computability, not

Ah. Yes, that would explain it. :-)
I think Dan explained the matter quite well.

 > Extra gratitude to the kind soul who will point me to a discussion
 > of "optimal" Turing machines - a notion that must make sense if

It usually doesn't matter, and here's why.
You could ask the following question:
   "What problems can be solved in time at most f(n),
    where n is the input size?"
The answer indeed depends on the exact formalism you choose, and thus
the question isn't a very good one. Instead, we define classes of
functions, i.e., poly(n) which denotes the class of all polynomial
functions, and then ask:
   "What problems can be solved in time f(n) such that f(n)
    is in poly(n)?"
Or in short:
   "What problems can be solved in time poly(n)"?

Now here's the trick. According to the Church-Turing thesis (which is
not quite well-defined, yet is widely believed), any "reasonable"
computational model can be simulated by a Turing machine with polynomial
overhead. That is, whatever "reasonable" computational model you pick,
if under this model a problem P can be solved in time f(n) then a Turing
machine can solve P in time f(n)^c for some constant c. Specifically, 
this has been proven for all "reasonable" models proposed so far, with 
the notable exceptions for quantum computation.

The trick is that the commonly discussed classes of functions are
indifferent to the simulation overhead for instance, if f(n) is in 
poly(n) then so is f(n)^c. Thus, as long as we deal with classes like 
poly(n), we don't give a hoot about optimality of the model, but merely 
pick the model that's most convenient for us at the moment, and (if 
needed) prove its equivalance (up to polynomial overhead) to a the 
Turing machine model.

I can't at the moment think of any reference material which addresses
these issues prior to page 150, but I don't see a good reason for that,
so I can try to find some if you wish.

   Regards,
     Eran Tromer