Constructs quantum filtered oracle for Valiant-Vazirani theorem reducing SAT to UNIQUE SAT, enabling polynomial-time NP solution via torsion nonlinearity in noise-free limit but not #P.
NP-complete Problems and Physical Reality
3 Pith papers cite this work. Polarity classification is still indexing.
3
Pith papers citing it
abstract
Can NP-complete problems be solved efficiently in the physical universe? I survey proposals including soap bubbles, protein folding, quantum computing, quantum advice, quantum adiabatic algorithms, quantum-mechanical nonlinearities, hidden variables, relativistic time dilation, analog computing, Malament-Hogarth spacetimes, quantum gravity, closed timelike curves, and "anthropic computing." The section on soap bubbles even includes some "experimental" results. While I do not believe that any of the proposals will let us solve NP-complete problems efficiently, I argue that by studying them, we can learn something not only about computation but also about physics.
fields
quant-ph 3verdicts
UNVERDICTED 3representative citing papers
Nonlinear Hamiltonians on ancilla qubits enable efficient solution of UNIQUE SAT with ⟨σ^z⟩σ^z, 3SAT with ⟨σ^x⟩σ^y - ⟨σ^y⟩σ^x, and #SAT with ⟨σ^y⟩⟨σ^z⟩σ^x - ⟨σ^x⟩⟨σ^z⟩σ^y nonlinearity.
In the large-N limit, spin squeezing torsion yields a nonlinear qubit governed by the two-state Gross-Pitaevskii equation that solves single-input state discrimination on the Bloch sphere.
citing papers explorer
-
Quantum algorithm for Valiant-Vazirani reduction
Constructs quantum filtered oracle for Valiant-Vazirani theorem reducing SAT to UNIQUE SAT, enabling polynomial-time NP solution via torsion nonlinearity in noise-free limit but not #P.
-
Nonlinear Hamiltonians and Boolean satisfiability
Nonlinear Hamiltonians on ancilla qubits enable efficient solution of UNIQUE SAT with ⟨σ^z⟩σ^z, 3SAT with ⟨σ^x⟩σ^y - ⟨σ^y⟩σ^x, and #SAT with ⟨σ^y⟩⟨σ^z⟩σ^x - ⟨σ^x⟩⟨σ^z⟩σ^y nonlinearity.