Abstract
We study the query complexity of computing a function \(f:\{0,1\}^n\rightarrow \mathbb {R}_+\) in expectation. This requires the algorithm on input \(x\) to output a nonnegative random variable whose expectation equals \(f(x)\), using as few queries to the input \(x\) as possible. We exactly characterize both the randomized and the quantum query complexity by two polynomial degrees, the nonnegative literal degree and the sum-of-squares degree, respectively. We observe that the quantum complexity can be unboundedly smaller than the classical complexity for some functions, but can be at most polynomially smaller for Boolean functions. These query complexities relate to (and are motivated by) the extension complexity of polytopes. The linear extension complexity of a polytope is characterized by the randomized communication complexity of computing its slack matrix in expectation, and the semidefinite (psd) extension complexity is characterized by the analogous quantum model. Since query complexity can be used to upper bound communication complexity of related functions, we can derive some upper bounds on psd extension complexity by constructing efficient quantum query algorithms. As an example we give an exponentially-close entrywise approximation of the slack matrix of the perfect matching polytope with psd-rank only \(2^{n^{1/2+\varepsilon }}\). Finally, we show randomized and quantum query complexity in expectation corresponds to the Sherali-Adams and Lasserre hierarchies, respectively.
Access provided by Autonomous University of Puebla. Download to read the full chapter text
Chapter PDF
Similar content being viewed by others
Keywords
These keywords were added by machine and not by the authors. This process is experimental and the keywords may be updated as the learning algorithm improves.
References
Arunachalam, S., Yuen, H., de Wolf, R.: Unpublished manuscript, August 2014
Beals, R., Buhrman, H., Cleve, R., Mosca, M., de Wolf, R.: Quantum lower bounds by polynomials. Journal of the ACM 48(4), 778–797 (2001)
Blekherman, G., Gouveia, J., Pfeiffer, J.: Sums of squares on the hypercube, February 18, 2014. arXiv/1402.4199
Brassard, G., Høyer, P., Mosca, M., Tapp, A.: Quantum amplitude amplification and estimation. In: Quantum Computation and Quantum Information: A Millennium Volume, AMS Contemporary Mathematics Series, vol. 305, pp. 53–74 (2002)
Braun, G., Pokutta, S.: The matching polytope does not admit fully-polynomial size relaxation schemes. In: Proc. of 26th SODA, pp. 837–846 (2015)
Buhrman, H., Cleve, R., Wigderson, A.: Quantum vs. classical communication and computation. In: Proc. of 30th ACM STOC, pp. 63–68 (1998)
Buhrman, H., Cleve, R., de Wolf, R., Zalka, C.: Bounds for small-error and zero-error quantum algorithms. In: Proc. of 40th IEEE FOCS, pp. 358–368 (1999)
Buhrman, H., de Wolf, R.: Communication complexity lower bounds by polynomials. In: Proc. of 16th IEEE Complexity (CCC), pp. 120–130 (2001)
Buhrman, H., de Wolf, R.: Complexity measures and decision tree complexity: A survey. Theoretical Computer Science 288(1), 21–43 (2002)
Chan, S.O., Lee, J.R., Raghavendra, P., Steurer, D.: Approximate constraint satisfaction requires large LP relaxations. In: Proc. of 54th IEEE FOCS, pp. 350–359 (2013)
Drucker, A., de Wolf, R.: Quantum proofs for classical theorems. Theory of Computing (2011). ToC Library, Graduate Surveys 2
Edmonds, J.: Maximum matching and a polyhedron with 0,1-vertices. Journal of research of the National Bureau of Standards-B 69B(1,2), 125–130 (1965)
Faenza, Y., Fiorini, S., Grappe, R., Tiwary, H.R.: Extended formulations, nonnegative factorizations, and randomized communication protocols. In: Mahjoub, A.R., Markakis, V., Milis, I., Paschos, V.T. (eds.) ISCO 2012. LNCS, vol. 7422, pp. 129–140. Springer, Heidelberg (2012)
Fawzi, H., Saunderson, J., Parrilo, P.: Equivariant semidefinite lifts and sum-of-squares hierarchies, December 23, 2013. arXiv:1312.6662
Fiorini, S., Massar, S., Pokutta, S., Tiwary, H.R., de Wolf, R.: Linear vs. semidefinite extended formulations: exponential separation and strong lower bounds. In: Proc. of 44th ACM STOC, pp. 95–106 (2012)
Gouveia, J., Parrilo, P., Thomas, R.: Lifts of convex sets and cone factorizations. Mathematics of Operations Research 38(2), 248–264 (2013). arXiv:1111.3164
Grigoriev, D.: Complexity of Positivstellensatz proofs for the knapsack. Computational Complexity 10, 139–154 (2001)
Grover, L.K.: A fast quantum mechanical algorithm for database search. In: Proc. of 28th ACM STOC, pp. 212–219 (1996). quant-ph/9605043
Kremer, I.: Quantum Communication. MSc thesis, Hebrew University (1995)
Kushilevitz, E., Nisan, N.: Communication complexity. Cambridge UP (1997)
Lasserre, J.B.: Global optimization with polynomials and the problem of moments. SIAM Journal on Optimization 11(3), 796–817 (2001)
Laurent, M.: Lower bound for the number of iterations in semidefinite hierarchies for the cut polytope. Mathematics of operations research 28(4), 871–883 (2003)
Lee, J.R., Raghavendra, P., Steurer, D.: Lower bounds on the size of semidefinite programming relaxations, November 24, 2014. To appear in STOC 2015. arXiv:1411.6317
Lee, J.R., Raghavendra, P., Steurer, D., Tan, N.: On the power of symmetric LP and SDP relaxations. In: Proc. of 29th IEEE Complexity (CCC), pp. 13–21 (2014)
Midrijanis, G.: Exact quantum query complexity for total Boolean functions, March 23, 2004. quant-ph/0403168
Minsky, M., Papert, S.: Perceptrons. MIT Press (1987)
Nielsen, M.A., Chuang, I.L.: Quantum Computation and Quantum Information. Cambridge University Press (2000)
Padberg, M.: The boolean quadric polytope. Math. prog. 45, 139–172 (1989)
Parrilo, P.: Structured semidefinite programs and semialgebraic geometry methods in robustness and optimization. Ph.D. thesis, Caltech (2000)
Rothvoß, T.: The matching polytope has exponential extension complexity. In: Proc. of 46th ACM STOC, pp. 263–272 (2014)
Sherali, H.D., Adams, W.P.: A hierarchy of relaxations between the continuous and convex hull representations for zero-one programming. SIAM Journal on Discrete Mathematics 3, 411–430 (1990)
Shor, N.Z.: An approach to obtaining global extremums in polynomial mathematical programming problems. Cybernetics 23, 695–700 (1987)
Swart, T.: P = NP. Tech. rep., University of Guelph (1986), revision 1987
de Wolf, R.: Quantum communication and complexity. Theoretical Computer Science 287(1), 337–353 (2002)
de Wolf, R.: Nondeterministic quantum query and quantum communication complexities. SIAM Journal on Computing 32(3), 681–699 (2003)
Yannakakis, M.: Expressing combinatorial optimization problems by linear programs. Journal of Computer and System Sciences 43(3), 441–466 (1991)
Yao, A.C.C.: Quantum circuit complexity. In: Proc. of 34th IEEE FOCS, pp. 352–360 (1993)
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2015 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Kaniewski, J., Lee, T., de Wolf, R. (2015). Query Complexity in Expectation. In: Halldórsson, M., Iwama, K., Kobayashi, N., Speckmann, B. (eds) Automata, Languages, and Programming. ICALP 2015. Lecture Notes in Computer Science(), vol 9134. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-662-47672-7_62
Download citation
DOI: https://doi.org/10.1007/978-3-662-47672-7_62
Published:
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-662-47671-0
Online ISBN: 978-3-662-47672-7
eBook Packages: Computer ScienceComputer Science (R0)