SciPost Physics

SciPost Phys. 2, 013 (2017) · published 7 April 2017

• doi: 10.21468/SciPostPhys.2.2.013
• pdf
• BiBTeX
• RIS
• Submissions/Reports
• 

Abstract

Satisfiability filters, introduced by S. A. Weaver et al. in 2014, are a new and promising type of filters to address set membership testing. In order to construct satisfiability filters, it is necessary to find disparate solutions to hard random $k$-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.

• Weaver et al.,
  10929, 401 (2018) [Crossref]
• Zhu et al., Fair sampling of ground-state configurations of binary optimization problems
  Phys. Rev. E 99, 063314 (2019) [Crossref]
• Zhu et al., Multi-round QAOA and advanced mixers on a trapped-ion quantum computer
  Quantum Sci. Technol. 8, 015007 (2023) [Crossref]
• Finzgar et al.,
  , 226 (2022) [Crossref]
• Chancellor et al., A Direct Mapping of Max k-SAT and High Order Parity Checks to a Chimera Graph
  Sci Rep 6, 37107 (2016) [Crossref]
• Hamze et al., From near to eternity: Spin-glass planting, tiling puzzles, and constraint-satisfaction problems
  Phys. Rev. E 97, 043303 (2018) [Crossref]
• Könz et al., Uncertain fate of fair sampling in quantum annealing
  Phys. Rev. A 100, 030303 (2019) [Crossref]
• Hegde et al., Deep learning optimal quantum annealing schedules for random Ising models
  New J. Phys. 25, 073013 (2023) [Crossref]
• Passarelli et al., Standard quantum annealing outperforms adiabatic reverse annealing with decoherence
  Phys. Rev. A 105, 032431 (2022) [Crossref]
• Passarelli et al., Counterdiabatic reverse annealing
  Phys. Rev. A 107, 022607 (2023) [Crossref]
• Zhang et al., Grover-QAOA for 3-SAT: quadratic speedup, fair-sampling, and parameter clustering
  Quantum Sci. Technol. 10, 015022 (2025) [Crossref]
• Pelofske, Mapping state transition susceptibility in quantum annealing
  Phys. Rev. Research 5, 013224 (2023) [Crossref]
• Pelofske et al.,
  , 207 (2021) [Crossref]
• Yamamoto et al., Fair Sampling by Simulated Annealing on Quantum Annealer
  J. Phys. Soc. Jpn. 89, 025002 (2020) [Crossref]