Quantum and classical query complexities of local search are polynomially related. (English) Zbl 1192.68266
Proceedings of the 36th annual ACM symposium on theory of computing (STOC 2004), Chicago, IL, USA, June 13 - 15, 2004. New York, NY: ACM Press (ISBN 1-58113-852-0). 494-501, electronic only (2004).
Abstract: Let \(f\) be an integer-valued function on a finite set \(V\). We call an undirected graph \(G(V,E)\) a neighborhood structure for \(f\). The problem of finding a local minimum for \(f\) can be phrased as: for a fixed neighborhood structure \(G(V,E)\) find a vertex \(x\in V\) such that \(f(x)\) is not bigger than any value that \(f\) takes on some neighbor of \(x\). The complexity of the algorithm is measured by the number of questions of the form “what is the value of \(f\) on \(x\)?” We show that the deterministic, randomized and quantum query complexities of the problem are polynomially related. This generalizes earlier results of D. Aldous [Ann. Probab. 11, No. 2, 403–413 (1983; Zbl 0513.60068)] and S. Aaronson [SIAM J. Comput. 35, No. 4, 804–824 (2006; Zbl 1099.68034)] and solves the main open problem in Aaronson’s paper [loc. cit.].
For an extended version, see the published article [Algorithmica 55, No. 3, 557–575 (2009; Zbl 1191.68310)].
For the entire collection see [Zbl 1074.68504].
For an extended version, see the published article [Algorithmica 55, No. 3, 557–575 (2009; Zbl 1191.68310)].
For the entire collection see [Zbl 1074.68504].
MSC:
| 68Q05 | Models of computation (Turing machines, etc.) (MSC2010) |
| 68Q10 | Modes of computation (nondeterministic, parallel, interactive, probabilistic, etc.) |
| 68Q25 | Analysis of algorithms and problem complexity |
| 81P68 | Quantum computation |
References:
| [1] | S. Aaronson. Lower bounds for local search by quantum arguments, these proceedings, 2004, also quant-ph/0307149. 10.1145/1007352.1007358 |
| [2] | S. Aaronson. Quantum lower bound for the collision problem, in Proc. of the 34th ACM Symposium on Theory of Computing, pp. 635-642, 2002. 10.1145/509907.509999 · Zbl 1192.68255 |
| [3] | A. Aho, J. Hopcroft, and J Ullman. Data Structures and Algorithms, Addison-Wesley, 1983. · Zbl 0487.68005 |
| [4] | D. Aldous. Minimization algorithms and random walk on the d-cube, Annals of probability 11(2), pp. 403-413, 1983. · Zbl 0513.60068 |
| [5] | A. Ambainis. Quantum lower bounds by quantum arguments, Journal of Computer and System Sciences 64, pp. 750-767, 2002. 10.1006/jcss.2002.1826 · Zbl 1015.68075 |
| [6] | H. Barnum, M. Saks, and M. Szegedy. Quantum decision trees and semidefinite programming, in Proc. of the 18th IEEE Conference on Computational Complexity, pp. 179-193, 2003. |
| [7] | R. Beals, H. Buhrman, R. Cleve, M. Mosca, and R. de Wolf. Quantum lower bounds by polynomials, Journal of the ACM (48):4, pp. 778-797, 2001. 10.1145/502090.502097 · Zbl 1127.68404 |
| [8] | C. Bennett, E. Bernstein, G. Brassard, and U. Vazirani. Strength and weaknesses of quantum computing, SIAM Journal on Computing (26):5, pp. 1510-1523, 1997. 10.1137/S0097539796300933 · Zbl 0895.68044 |
| [9] | H. Buhrman, and R. de Wolf. A lower bounds for quantum search of an ordered list, Information and Processing Letters 70, pp. 205-209, 1999. 10.1016/S0020-0190(99)00069-1 · Zbl 1002.68035 |
| [10] | D. Deutsch, and R. Jozsa. Rapid solution of problems by quantum computation, in Proc. of the Royal Society A, volume 439,1985. |
| [11] | C. Dürr, and P. Høyer. A quantum algorithm for finding the minimum, quant-ph/9607014, 1996. |
| [12] | L. Grover. A fast quantum mechanical algorithm for database search, in Proc. of the 28th ACM Symposium on Theory of Computing, pp. 212-219, 1996. 10.1145/237814.237866 · Zbl 0922.68044 |
| [13] | P. Høyer, J. Neerbek, and Y. Shi. Quantum complexities of ordered searching, sorting, and element distinctness, Algorithmica 34(4), pp. 429-448, 2002. · Zbl 1012.68071 |
| [14] | D. Johnson, C. Papadimitriou, and M. Yannakakis. How easy is local search, Journal of Computer and System Sciences 37, pp. 429-448, 1988. 10.1016/0022-0000(88)90046-3 |
| [15] | S. Laplante, and F. Magniez. Lower bounds for randomized and quantum query complexity using Kolmogorov arguments, to appear in Proc. of the 19th IEEE Conference on Computational Complexity, 2004, also quant-ph/0311189. 10.1109/CCC.2004.17 |
| [16] | D. Llewellyn, and C. Tovey. Dividing and conquering the square, Discrete Applied Mathematics 43, pp. 131-153, 1993. 10.1016/0166-218X(93)90004-8 · Zbl 0783.68058 |
| [17] | D. Llewellyn, C. Tovey, and M. Trick. Local optimization on graphs, Discrete Applied Mathematics 23, pp. 157-178, 1989. Erratum: 46, pp. 93-94, 1993. 10.1016/0166-218X(89)90025-5 · Zbl 0675.90085 |
| [18] | N. Megiddo, and C. Papadimitriou. On total functions, existence theorems, and computational complexity, Theoretical Computer Science 81, pp. 317-324, 1991. 10.1016/0304-3975(91)90200-L · Zbl 0731.68036 |
| [19] | Y. Shi. Quantum lower bounds for the collision and the element distinctness problems, in Proc. of the 43rd IEEE Symposium on Foundations of Computer Science, pp. 513-519, 2002. |
| [20] | D. Simon. On the power of quantum computation, SIAM Journal on Computing (26):5, pp. 1474-1783, 1997. 10.1137/S0097539796298637 · Zbl 0883.03024 |
| [21] | Yves Verhoeven. Local optimization over grids, Unpublished manuscript. |
| [22] | C. Zalka. Grover’s quantum searching algorithm is optimal, Physical Review A 60, pp. 2746-2751, 1999. |
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.
