Exact quantum query complexity of EXACT and THRESHOLD

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

8 pages

References in corpus (3)

• Quantum Algorithms Revisited
• An Exact Quantum Polynomial-Time Algorithm for Simon's Problem
• A Limit on the Speed of Quantum Computation in Determining Parity

Cited by in corpus (8)

• Generalizations of the distributed Deutsch-Jozsa promise problem
• Potential of quantum finite automata with exact acceptance
• Characterizations of symmetrically partial Boolean functions with exact quantum query complexity
• Quantum Query as a State Decomposition
• Partial Boolean functions with exact quantum 1-query complexity
• Exact quantum algorithms have advantage for almost all Boolean functions
• Superlinear advantage for exact quantum algorithms
• On exact counting and quasi-quantum complexity