文章基本信息

标题：Polynomials, Quantum Query Complexity, and Grothendieck's Inequality
本地全文：下载
作者：Scott Aaronson ; Andris Ambainis ; Janis Iraids 等
期刊名称：LIPIcs : Leibniz International Proceedings in Informatics
电子版ISSN：1868-8969
出版年度：2016
卷号：50
页码：25:1-25:19
DOI：10.4230/LIPIcs.CCC.2016.25
出版社：Schloss Dagstuhl -- Leibniz-Zentrum fuer Informatik
摘要：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 epsilon [-1,1] with O(n^{1-1/(2k)) queries.
关键词：quantum algorithms; Boolean functions; approximation by polynomials; Grothendieck's inequality