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.
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.
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.
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.
Grover gives an at most quadratic speedup for NP-hard problems, it does not turn a non-polynomial algorithm into a polynomial one.
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.
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...
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.)
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.
"Assuming [assumptions] we show that ... can in principle solve..."
Yeah, well, you know... that doesn't sound as promising as the title.
"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]"