An application of the Deutsch-Josza algorithm to formal languages and the word problem in groups

Simple item page
dc.creatorBatty, Michael
dc.creatorCasaccino, Andrea
dc.creatorDuncan, Andrew J.
dc.creatorRees, Sarah
dc.creatorSeverini, Simone
dc.date2008-01-18
dc.date2008-02-05
dc.date.accessioned2026-07-07T09:18:24Z
dc.date.available2026-07-07T09:18:24Z
dc.descriptionWe adapt the Deutsch-Josza algorithm to the context of formal language theory. Specifically, we use the algorithm to distinguish between trivial and nontrivial words in groups given by finite presentations, under the promise that a word is of a certain type. This is done by extending the original algorithm to functions of arbitrary length binary output, with the introduction of a more general concept of parity. We provide examples in which properties of the algorithm allow to reduce the number of oracle queries with respect to the deterministic classical case. This has some consequences for the word problem in groups with a particular kind of presentation.
dc.description14 pages, 2 EPS figure
dc.identifierhttps://arxiv.org/abs/0801.2801
dc.identifierhttp://arxiv.org/abs/0801.2801
dc.identifier.urihttp://salesiana.dossiersoluciones.com/handle/123456789/154014
dc.subjectQuantum Physics
dc.titleAn application of the Deutsch-Josza algorithm to formal languages and the word problem in groups
dc.typetext

Files

Collections

arXiv