Adversary lower bounds for nonadaptive quantum algorithms

DOI10.1016/J.JCSS.2009.10.007MaRDI QIDQ980943zbMATH OpenOpenAlexFDO

Authors Pascal Koiran, Jürgen Landes, Natacha Portier, 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

lower boundsquery complexityquantum algorithmsadversary 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)

Recommendations

• Quantum lower bounds by quantum arguments
• Nonadaptive quantum query complexity
• Quantum lower bounds by quantum arguments
• Quantum adversary (upper) bound
• Quantum adversary (upper) bound

Cites work

• scientific article; zbMATH DE number 5605071 (Why is no real title available?)
• Automata, Languages and Programming
• Automata, Languages and Programming
• Hidden translation and orbit coset in quantum computing
• Lower Bounds for Randomized and Quantum Query Complexity Using Kolmogorov Arguments
• Lower bounds for local search by quantum arguments
• Mathematical Foundations of Computer Science 2004
• Polynomial degree vs. quantum query complexity
• Quantum Query Complexity of Some Graph Problems
• Quantum lower bounds by polynomials
• Quantum lower bounds for the collision and the element distinctness problems
• Sampling algorithms: lower bounds and applications
• The quantum query complexity of the abelian hidden subgroup problem

Cited in

(10)

• Quantum adversary (upper) bound
• Quantum adversary (upper) bound
• Automata, Languages and Programming
• Quantum lower bounds by quantum arguments
• scientific article; zbMATH DE number 5899240 (Why is no real title available?)
• Optimal Quantum Adversary Lower Bounds for Ordered Search
• Nonadaptive quantum query complexity
• The quantum adversary method and classical formula size power bounds
• Quantum algorithms for learning symmetric juntas via the adversary bound
• Mathematical Foundations of Computer Science 2004

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q980943)