Adversary Lower Bounds for Nonadaptive Quantum Algorithms

DOI10.1007/978-3-540-69937-8_20zbMATH Open1155.68398arXiv0804.1440OpenAlexW2571124126MaRDI QIDQ3511461FDOQ3511461

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)

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.

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)

Cited In (4)

• Title not available (Why is that?)
• Mathematical Foundations of Computer Science 2004
• Nonadaptive quantum query complexity
• The quantum adversary method and classical formula size power bounds

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)