Ashwin Nayak
- 1.R. Beals, H. Buhrman, R. Cleve, M. Mosca and R. de Wolf. Quantum lower bounds by polynomials. Proceedings of the 39th Annual IEEE Symposium on Foundations of Computer Science, 1998, pp. 352-361. Google Scholar
Digital Library
- 2.C. Bennett, E. Bernstein, G. Brassard and U. Vazirani. Strengths and weaknesses of quantum computing. SIAM Journal on Computing 26(5), 1997, pp. 1510- 1523. Google ScholarDigital Library
- 3.M. Blum, R.W. Floyd, V. Prat~,, R.L. Rivest and R.E. Tarjan. Time bounds for selection. Journal oj' Computer and System Sciences 7, 1973, pp. 448-461.Google Scholar
- 4.M. Boyer, G. Brassard, P. H0yer and A. Tapp. Tighf. bounds on quantum searching. Forschritte Der Physik 4/5, 1998, pp. 493-505.Google ScholarCross Ref
- 5.G. Brassard, P. Hoyer and A. Tapp. Quantum counting. Proceedings of the ~5th International Colloquium on Automata, Languages and Programming, Lecture Notes in Computer Science 1443, 1998~ pp. 820-831. Google ScholarDigital Library
- 6.G. Brassard, P. Helyer, M. Mosca and A. Tapp. Quantum amplitude amplification and estimation. Manuscript, 1998.Google Scholar
- 7.H. Buhrman, R. Cleve and A. Wigderson. Quantum vs. classical communication and computatAon. Proceedings of the 30th Annual A CM Symposium on Theory of Computing, 1998, pp. 63-68. Google ScholarDigital Library
- 8.C. D'tirr and P. H0yer. A quantum algorithm for finding the minimum. Quantum Physics e-Print archive, http://xxx, lanl. gov/abs/quant-ph/9607014, 1996.Google Scholar
- 9.E. Farhi, J. Goldstone, S. Gutmann and M. Sipser. A limit on the speed of quantum computation in determining parity. Quantum Physics e-Print archive, http://xxx, lanl. gov/abs/quant-1~h/9802045, 1998.Google Scholar
- 10.L.K. Grover. A fast quantum mechanical algorithm for database search. Proceedings of the ~8th A CM Symposium on Theory of Computing, 1996, pp. 212-219. Google ScholarDigital Library
- 11.L.K. Grover. A fast quantum mechanical algorit~hm for estimating the median. Quantum Physics e- Print archive, http://xxx.lanl.gov/abs/quant-ph/ 9607024, 1996. Google ScholarDigital Library
- 12.L.K. Grover. A framework for fast quantum mechanical algorithms. Proceedings of the 30th Annual A CM Symposium or~ Theory of Computing, 1998, pp. 53-62. Google ScholarDigital Library
- 13.M. Minsky and S. Papert. Perceptrons. MIT Press, Cambridge, MA, 2nd edition, 1988. Google ScholarDigital Library
- 14.M. Mosca. Quantum searching, counting and amplitude amplification by eigenvector analysis. Proceedings oj~ the Workshop on Randomized Algorithms, Mathematical Foundations of Computer Science, 1998.Google Scholar
- 15.R. Paturi. On the degree of polynomials that approxima~e symmetric boolean functions. Proceedir~gs o{ the ~Jth Annual ACM Symposium on Theory o)~ Computing, 1992, pp. 468-474. Google ScholarDigital Library
- 16.P.P. Petrushev and V.A. Popov. Rational approximation of real functions. Cambridge University Press, 1987.Google Scholar
- 17.T.J. Rivlin. The Chebyshev polynomials. John Wiley and Sons, 1974.Google Scholar
- 18.U. Vazirarfi. Personal communication, 1997.Google Scholar
Index Terms
- The quantum query complexity of approximating the median and related statistics
Recommendations
Open Problems Related to Quantum Query Complexity
I offer a case that quantum query complexity still has loads of enticing and fundamental open problems—from relativized QMA versus QCMA and BQP versus IP, to time/space tradeoffs for collision and element distinctness, to polynomial degree versus quantum ...
Quantum and classical complexity classes: Separations, collapses, and closure properties
We study the complexity of quantum complexity classes such as EQP, BQP, and NQP (quantum analogs of P, BPP, and NP, respectively) using classical complexity classes such as ZPP, WPP, and C=P. The contributions of this paper are threefold. First, via ...
Average-Case Quantum Query Complexity
STACS '00: Proceedings of the 17th Annual Symposium on Theoretical Aspects of Computer ScienceWe compare classical and quantum query complexities of total Boolean functions. It is known that for worst-case complexity, the gap between quantum and classical can be at most polynomial [3]. We show that for average-case complexity under the uniform ...
Comments