publication . Conference object . Article . Preprint . 2000

quantum lower bounds by quantum arguments

Ambainis, Andris;
Open Access
  • Published: 23 Feb 2000
  • Publisher: ACM Press
We propose a new method for proving lower bounds on quantum query algorithms. Instead of a classical adversary that runs the algorithm with one input and then modifies the input, we use a quantum adversary that runs the algorithm with a superposition of inputs. If the algorithm works correctly, its state becomes entangled with the superposition over inputs. We bound the number of queries needed to achieve a sufficient entanglement and this implies a lower bound on the number of queries for the computation. Using this method, we prove two new $\Omega(\sqrt{N})$ lower bounds on computing AND of ORs and inverting a permutation and also provide more uniform proofs f...
free text keywords: Upper and lower bounds, Quantum error correction, Quantum operation, Computer science, Quantum computer, Quantum algorithm, Quantum capacity, Combinatorics, Quantum sort, Discrete mathematics, Quantum phase estimation algorithm, Theoretical Computer Science, Computer Networks and Communications, Computational Theory and Mathematics, Applied Mathematics, quantum computing, quantum lower bounds, quantum query algorithms., Quantum Physics, Computer Science - Computational Complexity
Funded by
NSF| A Proposal for Research on Quantum Computation and Clustering Algorithms
  • Funder: National Science Foundation (NSF)
  • Project Code: 9800024
  • Funding stream: Directorate for Computer & Information Science & Engineering | Division of Computing and Communication Foundations
18 references, page 1 of 2

[1] A. Ambainis. A better lower bound for quantum algorithms searching an ordered list. Proceedings of FOCS'99, pages 352-357. Also1 quant-ph/9902053.

[2] A. Ambainis, L. Schulman, A. Ta-Shma, U. Vazirani, A. Wigderson. Quantum communication complexity of sampling. Proceedings of FOCS'98, pages 342-351.

[3] R. Beals, H. Buhrman, R. Cleve, M. Mosca, R. de Wolf. Quantum lower bounds by polynomials. Proceedings of FOCS'98, pages 352-361. Also quant-ph/9802049.

[4] C. Bennett, E. Bernstein, G. Brassard, U. Vazirani. Strengths and weaknesses of quantum computing. SIAM Journal on Computing, 26(3):1510-1523, 1997, quant-ph/9701001.

[5] G. Brassard, P. Høyer, and A. Tapp. Quantum algorithm for the collision problem. ACM SIGACT News (Cryptology Column), 28:14-19, 1997. quant-ph/9705002. [OpenAIRE]

[6] H. Buhrman, R. Cleve, R. de Wolf, C. Zalka. Bounds for small-error and zero-error quantum algorithms. Proceedings of FOCS'99, pages 358-368. Also cs.CC/9904019.

[7] H. Buhrman, R. Cleve, A. Wigderson. Quantum vs. classical communication and computation. Proceedings of STOC'98, pages 63-68. Also quant-ph/9802046.

[8] H. Buhrman, R. de Wolf. Communication complexity lower bounds by polynomials. cs.CC/9910010.

[9] L. Grover. A fast quantum mechanical algorithm for database search, Proceedings of the 28th ACM Symposium on Theory of Computing, pp. 212-219, 1996, quant-ph/9605043. [OpenAIRE]

[10] L. Grover. How fast can a quantum computer search? quant-ph/9809029.

[11] A. Yu. Kitaev. Quantum measurements and the Abelian stabilizer problem. quant-ph/9511026.

[12] B. Kalyanasundaram, G. Schnitger. The probabilistic communication complexity of set intersection. Proceedings of Structures'87, pages 41-49, 1987.

[13] A. Nayak and F. Wu. The quantum query complexity of approximating the median and related statistics. In Proceedings of 31th STOC, pages 384-393, 1999. Also quant-ph/9804066.

[14] N. Nisan. CREW PRAMs and decision trees. SIAM Journal on Computing, 20:999-1007, 1991. Also STOC'89.

[15] A. Razborov. On the distributional complexity of disjointness. Theoretical Computer Science, 106:385- 90, 1992. Also ICALP'90. [OpenAIRE]

18 references, page 1 of 2
Powered by OpenAIRE Research Graph
Any information missing or wrong?Report an Issue