Semiclassical Gravity Efficiently Solves NP-Complete Problems
1–10 of 46 posts
Re: Semiclassical Gravity Efficiently Solves NP-Complete Problems
#2[deleted]
Re: Semiclassical Gravity Efficiently Solves NP-Complete Problems
#3Anyone care to ELI5 the novelty or significance of this?
Re: Semiclassical Gravity Efficiently Solves NP-Complete Problems
#4Anyone 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 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.
Re: Semiclassical Gravity Efficiently Solves NP-Complete Problems
#5Anyone care to ELI5 the novelty or significance of this?
[deleted]
Re: Semiclassical Gravity Efficiently Solves NP-Complete Problems
#6[deleted]
Re: Semiclassical Gravity Efficiently Solves NP-Complete Problems
#7Anyone 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…
But isn't PECTT already challenged by quantum algorithms such as Shor and Grover?
Re: Semiclassical Gravity Efficiently Solves NP-Complete Problems
#8Earlier quoted context omitted.
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…
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.
Re: Semiclassical Gravity Efficiently Solves NP-Complete Problems
#9Earlier quoted context omitted.
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…
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 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...
Re: Semiclassical Gravity Efficiently Solves NP-Complete Problems
#10Earlier quoted context omitted.
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…
But isn't PECTT already challenged by quantum algorithms such as Shor and Grover?
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.