REVIEW 1 cited by
SAT, Gadgets, Max2XOR, and Quantum Annealers
Not yet reviewed by Pith; the record is open.
This paper has not been read by Pith yet. Machine review is queued; the pith claim, tier, and objections will appear here once it completes.
SPECIMEN: schema-true, not a live event
T0 review · schema-true
One-sentence machine reading of the paper's core claim.
pith:XXXXXXXX · record.json · timestamp
read the original abstract
Quantum Annealers are basically quantum computers that with high probability can optimize certain quadratic functions on Boolean variables in constant time. These functions are basically the Hamiltonian of Ising models that reach the ground energy state, with a high probability, after an annealing process. They have been proposed as a way to solve SAT. These Hamiltonians can be seen as Max2XOR problems, i.e. as the problem of finding an assignment that maximizes the number of XOR clauses of at most 2 variables that are satisfied. In this paper, we present several gadgets to reduce SAT to Max2XOR. We show how they can be used to translate SAT instances to initial configurations of a quantum annealer.
Forward citations
Cited by 1 Pith paper
-
Strong Structural Bounds for MaxSAT: The Fine Details of Using Neuromorphic and Quantum Hardware Accelerators
MaxSAT, Max2SAT, and QUBO are mutually reducible in linear time with treewidth preserved up to small constants, giving ETH- and SETH-tight bounds and a 2^treewidth algorithm for QUBO.
Discussion (0). Continue with ORCID to comment.