Title: Quantum programming: From superposition of data to superposition of programs

Speaker: Prof. Mingsheng YING

Time: 14:00, April 25, 2014

Meeting Room: FIT 1-415

Abstract:

We propose a novel quantum programming paradigm - superposition-of-programs, motivated by the design idea of a popular class of quantum algorithms, namely quantum walk-based algorithms.

A new quantum programming language QGCL is defined to support the paradigm of superposition-of-programs. This language can be seen as a quantum extension of Dijkstra’s GCL (Guarded Command Language). Surprisingly, alternation in GCL splits into two different notions in the quantum setting: (1) classical alternation (of quantum programs) based on measurements, and (2) quantum alternation defined by external quantum "coins", with the latter being introduced in QGCL for the first time. Quantum alternation is the key program construct for realizing the paradigm of superposition-of-programs. Another very useful program construct in realizing the paradigm of superposition-of-programs, called quantum choice, can be easily defined in terms of quantum alternation. Furthermore, a kind of truly quantum recursion is introduced.

The denotational semantics of QGCL are defined by introducing a new mathematical tool called the guarded composition of operator-valued functions. In particular, the semantics of quantum recursion can be properly defined by employing mathematical tools from second quantization, including Fock space and creation and annihilation operators.

We believe that quantum programming techniques in the superposition-of-programs paradigm will play an important role in further exploiting the unique power of quantum computing.

Bio:

Professor Ying graduated from Fuzhou Teachers College, Jiangxi, China, in 1981. He is a Distinguished Professor with and the Research Director of the Center for Quantum Computation and Intelligent Systems(QCIS), Faculty of Engineering and Information Technology, University of Technology, Sydney, Australia, and Cheung Kong Professor with the State Key Laboratory of Intelligent Technology and Systems, Department of Computer Science and Technology, Tsinghua University, Beijing, China. His research interests are quantum computation and quantum information, formal methods and logics in computer science, and foundations of artificial intelligence. He has published more than 100 papers in various international journals. He is the author of the book "Topology in Process Calculus: Approximate Correctness and Infinite Evolution of Concurrent Programs"(Springer-Verlag, 2001).