[FOM] Status of Quantum Computing vis-a-vis Chomsky Hierarchy/Computing

[Duraid Madina]

Steve,
 
> 1. QC would apparently fail on several of the restrictions on 
> "computing abstractions", particularly those in Rogers 
> *Theory of Recursive Functions and Effective Computability*, 
> chapter 1.
> 
> True or False?

I can't say I've seen this text, but just looking at that title I'm
going to guess "false" anyway. (If you can tell me what these
abstractions are, I'd be happy to give you a more considered answer!)

For the vast majority of people in the field (i.e. everyone short of a
few individuals), a quantum computer computes just your normal recursive
functions, and the evolution of a quantum computer is something
perfectly computable by a classical computer. There are a relatively
large number of papers describing the various quantum computer
simulators that are in use.

> 2. Does QC compute something outside Turing computable?
> 
> If so, what is the simplest example?

No, QCs can't compute anything a classical computer can't, but it's
supposed that a large QC could do some things much faster than its
classical counterpart. Most people see the act of quantum computation as
the steering of some device with a state somewhere in a _finite_ (albeit
very large, one hopes!) Hilbert space, this "steering" taking the form
of a finite sequence of point-to-point movements (the application of
local transformations on the QC, such as rotating a qubit) that are
performed with finite precision.

Unfortunately, QC isn't free from those unfortunate types who try and
sneak infinities into the formulation, only to then proudly announce
"look at my amazing algorithm for the halting problem!". If you must
read one such paper (and I *strongly* encourage you not to, given that
you're new to QC), you can try "Coins, Quantum Measurements and Turing's
Barrier" by Calude and Pavlov:

	http://www.cs.auckland.ac.nz/~cristian/coinsQIP.pdf

	Hope this helps,

	Duraid