exponentially fewer queries than *any* classical algorithm.

Variations on Quantum Mechanics\[VQM\]
======================================

Quantum computing skeptics sometimes argue that we do not *really* know whether quantum mechanics itself will remain valid in the regime tested by quantum computing.[^9]  Here, for example, is Leonid Levin [@levin:qc]: The major problem \[with quantum computing\] is the requirement that basic quantum equations hold to multi-hundredth if not millionth decimal positions where the significant digits of the relevant quantum amplitudes reside.  We have never seen a physical law valid to over a dozen decimals.

The irony is that most of the specific proposals for how quantum mechanics *could* be wrong suggest a world with more, not less, computational power than $\mathsf{BQP}$.  For, as we saw in Section \[QUANTUM\], the linearity of quantum mechanics is what prevents one needle in an exponentially large haystack from shouting above the others.  And as observed by Weinberg [@weinberg], it seems difficult to change quantum mechanics in any consistent way while preserving linearity.

But how drastic could the consequences possibly be, if we added a tiny nonlinear term to the Schrödinger equation (which describes how quantum states evolve in time)?  For starters, Gisin [@gisin] and Polchinski [@polchinski] showed that in most 