Exact quantum query complexity of EXACT and THRESHOLD

2013/02/06 by Andris Ambainis, Ambainis, Andris, Jānis Iraids +3
Computer Science · Physics and Astronomy · #Computational Complexity (cs.CC) #FOS: Computer and information sciences #FOS: Physical sciences #Quantum Computing Algorithms and Architecture #Quantum Information and Cryptography #Quantum Mechanics and Applications #Quantum Physics (quant-ph) #cs.CC #quant-ph

paper · pdf · doi:10.48550/arxiv.1302.1235

8 pages

arxiv created 2013/02/06 · openalex publication_date 2013/02/06 · arxiv updated 2013/02/07 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

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: 1) for the problem EXACT_kⁿ in which we have to determine whether the sequence of input bits x₁, ..., x_n contains exactly k values x_i=1; 2) for the problem THRESHOLD_kⁿ in which we have to determine if at least k of n input bits are equal to 1.

Citations

• Quantum Algorithms Revisited
• On the Power of Quantum Computation

Related

• Exact quantum query complexity for total Boolean functions
• Exact quantum algorithms have advantage for almost all Boolean functions
• Superlinear advantage for exact quantum algorithms
• Quantum Query Algorithms for Certain Problems and Generalization of Algorithm Designing Techniques
• Understanding Quantum Algorithms via Query Complexity