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.
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.
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.
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.
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?
14 comments
[ 3.1 ms ] story [ 39.0 ms ] thread"Assuming [assumptions] we show that ... can in principle solve..."
Yeah, well, you know... that doesn't sound as promising as the title.
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.
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.
https://www.scottaaronson.com/papers/npcomplete.pdf
(Doing my best to ignore his abysmal politics.)
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?