” If P=NP, then the world would be a profoundly different place than we usually assume it to be. There would be no special value in “creative leaps,” no fundamental gap between solving a problem and recognizing the solution once it’s found. Everyone who could appreciate a symphony would be Mozart; everyone who could follow a step-by-step argument would be Gauss; everyone who could recognize a good investment strategy would be Warren Buffett.”

Let’s talk about the gap between following a step-by-step argument and providing such an argument. If this gap was a manifestation of NP=!P we could expect the
difficulty of finding a proof
for a theorem to be exponential (or super-polynomial) in the size of the proof. I would expect a linear dependece.
(Namely I see no evidence the ratio is increasing in the size of the proof.)

My view is that P=!NP is an important problem in mathematics but we should not over-push its meaning to mathematics and certainly not beyond mathematics.
The question if people (even creative) can do things computers can’t (in principle) is interesting by itself, but there is certainly no evidence that even creative people can do NP hard problems and it looks to me that this idea is rather absurd. (Also not every thing which is related to insights of computational complexity is automatically related to NP=!P.)

“Let me know if you’d rather not think about these questions, and I’ll do it myself when I have time.”

Please, please, do think about these questions, by all means please do.

It occurs to me that your conjecture on page 18, that

~ENT(rho;A) = O(poly(n)),

might already be ruled out experimentally by the so-called cluster states. A cluster state is basically a lattice of qubits in 1 to 3 dimensions, where each basis state has a phase of -1^z, where z is the number of pairs of adjacent qubits that are both 1. (See e.g. my multilinear formulas paper for details.) Aeppli et al. have given evidence that states very much like these arise in condensed-matter physics.

I believe ~ENT(rho;A) will be exponential for cluster states. Can you prove or disprove that?

(Also, can you prove that ~ENT(rho;A) is superpolynomial for random coset states, or for the states arising in Shor’s algorithm?)

Let me know if you’d rather not think about these questions, and I’ll do it myself when I have time.

1. ” Can you please give me one example of such a concrete line? I’ve been looking for one for years! ”

An (almost) pure state which is not (almost) determined by the entanglement of small sets of elements is possibly something not seen in nature, but we do see plenty such states in quantum algorithms e.g. error correcting codes on n qubits where each t are independent for t large. (I do not know if we see in nature any case where an (almost) pure state is not essentially determined by entanglements of pairs. )

A concrete suggested mathematical formulation (along with a few potential counter examples) for this is proposed in my paper “How quantum computers can fail” on my homepage. The paper contains a few other concrete conjectures concerning the state of qubits and errors. (Alao with newly added mathematical formulations.)

(It is not clear if an “obstruction” or a “clear line” is better expressed in terms of a single “forbidden” state rather than the variety of possible states. I am mainly interested in expressing such “lines” via pairs (states, errors) for noisy quantum computers.

Robust qubits based on highly entangled states will contradict most skeptical ideas (so this is a natural line to draw).
Some skeptical ideas will conflict with viable “superconductivity qubits”)

2. Discussig beliefs and certainly firm beliefs is a tricky business. Let’s try something I think most of us do not have strong beliefs about, and try to test our intuitions based on such an example.

Are noisy reversible quantum computers capable of factoring in polynomial time?

ABIN showed that they cannot do more than log-depth quantum circuits. This confirms
the physics intuition that noisy reversible QC are useless which is based on thermodynamics (and indeed the proof has a thermodynamic flavor.) …But log-depth quantum circuits plus a controlling PC allow for factoring in a polynomial time. This suggest that perhaps even noisy reversible computers (without cold ancilias) can factor.

So what is your take on it?

3. I hope this interesting discussion (in fact also on R2BI) will span more than the ususal life time of discussion-for-a-post on a blog.

http://xxx.lanl.gov/abs/quant-ph/0508218

but the authors believe that they introduce an architecture for robust and scalable quantum computation using both stationary qubits (e.g. single photon sources made out of trapped atoms, molecules, ions, quantum dots, or defect centers in solids) and flying qubits (e.g. photons). I suspect that progress will come more quickly than many people realize, but time will tell.

Oh, well, as for me, the answer is I *do* believe QC will be possible. I just don’t *WANT* it to be so.

I can state it better with my our argument:

The God-Hates-Me Argument: QC is possible by the very same reason P != NP: Because otherwise it would be too good to be true.

“If building quantum computers that outperform classical ones is fundamentally impossible, then it must be possible to write classical computer programs that efficiently simulate any quantum system found in Nature. “

Uh?

There are various rather concrete “lines” conjectured in the few papers that present “pessimistic” or “skeptical” views.

Can you please give me one example of such a concrete line? I’ve been looking for one for years!

A reason to doubt QC is that the highly entangled states like those of quantum computers are not seen anywhere in nature.

Under the most obvious interpretation of “highly entangled state,” this is simply false. See the comments by me and Greg above for examples of such states.

(Of course, it’s possible that by “highly entangled state” you mean something more specific than “entangled state of hundreds or thousands of particles.” But then I’ll want to know just what you mean, which leads back to my question above.)

A few comments:

1 (to various points of Scott’s) . It looks from Scott’s discussion that
quantum computer are impossible only if quantum physics will break down. (E.g., if linearity of quantum physics will break down.) I do not think this is the way most skeptics see it. (This applies to those skeptics who are “observers” and the few who try to translate skepticism about QC into actual research.)

2. Sure/Shor. Scott ask for a “line” that cannot be crossed. (Again the issue is not breakdown of Quantum physics but of breakdown of the possibility for quantum computers.)

There are various rather concrete “lines” conjectured in the few papers that present “pessimistic” or “skeptical” views.

3. Fualt-tolerancs. All fault tolerance theorems assume assumptions on the noise which may well be unrealistic. In any case this seems the crux of the matter.

Most other points look rather neutral
in the sense that they do not support QC
and not support the view that QC is not possible. This goes for the possibility of more than BQP (so what?) the possibility to simulate physics with digital computers if QC are impossible (so what?)
(And these points are not avoided by skeptics.)

Historical precedences (they go both ways) the fact that there are not anti quantum computers research communities (what is the interpretation of this fact? again it goes both ways.)

Point 8 is nice! (not that strong though)

And point 10 make this blog a grand unified blog (almost – a bit of middle-east politics is still missing to this post) (And you promised NOT to talk about string theory until Sept 27.)

A reason to doubt QC is that the highly entangled states like those of quantum computers are not seen anywhere in nature.

“might” should be “would be”, unless there is a general algorithm in BPP for period-finding.

and others just like classical computers but operating on quantum bits to show off technological expertise or feasibility?

Computing classically with qubits is like serving ketchup in a silver caviar bowl. You can do it, but it’s expensive and slow.

(But see, it is functional, unlike serving caviar in a ketchup bottle.)

Note that Section 1.1 is an excellent prose introduction to the field. The rest of the book is the more difficult brain-improvement regimen.

(Also, even if you don’t register with Blogger, you could link your name to your web page.)

Anonymous: To make QM don’t you need to some how create an entagled state with 100 or 1000 qubits. Is this practically possible?

It helps a lot to understand that entanglement is no more than a quantum generalization of correlation. If you set a billion bits of a computer to either all 0 or all 1, but you flipped a coin to decide which, then they are massively correlated. (Incredible! Powerful! Non-local!) Massive entanglement is not conceptually much different from that. However, it is computationally much more useful, in principle.

If you allow a general enough definition of entanglement, then massive entanglement was created by physicists in the past 100 years: superconducters, superfluids, and lasers might all count. In fact, it has existed for billions of years, because neutron stars exist and there are also naturally created masers in astronomy.

What Scott means when he refers to what has been created in the past 10 years is entanglement that plausibly resembles the organization of a quantum computer. In other words, potentially useful entanglement is more recent.