"P not equal NP" as a physical principle?

[John Baez]

I'm hanging out with a bunch of computer scientists and logicians
here in Marseille....

Peter Selinger told me that Richard Jozsa said some people are
thinking of "P not equal to NP" as a principle of physics, in the
following sense. Nobody has figured out how to use quantum
computers to solve NP problems in polynomial time. Of course,
nobody has has proved it *can't* be done, since this would
imply that *classical* computers can't solve NP problems in
polynomial time, thus resolving one of the biggest unsolved
problems in mathematics. But, lots of people believe it can't
be done. So, in some sense they believe "quantum computation
respects P not equal to NP".

But, according to my nth-hand gossip, some "slight modifications"
of quantum mechanics would allow for computers that solve NP
problems in polynomial time. (I have no idea what these "slight
modifications" would be, and that's part of why I'm posting -
I'd like to know!)

So, apparently some people are considering "P not equal to NP"
as a physical principle that would rule out these slight modifications
of quantum mechanics.

That's all I know about this. It sounds neat. What I want to know is:
who are these people? Have they written anything about this? What
are these "slight modifications" of quantum mechanics? Etc.!

Peter Selinger: http://www.mathstat.dal.ca/~selinger/research.html
Richard Jozsa: http://www.cs.bris.ac.uk/Publications/pub_by_author.jsp?id=115954

[Marc Nardmann]

John Baez wrote:

>But, according to my nth-hand gossip, some "slight modifications"
>of quantum mechanics would allow for computers that solve NP
>problems in polynomial time. (I have no idea what these "slight
>modifications" would be, and that's part of why I'm posting -
>I'd like to know!)
>
>So, apparently some people are considering "P not equal to NP"
>as a physical principle that would rule out these slight modifications
>of quantum mechanics.
>
>That's all I know about this. It sounds neat. What I want to know is:
>who are these people? Have they written anything about this? What
>are these "slight modifications" of quantum mechanics? Etc.!
>
>

I don't know. But the nth-hand gossip could at least be related to work
of Michael Freedman, e.g. this ("P/NP, and the quantum field computer"):

http://www.pnas.org/cgi/content/abstract/95/1/98

(That's just the article's abstract. Your institution needs a
subscription when you want to download the 4-page text as a PDF file.)


-- Marc Nardmann

[Aaron Denney]

On 2006-02-08, John Baez <baez@math.removethis.ucr.andthis.edu> wrote:
> So, apparently some people are considering "P not equal to NP"
> as a physical principle that would rule out these slight modifications
> of quantum mechanics.

You have to be very careful here about terminology -- P vs NP is a
purely mathematical problem. The question is whether NP is realizable
in polynomial "resources" given current theories (or possible theories).

> That's all I know about this. It sounds neat. What I want to know is:
> who are these people? Have they written anything about this? What
> are these "slight modifications" of quantum mechanics? Etc.!

Scott Aaronson is the big one I know discussing this area.
http://www.scottaaronson.com/blog/

The "slight modifications" are such things as measurement projection
probabilities not being |<psi|phi>|^2, or allowing (even slight) non-unitary
evolution.

Is Quantum Mechanics An Island In Theoryspace?
http://arxiv.org/abs/quant-ph/0401062
Quick read, complexity results superseded by
http://arxiv.org/abs/quant-ph/0412187

Limits on Efficient Computation in the Physical World
http://arxiv.org/abs/quant-ph/0412143
Long, PhD thesis

NP-complete Problems and Physical Reality
http://arxiv.org/abs/quant-ph/0502072


--
Aaron Denney
-><-

[John Baez]

In article <slrndukosm.ugp.wnoise@ofb.net>,
Aaron Denney <wnoise@ofb.net> wrote:

>On 2006-02-08, John Baez <baez@math.removethis.ucr.andthis.edu> wrote:

>> So, apparently some people are considering "P not equal to NP"
>> as a physical principle that would rule out these slight modifications
>> of quantum mechanics.

>You have to be very careful here about terminology -- P vs NP is a
>purely mathematical problem.

Yeah, I explained what I meant more carefully in some text you excised.
But if I ever write about this in This Week's Finds, I promise to be
more careful than I was above!

>The question is whether NP is realizable
>in polynomial "resources" given current theories (or possible theories).

Right.

>Scott Aaronson is the big one I know discussing this area.
>http://www.scottaaronson.com/blog/

Great! Funny how I wound up discussing a cool paper of his about
P vs NP in "week226" even without knowing this....

>The "slight modifications" are such things as measurement projection
>probabilities not being |<psi|phi>|^2, or allowing (even slight) non-unitary
>evolution.
>
>Is Quantum Mechanics An Island In Theoryspace?
>http://arxiv.org/abs/quant-ph/0401062
>Quick read, complexity results superseded by
>http://arxiv.org/abs/quant-ph/0412187
>
>Limits on Efficient Computation in the Physical World
>http://arxiv.org/abs/quant-ph/0412143
>Long, PhD thesis
>
>NP-complete Problems and Physical Reality
>http://arxiv.org/abs/quant-ph/0502072

Excellent - thanks a googol!

It seems that some of this work got its start here:

Daniel S. Abrams and Seth Lloyd, Nonlinear quantum mechanics implies
polynomial-time solution for NP-complete and #P problems,
http://arxiv.org/abs/quant-ph/9801041

[Arnold Neumaier]

John Baez wrote:

> according to my nth-hand gossip, some "slight modifications"
> of quantum mechanics would allow for computers that solve NP
> problems in polynomial time. (I have no idea what these "slight
> modifications" would be, and that's part of why I'm posting -
> I'd like to know!)
>
> So, apparently some people are considering "P not equal to NP"
> as a physical principle that would rule out these slight modifications
> of quantum mechanics.

http://arxiv.org/abs/cs/0406056 is about a physical pseudo-proof of
P=NP, though not one involving quantum mechanics. It is based upon the
observation that many physical systems move towards equilibrium,
nd the assumption that the equilibrium state is a global minimum of
the free energy.

Unfortunately, the latter is not the case although often assumed for
simplicity: If it were true, all crystals in Nature would be perfect...

Probably similar counterindications can be given for recipes that
use quantum computation...


Arnold Neumaier