Hacker News Reader

Comment by tancop | Hacker News Reader

if the PECTT (Physical Extended Church-Turing Thesis) is true then the current standard way of connecting classical gravity with quantum mechanics is wrong. the authors take it as evidence for full quantum gravity because the alternative is changing the Einstein equations in some arbitrary complex way. im not a physicist so this might be a bad explanation.

the extended thesis it depends on is "No physical procedure can decide an NP-complete problem in polynomially many steps." imo thats a very strong and controversial assumption when we still dont know the limits of what quantum computers can do.

View on HN

> we still dont know the limits of what quantum computers can do.

Well, we don't know the limits of what classical computers can do too (P!=NP is not proven).

While not directly related to P!=NP, historical claims of quantum superiority were occasionally taken down by finding an efficient classical algorithm.

> the extended thesis it depends on is "No physical procedure can decide an NP-complete problem in polynomially many steps."

I think part of the confusion here, is that usually the extended church turing thesis means that any physical computation can be efficiently (in polynomial time) simulated by a deterministic turing machine. (And thus if quantum computers exist and BQP is a superset of P, the proposition is false). I've never seen it defined before as above. But im definitely not a complexity theorists.

But remember that "efficient" in terms of P and NP is about scaling. P == NP doesn't necessarily mean that a practically efficient algorithm can be found. The polynomial exponents involved may be large: O(N^1000) does eventually scale better than O(e^N), but that doesn't mean it is practically useful!

This is pretty unrelated to the topic at hand, but people say that as if its a cop out answer to the conundrum, however i think it would be both the most intersting and most unlikely outcome to the whole p vs np saga. Possibly even more crazy than the answer being uncomputable.

Think about what that would mean. It essentially amounts to a loop nested 1000 times would be enough. 1001 tumes is more than needed, 999 times is enough. Having high transition points like that in math is super rare and interesting. Things are usually either a small number or infinity; almost never a large number. Like i can't think of any non contrived polynomial time problems you would actually want to solve that are worse than n^20, let alone n^100 (excluding cheating by fixing one of the parameters as part of the problem). I don't know what such a result would mean but it would be fascinating.

What non-contrived polynomial time problem can you think of that is n^20? I'm really curious.

But isn't PECTT already challenged by quantum algorithms such as Shor and Grover?

Shor doesn't solve an NP hard problem. It's even possible that factoring and discrete log are in P, while P != NP.

The paper builds on the results of "Nonlinear quantum mechanics implies polynomial-time solution for NP-complete and #P problems" by Abrams and Loyd [1], from which I quote:

> The last qubit now contains all the information that we need; however, for small s, a measurement of the last qubit will almost always return |0>, yielding no information. > We wish to distinguish between the cases s=0 and s>0.

> Step 4. Repeatedly apply the nonlinear operation to drive the states representing these two cases apart at an exponential rate: eventually, at a time determined by a polynomial function of the number of qubits n, the number of solutions s, and the rate of spreading (Lyapunov exponent) λ, the two cases will become macroscopically distinguishable.

[1] https://arxiv.org/abs/quant-ph/9801041

No. As far as we know, no realization of a quantum algorithm can solve NP-complete problems in polynomial many steps.

Some people that worked on this topic told me that there seems to be some improvements on the quasi-optimal solution found, but that due to the scale of current quantum computers, it just have been tried out on small-sized problems.

Theoretically, there are some papers suggesting that there are problems in BQP (the computational model of quantum computers) outside of NP [1] and even, the PH [2] (Polynomial Hierarchy, the infinite hierarchy of composition of NP and co-NP problems), which is why we cannot still satisfactorily say whether quantum computers can or cannot solve NP-complete problems.

The Wikipedia page for BQP [3] does a good job showing what is currently known.

[1] https://arxiv.org/abs/2209.10398 [2] https://eccc.weizmann.ac.il/report/2018/107/ [3] https://en.wikipedia.org/wiki/BQP#Relationship_to_other_comp...

As to the PH result, arguments on relativized classes can be pretty inconclusive. There's both oracles for P^A = NP^A and P^B != NP^B.

I would also observe that it is a completely reasonable hypothesis that even if you can construct a problem in some higher complexity class that a quantum computer "should" be able to solve, it is possible that it would turn out that it couldn't because the complexity barrier turns out to be even more fundamental than quantum mechanics. If I understand it correctly, Scott Aaronson at least takes this possibility seriously, and points out that it is at least a possibility that this could end up being the legacy of quantum computing, along with the possibility that it could demonstrate some sort of currently-unknown fundamental limit on entanglement. And I'd add my own commentary that the experiment that shows QM breaks down and refuses to solve some problem that it "should" be able to solve would be on the instant shortlist for Nobel prizes for the experimenters, pending only extended confirmation, because it would be a big, big deal.

Prime factorisation is not proven to be NP-hard so the existence of a quantum polynomial algorithm (Shor) has no bearing on complexity classes other than showing that prime factorisation is in BQP (quantum polynomial). So it does challenge PECTT on 'vibes' as most experts think it is not in P, but there is no mathematical proof for it.

Grover gives an at most quadratic speedup for NP-hard problems, it does not turn a non-polynomial algorithm into a polynomial one.

To be fair - I'd be more shocked by the result that a physical process can solve NP complete problems.

If that were true, I'd have expected Mother Nature to have exploited it a long time ago.

It's amazing what some physical processes can do. During the years I worked with laser physicists, I learned that passive optical systems can do crazy things, such as Fourier transforms.

Hmm... I suppose it can come across as pedantic, but physical processes as a whole can do anything that can be done, hence it shouldn't come as a surprise that there exists a physical process that can perform a Fourier transform, or any computable process whatsoever.

I agree. To me it's more interesting that there exists a physical process that performs a Fourier transform than that there could exist such a process. If it can be done on pen and paper, it's already proven that it can be done in a physical system, since the pen and paper are physical.

This is done by prisms breaking sunlight into a rainbow, or Newton's Rings of color appearing on oil slicks. Peacocks and bluejays and blue morphos all get their color from notch filters applied to the Fourier transform.

It's a pretty common effect, and frankly trivial. Lensless holographic focusing lenses on sea star exoskeletons are a bit less surprising... but only because they actually evolved, not because it could happen.

Reply on news.ycombinator.com