报告题目：Quantum Annealing Solutions for the Graph Isomorphism Problem and Related Problems
主讲：Cristian S. Calude，University of Auckland, New Zealand
日期：2017 年7 月5日 (周三)
时间：上午10:30 - 12:00
地点：jbo竞博电竞官方网站东校区数据科学与jbo竞博电竞官方网站A201
主持：邱道文 教授
摘要:
We present and compare various methods to construct efficient QUBO formulations for the Graph Isomorphism Problem—one of a very few problems in NP that is neither known to be solvable in polynomial time nor NP-complete---and related Subgraph Isomorphism Problems that are NP-hard. They are then used to obtain quantum annealing solutions for the D-Wave 2X machine. Experimental results suggest that our direct QUBO formulation is more practical than the others for the D-Wave architecture.
报告人简介:
Cristian S. Calude, a member of Academia Europaea, is Chair Professor of Computer Science and Director of the Centre for Discrete Mathematics and Theoretical Computer Science at the University of Auckland, New Zealand. He is a research consultant for the Quantum Computing Research Initiatives at Lockheed Martin, USA. He received his higher education at the Bucharest University, where he was a student of Gr. C. Moisil and S. Marcus. He is currently working in algorithmic information theory and quantum physics. He published 40 books and more than 250 articles in discrete mathematics, computational complexity, algorithmic information theory, quantum theory, history and philosophy of mathematics and computer science. He had more than 25 visiting appointments including visiting professorships at Cambridge University, Ecole Normale Superieure and Ecole Politechnique in Paris, Japan Advanced Institute of Science and Technology, Microsoft Research, Sandia National Laboratories, IBM Research and Google, Mountainview. Prof. Calude gave more than 50 invited talks to international conferences and 160 seminar presentations to universities in Europe, Americas, Australasia and Africa. He is the founder of the international conference series "Unconventional Computation and Natural Computation". His works have been cited by more than 5500 papers and 120 books by 550 authors. Prof. Calude was awarded many prizes and distinctions: his joint paper on a quasipolynomial algorithm deciding the parity game was presented a Best Paper Award at ACM STOC2017, Montreal. In his ever-vanishing spare time he plays tennis and keyboard.