lanl/qa-prolog

Quantum Annealing Prolog

QA Prolog

Description

QA Prolog ("Quantum Annealing Prolog") compiles a subset of the Prolog programming language, enhanced with some native support for constraint-logic programming, into a 2-local Ising-model Hamiltonian function suitable for execution on a D‑Wave quantum annealer. Technically, though, QA Prolog produces a classical Hamiltonian function so it can in principle target classical annealers as well.

QA Prolog is largely a proof of concept, but it does hold out the possibility—not yet demonstrated—of improving Prolog program execution time by replacing backtracking with fully parallel annealing into a solution state.

Installation

See INSTALL.md.

Usage

Run qa-prolog --help for a list of command-line options. At a minimum, you'll need to provide --query=〈Prolog goal〉 and a filename corresponding to a database of Prolog facts and rules.

Here's an example (running on D‑Wave hardware):

$ qa-prolog --verbose --qmasm-args="-O1 --postproc=opt" --query='friends(P1, P2).' examples/friends.pl 
qa-prolog: INFO: Parsing examples/friends.pl as Prolog code
qa-prolog: INFO: Representing symbols with 3 bit(s) and integers with 1 bit(s)
qa-prolog: INFO: Storing intermediate files in /tmp/qap-227417173
qa-prolog: INFO: Writing Verilog code to friends.v
qa-prolog: INFO: Writing a Yosys synthesis script to friends.ys
qa-prolog: INFO: Converting Verilog code to an EDIF netlist
qa-prolog: INFO: Executing yosys -q friends.v friends.ys -b edif -o friends.edif
qa-prolog: INFO: Converting the EDIF netlist to QMASM code
qa-prolog: INFO: Executing edif2qmasm -o friends.qmasm friends.edif
qa-prolog: INFO: Executing qmasm --run --values=ints -O1 --postproc=opt --pin=Query.Valid := true friends.qmasm
P1 = charlie
P2 = alice

P1 = alice
P2 = charlie

Citation

The following journal publication discusses the design and implementation of QA Prolog:

Pakin, Scott. “Performing Fully Parallel Constraint Logic Programming on a Quantum Annealer.” Theory and Practice of Logic Programming, vol. 18, no. 5–6, pp. 928–949, September 2018. Eds.: Ferdinando Fioretto and Enrico Pontelli. Cambridge University Press. ISSN: 1475‑3081, DOI: 10.1017/S1471068418000066, arXiv:1804.00036 [cs.PL].

License

QA Prolog is provided under a BSD-ish license with a "modifications must be indicated" clause. See the LICENSE file for the full text.

QA Prolog is part of the Hybrid Quantum-Classical Computing suite, known internally as LA-CC-16-032.

Author

Scott Pakin, [email protected]

qa-prolog's Issues

ERROR: Can't guess frontend for input file `-b' (missing -f option)!

I am getting this error and I am not sure where the toolchain is broken in my system:

qa-prolog --verbose --qmasm-args="-O1 --postproc=opt" --query='friends(P1, P2).' examples/friends.pl
qa-prolog: INFO: Parsing examples/friends.pl as Prolog code
qa-prolog: INFO: Representing symbols with 3 bit(s) and integers with 1 bit(s)
qa-prolog: INFO: Storing intermediate files in /var/folders/t4/f39wd1sd25x8ry2hq74xhz1r0000gn/T/qap-443035463
qa-prolog: INFO: Writing Verilog code to friends.v
qa-prolog: INFO: Writing a Yosys synthesis script to friends.ys
qa-prolog: INFO: Converting Verilog code to an EDIF netlist
qa-prolog: INFO: Executing yosys -q friends.v friends.ys -b edif -o friends.edif
ERROR: Can't guess frontend for input file `-b' (missing -f option)!
qa-prolog: exit status 1

It seems to break at the yosys execution step: in my system yosys is installed in /usr/local/bin/yosys

Yosys 0.9+932 (git sha1 4072a966, clang 10.0.1 -fPIC -Os)

and all its tests are passing.

The files friends.v and friends.ys can be found in the intermediate folder /var/folders/t4/f39wd1sd25x8ry2hq74xhz1r0000gn/T/qap-443035463

ls -al /var/folders/t4/f39wd1sd25x8ry2hq74xhz1r0000gn/T/qap-443035463
total 16
drwx------    4 acortis  staff   128 Oct  7 07:25 .
drwx------@ 207 acortis  staff  6624 Oct  7 07:25 ..
-rw-r--r--    1 acortis  staff  1588 Oct  7 07:25 friends.v
-rw-r--r--    1 acortis  staff   370 Oct  7 07:25 friends.ys

Would be very grateful if you could suggest where to start debugging. Thanks, Andrea

Linear recursion

Hi!

Is the following program valid:

e(a, b).
e(b, c).
e(c, d).

tc(x, y) :- e(x, y).
tc(x, z) :- e(x, y), tc(y, z).

If so, would QA-prolog correctly answer whether tc(a, d) is satisfiable?

Failed to open stdcell for input

Hello, could you please explain where this error is coming from and how can I fix it?
Thanks!

>> qa-prolog --verbose --qmasm-args="-O1 --postproc=opt" --query='friends(P1, P2).' examples/friends.pl

qa-prolog: INFO: Parsing examples/friends.pl as Prolog code
qa-prolog: INFO: Representing symbols with 3 bit(s) and integers with 1 bit(s)
qa-prolog: INFO: Storing intermediate files in /var/folders/t4/f39wd1sd25x8ry2hq74xhz1r0000gn/T/qap-974853030
qa-prolog: INFO: Writing Verilog code to friends.v
qa-prolog: INFO: Writing a Yosys synthesis script to friends.ys
qa-prolog: INFO: Converting Verilog code to an EDIF netlist
qa-prolog: INFO: Executing yosys -q -s friends.ys -b edif -o friends.edif friends.v
qa-prolog: INFO: Converting the EDIF netlist to QMASM code
qa-prolog: INFO: Executing edif2qmasm -o friends.qmasm friends.edif
qa-prolog: INFO: Executing qmasm --run --values=ints -O1 --postproc=opt --pin=Query.Valid := true friends.qmasm
friends.qmasm:5: error: Failed to open stdcell for input
qa-prolog: exit status 1

I also tried this from the temp directory and got the same error:

>> qmasm --format=qbsolv -o friend.qubo --pin='Query.Valid := true' friends.qmasm

friends.qmasm:5: error: Failed to open stdcell for input