2012/09/24 by Katie Barr, Viv Kendon, Barr, Katie +1
Computer Science · #FOS: Computer and information sciences #FOS: Physical sciences #Formal Languages and Automata Theory (cs.FL) #Quantum Computing Algorithms and Architecture #Quantum Information and Cryptography #Quantum Physics (quant-ph) #Quantum-Dot Cellular Automata
paper · pdf · doi:10.48550/arxiv.1209.5238
openalex publication_date 2012/09/24 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
Discrete time quantum walks are known to be universal for quantum computation. This has been proven by showing that they can simulate a universal gate set. In this paper we examine computation 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 be interpreted as performing state discrimination.