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.

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.

https://www.scottaaronson.com/papers/npcomplete.pdf

(Doing my best to ignore his abysmal politics.)

"Assuming [assumptions] we show that ... can in principle solve..."

Yeah, well, you know... that doesn't sound as promising as the title.

   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