License: Creative Commons Attribution-NonCommercial-NoDerivs 3.0 Unported license (CC BY-NC-ND 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/DROPS.MEMICS.2009.2343
URN: urn:nbn:de:0030-drops-23434
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2009/2343/
Go to the corresponding OASIcs Volume Portal

Vasilieva, Alina

Exact Quantum Query Algorithm for Error Detection Code Verification

pdf-format:
09006.VasilievaAlina.2343.pdf (0.5 MB)

Abstract

Quantum algorithms can be analyzed in a query model to compute Boolean functions.
Function input is provided in a black box, and the aim is to compute the function value using as few queries to the black box as possible.
A repetition code is an error detection scheme that repeats each bit of the original message r times.
After a message with redundant bits is transmitted via a communication channel, it must be verified.
If the received message consists of r-size blocks of equal bits, the conclusion is that there were no errors.
The verification procedure can be interpreted as an application of a query algorithm, where input is a message to be checked.
Classically, for N-bit message, values of all N variables must be queried. We demonstrate an exact quantum algorithm that uses only N/2 queries.

BibTeX - Entry

@InProceedings{vasilieva:OASIcs:2009:2343,
  author =	{Alina Vasilieva},
  title =	{{Exact Quantum Query Algorithm for Error Detection Code Verification}},
  booktitle =	{Annual Doctoral Workshop on Mathematical and Engineering Methods in Computer Science (MEMICS'09)},
  pages =	{45--52},
  series =	{OpenAccess Series in Informatics (OASIcs)},
  ISBN =	{978-3-939897-15-6},
  ISSN =	{2190-6807},
  year =	{2009},
  volume =	{13},
  editor =	{Petr Hlinen{\'y} and V{\'a}clav Maty{\'a}{\v{s}} and Tom{\'a}{\v{s}} Vojnar},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2009/2343},
  URN =		{urn:nbn:de:0030-drops-23434},
  doi =		{10.4230/DROPS.MEMICS.2009.2343},
  annote =	{Keywords: Quantum computing, quantum query algorithms, algorithm complexity, Boolean functions, algorithm design}
}

Keywords: Quantum computing, quantum query algorithms, algorithm complexity, Boolean functions, algorithm design
Collection: Annual Doctoral Workshop on Mathematical and Engineering Methods in Computer Science (MEMICS'09)
Issue Date: 2009
Date of publication: 15.12.2009

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI