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.
> 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.
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.
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.
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.
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.
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.
Semiclassical gravity is the best we can currently do for a theory of gravity without invoking speculative ideas that are currently untestable. If the paper holds up (I haven't read it), then there are several possibilities:
1. Maybe P = NP, and semiclassical gravity isn't special.
2. Maybe P = NP, and the way we'll prove it is finding an efficient way to simulate semiclassical gravity.
3. P = NP is a hypothesis about traditional theories of computation, but they don't rule out that we can build a special machine that solves them. There's a stronger hypothesis, the extended Church-Turing thesis (ECTT), that says this is impossible. Maybe the extended Church-Turing thesis is wrong, and this is how we'll show it.
4. If ECTT thesis is right, then maybe we can conduct an experiment where semiclassical gravity fails. This gives us a clue to new physics.
5. If we can't eventually conduct an experiment, then at least we learn about a new angle on complexity -- problems that can be efficiently solved this way but not by a deterministic Turing machine.
Both quantum mechanics and general relativity are thought to satisfy the ECTT, so the fact that our most experimentally successful combination of the two doesn't is of some interest. (Semiclassical gravity is thought to fail eventually, but in a way that's out of reach of current experiments.)
They use what looks like an impossible computational result to back into the idea that this is indirect evidence that gravity is quantized.
The controversy here is whether gravity is continuous (as classical Einstein models it) all the way down, or if the large scale behavior is built on a quantum foundation like everything else.
As far as I know most physicists believe gravity must be quantized, but we have no theory for it that works and plays nice with the well validated relativistic stuff at scale.
We have some candidates like string theory and loop quantum gravity but testing and refining them requires accelerators the size of the solar system or direct access to a black hole. The latter was the plot of Interstellar.
They essentially are saying semiclassical gravity (a broader theory subsuming classical) is theoretically incorrect. Like doing the konami code IRL and getting infinite money.
I 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.
Doh! You are correct. I had been looking at a previous paper (which this new paper references). The previous paper showed that you can use any non-linearity in QM to solve NP-complete problems, and the new one shows that semi-classical gravity + QM has such a non-linearity. The earlier paper: https://arxiv.org/pdf/quant-ph/9801041
Demorgan's theorem says AND and OR are equivalent, and only depend upon the polarity of the bits. So if "state |1>" is a binary zero, AND is the proper logical operator.
Yes, I think that was implied in my original post, that if you define |0> as logical 1 then it works as an AND. It just seems confusing and unnecessary when they could have framed it to be consistent with classical logic.
I'm not convinced. They aren't actually using the semiclassical Einstein equation, they are using some simplification they call Newton Schrodinger equation. They claim that this equation can lead to distinguish a state that's exponentially close to |0> from |0>. I don't follow their whole argument.
Anyway, I wouldn't be surprised if you could actually do hard computations with semiclassical Einstein equation, because they have strong self consistency - the expectation value of the stress energy tensor curves the metric, which in turn excites the quantum vacuum and causes expectation value of the stress energy tensor. But this isn't what they use in the paper. Nobody knows if this self consistency can be achieved in all configurations, and physicists working with semiclassical gravity usually do only one iteration of the self consistency.
If someone wanted to make semiclassical gravity into quantum gravity, he'll probably assume that gravity causes measurements, which would prevent these kinds of abuses where you have superposition you're probing via gravity while keeping it intact.
What of the/a dilatant fluid model of gravity which predicts the perihelion of Mercury does not jive with observation?
Doesn't that indicate that CFD is the viable way forward?
The point of the OP is that it's neat or maybe useful that semiclassical gravity solves NP-complete problems; but if the semiclassical model of gravity is insufficient to describe even gravity, why should it be sufficient to solve NPC problems, and what does a sufficient model of n-body fluidic gravity enable low-error predictions of?
Yes, but the title suggests that "[method] solves NP-complete problems", and sounds kind of like "Quantum-Physics-related trick solves NP-complete problems".
Moreover - it doesn't even solve NPC problems conditionally, but that show that "in principle" they should be / would be solvable.
It doesn't disprove a theory if it results in the physical universe violating NP!=P. In fact, we already know the universe violates NP!=P via the O(N) sorting algorithm[1]:
for each element:
cut a spaghetti strand to the a the length of the elemnet
add strand to bundle of spaghetti
hold spaghetti bundle vertical
lower spaghetti bundle to a flat surface.
loosen grip so that each spaghetti strand comes to rest on flat surface
while there is spaghetti in the bundle:
lower a second flat surface above the bundle until it touches the topmost spaghetti piece
remove the piece, and output it's length
[1] which I learned about in "The New Turing Ominbus" by A K Dewdney
I feel like there's some hidden complexity there. For any finite flat surface there's a point where not all the spaghetti will fit on it simultaneously. So you have to do O(N) compression steps to find the bundle with the long strand. Locating the strand within the bundle also seems non-trivial if it's big enough. Both are easier to see if you start thinking about scaling to sorting like, square miles of spaghetti at a time.
it is still O(n) weight to transport, so O(n^2) amortised; if you liken having a stronger hand that can carry more spaghetti to parallelisation, it's beaten by O(log^2 n) sorting algorithms on parallelised classical computers.
Anyone 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.
> 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.
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.
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.
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...
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.
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.
Semiclassical gravity is the best we can currently do for a theory of gravity without invoking speculative ideas that are currently untestable. If the paper holds up (I haven't read it), then there are several possibilities:
1. Maybe P = NP, and semiclassical gravity isn't special. 2. Maybe P = NP, and the way we'll prove it is finding an efficient way to simulate semiclassical gravity. 3. P = NP is a hypothesis about traditional theories of computation, but they don't rule out that we can build a special machine that solves them. There's a stronger hypothesis, the extended Church-Turing thesis (ECTT), that says this is impossible. Maybe the extended Church-Turing thesis is wrong, and this is how we'll show it. 4. If ECTT thesis is right, then maybe we can conduct an experiment where semiclassical gravity fails. This gives us a clue to new physics. 5. If we can't eventually conduct an experiment, then at least we learn about a new angle on complexity -- problems that can be efficiently solved this way but not by a deterministic Turing machine.
Both quantum mechanics and general relativity are thought to satisfy the ECTT, so the fact that our most experimentally successful combination of the two doesn't is of some interest. (Semiclassical gravity is thought to fail eventually, but in a way that's out of reach of current experiments.)
They use what looks like an impossible computational result to back into the idea that this is indirect evidence that gravity is quantized.
The controversy here is whether gravity is continuous (as classical Einstein models it) all the way down, or if the large scale behavior is built on a quantum foundation like everything else.
As far as I know most physicists believe gravity must be quantized, but we have no theory for it that works and plays nice with the well validated relativistic stuff at scale.
We have some candidates like string theory and loop quantum gravity but testing and refining them requires accelerators the size of the solar system or direct access to a black hole. The latter was the plot of Interstellar.
They essentially are saying semiclassical gravity (a broader theory subsuming classical) is theoretically incorrect. Like doing the konami code IRL and getting infinite money.
I 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.
Are you sure you're looking at the right paper? I don't find the sentence you mention in the paper.
Doh! You are correct. I had been looking at a previous paper (which this new paper references). The previous paper showed that you can use any non-linearity in QM to solve NP-complete problems, and the new one shows that semi-classical gravity + QM has such a non-linearity. The earlier paper: https://arxiv.org/pdf/quant-ph/9801041
Demorgan's theorem says AND and OR are equivalent, and only depend upon the polarity of the bits. So if "state |1>" is a binary zero, AND is the proper logical operator.
Yes, I think that was implied in my original post, that if you define |0> as logical 1 then it works as an AND. It just seems confusing and unnecessary when they could have framed it to be consistent with classical logic.
I'm not convinced. They aren't actually using the semiclassical Einstein equation, they are using some simplification they call Newton Schrodinger equation. They claim that this equation can lead to distinguish a state that's exponentially close to |0> from |0>. I don't follow their whole argument.
Anyway, I wouldn't be surprised if you could actually do hard computations with semiclassical Einstein equation, because they have strong self consistency - the expectation value of the stress energy tensor curves the metric, which in turn excites the quantum vacuum and causes expectation value of the stress energy tensor. But this isn't what they use in the paper. Nobody knows if this self consistency can be achieved in all configurations, and physicists working with semiclassical gravity usually do only one iteration of the self consistency.
If someone wanted to make semiclassical gravity into quantum gravity, he'll probably assume that gravity causes measurements, which would prevent these kinds of abuses where you have superposition you're probing via gravity while keeping it intact.
Scott Aaronson has a really good explainer about complexity theory and physical computing:
https://www.scottaaronson.com/papers/npcomplete.pdf
(Doing my best to ignore his abysmal politics.)
But does it solve fluids or n-body gravity?
What of the/a dilatant fluid model of gravity which predicts the perihelion of Mercury does not jive with observation?
Doesn't that indicate that CFD is the viable way forward?
The point of the OP is that it's neat or maybe useful that semiclassical gravity solves NP-complete problems; but if the semiclassical model of gravity is insufficient to describe even gravity, why should it be sufficient to solve NPC problems, and what does a sufficient model of n-body fluidic gravity enable low-error predictions of?
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.
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.
Yes, but the title suggests that "[method] solves NP-complete problems", and sounds kind of like "Quantum-Physics-related trick solves NP-complete problems".
Moreover - it doesn't even solve NPC problems conditionally, but that show that "in principle" they should be / would be solvable.
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]"
Shocking..
It doesn't disprove a theory if it results in the physical universe violating NP!=P. In fact, we already know the universe violates NP!=P via the O(N) sorting algorithm[1]:
[1] which I learned about in "The New Turing Ominbus" by A K DewdneyI feel like there's some hidden complexity there. For any finite flat surface there's a point where not all the spaghetti will fit on it simultaneously. So you have to do O(N) compression steps to find the bundle with the long strand. Locating the strand within the bundle also seems non-trivial if it's big enough. Both are easier to see if you start thinking about scaling to sorting like, square miles of spaghetti at a time.
What does sorting have to do with violating p != np?
The common bound on sorting is you can't do better than O(n lg n) worst-case, but that is strictly only for comparison sorts anyway.
For purely randomly distributed groups of n things.
i hate every time i hear about spaghettisort.
it is still O(n) weight to transport, so O(n^2) amortised; if you liken having a stronger hand that can carry more spaghetti to parallelisation, it's beaten by O(log^2 n) sorting algorithms on parallelised classical computers.