2026-07-26T16:44:48Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:4326 2024-03-06T10:34:50Z ddc:004 open_access

Exact Quantum Query Complexity of EXACT and THRESHOLD Ambainis, Andris Iraids, Janis Smotrovs, Juris Quantum query algorithms Complexity of Boolean functions A quantum algorithm is exact if it always produces the correct answer, on any input. Coming up with exact quantum algorithms that substantially outperform the best classical algorithm has been a quite challenging task. In this paper, we present two new exact quantum algorithms for natural problems: - for the problem EXACT_k^n in which we have to determine whether the sequence of input bits x_1, ..., x_n contains exactly k values x_i=1; - for the problem THRESHOLD_k^n in which we have to determine if at least k of n input bits are equal to 1. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Andris Ambainis and Janis Iraids and Juris Smotrovs 2013 Is Part Of LIPIcs, Volume 22, 8th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2013) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.TQC.2013.263 urn:nbn:de:0030-drops-43261 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.TQC.2013.263 eng https://creativecommons.org/licenses/by/3.0/legalcode