An optimal quantum algorithm for the oracle identification problem

Dana Angluin, Queries and Concept Learning , Machine Learning 2

1988

Earlier work this paper cites.

Nick Littlestone, Learning quickly when irrelevant attributes abound: A new linear-threshold algorithm , Machine Learning 2

1988

Earlier work this paper cites.

Peter W. Shor, Polynomial-time algorithms for prime factorization and discrete logarithms on a quantum computer , SIAM Journal on Computing 26

1994

Earlier work this paper cites.

Tibor Hegedűs, Generalized teaching dimensions and the query complexity of learning , Proceedings of the eighth annual conference on Computational learning theory, COLT ’95, ACM, 1995, pp. 108–117

1995

Earlier work this paper cites.

Lov K. Grover, A fast quantum mechanical algorithm for database search , Proceedings of the twenty-eighth annual ACM symposium on Theory of computing (New York, NY, USA), STOC ’96, ACM, 1996, pp. 212–219

1996

Earlier work this paper cites.

Charles H. Bennett, Ethan Bernstein, Gilles Brassard, and Umesh Vazirani, Strengths and Weaknesses of Quantum Computing , SIAM Journal on Computing 26

1997

Earlier work this paper cites.

Ethan Bernstein and Umesh Vazirani, Quantum Complexity Theory , SIAM Journal on Computing 26

1997

Earlier work this paper cites.

Michel Boyer, Gilles Brassard, Peter Høyer, and Alain Tapp, Tight Bounds on Quantum Searching , Fortschritte der Physik 46

1998

Earlier work this paper cites.

Wim van Dam, Quantum Oracle Interrogation: Getting All Information for Almost Half the Price , Proceedings of the 39th Annual Symposium on Foundations of Computer Science, FOCS ’98, 1998, p. 362

1998

Cited alongside, same era.

Andris Ambainis, Quantum lower bounds by quantum arguments , Journal of Computer and System Sciences 64

2000

Cited alongside, same era.

Andris Ambainis, Kazuo Iwama, Akinori Kawachi, Hiroyuki Masuda, Raymond H. Putra, and Shigeru Yamashita, Quantum Identification of Boolean Oracles , STACS 2004, Lecture Notes in Computer Science, vol. 2996, Springer, 2004, pp. 105–116

2004

Cited alongside, same era.

Christoph Dürr, Mark Heiligman, Peter Høyer, and Mehdi Mhalla, Quantum query complexity of some graph problems , SIAM Journal on Computing 35

2004

Cited alongside, same era.

Rocco A. Servedio and Steven J. Gortler, Equivalences and Separations Between Quantum and Classical Learnability , SIAM Journal on Computing 33

Andris Ambainis, Kazuo Iwama, Akinori Kawachi, Rudy Raymond, and Shigeru Yamashita, Improved algorithms for quantum identification of Boolean oracles , Theoretical Computer Science 378

2007

Later among the works it cites.

Andris Ambainis, Kazuo Iwama, Masaki Nakanishi, Harumichi Nishimura, Rudy Raymond, Seiichiro Tani, and Shigeru Yamashita, Average/worst-case gap of quantum query complexities by on-set size , arXiv preprint arXiv:0908.2468 (2009)

Original

2009

Later among the works it cites.

Markus Hunziker, David A. Meyer, Jihun Park, James Pommersheim, and Mitch Rothstein, The geometry of quantum learning , Quantum Information Processing 9

2010

Later among the works it cites.

Troy Lee, Rajat Mittal, Ben W. Reichardt, Robert Špalek, and Mario Szegedy, Quantum Query Complexity of State Conversion , Proceedings of the 2011 IEEE 52nd Annual Symposium on Foundations of Computer Science, FOCS ’11, 2011, pp. 344–353

2011

Later among the works it cites.