Assessment of Quantum Annealing for the Construction of Satisfiability Filters
arXiv:1607.03329 · doi:10.21468/SciPostPhys.2.2.013
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 -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.
arXiv commentSubmission to SciPost
References in corpus (18)
- Quantum Annealing in the Transverse Ising Model
- A Quantum Adiabatic Evolution Algorithm Applied to Random Instances of an NP-Complete Problem
- Quantum annealing with more than one hundred qubits
- Theory of Quantum Annealing of an Ising Spin Glass
- Quantum Annealing and Analog Quantum Computation
- Quantum Annealing: A New Method for Minimizing Multidimensional Functions
- Defining and detecting quantum speedup
- What is the Computational Value of Finite Range Tunneling?
- Quantum versus Classical Annealing of Ising Spin Glasses
- Glassy Chimeras could be blind to quantum speedup: Designing better benchmarks for quantum annealing machines
- Optimization by Quantum Annealing: Lessons from hard 3-SAT cases
- Understanding Quantum Tunneling through Quantum Monte Carlo Simulations
- Exponentially-Biased Ground-State Sampling of Quantum Annealing Machines with Transverse-Field Driving Hamiltonians
- Scaling of running time of quantum adiabatic algorithm for propositional satisfiability
- A Random Matrix Model of Adiabatic Quantum Computing
- Quantum Register Physics
- Classical and Quantum Annealing in the Median of Three Satisfiability
- 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