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

The Code: Covariant Abelian Quartic-N Dynamics, Quantum States, Inverse Invariants, and Bidirectional Time; Exact Infinite Nonlinear Polynomial Quantum SAT

Jeremy Storm

Published Nov 13, 2026• 0 citations
Publisher

Abstract

Infinite, finite, and arbitrary non-linear exact SAT
DOI
10.5281/zenodo.24186379

Related papers

A Dissipative Complexity Barrier for Local Non-Oracular SAT Dynamics

Christopher Paradise

This paper studies a no-go barrier for physically inspired SAT solvers built from local, non-oracular dissipative dynamics. It formalizes a Local Repair GKSL family in which the generator is polynomial-time constructible from the formula, local in the witness encoding, and triggered only by local inconsistency or repair signals. The paper argues that such dynamics inherits the same bottleneck obstruction already visible in washout-style classical SAT dynamics: there exist SAT instance families for which any local repair process has exponentially small effective conductance or dissipative gap, preventing inverse-polynomial time-bounded discrimination between satisfiable and unsatisfiable instances. The paper is intentionally narrow. It does not claim that all physical solvers are weak, and it leaves open separator-based and global-but-non-oracular escape routes. Its contribution is to turn the “physics route” barrier into a precise transport obstruction.

•Apr 11, 2026•0 citations

Quantum Algorithms and Circuits for Linear Equations with Infinite or No Solutions

Jin‐Min Liang, Shu‐Qian Shen, Ming Li

International Journal of Theoretical Physics•May 28, 2019•7 citations

Quantum algorithm for Valiant-Vazirani reduction

Patrick Kelly, Victoria S. Ordonez, Michael R. Geller +1 more

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.

quant-pharXiv:2606.18428•Jun 18, 2026•0 citations

Strong Refutation for Random Quantum 3-SAT at Constant Density

Siu On Chan, Jeff Xu

We give a classical polynomial-time algorithm that strongly refutes random quantum $3$-SAT at sufficiently large constant constraint density, thereby disproving the quantum analogue of Feige's random $3$-SAT hypothesis. This stands in sharp contrast to classical random $3$-SAT, for which polynomial-time strong refutation is known only at constraint density $Δ\gtrsim n^{1/2}$. Although quantum $3$-SAT shares the pairwise-independence barrier of its classical counterpart, our SDP-based refutation overcomes this barrier by exploiting the noncommutativity of quantum constraints.

arXiv:2610.05430•Oct 4, 2026•0 citations

Quantum weighted algebraic geometry codes

Tony Shaska

Designs Codes and Cryptography•Jul 1, 2026•0 citations

Algebraic structure of linear and non-linear models of open quantum systems

A. D. Jannussis, R. Mignani

Physica A Statistical Mechanics and its Applications•Oct 1, 1988•9 citations
This paper studies a no-go barrier for physically inspired SAT solvers built from local, non-oracular dissipative dynamics. It formalizes a Local Repair GKSL family in which the generator is polynomial-time constructible from the formula, local in the witness encoding, and triggered only by local inconsistency or repair signals. The paper argues that such dynamics inherits the same bottleneck obstruction already visible in washout-style classical SAT dynamics: there exist SAT instance families for which any local repair process has exponentially small effective conductance or dissipative gap, preventing inverse-polynomial time-bounded discrimination between satisfiable and unsatisfiable instances. The paper is intentionally narrow. It does not claim that all physical solvers are weak, and it leaves open separator-based and global-but-non-oracular escape routes. Its contribution is to turn the “physics route” barrier into a precise transport obstruction.
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.
We give a classical polynomial-time algorithm that strongly refutes random quantum 333-SAT at sufficiently large constant constraint density, thereby disproving the quantum analogue of Feige's random 333-SAT hypothesis. This stands in sharp contrast to classical random 333-SAT, for which polynomial-time strong refutation is known only at constraint density Δ≳n1/2Δ\gtrsim n^{1/2}Δ≳n1/2. Although quantum 333-SAT shares the pairwise-independence barrier of its classical counterpart, our SDP-based refutation overcomes this barrier by exploiting the noncommutativity of quantum constraints.