Polynomial degree vs. quantum query complexity. (English) Zbl 1095.68034
Summary: The degree of a polynomial representing (or approximating) a function \(f\) is a lower bound for the quantum query complexity of \(f\). This observation has been a source of many lower bounds on quantum algorithms. It has been an open problem whether this lower bound is tight.
We exhibit a function with polynomial degree \(M\) and quantum query complexity \(\Omega(M^{1.321\dots})\). This is the first superlinear separation between polynomial degree and quantum query complexity. The lower bound is shown by a generalized version of the quantum adversary method.
We exhibit a function with polynomial degree \(M\) and quantum query complexity \(\Omega(M^{1.321\dots})\). This is the first superlinear separation between polynomial degree and quantum query complexity. The lower bound is shown by a generalized version of the quantum adversary method.
MSC:
| 68Q17 | Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) |
| 68Q25 | Analysis of algorithms and problem complexity |
| 68Q10 | Modes of computation (nondeterministic, parallel, interactive, probabilistic, etc.) |
| 81P68 | Quantum computation |
References:
| [1] | A. Aaronson, Lower bounds for local search by quantum arguments, Proceedings of STOC’04, 2004, pp. 465-474, also quant-ph/0307149.; A. Aaronson, Lower bounds for local search by quantum arguments, Proceedings of STOC’04, 2004, pp. 465-474, also quant-ph/0307149. · Zbl 1192.68256 |
| [2] | Aaronson, S.; Shi, Y., Quantum lower bounds for the collision and the element distinctness problems, J. ACM, 51, 595-605 (2004) · Zbl 1169.68406 |
| [3] | Ambainis, A., Quantum lower bounds by quantum arguments, J. Comput. System Sci., 64, 750-767 (2002), earlier versions at STOC’00 and quant-ph/0002066 · Zbl 1015.68075 |
| [4] | A. Ambainis, Polynomial degree and lower bounds in quantum complexity: collision and element distinctness with small range, Theory of Computing 1 (2005) 37-46, als quantph/0305179.; A. Ambainis, Polynomial degree and lower bounds in quantum complexity: collision and element distinctness with small range, Theory of Computing 1 (2005) 37-46, als quantph/0305179. · Zbl 1213.68281 |
| [5] | A. Ambainis, Quantum query algorithms and lower bounds. Proceedings of FOTFS’III, Trends in Logic, Kluwer Academic Publishers, 23 (2004) 15-32.; A. Ambainis, Quantum query algorithms and lower bounds. Proceedings of FOTFS’III, Trends in Logic, Kluwer Academic Publishers, 23 (2004) 15-32. |
| [6] | H. Barnum, M. E. Saks, A lower bound on the quantum query complexity of read-once functions. J. Comput system Sci.69(2004) 244-258.; H. Barnum, M. E. Saks, A lower bound on the quantum query complexity of read-once functions. J. Comput system Sci.69(2004) 244-258. · Zbl 1083.68045 |
| [7] | H. Barnum, M. Saks, M. Szegedy, Quantum decision trees and semidefinite programming, Complexity’03, 2003, pp. 179-193.; H. Barnum, M. Saks, M. Szegedy, Quantum decision trees and semidefinite programming, Complexity’03, 2003, pp. 179-193. |
| [8] | Beals, R.; Buhrman, H.; Cleve, R.; Mosca, M.; de Wolf, R., Quantum lower bounds by polynomials, J. ACM, 48, 778-797 (2001), earlier versions at FOCS’98 and quant-ph/9802049 · Zbl 1127.68404 |
| [9] | Bennett, C.; Bernstein, E.; Brassard, G.; Vazirani, U., Strengths and weaknesses of quantum computing, SIAM J. Comput., 26, 1510-1523 (1997), quant-ph/9701001 · Zbl 0895.68044 |
| [10] | H. Buhrman, R. Cleve, A. Wigderson, Quantum vs. classical communication and computation, Proceedings of STOC’98, 1998, pp. 63-68, quant-ph/9702040.; H. Buhrman, R. Cleve, A. Wigderson, Quantum vs. classical communication and computation, Proceedings of STOC’98, 1998, pp. 63-68, quant-ph/9702040. · Zbl 1028.68056 |
| [11] | H. Buhrman, C. Durr, M. Heiligman, P. Hoyer, F. Magniez, M. Santha, R. de Wolf, Quantum algorithms for element distinctness, Proceedings of Complexity’01, 2001, pp. 131-137, quant-ph/0007016.; H. Buhrman, C. Durr, M. Heiligman, P. Hoyer, F. Magniez, M. Santha, R. de Wolf, Quantum algorithms for element distinctness, Proceedings of Complexity’01, 2001, pp. 131-137, quant-ph/0007016. · Zbl 1081.68029 |
| [12] | Buhrman, H.; de Wolf, R., Complexity measures and decision tree complexity: a survey, Theoret. Comput. Sci., 288, 21-43 (2002) · Zbl 1061.68058 |
| [13] | Cheney, E. W., Introduction to Approximation Theory (1966), McGraw-Hill: McGraw-Hill New York · Zbl 0161.25202 |
| [14] | L. Grover, A fast quantum mechanical algorithm for database search, STOC’96, 1996, pp. 212-219, quant-ph/9605043.; L. Grover, A fast quantum mechanical algorithm for database search, STOC’96, 1996, pp. 212-219, quant-ph/9605043. · Zbl 0922.68044 |
| [15] | P. Hoyer, M. Mosca, R. de Wolf, Quantum search on bounded-error inputs, Proceedings of ICALP’03, Lecture Notes in Computer Science, vol. 2719, Springer, Berlin, 2003, pp. 291-299, also quant-ph/0304052.; P. Hoyer, M. Mosca, R. de Wolf, Quantum search on bounded-error inputs, Proceedings of ICALP’03, Lecture Notes in Computer Science, vol. 2719, Springer, Berlin, 2003, pp. 291-299, also quant-ph/0304052. · Zbl 1039.68056 |
| [16] | Hoyer, P.; Neerbek, J.; Shi, Y., Quantum lower bounds of ordered searching, sorting and element distinctness, Algorithmica, 34, 429-448 (2002), earlier versions at ICALP’01 and quant-ph/0102078 · Zbl 1012.68071 |
| [17] | S. Kutin, A quantum lower bound for the collision problem, with small range, Theory of Computing 1 (2005) 29-36.; S. Kutin, A quantum lower bound for the collision problem, with small range, Theory of Computing 1 (2005) 29-36. · Zbl 1213.68286 |
| [18] | S. Laplante, F. Magniez, Lower bounds for randomized and quantum query complexity using Kolmogorov arguments, Proceedings of Complexity’04, 2004, pp. 294-304, also quant-ph/0311189.; S. Laplante, F. Magniez, Lower bounds for randomized and quantum query complexity using Kolmogorov arguments, Proceedings of Complexity’04, 2004, pp. 294-304, also quant-ph/0311189. · Zbl 1158.81319 |
| [19] | F. Magniez, M. Santha, M. Szegedy, An \(O( n^{1.3})\); F. Magniez, M. Santha, M. Szegedy, An \(O( n^{1.3})\) · Zbl 1297.68078 |
| [20] | G. Midrijānis, Exact quantum query complexity for total Boolean functions, quant-ph/0403168.; G. Midrijānis, Exact quantum query complexity for total Boolean functions, quant-ph/0403168. |
| [21] | A. Nayak, F. Wu, The quantum query complexity of approximating the median and related statistics, Proceedings of STOC’99, 1999, pp. 384-393, quant-ph/9804066.; A. Nayak, F. Wu, The quantum query complexity of approximating the median and related statistics, Proceedings of STOC’99, 1999, pp. 384-393, quant-ph/9804066. · Zbl 1345.68141 |
| [22] | Nisan, N.; Szegedy, M., On the degree of Boolean functions as real polynomials, Comput. Complexity, 4, 301-313 (1994) · Zbl 0829.68047 |
| [23] | Nisan, N.; Wigderson, A., On rank vs. communication complexity, Combinatorica, 15, 557-565 (1995), also FOCS’94 · Zbl 0845.68038 |
| [24] | Razborov, A., Quantum communication complexity of symmetric predicates, Izvestiya Russian Acad. Sci. Math., 67, 159-176 (2003), also quant-ph/0204025 · Zbl 1088.68052 |
| [25] | M. Saks, A. Wigderson, Probabilistic boolean decision trees and the complexity of evaluating game trees, FOCS’86, 1986, pp. 29-38.; M. Saks, A. Wigderson, Probabilistic boolean decision trees and the complexity of evaluating game trees, FOCS’86, 1986, pp. 29-38. |
| [26] | M. Santha, On the Monte Carlo Boolean decision tree complexity of read-once formulae, Structures’91, 1991, pp. 180-187.; M. Santha, On the Monte Carlo Boolean decision tree complexity of read-once formulae, Structures’91, 1991, pp. 180-187. |
| [27] | Y. Shi, Approximating linear restrictions of Boolean functions, Manuscript, 2002.; Y. Shi, Approximating linear restrictions of Boolean functions, Manuscript, 2002. |
| [28] | Shor, P., Polynomial-time algorithms for prime factorization and discrete logarithms on a quantum computer, SIAM J. Comput., 26, 1484-1509 (1997), quant-ph/9508027 · Zbl 1005.11065 |
| [29] | Snir, M., Lower bounds on probabilistic linear decision trees, Theoret. Comput. Sci., 38, 69-82 (1985) · Zbl 0581.68042 |
| [30] | R. Spalek, M. Szegedy, All quantum adversary methods are equivalent, quant-ph/0409116, 2004.; R. Spalek, M. Szegedy, All quantum adversary methods are equivalent, quant-ph/0409116, 2004. · Zbl 1081.68025 |
| [31] | M. Szegedy, On the quantum query complexity of detecting triangles in graphs, quant-ph/0310107, 2003.; M. Szegedy, On the quantum query complexity of detecting triangles in graphs, quant-ph/0310107, 2003. |
| [32] | S. Zhang, On the power of Ambainis’s lower bounds, Proceedings of ICALP’04, Lecture Notes in Computer Science, vol. 3142, Springer, Berlin, 2004, pp. 1238-1250, also quant-ph/0311060.; S. Zhang, On the power of Ambainis’s lower bounds, Proceedings of ICALP’04, Lecture Notes in Computer Science, vol. 3142, Springer, Berlin, 2004, pp. 1238-1250, also quant-ph/0311060. · Zbl 1098.68053 |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
