Hacker News Reader

Comment by sova | Hacker News Reader

Information and computation ("utilization of information") are not equivalent things. The solution is there, staring us right in the face, it's just our primitive methods of sequential operations on a silicon abacus are incapable of rendering a solution immediately. Infinitely parallellize operations, such as with a "quantum computer" and suddenly what is infeasible in one era becomes quite feasible in another. I don't think it's right to equate information theory and computing, because one is per-se data and its solubles/solutions while the other is step-wise sequential logic to infer some step-wise sequential fact.

View on HN

P?=NP isn't the question of, "If given an infinite number of monkeys can one compute an exponential problem really quickly?"

Its the question of, "Does a mapping exist from that fast infinite monkey machine to a finite monkey machine that runs in polynomial time?"

I think parent's question is "Can the problem be encoded such that one can prove that no translation can prune the number of monkeys required at an exponential rate?" I have wondered that myself, but never found any particularly useful answer.

Yes, but is it right to approach this question from sequence just because computation implies sequence? Mathematics has an equals sign and suggests not the computational sequence, just the logical sequence of our axioms mapped to self-evident fact. Mathematics to Information Theory to Computation naturally goes from clear postulates and language-able axioms to water-wheelable traits. I suggest there is some room for exploration in between.

A quantum computer is not "infinitely parallel" and though it's still an open problem, it's considered unlikely that that quantum computers can solve NP-complete problems in polynomial time.

>A quantum computer is not "infinitely parallel"

Explain

I mean that's pretty much it. You can't use a quantum computer like a classical computer with a huge (infinite) number of compute cores. Its not a gpu. That's not how it works.

If you use the metaphor that superposition is like computing many things in paralell, the problem comes in that when you measure. The superposition collapses to a single answer at random (with probability related to the amplitude of each possibility) which will usually not be the answer you're interested in.

My take on it: you get "infinitely parallel" computation, generating "inifinetly parallel" results that are in superposition. Problem is, at the end you can only access your "infinitely parallel" result via a classical measurement, involving a wave function collapse [1].

For some problems, people have found ways to extract useful information via classical measurements, e.g. Shor's algorithm (in theory breaking RSA/DSA/ECDSA/DH/ECDH style public-key algorithms [1]). However in the general case this does not work (so AES and hash algorithms are safe for now).

[1] https://en.wikipedia.org/wiki/Wave_function_collapse

[2] https://en.wikipedia.org/wiki/Shor%27s_algorithm#Quantum_par...

I think it's time someone had the talk with you: https://www.smbc-comics.com/comic/the-talk-3

Quantum computing doesn't do what you think it does.

Not so coincidentally, Scott is the first person quoted in OP's article, as well as the co-author of that comic.

“The Blog of Scott Aaronson

If you take nothing else from this blog: quantum computers won't solve hard problems instantly by just trying all solutions in parallel.”

Only a madman would try all possible "solutions."

Also, even if it did, that wouldn’t change the status of P=NP, which is a statement about problems computed by classical Turing machines

>a statement about problems computed by classical Turing machines

Are we out of tape already?

He's just stating that there could be an equivalence class that could get us closer to P=NP and it doesn't have to be computable. The complexity class he mentions is `P^(NP[k])`, 'P With k NP Queries(for constant k)'.

Rock n roll dude. Suggest that Tiger Woods can get a hole in one every time and people attack you as if you had questioned their fundamental religious beliefs. Ramanujan created an approximating function for pi in 1904 and nobody knows how it works. Packed with factorials to the gills. It's not like the digits of pi are a secret to be computed every time and to try and snag a spare computation cycle here and there -- they are what they are. And finding a pattern comes down not to the self-evident information, but to the method.

I'm pretty sure you're being downvoted because you're being incoherent, not because of anything you've suggested.

I have no idea how you could have possibly got that from anything Sova wrote. Nothing they wrote seems to remotely resemble that.

I'm just trying to be helpful. :(

I apologize. I could have (and should have) wrote that comment in a way that was less confrontational.

And even if it did, P=NP is based on a model of computation. So even if there is a proof of P=NP with quantum computers, that could still leave the question open on classical computers.

Now that's a notion I do not often hear. Maybe a question for a 3D-abacus made of stones and flowing water.

> So even if there is a proof of P=NP with quantum computers

That doesn't really even make sense as a sentence. A quantum computer is neither a Turing machine nor a non-deterministic Turing machine.

I guess what you're trying to say is that even if someone proved/disproved BQP=NP it would leave P=NP open.

"A new ontological category"... more like multiple golf balls competing for the same hole. "Choreographing interference patterns" would not actually further computation, but simply suggest a new set of tools that could be, by accident or happenstance, calibrated to produce results where other devices could not. Is that your point?

Reply on news.ycombinator.com