Vasilieva, Alina
Exact Quantum Query Algorithm for Error Detection Code Verification
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 rsize 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 Nbit 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 = {4552},
series = {OpenAccess Series in Informatics (OASIcs)},
ISBN = {9783939897156},
ISSN = {21906807},
year = {2009},
volume = {13},
editor = {Petr Hlinen{\'y} and V{\'a}clav Maty{\'a}{\v{s}} and Tom{\'a}{\v{s}} Vojnar},
publisher = {Schloss DagstuhlLeibnizZentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2009/2343},
URN = {urn:nbn:de:0030drops23434},
doi = {http://dx.doi.org/10.4230/DROPS.MEMICS.2009.2343},
annote = {Keywords: Quantum computing, quantum query algorithms, algorithm complexity, Boolean functions, algorithm design}
}
2009
Keywords: 

Quantum computing, quantum query algorithms, algorithm complexity, Boolean functions, algorithm design 
Seminar: 

Annual Doctoral Workshop on Mathematical and Engineering Methods in Computer Science (MEMICS'09)

Related Scholarly Article: 


Issue date: 

2009 
Date of publication: 

2009 