Part of the book series:Lecture Notes in Computer Science ((LNCS,volume 1443))
Included in the following conference series:
965Accesses
315Citations
Abstract
We study some extensions of Grover's quantum searching algorithm. First, we generalize the Grover iteration in the light of a concept called amplitude amplification. Then, we show that the quadratic speedup obtained by the quantum searching algorithm over classical brute force can still be obtained for a large family of search problems for which good classical heuristics exist. Finally, as our main result, we combine ideas from Grover's and Shor's quantum algorithms to perform approximate counting, which can be seen as an amplitude estimation process.
Supported in part by Canada's NSERC, Québec'sfcar and the Canada Council.
Supported in part by theesprit Long Term Research Programme of the EU under project number 20244 (alcom-it). Research carried out while this author was at the Université de Montréal.
Supported in part by postgraduate fellowships fromfcar andnserc.
This is a preview of subscription content,log in via an institution to check access.
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
Explore related subjects
Discover the latest articles, books and news in related subjects, suggested using machine learning.References
Barenco, Adriano, “Quantum physics and computers”,Contemporary Physics, Vol. 38, 1996, pp. 357–389.
Bennett, Charles H., Ethan Bernstein, Gilles Brassard and Umesh Vazirani, “Strengths and weaknesses of quantum computing”,SIAM Journal on Computing, Vol. 26, no. 5, October 1997, pp. 1510–1523.
Boyer, Michel, GillesBrassard, PeterHØyer and AlainTapp, “Tight bounds on quantum searching”,Proceedings of Fourth Workshop on Physics and Computation — PhysComp '96, November 1996, pp. 36–43. Final version to appear inFortschritte Der Physik.
Brassard, Gilles, “A quantum jump in computer science”, inComputer Science Today, Jan van Leeuwen (editor), Lecture Notes in Computer Science, Vol. 1000, Springer-Verlag, 1995, pp. 1–14.
Brassard, Gilles, “New horizons in quantum information processing”,Proceedings of this ICALP Conference, 1998.
Brassard, Gilles and PeterHØyer, “An exact quantum polynomial-time algorithm for Simon's problem”,Proceedings of Fifth Israeli Symposium on Theory of Computing and Systems — ISTCS '97, June 1997, IEEE Computer Society Press, pp. 12–23.
Chi, Dong-Pyo and JinsooKim, “Quantum database searching by a single query”, Lecture at First NASA International Conference on Quantum Computing and Quantum Communications, Palm Springs, February 1998.
Cleve, Richard, Artur Ekert, Chiara Macchiavello andMichele Mosca, “Quantum algorithms revisited”,Proceedings of the Royal Society, London, Vol. A354, 1998, pp. 339–354.
Grover, Lov K., “Quantum mechanics helps in searching for a needle in a haystack”,Physical Review Letters, Vol. 79, no. 2, 14 July 1997, pp. 325–328.
Mosca, Michele, “Quantum computer algorithms and interferometry”, Lecture atBRICS Workshop on Algorithms in Quantum Information Processing, Aarhus, January 1998.
Shor, Peter W., “Polynomial-time algorithms for prime factorization and discrete logarithms on a quantum computer”,SIAM Journal on Computing, Vol. 26, no. 5, October 1997, pp. 1484–1509.
Author information
Authors and Affiliations
Université de Montréal, Canada
Gilles Brassard & Alain Tapp
Odense University, Denmark
Peter HØyer
- Gilles Brassard
Search author on:PubMed Google Scholar
- Peter HØyer
Search author on:PubMed Google Scholar
- Alain Tapp
Search author on:PubMed Google Scholar
Editor information
Rights and permissions
Copyright information
© 1998 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Brassard, G., HØyer, P., Tapp, A. (1998). Quantum counting. In: Larsen, K.G., Skyum, S., Winskel, G. (eds) Automata, Languages and Programming. ICALP 1998. Lecture Notes in Computer Science, vol 1443. Springer, Berlin, Heidelberg. https://doi.org/10.1007/BFb0055105
Download citation
Published:
Publisher Name:Springer, Berlin, Heidelberg
Print ISBN:978-3-540-64781-2
Online ISBN:978-3-540-68681-1
eBook Packages:Springer Book Archive
Share this paper
Anyone you share the following link with will be able to read this content:
Sorry, a shareable link is not currently available for this article.
Provided by the Springer Nature SharedIt content-sharing initiative
Keywords
These keywords were added by machine and not by the authors. This process is experimental and the keywords may be updated as the learning algorithm improves.
Publish with us
Profiles
- Gilles BrassardView author profile