If quantum states exhibit small nonlinearities during time evolution, then quantum computers can be used to solve
NP-complete and #
P problems in polynomial time. We provide algorithms that solve
NP-complete and #
P oracle problems by exploiting nonlinear quantum logic gates. Using the Weinberg model as a simple example, the explicit construction of these gates is derived from the underlying physics. Nonlinear quantum algorithms are also presented using Polchinski type nonlinearities which do not allow for superluminal communication.
We consider an extended model of quantum computation where a scalable fault-tolerant quantum computer is coupled to one or more ancilla qubits that evolve according to a nonlinear Schrödinger equation. Following the approach of Abrams and Lloyd, an efficient quantum circuit evaluating an
n-bit Boolean function in conjunctive normal form is used to prepare an ancilla encoding its number
s of satisfying assignments (
0≤s≤2n). This is followed by a nonlinear quantum state discrimination gate on the ancilla qubit that is used to learn properties of
s. Here we consider three types of state discriminators generated by different nonlinear Hamiltonians. First, given a restricted Boolean satisfiability problem with the promise of at most one satisfying assignment ($ 0 \le s \le 1$), we show that a qubit with
⟨σz⟩σz nonlinearity can be used to efficiently determine whether
s=0 or
s=1, solving the UNIQUE SAT problem. Here $\langle A \rangle := \langle ψ| A |ψ\rangle $ denotes expectation in the current state. UNIQUE SAT is NP-hard under a randomized polynomial-time reduction (of course any discussion of complexity assumes a scalable, fault-tolerant implementation). Second, for unrestricted satisfiability problems with $ 0 \le s \le 2^n$, a Hamiltonian with $ \langle σ^x \rangle σ^y - \langle σ^y \rangle σ^x$ nonlinearity can be used to efficiently determine whether
s=0 or
s>0, thereby solving 3SAT, which is NP-complete. Finally, we show that $ \langle σ^y \rangle \langle σ^z \rangle σ^x - \langle σ^x \rangle \langle σ^z \rangle σ^y $ nonlinearity can be used to efficiently measure
s and solve #SAT, which is #P-complete. The nonlinear models are of mean field type and might be simulated with ultracold atoms.
Quantum computers are widely believed have an advantage over classical computers, and some have even published some empirical evidence that this is the case. However, these publications do not include a rigorous proof of this advantage, which would have to minimally state that the class of problems decidable by a quantum computer in polynomial time, BQP, contains problems that are not in the class of problems decidable by a classical computer with similar time bounds, P. Here, I provide the proof of a stronger result that implies this result: BQP contains problems that lie beyond the much larger classical computing class NP. This proves that quantum computation is able to efficiently solve problems which are far beyond the capabilities of classical computers.
There is growing interest in extensions of the standard model of gate-based quantum computation to include auxiliary degrees of freedom evolving according to a nonlinear Schrödinger equation. By reducing the
Boolean satisfiability problem SAT to quantum state discrimination, Abrams and Lloyd argued that the right type of nonlinearity can be used to solve NP and #P problems in polynomial time, at least in an
idealized noise-free limit. For practical implementation, however, we are restricted to simulated and emergent nonlinearities, such as that appearing in mean field models for ultracold atoms and similar
ensembles. A prominent example is the torsion model, which arises in two-component Bose-Einstein condensates and spin models with all-to-all Ising interaction. But torsion-based state discrimination appears to
fall short of solving SAT. Here we close this gap by constructing the filtered oracle of the Valiant-Vazirani theorem, providing a randomized polynomial-time reduction from SAT to UNIQUE SAT, a promise problem
where there is at most 1 satisfying assignment. In the noise-free limit, the UNIQUE SAT problem can be solved in polynomial time using torsion nonlinearity. Quantum Valiant-Vazirani reduction is no faster than
the efficient classical version, but a fault-tolerant implementation coupled to a nonlinear quantum coprocessor simulating torsion would enable polynomial time solution to NP (but not #P) problems.
What does it mean for the physically motivated computational complexity class
BQP and the logically motivated class
NP to be incomparable, from a physical perspective? Although it is unlikely that quantum computers can solve
NP-complete problems in polynomial time, yet it may be instructive to see how a physical theory (denoted
Θ(NP) or
Θ(PSPACE)) for which
NP or even
PSPACE, respectively, constitutes an efficient model of computation, would compare with quantum theory. The present work explores this question, after briefly reviewing some complexity results indicative of the incomparability of
BQP and
NP. We argue that theories
Θ(NP) or
Θ(PSPACE) effectively feature degrees of nonlinearity. Thus, the linearity of quantum theory prevents complete problems in these complexity classes to be efficiently solvable on a quantum computer. On the other hand, the exponentiality of quantum theory endows quantum computers with a certain strength going beyond
NP or even
PH. Thus the contrasting roles of the empowerment provided by quantum mechanical exponentiality and the limitation imposed by quantum mechanical linearity seem to be at the heart of the incomparability of the classes
BQP and
NP. Quanta 2025; 14: 38–47.