MAX 2-SAT with up to 108 qubits

Abstract

We experimentally study the performance of a programmable quantum annealing processor, the D-Wave One (DW1) with up to 108 qubits, on maximum satisfiability problem with 2 variables per clause (MAX 2-SAT) problems. We consider ensembles of random problems characterized by a fixed clause density, an order parameter which we tune through its critical value in our experiments. We demonstrate that the DW1 is sensitive to the critical value of the clause density. The DW1 results are verified and compared with akmaxsat, an exact, state-of-the-art algorithm. We study the relative performance of the two solvers and how they correlate in terms of problem hardness. We find that the DW1 performance scales more favorably with problem size and that problem hardness correlation is essentially non-existent. We discuss the relevance and limitations of such a comparison.

18 pages, 23 figures

References in corpus (8)

• Mathematical Foundation of Quantum Annealing
• Minor-embedding in adiabatic quantum computation: II. Minor-universal graph design
• Simple proof of equivalence between adiabatic quantum computation and the circuit model
• Towards Fault Tolerant Adiabatic Quantum Computation
• Size dependence of the minimum excitation gap in the Quantum Adiabatic Algorithm
• The performance of the quantum adiabatic algorithm on random instances of two optimization problems on regular hypergraphs
• Noise resistance of adiabatic quantum computation using random matrix theory
• High Fidelity Adiabatic Quantum Computation via Dynamical Decoupling

Cited by in corpus (38)

• Defining and detecting quantum speedup
• Perspectives of quantum annealing: Methods and implementations
• QAOA for Max-Cut requires hundreds of qubits for quantum speed-up
• What is the Computational Value of Finite Range Tunneling?
• Computational Role of Multiqubit Tunneling in a Quantum Annealer
• Quantum Optimization of Fully-Connected Spin Glasses
• Error corrected quantum annealing with hundreds of qubits
• Adiabatic Quantum Simulation of Quantum Chemistry
• Probing for quantum speedup in spin glass problems with planted solutions
• Strengths and weaknesses of weak-strong cluster problems: A detailed overview of state-of-the-art classical heuristics vs quantum approaches
• Circuit design for multi-body interactions in superconducting quantum annealing system with applications to a scalable architecture
• A Direct Mapping of Max k-SAT and High Order Parity Checks to a Chimera Graph
• Uncertain fate of fair sampling in quantum annealing
• Maximum-Entropy Inference with a Programmable Annealer
• Scaling overhead of embedding optimization problems in quantum annealing
• From Near to Eternity: Spin-glass planting, tiling puzzles, and constraint satisfaction problems
• Modeling and mitigation of cross-talk effects in readout noise with applications to the Quantum Approximate Optimization Algorithm
• Performance of a Quantum Annealer for Ising Ground State Computations on Chimera Graphs
• Analytical Framework for Quantum Alternating Operator Ansätze
• Robust Quantum Control for Adiabatic Quantum Computation
• Solving Quadratic Unconstrained Binary Optimization with divide-and-conquer and quantum algorithms
• Fair sampling of ground-state configurations of binary optimization problems
• Viewing Vanilla Quantum Annealing Through Spin Glasses
• Exponential capacity of associative memories under quantum annealing recall
• Solving SAT and MaxSAT with a Quantum Annealer: Foundations, Encodings, and Preliminary Results
• Disorder-assisted graph coloring on quantum annealers
• Realization of Heisenberg models of spin systems with polar molecules in pendular states
• Error measurements for a quantum annealer using the one-dimensional Ising model with twisted boundaries
• Comparing the hardness of MAX 2-SAT problem instances for quantum and classical algorithms
• Performance of quantum annealing for 2-SAT problems with multiple satisfying assignments
• Posiform Planting: Generating QUBO Instances for Benchmarking
• Entropy Computing, A Paradigm for Optimization in Open Photonic Systems
• Benchmarking a heuristic Floquet adiabatic algorithm for the Max-Cut problem
• A Quantum Annealing Approach to Reduce Covid-19 Spread on College Campuses
• Lack of a thermodynamic finite-temperature spin-glass phase in the two-dimensional randomly-coupled ferromagnet
• An Adiabatic Quantum Algorithm for Determining Gracefulness of A Graph
• Quantum Encoded Quantum Evolutionary Algorithm for the Design of Quantum Circuits
• Efficient Digital Quadratic Unconstrained Binary Optimization Solvers for SAT Problems