[Proof Complexity] Proof Complexity Of Satisfiability = Computational Complexity? Exploring Quantum Proofs

[wale oluwasanmi]

ABSTRACT 

We present a treatise on a new quantum theoretic algorithmfor solving the 3 Satisfiability problem. The presented algorithm is not astandard quantum algorithm in the sense that it is intended solely for true“physical” quantum systems (if it at all can be realized on these systems).Instead, we posit that the 3 Satisfiability problem has an intrinsic complex quantumform that can be programmed in order to build a model of the solution space forsatisfiable instances or show that such a model cannot be constructed. Thisyields surprising results on the ability for classical systems to abstractly simulategeneral quantum systems. We also present other relevant structures, mathematicaland physical, that bear close analogies with the methods and structurespresented.
'Note: Uses standard computational language as opposed to that of quantum mechanics.

Article: https://engrxiv.org/8ht2m/