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

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

Mathematics Subject Classification ID

Quantum algorithms and complexity in the theory of computing (68Q12)

Related Items (3)

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

This page was built for publication: Exact Quantum Query Complexity of $$\text {EXACT}_{k,l}^n$$