The expressive power of quantum walks in terms of language acceptance

Katie Barr
(University of Leeds)
Viv Kendon
(University of Leeds)

Discrete time quantum walks are known to be universal for quantum computation. This has been proven by showing that they can simulate a universal quantum gate set. In this paper, we examine computation by quantum walks in terms of language acceptance, and present two ways in which discrete time quantum walks can accept some languages with certainty. These walks can take quantum as well as classical inputs, and we show that when the input is quantum, the walks can also be interpreted as performing the task of quantum state discrimination.

In Ross Duncan and Prakash Panangaden: Proceedings 9th Workshop on Quantum Physics and Logic (QPL 2012), Brussels, Belgium, 10-12 October 2012, Electronic Proceedings in Theoretical Computer Science 158, pp. 39–51.
Published: 29th July 2014.

ArXived at: bibtex PDF
References in reconstructed bibtex, XML and HTML format (approximated).
Comments and questions to:
For website issues: