A Direct Mapping of Max k-SAT and High Order Parity Checks to a Chimera Graph

Abstract

We demonstrate a direct mapping of max k-SAT problems (and weighted max k-SAT) to a Chimera graph, which is the non-planar hardware graph of the devices built by D-Wave Systems Inc. We further show that this mapping can be used to map a similar class of maximum satisfiability problems where the clauses are replaced by parity checks over potentially large numbers of bits. The latter is of specific interest for applications in decoding for communication. We discuss an example in which the decoding of a turbo code, which has been demonstrated to perform near the Shannon limit, can be mapped to a Chimera graph. The weighted max k-SAT problem is the most general class of satisfiability problems, so our result effectively demonstrates how any satisfiability problem may be directly mapped to a Chimera graph. Our methods faithfully reproduce the low energy spectrum of the target problems, so therefore may also be used for maximum entropy inference.

8 pages, 5 figures, minor changes in version 2, mostly to improve clarity of writing changes at request of referee added in v3, accepted by Scientific Reports

References in corpus (7)

• Minor-embedding in adiabatic quantum computation: II. Minor-universal graph design
• Non-perturbative k-body to two-body commuting conversion Hamiltonians and embedding problem instances into Ising spins
• Ground State Spin Logic
• Stabilisers as a design tool for new forms of Lechner-Hauke-Zoller Annealer
• Adiabatic Quantum Algorithms for the NP-Complete Maximum-Weight Independent Set, Exact Cover and 3SAT Problems
• Computational Role of Collective Tunneling in a Quantum Annealer
• Assessment of Quantum Annealing for the Construction of Satisfiability Filters

Cited by in corpus (25)

• Domain wall encoding of discrete variables for quantum annealing and QAOA
• Improving quantum annealing of the ferromagnetic $p$-spin model through pausing
• QUARK: A Framework for Quantum Computing Application Benchmarking
• Stabilisers as a design tool for new forms of Lechner-Hauke-Zoller Annealer
• Quantum search with hybrid adiabatic-quantum walk algorithms and realistic noise
• Finding spin-glass ground states using quantum walks
• An energetic perspective on rapid quenches in quantum annealing
• Understanding domain-wall encoding theoretically and experimentally
• 3SAT on an All-to-All-Connected CMOS Ising Solver Chip
• Optimal Thermometers with Spin Networks
• Algorithmic QUBO Formulations for k-SAT and Hamiltonian Cycles
• Practical designs for permutation symmetric problem Hamiltonians on hypercubes
• Quadratization in discrete optimization and quantum mechanics
• Towards Prediction of Financial Crashes with a D-Wave Quantum Computer
• Fluctuation guided search in quantum annealing
• Pattern QUBOs: Algorithmic construction of 3SAT-to-QUBO transformations
• Amplitude amplification-inspired QAOA: Improving the success probability for solving 3SAT
• Modernizing Quantum Annealing II: Genetic algorithms with the Inference Primitive Formalism
• Decoding quantum error correction with Ising model hardware
• Entropy Computing, A Paradigm for Optimization in Open Photonic Systems
• A measurement driven analog of adiabatic quantum computation for frustration-free Hamiltonians
• Performance of Domain-Wall Encoding for Quantum Annealing
• Efficient Digital Quadratic Unconstrained Binary Optimization Solvers for SAT Problems
• Quantum annealing and condensed matter physics
• Weyl's Relations, Integrable Matrix Models and Quantum Computation