Assessment of Quantum Annealing for the Construction of Satisfiability Filters
Abstract
Satisfiability filters are a new and promising type of filters for set membership testing. In order to construct satisfiability filters, it is necessary to find disparate solutions to hard random kk-SAT problems. This paper compares simulated annealing, simulated quantum annealing and WalkSAT, an open-source SAT solver, in terms of their ability to find such solutions. The results indicate that solutions found by simulated quantum annealing are generally less disparate than solutions found by the other solvers and therefore less useful for the construction of satisfiability filters.
Document Details
- Document Type
- Pub Defense Publication
- Publication Date
- Apr 07, 2017
- Source ID
- 10.21468/scipostphys.2.2.013
Entities
People
- Bettina Heim
- Daniel Herr
- Ethan G Brown
- Marlon Azinović
- Matthias Troyer
Organizations
- Aspen Center for Physics
- ETH Zurich
- Intelligence Advanced Research Projects Activity
- Microsoft
- National Science Foundation
- Office of the Director of National Intelligence
- RIKEN
- United States Department of Defense