6533b86dfe1ef96bd12ca7a6
RESEARCH PRODUCT
Exact Quantum Query Complexity of $$\text {EXACT}_{k,l}^n$$
Daniel NagajJānis IraidsAndris Ambainissubject
CombinatoricsQuantum query010201 computation theory & mathematics0103 physical sciences0102 computer and information sciencesFunction (mathematics)010306 general physics01 natural sciencesUpper and lower boundsValue (mathematics)OracleMathematicsdescription
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 |
|---|---|---|---|---|
| 2017-01-01 |