6533b7ddfe1ef96bd1273651
RESEARCH PRODUCT
Exact quantum query complexity of $\rm{EXACT}_{k,l}^n$
Andris AmbainisJ��nis IraidsDaniel Nagajsubject
FOS: Computer and information sciencesQuantum PhysicsComputer Science - Computational ComplexityFOS: Physical sciencesComputational Complexity (cs.CC)Quantum Physics (quant-ph)description
In the exact quantum query model a successful algorithm must always output the correct function value. We investigate the function that is true if exactly $k$ or $l$ of the $n$ input bits given by an oracle are 1. We find an optimal algorithm (for some cases), and a nontrivial general lower and upper bound on the minimum number of queries to the black box.
| year | journal | country | edition | language |
|---|---|---|---|---|
| 2016-08-08 |