[SyzygyRhythm]

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.

[slwvx]

Are you sure you're looking at the right paper? I don't find the sentence you mention in the paper.

[SyzygyRhythm]

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

[anonymousiam]

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.

[SyzygyRhythm]

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.