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.

arXiv comment8 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 (18)

• Quantum Annealing in the Transverse Ising Model
• Quantum Annealing and Analog Quantum Computation
• Quantum Annealing: A New Method for Minimizing Multidimensional Functions
• Minor-embedding in adiabatic quantum computation: II. Minor-universal graph design
• Computational Role of Multiqubit Tunneling in a Quantum Annealer
• Estimation of effective temperatures in quantum annealers for sampling applications: A case study with possible applications in deep learning
• Application of Quantum Annealing to Training of Deep Neural Networks
• Non-perturbative k-body to two-body commuting conversion Hamiltonians and embedding problem instances into Ising spins
• Circuit design for multi-body interactions in superconducting quantum annealing system with applications to a scalable architecture
• MAX 2-SAT with up to 108 qubits
• Ground State Spin Logic
• Stabilisers as a design tool for new forms of Lechner-Hauke-Zoller Annealer
• Random MAX SAT, Random MAX CUT, and Their Phase Transitions
• Maximum-Entropy Inference with a Programmable Annealer
• Adiabatic Quantum Algorithms for the NP-Complete Maximum-Weight Independent Set, Exact Cover and 3SAT Problems
• Simulated Quantum Annealing with Two All-to-All Connectivity Schemes
• Computational Role of Collective Tunneling in a Quantum Annealer
• Assessment of Quantum Annealing for the Construction of Satisfiability Filters

Cited by in corpus (26)

• Domain wall encoding of discrete variables for quantum annealing and QAOA
• Circuit design for multi-body interactions in superconducting quantum annealing system with applications to a scalable architecture
• 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
• Fluctuation guided search in quantum annealing
• Towards Prediction of Financial Crashes with a D-Wave Quantum Computer
• 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
• Performance of Domain-Wall Encoding for Quantum Annealing
• A measurement driven analog of adiabatic quantum computation for frustration-free Hamiltonians
• Efficient Digital Quadratic Unconstrained Binary Optimization Solvers for SAT Problems
• Weyl's Relations, Integrable Matrix Models and Quantum Computation
• Quantum annealing and condensed matter physics