Exact Quantum Query Complexity of EXACT and THRESHOLD

Ambainis, Andris; Iraids, Janis; Smotrovs, Juris

doi:10.4230/LIPIcs.TQC.2013.263

Document

Exact Quantum Query Complexity of EXACT and THRESHOLD

Authors Andris Ambainis, Janis Iraids, Juris Smotrovs

Part of: Volume: 8th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2013)
Part of: Series: Leibniz International Proceedings in Informatics (LIPIcs)
Part of: Conference: Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC)
License: Creative Commons Attribution 3.0 Unported license
Publication Date: 2013-11-13

PDF

File

PDF

LIPIcs.TQC.2013.263.pdf

Filesize: 360 kB
7 pages

Document Identifiers

DOI: 10.4230/LIPIcs.TQC.2013.263
URN: urn:nbn:de:0030-drops-43261

Subject Classification

Keywords

Quantum query algorithms
Complexity of Boolean functions

Metrics

Access Statistics
Total Accesses (updated on a weekly basis)

0

PDF Downloads

0

Metadata Views

Abstract

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.

Cite As Get BibTex

Andris Ambainis, Janis Iraids, and Juris Smotrovs. Exact Quantum Query Complexity of EXACT and THRESHOLD. In 8th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2013). Leibniz International Proceedings in Informatics (LIPIcs), Volume 22, pp. 263-269, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2013) https://doi.org/10.4230/LIPIcs.TQC.2013.263

Author Details

Andris Ambainis

Janis Iraids

Juris Smotrovs

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