Adversary lower bounds for nonadaptive quantum algorithms
DOI10.1016/J.JCSS.2009.10.007zbMATH Open1206.68127OpenAlexW1888573181MaRDI QIDQ980943FDOQ980943
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
Recommendations
Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Quantum algorithms and complexity in the theory of computing (68Q12)
Cites Work
- Sampling algorithms: lower bounds and applications
- Quantum lower bounds for the collision and the element distinctness problems
- Quantum lower bounds by polynomials
- Quantum Query Complexity of Some Graph Problems
- Polynomial degree vs. quantum query complexity
- Title not available (Why is that?)
- Hidden translation and orbit coset in quantum computing
- Lower bounds for local search by quantum arguments
- Lower Bounds for Randomized and Quantum Query Complexity Using Kolmogorov Arguments
- Automata, Languages and Programming
- The quantum query complexity of the abelian hidden subgroup problem
- Mathematical Foundations of Computer Science 2004
- Automata, Languages and Programming
Cited In (10)
- Quantum algorithms for learning symmetric juntas via the adversary bound
- Quantum adversary (upper) bound
- Quantum adversary (upper) bound
- Title not available (Why is that?)
- Quantum lower bounds by quantum arguments
- Optimal Quantum Adversary Lower Bounds for Ordered Search
- Mathematical Foundations of Computer Science 2004
- Nonadaptive quantum query complexity
- The quantum adversary method and classical formula size power bounds
- Automata, Languages and Programming
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)
