The expressive power of quantum walks in terms of language acceptance

Katie Barr; Viv Kendon

doi:10.4204/EPTCS.158.4

The expressive power of quantum walks in terms of language acceptance

Katie Barr, Viv Kendon

Physics

Research output: Contribution to conference › Paper › peer-review

8 Downloads (Pure)

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.

Original language	English
Pages	39-51
Number of pages	13
DOIs	https://doi.org/10.4204/EPTCS.158.4
Publication status	Published - 1 Aug 2014
Event	9th Workshop on Quantum Physics and Logic, QPL 2012 - Brussels, Belgium Duration: 10 Oct 2012 → 12 Oct 2012

Workshop

Workshop	9th Workshop on Quantum Physics and Logic, QPL 2012
Abbreviated title	QPL 2012
Country/Territory	Belgium
City	Brussels
Period	10/10/12 → 12/10/12

Keywords

computation theory
computer circuits
quantum computers
discrete time
expressive power
quantum state discrimination
quantum walk
two ways
universal quantum gates
quantum theory

Access to Document

10.4204/EPTCS.158.4

Barr-Kendon-QPL2012-The-expressive-power-quantum-walks-terms-language-acceptanceFinal published version, 682 KB

Cite this

@conference{3de91c2a8514421586149127a961cfb4,

title = "The expressive power of quantum walks in terms of language acceptance",

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.",

keywords = "computation theory, computer circuits, quantum computers, discrete time, expressive power, quantum state discrimination, quantum walk, two ways, universal quantum gates, quantum theory",

author = "Katie Barr and Viv Kendon",

note = "Conference code: 113262 ; 9th Workshop on Quantum Physics and Logic, QPL 2012, QPL 2012 ; Conference date: 10-10-2012 Through 12-10-2012",

year = "2014",

month = aug,

day = "1",

doi = "10.4204/EPTCS.158.4",

language = "English",

pages = "39--51",

}

TY - CONF

T1 - The expressive power of quantum walks in terms of language acceptance

AU - Barr, Katie

AU - Kendon, Viv

N1 - Conference code: 113262

PY - 2014/8/1

Y1 - 2014/8/1

N2 - 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.

AB - 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.

KW - computation theory

KW - computer circuits

KW - quantum computers

KW - discrete time

KW - expressive power

KW - quantum state discrimination

KW - quantum walk

KW - two ways

KW - universal quantum gates

KW - quantum theory

UR - https://www.scopus.com/inward/record.uri?eid=2-s2.0-84938562265&doi=10.4204%2fEPTCS.158.4&partnerID=40&md5=0ab94e4094db3309d0942558a4d9caa7

U2 - 10.4204/EPTCS.158.4

DO - 10.4204/EPTCS.158.4

M3 - Paper

SP - 39

EP - 51

T2 - 9th Workshop on Quantum Physics and Logic, QPL 2012

Y2 - 10 October 2012 through 12 October 2012

ER -

The expressive power of quantum walks in terms of language acceptance

Abstract

Workshop

Keywords

Access to Document

Other files and links

Fingerprint

Cite this