Adversary lower bounds for nonadaptive quantum algorithms

DOI10.1016/j.jcss.2009.10.007zbMath1206.68127OpenAlexW1888573181MaRDI QIDQ980943

Pascal Koiran, Natacha Portier, Jürgen Landes, Penghui Yao

Publication date: 8 July 2010

Published in: Journal of Computer and System Sciences (Search for Journal in Brave)

Full work available at URL: https://hal-ens-lyon.archives-ouvertes.fr/ensl-00260279/file/nonadaptQuantum.pdf

zbMATH Keywords

quantum algorithmslower boundsquery complexityadversary methodnonadaptive algorithms

Mathematics Subject Classification ID

Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Quantum algorithms and complexity in the theory of computing (68Q12)

Related Items

Quantum algorithms for learning symmetric juntas via the adversary bound

Cites Work

• Unnamed Item
• The quantum query complexity of the abelian hidden subgroup problem
• Polynomial degree vs. quantum query complexity
• Quantum lower bounds for the collision and the element distinctness problems
• Lower bounds for local search by quantum arguments
• Hidden translation and orbit coset in quantum computing
• Lower Bounds for Randomized and Quantum Query Complexity Using Kolmogorov Arguments
• Sampling algorithms
• Mathematical Foundations of Computer Science 2004
• Quantum lower bounds by polynomials
• Quantum Query Complexity of Some Graph Problems
• Automata, Languages and Programming
• Automata, Languages and Programming

This page was built for publication: Adversary lower bounds for nonadaptive quantum algorithms