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

[Stephen Fenner]

On Tue, 15 Oct 2002, Steve Stevenson wrote:

> 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?
>
> 2. Does QC compute something outside Turing computable?

No.  No reasonable model of QC computes anything that cannot be Turing
computed.

> I'd appreciate any comments.

There is room for fudging in choosing the allowed set of quantum gates for
a circuit; one could imagine a quantum gate that has Chaitin's Omega as
one of its transition amplitudes.  Such gates are not reasonable, though.
Every quantum gate must ultimately be fabricated in the laboratory by
classical means, and so we just cannot calibrate a gate to include
definite, clearly defined, noncomputable amplitudes.

Steve

------
Stephen Fenner
Computer Science and Engineering
University of South Carolina
fenner at cse.sc.edu