Pāriet uz galveno navigāciju Pāriet uz meklēšanu Pāriet uz galveno saturu

Polynomials, quantum query complexity, and grothendieck's inequality

  • Massachusetts Institute of Technology

Zinātniskās darbības rezultāts: Nodaļa grāmatā/enciklopēdijā/konferences krājumā › Konferences zinātniskais raksts › Pētniecība › koleģiāli recenzēts

14 Atsauces (Scopus)

Kopsavilkums

We show an equivalence between 1-query quantum algorithms and representations by degree- 2 polynomials. Namely, a partial Boolean function f is computable by a 1-query quantum algorithm with error bounded by ϵ < 1/2 iff f can be approximated by a degree-2 polynomial with error bounded by ϵ < 1/2. This result holds for two different notions of approximation by a polynomial: The standard definition of Nisan and Szegedy [21] and the approximation by block-multilinear polynomials recently introduced by Aaronson and Ambainis [1]. The proof uses Grothendieck's inequality to relate two matrix norms, with one norm corresponding to polynomial approximations and the other norm corresponding to quantum algorithms. We also show two results for polynomials of higher degree. First, there is a total Boolean function which requires ∼(n) quantum queries but can be represented by a block-multilinear polynomial of degree ∼O(p n). Thus, in the general case (for an arbitrary number of queries), block-multilinear polynomials are not equivalent to quantum algorithms. Second, for any constant degree k, the two notions of approximation by a polynomial (the standard and the block-multilinear) are equivalent. As a consequence, we solve an open problem from [1], showing that one can estimate the value of any bounded degree-k polynomial p : {0, 1}n ! [-1, 1] with O(n1- 1 2k ) queries.

OriģinālvalodaAngļu
Publikācijas avota nosaukums31st Conference on Computational Complexity, CCC 2016
RedaktoriRan Raz
IzdevējsSchloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing
Lapas25:1-25:19
ISBN (Elektroniski)9783959770088
DOIs
Publikācijas statussPublicēts - 1 maijs 2016
Pasākums31st Conference on Computational Complexity, CCC 2016 - Tokyo, Japāna
Ilgums: 29 maijs 2016 → 1 jūn. 2016

Publikāciju sērijas

NosaukumsLeibniz International Proceedings in Informatics, LIPIcs
Sējums50
ISSN (Drukātā versija)1868-8969

Konference

Konference31st Conference on Computational Complexity, CCC 2016
Valsts/TeritorijaJapāna
PilsētaTokyo
Periods29/05/16 → 1/06/16

Nospiedums

Uzziniet vairāk par pētniecības tēmām “Polynomials, quantum query complexity, and grothendieck's inequality”. Kopā tie veido unikālu nospiedumu.

Citēt šo