The expressive power of quantum walks in terms of language acceptance

Barr, Katie and Kendon, Viv (2014) The expressive power of quantum walks in terms of language acceptance. In: 9th Workshop on Quantum Physics and Logic, QPL 2012, 2012-10-10 - 2012-10-12. (https://doi.org/10.4204/EPTCS.158.4)

[thumbnail of Barr-Kendon-QPL2012-The-expressive-power-quantum-walks-terms-language-acceptance]
Preview
 Text. Filename: Barr_Kendon_QPL2012_The_expressive_power_quantum_walks_terms_language_acceptance.pdf
Final Published Version
Download (698kB)| Preview

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.

  • Item type:Conference or Workshop Item(Paper)
    ID code:78928
    Dates:
    Date
    Event
    1 August 2014
    Published
    Notes:Conference code: 113262
    Subjects:Science > Physics
    Department:Faculty of Science > Physics
    Depositing user: Pure Administrator
    Date deposited:16 Dec 2021 11:14
    Last modified:09 Apr 2024 06:55
    Related URLs:
    URI:https://strathprints.strath.ac.uk/id/eprint/78928
CORE (COnnecting REpositories)