LIPIcs.TQC.2013.263.pdf
- Filesize: 360 kB
- 7 pages
Document
Exact Quantum Query Complexity of EXACT and THRESHOLD
Authors
-
Part of:
Volume:
8th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2013)
Series: Leibniz International Proceedings in Informatics (LIPIcs)
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
Cite AsGet 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
https://doi.org/10.4230/LIPIcs.TQC.2013.263
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.
Keywords
- Quantum query algorithms
- Complexity of Boolean functions
Metrics
- Access Statistics
-
Total Accesses (updated on a weekly basis)
0PDF Downloads