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.

Adversary lower bounds for nonadaptive quantum algorithms / P. Koiran, J. Landes, N. Portier, P. Yao (LECTURE NOTES IN COMPUTER SCIENCE). - In: Logic, Language, Information and Computation / [a cura di] W. Hodges, R. Queiroz. - [s.l] : Springer, 2008. - ISBN 978-3-540-69936-1. - pp. 226-237 (( Intervento presentato al 15. convegno WoLLIC tenutosi a Edinburgh nel 2008 [10.1007/978-3-540-69937-8_20].

Adversary lower bounds for nonadaptive quantum algorithms

J. Landes
Secondo
;
2008

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.
Settore INF/01 - Informatica
Book Part (author)
File in questo prodotto:
File Dimensione Formato  
978-3-540-69937-8_20.pdf

accesso aperto

Tipologia: Publisher's version/PDF
Dimensione 226.82 kB
Formato Adobe PDF
226.82 kB Adobe PDF Visualizza/Apri
Pubblicazioni consigliate

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/2434/948039
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 1
  • ???jsp.display-item.citation.isi??? 0
social impact