Re: Rasetti: Quantum Computers based on TQFT
From: Ralph Hartley (hartley_at_aic.nrl.navy.mil)
Date: 03/23/05
- Next message: Arnold Neumaier: "Re: A classical mechanics aperitif"
- Previous message: whopkins_at_csd.uwm.edu: "Re: Teleportation of photons using entanglement"
- In reply to: Urs Schreiber: "Rasetti: Quantum Computers based on TQFT"
- Next in thread: Ralph Hartley: "Re: Rasetti: Quantum Computers based on TQFT"
- Messages sorted by: [ date ] [ thread ]
Date: Wed, 23 Mar 2005 00:38:32 +0000 (UTC)
Urs Schreiber wrote:
> So the idea is that there may be more types of quantum computers than
> currently considered in the standard literature. In particular, so
> Rasetti's idea, using systems that have to be described by quantum
> <em>field</em> theory one might be able to (in principle) construct
> new and more powerful types of quantum computers.
>
> This idea apparently goes back to Michael Friedman, who first proposed
> that non-abelian topological quantum field theories might exhibit
> features necessary so support a model of computation capable of
> solving not-P problems in polynomial time?
It would certainly be interesting if true.
> Apparently Friedman, Kitaev and Wang in particular proposed that
> Chern-Simons theory is a promising candidate.
..
> The computation of non-abelian holonomy as well as that of Jones
> polynomials is not in P.
The Jones polynomial is #P hard (I will use that as an example from here
on). That means it is not strictly speaking *known* to not be in P, but
if P!=NP it is. Having a device that can solve #P problems would let you
solve NP, BQP, and several other interesting complexity classes.
> Since the observables of CS theory are
> precisely these quantities all we have to do is to set up a system
> which is goverened by CS theory, somehow prepare it to be in a given
> knot state and then observe its observables. Since these will be not-P
> functions of these knots, we effectively have an analog quantum
> computer which computes not-P problems easily.
They would need to prove that both the state preparation and measurement
of the observables are polynomial.
Also, the Jones polynomial can be *approximated* in polynomial time, so
to be anything special, the system needs to calculate it exactly. That
can be a tall order for an analog computer.
> Clearly when talking about computational complexity one has to remove
> analog computers from the picture somehow. For instance protein
> folding is a famouns hard problem. It remains hard, even though I can
> figure out how a protein folds easily by just synthesizing it and
> seeing how it folds. That's an analog computation and I bet it scales
> linearly with the size of the protein. You might rather want to call
> it an experiment, though.
If it worked you could call it anything you wanted!
Unfortunately, most polypeptide sequences don't fold uniquely at all,
they end up in one of the billions of local minima that make the
computational problem hard.
Biological proteins are not typical. They are designed to have their
structure determined by that analog computation. They evolved to fold in
a unique way, because their function depends on it.
It's actually quite difficult to design a protein from scratch that
folds correctly.
Analog computers tend not to work on hard problems, or when they do,
tend to take a very long time.
> And that's the point, I think. It's an experiment rather than a
> computation. And the same is true for the Chern-Simons computer
> proposed by Rasetti et al. They propose to make experiments in field
> theory and regard the measurement of the outcome as a calculation.
>
> For practical purposes that may be fine. If I really want to know the
> value of some Jones polynomial and I really find it easier to come up
> with a system governed by CS theory, prepare it suitably and measure
> its observables somehow with sufficient accuracy, than to compute the
> polynomial on a digital computer up to that accuracy then that's fine
> I guess.
If you could really compute the Jones polynomial (exactly), you could
solve any problem in P^{#P} (including NP complete problems).
That's more than "ordinary" quantum computers are thought to be able to do.
You are right to be skeptical, and I noticed that you did not quote them
claiming to have succeeded. They talk of "promising candidates".
> a) this has little to do with quantum computation and is all about
> analog computers
It is certainly different from Quantum Computers as ordinarily defined.
I have seen something similar before. I seem to recall that abstract NMR
based quantum computers can do things an ordinary quantum computers
can't. It can't work in the real world because each step halves the
number of working molecules, and eventually there are zero.
> I assume the problem is related to the fact that we really want to
> study _universal_ computers, not just special-purpose ones.
I don't think so. The class of problems is universal enough. It's an
attempt to find another class of quantum based machines.
Most don't work out. I will have to read the original publications to
say more.
Ralph Hartley
- Next message: Arnold Neumaier: "Re: A classical mechanics aperitif"
- Previous message: whopkins_at_csd.uwm.edu: "Re: Teleportation of photons using entanglement"
- In reply to: Urs Schreiber: "Rasetti: Quantum Computers based on TQFT"
- Next in thread: Ralph Hartley: "Re: Rasetti: Quantum Computers based on TQFT"
- Messages sorted by: [ date ] [ thread ]
Relevant Pages
|
|
