2026-07-20T14:53:23Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:2343 2024-03-06T10:28:41Z ddc:004 open_access

Exact Quantum Query Algorithm for Error Detection Code Verification Vasilieva, Alina Quantum computing quantum query algorithms algorithm complexity Boolean functions algorithm design 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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Alina Vasilieva 2009 Is Part Of OASIcs, Volume 13, Annual Doctoral Workshop on Mathematical and Engineering Methods in Computer Science (MEMICS'09) (2009) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/DROPS.MEMICS.2009.2343 urn:nbn:de:0030-drops-23434 https://drops.dagstuhl.de/entities/document/10.4230/DROPS.MEMICS.2009.2343 eng https://creativecommons.org/licenses/by-nc-nd/3.0/legalcode