We present two general methods for proving lower bounds on the query complexity of nonadaptive quantum algorithms. Both methods are based on the adversary method of Ambainis. We show that they yield optimal lower bounds for several natural problems, and we challenge the reader to determine the nonadaptive quantum query complexity of the "1-to-1 versus 2-to-1" problem and of Hidden Translation.In addition to the results presented at Wollic 2008 in the conference version of this paper, we show that the lower bound given by the second method is always at least as good (and sometimes better) as the lower bound given by the first method. We also compare these two quantum lower bounds to probabilistic lower bounds. (C) 2009 Elsevier Inc. All rights reserved.

Adversary lower bounds for nonadaptive quantum algorithms / P. Koiran, J. Landes, N. Portier, P. Yao. - In: JOURNAL OF COMPUTER AND SYSTEM SCIENCES. - ISSN 0022-0000. - 76:5(2010), pp. 347-355. [10.1016/j.jcss.2009.10.007]

Adversary lower bounds for nonadaptive quantum algorithms

J. Landes
Secondo
;
2010

Abstract

We present two general methods for proving lower bounds on the query complexity of nonadaptive quantum algorithms. Both methods are based on the adversary method of Ambainis. We show that they yield optimal lower bounds for several natural problems, and we challenge the reader to determine the nonadaptive quantum query complexity of the "1-to-1 versus 2-to-1" problem and of Hidden Translation.In addition to the results presented at Wollic 2008 in the conference version of this paper, we show that the lower bound given by the second method is always at least as good (and sometimes better) as the lower bound given by the first method. We also compare these two quantum lower bounds to probabilistic lower bounds. (C) 2009 Elsevier Inc. All rights reserved.
Query complexity; Quantum algorithms; Lower bounds; Adversary method; Nonadaptive algorithms
Settore INF/01 - Informatica
Article (author)
File in questo prodotto:
Non ci sono file associati a questo prodotto.
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/948035
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 2
  • ???jsp.display-item.citation.isi??? 2
social impact