DROPS

Document

DOI: 10.4230/DROPS.MEMICS.2009.2343

Exact Quantum Query Algorithm for Error Detection Code Verification

Authors: Alina Vasilieva

Published in: OASIcs, Volume 13, Annual Doctoral Workshop on Mathematical and Engineering Methods in Computer Science (MEMICS'09) (2009)

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.

Cite as

Alina Vasilieva. Exact Quantum Query Algorithm for Error Detection Code Verification. In Annual Doctoral Workshop on Mathematical and Engineering Methods in Computer Science (MEMICS'09). Open Access Series in Informatics (OASIcs), Volume 13, pp. 45-52, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2009)

Copy BibTex To Clipboard

@InProceedings{vasilieva:OASIcs:2009:DROPS.MEMICS.2009.2343,
  author =	{Vasilieva, Alina},
  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 =	{Open Access Series in Informatics (OASIcs)},
  ISBN =	{978-3-939897-15-6},
  ISSN =	{2190-6807},
  year =	{2009},
  volume =	{13},
  editor =	{Hlinen\'{y}, Petr and Maty\'{a}\v{s}, V\'{a}clav and Vojnar, Tom\'{a}\v{s}},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/DROPS.MEMICS.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}
}

Search Results

Documents authored by Vasilieva, Alina

Exact Quantum Query Algorithm for Error Detection Code Verification

Abstract

Cite as

Thanks for your feedback!

Could not send message