Performing fully parallel constraint logic programming on a quantum annealer

DOI10.1017/S1471068418000066MaRDI QIDQ4559836zbMATH OpenOpenAlexWikidataFDO

Authors Scott Pakin

Publication date 4 December 2018

Published in Theory and Practice of Logic Programming (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1804.00036

zbMATH Keywords

constraint logic programmingD-wavePrologquantum annealingquantum computing

Mathematics Subject Classification ID

Logic programming (68N17) Quantum computation (81P68)

Abstract: A quantum annealer exploits quantum effects to solve a particular type of optimization problem. The advantage of this specialized hardware is that it effectively considers all possible solutions in parallel, thereby potentially outperforming classical computing systems. However, despite quantum annealers having recently become commercially available, there are relatively few high-level programming models that target these devices. In this article, we show how to compile a subset of Prolog enhanced with support for constraint logic programming into a 2-local Ising-model Hamiltonian suitable for execution on a quantum annealer. In particular, we describe the series of transformations one can apply to convert constraint logic programs expressed in Prolog into an executable form that bears virtually no resemblance to a classical machine model yet that evaluates the specified constraints in a fully parallel manner. We evaluate our efforts on a 1095-qubit D-Wave 2X quantum annealer and describe the approach's associated capabilities and shortcomings. Under consideration in Theory and Practice of Logic Programming (TPLP).

Recommendations

• Embedding equality constraints of optimization problems into a quantum annealer
• Boolean hierarchical Tucker networks on quantum annealers
• Optimizing adiabatic quantum program compilation using a graph-theoretic framework
• Solving SAT (and MaxSAT) with a quantum annealer: foundations, encodings, and preliminary results
• Quantum annealing of hard problems

Cites work

• A Machine-Oriented Logic Based on the Resolution Principle
• An open graph visualization system and its applications to software engineering
• Introduction to algorithms
• Minor-embedding in adiabatic quantum computation. I: The parameter setting problem
• On complexity of the quantum Ising model
• Optimization by simulated annealing
• Polynomial-Time Algorithms for Prime Factorization and Discrete Logarithms on a Quantum Computer
• SWI-Prolog

Cited in

(3)

• Solving SAT (and MaxSAT) with a quantum annealer: foundations, encodings, and preliminary results
• Least-squares solutions to polynomial systems of equations with quantum annealing
• Quantum annealing to solve the unrelated parallel machine scheduling problem

Describes a project that uses

Uses Software

• SWI-Prolog
• ScaffCC
• Deqo
• Python

This page was built for publication: Performing fully parallel constraint logic programming on a quantum annealer

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4559836)