Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

arXiv:2605.14822

Nonlinear Hamiltonians and Boolean satisfiability

Michael R. Geller, Victoria S. Ordonez, Yohannes Abate

quant-phSubmitted May 14, 2026• Announced May 15, 2026• 0 citations
arXivHTMLPDF

Abstract

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 \le s \le 2^n$). 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 $\langle σ^z \rangle σ^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.

Related papers

Universe as a nonlinear quantum simulation: Large- n limit of the central-spin model

Michael R. Geller

We investigate models of nonlinear qubit evolution based on mappings to an $n$-qubit central-spin model (CSM) in the large-$n$ limit, where mean-field theory is exact. Extending a theorem of Erd\"os and Schlein [J. Stat. Phys. 134, 859 (2009)], we establish that the CSM is rigorously dual to a nonlinear qubit when $n\ensuremath{\rightarrow}\ensuremath{\infty}$. The duality supports a type of nonlinear quantum computation in systems, such as a condensate, where a large number of ancillas couple symmetrically to a central qubit. It also enables a gate-model implementation of nonlinear quantum simulation with a rigorous error bound. Two variants of the model, with and without coupling between ancillas, map to effective models with different nonlinearity and symmetry. Without coupling the CSM simulates initial-condition nonlinearity, where the Hamiltonian is a linear combination of $\mathrm{tr}({\ensuremath{\rho}}_{0}{\ensuremath{\sigma}}^{x}){\ensuremath{\sigma}}^{x}, \mathrm{tr}({\ensuremath{\rho}}_{0}{\ensuremath{\sigma}}^{y}){\ensuremath{\sigma}}^{y}$, and $\mathrm{tr}({\ensuremath{\rho}}_{0}{\ensuremath{\sigma}}^{z}){\ensuremath{\sigma}}^{z}$, where ${\ensuremath{\sigma}}^{x}, {\ensuremath{\sigma}}^{y}$, and ${\ensuremath{\sigma}}^{z}$ are Pauli matrices and ${\ensuremath{\rho}}_{0}$ is the initial density matrix. With symmetric ancillas coupling it simulates linear combinations of $\mathrm{tr}(\ensuremath{\rho}{\ensuremath{\sigma}}^{x}){\ensuremath{\sigma}}^{x}, \mathrm{tr}(\ensuremath{\rho}{\ensuremath{\sigma}}^{y}){\ensuremath{\sigma}}^{y}$, and $\mathrm{tr}(\ensuremath{\rho}{\ensuremath{\sigma}}^{z}){\ensuremath{\sigma}}^{z}$, where $\ensuremath{\rho}$ is the current state. This case can simulate qubit torsion, which has been shown by Abrams and Lloyd [Phys. Rev. Lett. 81, 3992 (1998)] to enable an exponential speedup for state discrimination in an idealized setting. The duality discussed here might also be interesting from a quantum foundation perspective. There has long been interest in whether quantum mechanics might possess some type of small unobserved nonlinearity. If not, what is the principle prohibiting it? The duality implies that there is not a sharp distinction between universes evolving according to linear and nonlinear quantum mechanics: A one-qubit universe prepared in a pure state $|\ensuremath{\varphi}\ensuremath{\rangle}$ at the time of the big bang and symmetrically coupled to ancillas prepared in the same state would appear to evolve nonlinearly for any finite time $t>0$ as long as there are exponentially many ancillas $n\ensuremath{\gg}\mathrm{exp}[O(t)]$.

arXiv:2112.09005•Physical Review A•Oct 16, 2023•1 citation

On the Representation of Boolean and Real Functions as Hamiltonians for Quantum Computing

Stuart Hadfield

Mapping functions on bits to Hamiltonians acting on qubits has many applications in quantum computing. In particular, Hamiltonians representing Boolean functions are required for applications of quantum annealing or the quantum approximate optimization algorithm to combinatorial optimization problems. We show how such functions are naturally represented by Hamiltonians given as sums of Pauli Z operators (Ising spin operators) with the terms of the sum corresponding to the function’s Fourier expansion. For many classes of Boolean functions which are given by a compact description, such as a Boolean formula in conjunctive normal form that gives an instance of the satisfiability problem, it is #P-hard to compute its Hamiltonian representation, i.e., as hard as computing its number of satisfying assignments. On the other hand, no such difficulty exists generally for constructing Hamiltonians representing a real function such as a sum of local Boolean clauses each acting on a fixed number of bits as is common in constraint satisfaction problems. We show composition rules for explicitly constructing Hamiltonians representing a wide variety of Boolean and real functions by combining Hamiltonians representing simpler clauses as building blocks, which are particularly suitable for direct implementation as classical software. We further apply our results to the construction of controlled-unitary operators, and to the special case of operators that compute function values in an ancilla qubit register. Finally, we outline several additional applications and extensions of our results to quantum algorithms for optimization. A goal of this work is to provide a design toolkit for quantum optimization which may be utilized by experts and practitioners alike in the construction and analysis of new quantum algorithms, and at the same time to provide a unified framework for the various constructions appearing in the literature.

arXiv:1804.09130•ACM Transactions on Quantum Computing•Dec 21, 2021•86 citations

A quantum annealing approach for boolean satisfiability problem

Juexiao Su, Tianheng Tu, Lei He

Quantum annealing device has shown a great potential in solving discrete problems that are theoretically and empirically hard. Boolean Satisfiability (SAT) problem, determining if there is an assignment of variables that satisfies a given Boolean function, is the first proven NP-complete problem widely used in various domains. Here, we present a novel mapping of the SAT problem to the quadratic unconstrained binary optimization problem (QUBO), and further develop a tool flow embedding the proposed QUBO to the architecture of the commercialized quantum computer D-Wave. By leveraging electronic design automation techniques including synthesis, placement and routing, this is not only the first work providing the detail flow that embeds the QUBO, but also a technique scalable for real world applications and some hard SAT problems with over 6000 variables in QUBO. Based on our results, we discuss the challenges in solving SAT using the current generation of annealing device, and explore the problem solving capability of future quantum annealing computers.

ACM/IEEE Design Automation Conference (DAC)•May 25, 2016•39 citations

Testing Quantum Satisfiability

Ashley Montanaro, Changpeng Shao, Dominic Verdon

Abstract Quantum k-SAT (the problem of determining whether a k-local Hamiltonian is frustration-free) is known to be QMA $$_1$$ 1 -complete for $$k\ge 3$$ k ≥ 3 , and hence likely hard for quantum computers to solve. Building on a classical result of Alon and Shapira, we show that quantum k-SAT can be solved in randomised polynomial time given the ‘property testing’ promise that the instance is either satisfiable (by any state) or far from satisfiable by a product state; by ‘far from satisfiable by a product state’ we mean that $$\epsilon n^k$$ ϵ n k constraints must be removed before a product state solution exists, for some fixed $$\epsilon >0$$ ϵ > 0 . The proof has two steps: we first show that for a satisfiable instance of quantum k-SAT, most subproblems on a constant number of qubits are satisfiable by a product state. We then show that for an instance of quantum k-SAT which is far from satisfiable by a product state, most subproblems are unsatisfiable by a product state. Given the promise, quantum k-SAT may therefore be solved by checking satisfiability by a product state on randomly chosen subsystems of constant size.

arXiv:2301.10699•Communications in Mathematical Physics•Sep 1, 2025•1 citation

NP in BQP with Nonlinearity

Phil Gossett

If one modifies the laws of Quantum Mechanics to allow nonlinear evolution of quantum states, this paper shows that NP-complete problems would be efficiently solvable in polynomial time with bounded probability (NP in BQP). With that (admittedly very unlikely) assumption, this is demonstrated by describing a polynomially large network of quantum gates that solves the 3SAT problem with bounded probability in polynomial time. As in a previous paper by Abrams and Lloyd (but by a somewhat simpler argument), allowing nonlinearity in the laws of Quantum Mechanics would prove the "weak Church-Turing thesis" to be false. General Relativity is suggested as a possible mechanism to supply the necessary nonlinearity.

arXiv:quant-ph/9804025•Apr 9, 1998•1 citation

Quantum logic synthesis for Satisfiability Problems.

Shuai Yang, Wei Zi, Bujiao Wu +3 more

To demonstrate the advantage of quantum computation, many attempts have been made to attack classically intractable problems, such as the satisfiability problem (SAT), with quantum computer. To use quantum algorithms to solve these NP-hard problems, a quantum oracle with quantum circuit implementation is usually required. In this manuscript, we first introduce a novel algorithm to synthesize quantum logic in the Conjunctive Normal Form (CNF) model. Compared with linear ancillary qubits in the implementation of Qiskit open-source framework, our algorithm can synthesize an m clauses n variables k-CNF with $O(k^2 m^2/n)$ quantum gates by only using three ancillary qubits. Both the size and depth of the circuit can be further compressed with the increase in the number of ancillary qubits. When the number of ancillary qubits is $\Omega(m^\epsilon)$ (for any $\epsilon > 0$), the size of the quantum circuit given by the algorithm is O(km), which is asymptotically optimal. Furthermore, we design another algorithm to optimize the depth of the quantum circuit with only a small increase in the size of the quantum circuit. Experiments show that our algorithms have great improvement in size and depth compared with the previous algorithms.

•Jan 14, 2021•1 citation
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 nnn-bit Boolean function in conjunctive normal form is used to prepare an ancilla encoding its number sss of satisfying assignments (0≤s≤2n0 \le s \le 2^n0≤s≤2n). This is followed by a nonlinear quantum state discrimination gate on the ancilla qubit that is used to learn properties of sss. 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≤s≤1 0 \le s \le 10≤s≤1), we show that a qubit with ⟨σz⟩σz\langle σ^z \rangle σ^z⟨σz⟩σz nonlinearity can be used to efficiently determine whether s=0s = 0s=0 or s=1s = 1s=1, solving the UNIQUE SAT problem. Here ⟨A⟩:=⟨ψ∣A∣ψ⟩\langle A \rangle := \langle ψ| A |ψ\rangle ⟨A⟩:=⟨ψ∣A∣ψ⟩ 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≤s≤2n 0 \le s \le 2^n0≤s≤2n, a Hamiltonian with ⟨σx⟩σy−⟨σy⟩σx \langle σ^x \rangle σ^y - \langle σ^y \rangle σ^x⟨σx⟩σy−⟨σy⟩σx nonlinearity can be used to efficiently determine whether s=0s=0s=0 or s>0s>0s>0, thereby solving 3SAT, which is NP-complete. Finally, we show that ⟨σy⟩⟨σz⟩σx−⟨σx⟩⟨σz⟩σy\langle σ^y \rangle \langle σ^z \rangle σ^x - \langle σ^x \rangle \langle σ^z \rangle σ^y⟨σy⟩⟨σz⟩σx−⟨σx⟩⟨σz⟩σy nonlinearity can be used to efficiently measure sss and solve #SAT, which is #P-complete. The nonlinear models are of mean field type and might be simulated with ultracold atoms.
We investigate models of nonlinear qubit evolution based on mappings to an nnn-qubit central-spin model (CSM) in the large-nnn limit, where mean-field theory is exact. Extending a theorem of Erd\"os and Schlein [J. Stat. Phys. 134, 859 (2009)], we establish that the CSM is rigorously dual to a nonlinear qubit when $n\ensuremath{\rightarrow}\ensuremath{\infty}$. The duality supports a type of nonlinear quantum computation in systems, such as a condensate, where a large number of ancillas couple symmetrically to a central qubit. It also enables a gate-model implementation of nonlinear quantum simulation with a rigorous error bound. Two variants of the model, with and without coupling between ancillas, map to effective models with different nonlinearity and symmetry. Without coupling the CSM simulates initial-condition nonlinearity, where the Hamiltonian is a linear combination of $\mathrm{tr}({\ensuremath{\rho}}_{0}{\ensuremath{\sigma}}^{x}){\ensuremath{\sigma}}^{x}, \mathrm{tr}({\ensuremath{\rho}}_{0}{\ensuremath{\sigma}}^{y}){\ensuremath{\sigma}}^{y}$, and $\mathrm{tr}({\ensuremath{\rho}}_{0}{\ensuremath{\sigma}}^{z}){\ensuremath{\sigma}}^{z}$, where ${\ensuremath{\sigma}}^{x}, {\ensuremath{\sigma}}^{y}$, and ${\ensuremath{\sigma}}^{z}$ are Pauli matrices and ${\ensuremath{\rho}}_{0}$ is the initial density matrix. With symmetric ancillas coupling it simulates linear combinations of $\mathrm{tr}(\ensuremath{\rho}{\ensuremath{\sigma}}^{x}){\ensuremath{\sigma}}^{x}, \mathrm{tr}(\ensuremath{\rho}{\ensuremath{\sigma}}^{y}){\ensuremath{\sigma}}^{y}$, and $\mathrm{tr}(\ensuremath{\rho}{\ensuremath{\sigma}}^{z}){\ensuremath{\sigma}}^{z}$, where $\ensuremath{\rho}$ is the current state. This case can simulate qubit torsion, which has been shown by Abrams and Lloyd [Phys. Rev. Lett. 81, 3992 (1998)] to enable an exponential speedup for state discrimination in an idealized setting. The duality discussed here might also be interesting from a quantum foundation perspective. There has long been interest in whether quantum mechanics might possess some type of small unobserved nonlinearity. If not, what is the principle prohibiting it? The duality implies that there is not a sharp distinction between universes evolving according to linear and nonlinear quantum mechanics: A one-qubit universe prepared in a pure state $|\ensuremath{\varphi}\ensuremath{\rangle}$ at the time of the big bang and symmetrically coupled to ancillas prepared in the same state would appear to evolve nonlinearly for any finite time t>0t>0t>0 as long as there are exponentially many ancillas $n\ensuremath{\gg}\mathrm{exp}[O(t)]$.
Mapping functions on bits to Hamiltonians acting on qubits has many applications in quantum computing. In particular, Hamiltonians representing Boolean functions are required for applications of quantum annealing or the quantum approximate optimization algorithm to combinatorial optimization problems. We show how such functions are naturally represented by Hamiltonians given as sums of Pauli Z operators (Ising spin operators) with the terms of the sum corresponding to the function’s Fourier expansion. For many classes of Boolean functions which are given by a compact description, such as a Boolean formula in conjunctive normal form that gives an instance of the satisfiability problem, it is #P-hard to compute its Hamiltonian representation, i.e., as hard as computing its number of satisfying assignments. On the other hand, no such difficulty exists generally for constructing Hamiltonians representing a real function such as a sum of local Boolean clauses each acting on a fixed number of bits as is common in constraint satisfaction problems. We show composition rules for explicitly constructing Hamiltonians representing a wide variety of Boolean and real functions by combining Hamiltonians representing simpler clauses as building blocks, which are particularly suitable for direct implementation as classical software. We further apply our results to the construction of controlled-unitary operators, and to the special case of operators that compute function values in an ancilla qubit register. Finally, we outline several additional applications and extensions of our results to quantum algorithms for optimization. A goal of this work is to provide a design toolkit for quantum optimization which may be utilized by experts and practitioners alike in the construction and analysis of new quantum algorithms, and at the same time to provide a unified framework for the various constructions appearing in the literature.
Quantum annealing device has shown a great potential in solving discrete problems that are theoretically and empirically hard. Boolean Satisfiability (SAT) problem, determining if there is an assignment of variables that satisfies a given Boolean function, is the first proven NP-complete problem widely used in various domains. Here, we present a novel mapping of the SAT problem to the quadratic unconstrained binary optimization problem (QUBO), and further develop a tool flow embedding the proposed QUBO to the architecture of the commercialized quantum computer D-Wave. By leveraging electronic design automation techniques including synthesis, placement and routing, this is not only the first work providing the detail flow that embeds the QUBO, but also a technique scalable for real world applications and some hard SAT problems with over 6000 variables in QUBO. Based on our results, we discuss the challenges in solving SAT using the current generation of annealing device, and explore the problem solving capability of future quantum annealing computers.
Abstract Quantum k-SAT (the problem of determining whether a k-local Hamiltonian is frustration-free) is known to be QMA 1_11​ 1 -complete for k≥3k\ge 3k≥3 k ≥ 3 , and hence likely hard for quantum computers to solve. Building on a classical result of Alon and Shapira, we show that quantum k-SAT can be solved in randomised polynomial time given the ‘property testing’ promise that the instance is either satisfiable (by any state) or far from satisfiable by a product state; by ‘far from satisfiable by a product state’ we mean that ϵnk\epsilon n^kϵnk ϵ n k constraints must be removed before a product state solution exists, for some fixed ϵ>0\epsilon >0ϵ>0 ϵ > 0 . The proof has two steps: we first show that for a satisfiable instance of quantum k-SAT, most subproblems on a constant number of qubits are satisfiable by a product state. We then show that for an instance of quantum k-SAT which is far from satisfiable by a product state, most subproblems are unsatisfiable by a product state. Given the promise, quantum k-SAT may therefore be solved by checking satisfiability by a product state on randomly chosen subsystems of constant size.
If one modifies the laws of Quantum Mechanics to allow nonlinear evolution of quantum states, this paper shows that NP-complete problems would be efficiently solvable in polynomial time with bounded probability (NP in BQP). With that (admittedly very unlikely) assumption, this is demonstrated by describing a polynomially large network of quantum gates that solves the 3SAT problem with bounded probability in polynomial time. As in a previous paper by Abrams and Lloyd (but by a somewhat simpler argument), allowing nonlinearity in the laws of Quantum Mechanics would prove the "weak Church-Turing thesis" to be false. General Relativity is suggested as a possible mechanism to supply the necessary nonlinearity.
To demonstrate the advantage of quantum computation, many attempts have been made to attack classically intractable problems, such as the satisfiability problem (SAT), with quantum computer. To use quantum algorithms to solve these NP-hard problems, a quantum oracle with quantum circuit implementation is usually required. In this manuscript, we first introduce a novel algorithm to synthesize quantum logic in the Conjunctive Normal Form (CNF) model. Compared with linear ancillary qubits in the implementation of Qiskit open-source framework, our algorithm can synthesize an m clauses n variables k-CNF with O(k2m2/n)O(k^2 m^2/n)O(k2m2/n) quantum gates by only using three ancillary qubits. Both the size and depth of the circuit can be further compressed with the increase in the number of ancillary qubits. When the number of ancillary qubits is Ω(mϵ)\Omega(m^\epsilon)Ω(mϵ) (for any ϵ>0\epsilon > 0ϵ>0), the size of the quantum circuit given by the algorithm is O(km), which is asymptotically optimal. Furthermore, we design another algorithm to optimize the depth of the quantum circuit with only a small increase in the size of the quantum circuit. Experiments show that our algorithms have great improvement in size and depth compared with the previous algorithms.