Re: Quantum computer using using artificial atoms.

From: Seth (dopie_at_unlisted.net)
Date: 02/27/05 

Date: Sun, 27 Feb 2005 21:37:30 GMT

In article <1109528598.941998.92320@o13g2000cwo.googlegroups.com>,
<jstevh@msn.com> wrote:

> Beth wrote:

> > Please, please, please read a book or take a course in computational
> > complexity theory. Quantum computable and (deterministic-) Turing
> > computable are not the same thing and can not be made to be the same
> > thing - not with any known theory of computation.

> Why? Because you say so?

> I presume from your statement that I should read a book on
> computational complexity theory that you have actually read one, so my
> next queston should be easy for you.

> Can you cite any known text that supports your claim?

I gave you one reference which has a brief discussion of complexity
theory already - Quantum Computation and Quantum Information. You can
try the article "A Survey of Quantum Complexity Theory" by Umesh V.
Vazirani found in the book "Quantum Computation: A Grand Mathematical
Challenge for the Twenty-First Century and the Millenium", Samuel J.
Lomonaco, Jr., Editor, American Mathematical Society, ISBN
0-8218-2084-2. This article describes a quantum Turing maching, which
is different from a Turing machine - as you can see from the
mathematical definitions provided.

You could also try any of the more recent references on the MathWorld
web page:

Eric W. Weisstein. "Complexity Theory." From MathWorld--A Wolfram Web
Resource. http://mathworld.wolfram.com/ComplexityTheory.html

Wikipedia wouldn't be my first choice, but there are entertaining
Wikipedia web pages,
one that lists various complexity classes:

http://en.wikipedia.org/wiki/List_of_complexity_classes

and one with a fun graphic:

http://en.wikipedia.org/wiki/Computation

both of which can be indirectly reached from:

http://en.wikipedia.org/wiki/Computational_complexity_theory

As I've said before, the issue is efficiency. You can simulate a
quantum computer on a conventional computer, but you can't necessarily
get a quantum polynomial time algorithm to run in polynomial time on a
conventional computer. Of course, you could prove my wrong by proving
P=NP.

Relevant Pages

  • Re: Quantum Computer ?
    ... This paper gives a very nice basic understanding of quantum computers ... Its not that rigorous and in the first reading u may ... if u know about classical complexity theory:) ...
    (comp.theory)
  • Questions about quantum complexity theory.
    ... I am a grad student of CS and a newbie in the field of Quantum ... Complexity theory. ...
    (comp.theory)
  • Quantum computing
    ... As the limits of traditional silicon and Moore's Law - the guiding ... quantum computing researchers offers the best hope of ever-continuing ... The task for Professor Simmons and other researchers at the Australian ... A conventional computer performs its calculations on binary numbers, ...
    (uk.philosophy.humanism)
  • Quantum leap
    ... Professor Michelle Simmons at UNSW's quantum technology centre. ... As the limits of traditional silicon and Moore's Law - the guiding ... A conventional computer performs its calculations on binary numbers, ...
    (soc.culture.malaysia)
  • Re: Can the Shor oracle be used to prove that a function is constant?
    ... determine the period on the output qbit, ... Shor's algorithm works with statistical ... > addressed in polynomial time by performing a binary search on the ... the correct statement is that if there is a quantum polynomial ...
    (sci.physics.research)