Assessment of Quantum Annealing for the Construction of Satisfiability Filters

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.

Submission to SciPost

References in corpus (2)

• Exponentially-Biased Ground-State Sampling of Quantum Annealing Machines with Transverse-Field Driving Hamiltonians
• Ground-state statistics from annealing algorithms: Quantum vs classical approaches

Cited by in corpus (17)

• A Direct Mapping of Max k-SAT and High Order Parity Checks to a Chimera Graph
• QUARK: A Framework for Quantum Computing Application Benchmarking
• Uncertain fate of fair sampling in quantum annealing
• From Near to Eternity: Spin-glass planting, tiling puzzles, and constraint satisfaction problems
• Fair Sampling by Simulated Annealing on Quantum Annealer
• Sampling on NISQ Devices: "Who's the Fairest One of All?"
• Comparing Three Generations of D-Wave Quantum Annealers for Minor Embedded Combinatorial Optimization Problems
• Standard quantum annealing outperforms adiabatic reverse annealing with decoherence
• Multi-round QAOA and advanced mixers on a trapped-ion quantum computer
• Fair sampling of ground-state configurations of binary optimization problems
• Counterdiabatic Reverse Annealing
• Deep learning optimal quantum annealing schedules for random Ising models
• Grover-QAOA for 3-SAT: Quadratic Speedup, Fair-Sampling, and Parameter Clustering
• Graph minor embedding can affect sampling degenerate ground states using quantum annealing
• Mapping State Transition Susceptibility in Quantum Annealing
• Biased Degenerate Ground-State Sampling of Small Ising Models with Converged QAOA
• Noise Effects on Diabatic Quantum Annealing Protocols