From the abstract:
"Assuming [assumptions] we show that ... can in principle solve..."
Yeah, well, you know... that doesn't sound as promising as the title.
Semiclassical Gravity Efficiently Solves NP-Complete Problems
11–20 of 46 posts
Re: Semiclassical Gravity Efficiently Solves NP-Complete Problems
#12I was skimming the paper and came to this:
> This transformation is like an AND gate - it ignores the index qubit and places the flag qubit in the state |1> if and only if either of the original components had the state |1> for the flag qubit.
Shouldn't that be an OR gate? Not only does the description above say "if and only if either of the original components had the state |1>", which is an OR, but the truth table listed above shows the same thing for the flag qubit.
Of course, one could say it's an AND on the |0> states, which is just De Morgan's law, but that's pretty awkward phrasing.
Re: Semiclassical Gravity Efficiently Solves NP-Complete Problems
#13From the abstract: "Assuming [assumptions] we show that ... can in principle solve..." Yeah, well, you know... that doesn't sound as promising as the title.
Assuming X is true, that implies Y. We don't think Y is true therefore we now doubt that X is true, is a very standard thing to do in math.
Re: Semiclassical Gravity Efficiently Solves NP-Complete Problems
#14Anyone care to ELI5 the novelty or significance of this?
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 c…
> 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.
Re: Semiclassical Gravity Efficiently Solves NP-Complete Problems
#15Earlier quoted context omitted.
But isn't PECTT already challenged by quantum algorithms such as Shor and Grover?
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 proble…
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.
Re: Semiclassical Gravity Efficiently Solves NP-Complete Problems
#16Anyone care to ELI5 the novelty or significance of this?
They essentially are saying semiclassical gravity (a broader theory subsuming classical) is theoretically incorrect. Like doing the konami code IRL and getting infinite money.
Re: Semiclassical Gravity Efficiently Solves NP-Complete Problems
#17From the abstract: "Assuming [assumptions] we show that ... can in principle solve..." Yeah, well, you know... that doesn't sound as promising as the title.
[deleted]
Re: Semiclassical Gravity Efficiently Solves NP-Complete Problems
#18From the abstract: "Assuming [assumptions] we show that ... can in principle solve..." Yeah, well, you know... that doesn't sound as promising as the title.
Shocking..
Re: Semiclassical Gravity Efficiently Solves NP-Complete Problems
#19Anyone care to ELI5 the novelty or significance of this?
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 c…
> 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.
Re: Semiclassical Gravity Efficiently Solves NP-Complete Problems
#20From the abstract: "Assuming [assumptions] we show that ... can in principle solve..." Yeah, well, you know... that doesn't sound as promising as the title.
That's the whole point of the article:
"We show [Assuming {competing physics theory} then {P = NP}]"
(or something along the lines)
"But we actually think P != NP... so [Assuming {P != NP} then {competing physics theory} cant be true]"