Q-SATyrus: Mapping Neuro-symbolic Reasoning into an Adiabatic Quantum Computer

Abstract

Much has been promised about quantum computing accelerators, but few actual commercial technologies have been made available so far. The DWave Computers Series constitutes one family of adiabatic quantum computers, based on energy minimization techniques that are considered suitable for solving discrete optimization problems. This work shows a path to explore these machines in order to perform neuro-symbolic reasoning, by specifying it a a set of pseudo-Boolean constraints and associating their satisfiability to energy minimization. Also introduced is the platform Q-SATyrus, a spin-off of the original project SATyrus. Q-SATyrus is under development in order to systematically address such mappings.

Keywords

• neuro-symbolic reasoning
• adiabatic quantum computing
• artificial symmetric neural networks

-

By converting propositional satisfiability into energy minimization [ 7 ], some works specified limited depth proofs, among them it is possible to cite [ 8 ], [ 9 ], [ 10 ] and [ 11 ].

Copyright © 2017 for this paper by its authors. Copying permitted for private and academic purposes. Works [ 9 ], [ 10 ] and [ 11 ] led to the construction of the SATyrus platform other more traditional optimization problems as well as some of their combinations were also mapped to SATyrus [ 12 ], [ 13 ], [ 14 ], [ 15 ], [ 16 ]. It should be pointed out that the mappings issued by SATyrus do not generate only binary connections energy equations.

However, it is possible to convert higher-order connections into a set of binary ones together with additional units [ 17 ]. Q-SATyrus will provide the necessary intermediate conversion of energy minimization with higher-order connections to the one with corresponding global minima with binary connections. Also, although the works on binders [ 18 ], [ 19 ] and [ 20 ] were implemented in conventional computing, it is possible to map their solution to adiabatic computing.

Acknowlegements The author wishes to thank Professor Alberto Ferreira De Souza for suggesting considering D-Wave in connection with the SATyrus platform. This work was partially sponsored by FAPERJ BBP grant E-26/201.444/2014 (coordinator: Professor Valmir Barbosa).

References

1. McGeoch , C. C. , Wang , C. : Experimental Evaluation of an Adiabatic Quantum System for Combinatorial Optimization . In: Proceedings of the CF'13 . Ischia ( 2013 ).

2. D-WAVE Homepage , https://www.dwavesys.com, last accessed 2017 /06/18.

3. D-WAVE (D-Wave 2000Q ™ System) Homepage, https://www.dwavesys.com/d-wavetwo-system, last accessed 2017 /06/18.

4. D-WAVE (Press Release) Homepage, https://www.dwavesys.com/press-releases/dwave%C2% A0announces%C2%A0d-wave-2000q-quantum-computer-and-first-systemorder , last accessed 2017 /06/18.

5. Haykin , S. : Neural Networks: A Comprehensive Foundation , New Jersey, NJ, USA: PrenticeHall Internattional ( 1999 ).

6. D-WAVE (Programming) Homepage , https://www.dwavesys.com/sites/default/files/Map%20Coloring% 20WP2 .pdf, last accessed 2017 /06/18.

7. Pinkas , G.: Symmetric neural networks and propositional logic satisfiability . Neural Computation , 3 , 282 - 291 ( 1991a ).

8. Pinkas , G.: Constructing syntactic proofs in symmetric networks . In Proceedings of Advances in Neural Information Processing Systems (NIPS-91) , pp. 217 - 224 ( 1991b ).

9. Lima , P. M. V. : A Neural Propositional Reasoner that is Goal-Driven and Works Without Pre-Compiled Knowledge , Proc. of the 6th Brazilian Symposium on Neural Networks. IEEE Computer Society Press, 1 . pp 261 - 266 . Rio de Janeiro ( 2000 ).

10. Lima , P. M. V. : Resolution-based Inference with Artificial Neural Networks , PhD Thesis . Imperial College London ( 2000 ).

11. Lima , P. M. V. : A Goal-Driven Neural Propositional Interpreter. International Journal of Neural Systems , 11 ( 3 ), pp 311 - 322 ( 2001 ).

12. Lima , P. M. V. , Pereira , G. C. , Morveli-Espinosa , M. M. M. , França , F. M. G. , Lavor . C. C.: Mapping Molecular Geometry Problems into Pseudo-Boolean Constraints . In: Proceedings of International Workshop on Genomic Databases - IWGD´05 , 1 . Rio de Janeiro ( 2005 ).

13. Lima , P. M. V. , Pereira , G. C. , Morveli-Espinosa , M. M. M. , França , F. M. G. : Mapping and Combining Combinatorial Problems into Energy Landscapes via Pseudo-Boolean Constraints . Lecture Notes in Computer Science. , vol. 3704 , pp 308 - 317 . Springer ( 2005 ).

14. Lima , P. M. V. , Pereira , G. C. , Morveli-Espinosa , M. M. M. , França , F. M. G. : (2005) SATyrus: A SAT-based Neuro-Symbolic Architecture for Constraint , Proc. of HIS'05: Fifth International Conference on Hybrid Intelligent Systems . Los Alamitos, CA, USA: IEEE Computer Society Press, 2005 . p. 137 - 142 .

15. Lima , P. M. V. , Pereira , G. C. , Morveli-Espinosa , M. M. M. , Ferreira , T. O. , França , F. M. G. : Logical Reasoning via Satisfiability Mapped into Energy Functions . International Journal of Pattern Recognition and Artificial Intelligence , 33 ( 5 ), pp 1031 - 1043 ( 2008 )

16. Silva , E. F. , Lima , P. M. V. , Diacovo , R. , França , F. M. G. : Aggregating energy scenarios using the SATyrus neuro-symbolic tool . In: Proceedings of the 19th International Symposium on Mathematical Programming , pp 146 - 146 . Rio de Janeiro ( 2006 ).

17. Venkatesh , S. , Baldi , P. : Programmed Interactions in Higher-Order Neural Networks: Maximal Capacity . Journal of Complexity , 7 , pp 316 - 337 ( 1991 ).

18. Pinkas , G. , Lima , P. M. V. , Cohen , S. : Compact Crossbar Variable Binding for NeuroSymbolic Computation In: NeSy'11 CEUR Workshop Proceedings , 764 , pp 14 - 18 ( 2011 ).

19. Pinkas , G. , Lima.P. M. V. , Cohen , S.: A Dynamic Binding Mechanism for Retrieving and Unifying Complex Predicate-Logic Knowledge . In: ICANN'2012 Proceedings, 1 , pp 482 - 490 . Lausanne ( 2012 ).

20. Pinkas , G. , Lima , P. M. V. , Cohen , S. : Representing, binding, retrieving and unifying relational knowledge using pools of neural binders . Biologically Inspired Cognitive Architectures. , 6 , 87 - 95 ( 2013 ).