×

Quantum algorithms. (English) Zbl 1208.81065

Benatti, Fabio (ed.) et al., Quantum information, computation and cryptography. An introductory survey of theory, technology and experiments. Berlin: Springer (ISBN 978-3-642-11913-2/pbk; 978-3-642-11914-9/ebook). Lecture Notes in Physics 808, 309-342 (2010).
From the text: We begin this chapter by describing some useful notations in Section 1. We then describe the quantum circuit model of computation, introduced by Deutsch, in Section 2. In Section 3 we give a detailed account of Deutsch’s algorithm. We then outline the quantum Fourier transform (Section 4), which is a crucial ingredient in many quantum algorithms. As applications, we describe the algorithms of Deutsch-Josza and Simon in Section 5 and give in detail Shor’s algorithm for factoring in Section 6. These algorithms can be seen as special cases of a more general problem, called the hidden subgroup problem, which we present in Section 7. In Section 8 we give the details of another notable quantum algorithm: Grover’s 1996 algorithm for unstructured search. We finally end this chapter by giving an overview of new algorithms and algorithmic techniques in Section 9.
Those who are interested to know more find detailed expositions of the classic quantum algorithms in the literature (in particular [M. A. Nielsen and I. L. Chuang, Quantum computation and quantum information, Cambridge: Cambridge University Press (2000; Zbl 1049.81015); A. Yu. Kitaev, A. H. Shen and M. N. Vyalyi, Classical and quantum computation, Providence, RI: AMS, American Mathematical Society (2002; Zbl 1022.68001)]) and of more recent developments in the reference list.
For the entire collection see [Zbl 1197.81032].

MSC:

81P68 Quantum computation
68Q12 Quantum algorithms and complexity in the theory of computing
PDFBibTeX XMLCite
Full Text: DOI