The expressive power of quantum walks in terms of language acceptance
arXiv:1408.0051 · doi:10.4204/EPTCS.158.4
Abstract
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.
arXiv commentIn Proceedings QPL 2012, arXiv:1407.8427
References in corpus (9)
- Experimental realization of Shor's quantum factoring algorithm using nuclear magnetic resonance
- Quantum Communication Through an Unmodulated Spin Chain
- Universal computation by quantum walk
- Perfect Transfer of Arbitrary States in Quantum Spin Networks
- Universal quantum computation using the discrete time quantum walk
- Universal computation by multi-particle quantum walk
- Quantum State Discrimination
- Quantum walks on general graphs
- Quantum walk as a generalized measuring device