Exact Quantum Query Algorithm for Error Detection Code Verification

Vasilieva, Alina

doi:10.4230/DROPS.MEMICS.2009.2343

Document

Exact Quantum Query Algorithm for Error Detection Code Verification

Author Alina Vasilieva

Part of: Volume: Annual Doctoral Workshop on Mathematical and Engineering Methods in Computer Science (MEMICS'09) (MEMICS 2009)
Part of: Series: Open Access Series in Informatics (OASIcs)
License: Creative Commons Attribution-NonCommercial-NoDerivs 3.0 Unported license
Publication Date: 2009-12-15

PDF

File

PDF

DROPS.MEMICS.2009.2343.pdf

Filesize: 0.53 MB
8 pages

Document Identifiers

DOI: 10.4230/DROPS.MEMICS.2009.2343
URN: urn:nbn:de:0030-drops-23434

Subject Classification

Keywords

Quantum computing
quantum query algorithms
algorithm complexity
Boolean functions
algorithm design

Metrics

Access Statistics
Total Accesses (updated on a weekly basis)

0

PDF Downloads

0

Metadata Views

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 Get BibTex

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) https://doi.org/10.4230/DROPS.MEMICS.2009.2343

Author Details

Alina Vasilieva

Questions / Remarks / Feedback

Feedback for Dagstuhl Publishing

Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail