QI Algorithms: From Quantum-AI to Entanglement Detection

Quantum artificial intelligence (AI) is an interdisciplinary field, which has emerged in the last five years with the promise of enhancing AI performances. The first part of the talk will focus on reinforcement learning (RL), in which learning is achieved via interactions with a rewarding environment. Following an introduction to a classical-RL model we developed [1] and a short review of our work on discrete quantum walks [2-3], I will present a quantum-RL model that we constructed, which constitutes the first example of RL model that employs quantum processes. The model, which is based on incorporating quantum walks into the agent’s “memory scheme”, exhibits a proven quadratic speedup over its classical counterpart in terms of the agent's ‘’thinking time’’ [4]. 

In the second part of the talk I will establish a connection between entanglement detection and the NP-complete satisfiability problem (SAT): I will prove that having the capacity to (efficiently) determine if a pure state is entangled implies an efficient solution to the SAT problem [5]. 

[1] A. Makmal, A. A. Melnikov, V. Dunjko, H. J. Briegel, “Meta-learning within Projective Simulation”, IEEE ACCESS, 4, 2110, 2016. 

[2] A. Makmal, M. Zhu, D. Manzano, M. Tiersch, H. J. Briegel, “Quantum walks on embedded hypercubes”, Phys. Rev. A, 90, 022314, 2014. 

[3] A. Makmal, M. Tiersch, C. Ganahl, H. J. Briegel, “Quantum walks on embedded hypercubes: Non-symmetric and non-local cases”, Phys. Rev. A, 93, 022322, 2016. 

[4] G. D. Paparo, V. Dunjko, A. Makmal, M. A. Martin-Delgado, H. J. Briegel, “Quantum speedup for active learning agents”, Phys. Rev. X, 4 (3), 031002, 2014. 

[5] A. Makmal, M. Tiersch, V. Dunjko, S. Wu, “Entanglement of π–locally-maximally-entangleable states and the satisfiability problem”, Phys. Rev. A 90 (4), 042308, 2014.