Exact quantum query complexity of EXACT and THRESHOLD
From MaRDI portal
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.
Recommendations
Cited in
(19)- Quantum query as a state decomposition
- Sharp quantum versus classical query complexity separations
- Evaluation of exact quantum query complexities by semidefinite programming
- An exact quantum algorithm for a restricted subtraction game
- Revisiting Deutsch-Jozsa algorithm
- On exact quantum query complexity
- From the sum-of-squares representation of a Boolean function to an optimal exact quantum query algorithm
- Superlinear advantage for exact quantum algorithms
- Exact quantum query algorithm for error detection code verification
- From quantum query complexity to state complexity
- Exact quantum query complexity of \(\mathrm{EXACT}_{k,l}^n\)
- Generalizations of the distributed Deutsch-Jozsa promise problem
- scientific article; zbMATH DE number 6667586 (Why is no real title available?)
- scientific article; zbMATH DE number 5360947 (Why is no real title available?)
- Superlinear advantage for exact quantum algorithms
- Bounds on Threshold Gate Realizability
- STACS 2005
- Faster than classical quantum algorithm for dense formulas of exact satisfiability and occupation problems
- Distributed generalized Deutsch-Jozsa algorithm
This page was built for publication: Exact quantum query complexity of EXACT and THRESHOLD
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2958430)
