Adversary Lower Bounds for Nonadaptive Quantum Algorithms

DOI10.1007/978-3-540-69937-8_20MaRDI QIDQ3511461zbMATH OpenOpenAlexFDO

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

Publication date 10 July 2008

Published in Logic, Language, Information and Computation (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/0804.1440

Mathematics Subject Classification ID

Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Quantum computation (81P68)

Abstract: We present general methods for proving lower bounds on the query complexity of nonadaptive quantum algorithms. Our results are based on the adversary method of Ambainis.

Cited in

(4)

• Nonadaptive quantum query complexity
• The quantum adversary method and classical formula size power bounds
• scientific article; zbMATH DE number 5899240 (Why is no real title available?)
• 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 Q3511461)