Exact Quantum Query Complexity of $$\text {EXACT}_{k,l}^n$$
From MaRDI portal
Publication:2971138
DOI10.1007/978-3-319-51963-0_19zbMath1444.68075arXiv1608.02374OpenAlexW3101446907WikidataQ59482299 ScholiaQ59482299MaRDI QIDQ2971138
Daniel Nagaj, Jānis Iraids, Andris Ambainis
Publication date: 4 April 2017
Published in: SOFSEM 2017: Theory and Practice of Computer Science (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/1608.02374
Related Items
From the sum-of-squares representation of a Boolean function to an optimal exact quantum query algorithm, Parity decision tree in classical-quantum separations for certain classes of Boolean functions, Exact Quantum Query Complexity of $$\text {EXACT}_{k,l}^n$$
Cites Work
- Polynomials with two values
- On exact quantum query complexity
- Exact Quantum Query Complexity of EXACT and THRESHOLD
- Exact Quantum Query Complexity of $$\text {EXACT}_{k,l}^n$$
- Rapid solution of problems by quantum computation
- Quantum algorithms revisited
- Separations in Query Complexity Based on Pointer Functions
- On the sum-of-squares degree of symmetric quadratic functions
- Quantum lower bounds by polynomials
- Superlinear advantage for exact quantum algorithms
