0000000000404984

AUTHOR

Daniel Nagaj

showing 2 related works from this author

Exact quantum query complexity of $\rm{EXACT}_{k,l}^n$

2016

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.

FOS: Computer and information sciencesQuantum PhysicsComputer Science - Computational ComplexityFOS: Physical sciencesComputational Complexity (cs.CC)Quantum Physics (quant-ph)
researchProduct

Exact Quantum Query Complexity of $$\text {EXACT}_{k,l}^n$$

2017

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.

CombinatoricsQuantum query010201 computation theory & mathematics0103 physical sciences0102 computer and information sciencesFunction (mathematics)010306 general physics01 natural sciencesUpper and lower boundsValue (mathematics)OracleMathematics
researchProduct