This is an expository talk written for the Bourbaki Seminar. After a brief introduction, Section 1 discusses in the categorical language the structure of the classical deterministic computations. Basic notions of complexity icluding the P/NP problem are reviewed. Section 2 introduces the notion of quantum parallelism and explains the main issues of quantum computing. Section 3 is devoted to four quantum subroutines: initialization, quantum computing of classical Boolean functions, quantum Fourier transform, and Grover's search algorithm. The central Section 4 explains Shor's factoring algorithm. Section 5 relates Kolmogorov's complexity to the spectral properties of computable function. Appendix contributes to the prehistory of quantum computing.
This is an expository talk written for the Bourbaki Seminar. After a brief introduction, Section 1 discusses in the categorical language the structure of the classical deterministic computations. Basic notions of complexity icluding the P/NP problem are reviewed. Section 2 introduces the notion of quantum parallelism and explains the main issues of quantum computing. Section 3 is devoted to four quantum subroutines: initialization, quantum computing of classical Boolean functions, quantum Fourier transform, and Grover's search algorithm. The central Section 4 explains Shor's factoring algorithm. Section 5 relates Kolmogorov's complexity to the spectral properties of computable function. Appendix contributes to the prehistory of quantum computing.
In the last few years, theoretical study of quantum systems serving as computational devices has achieved tremendous progress. We now have strong theoretical evidence that quantum computers, if built, might be used as a dramatically powerful computational tool. This review is about to tell the story of theoretical quantum computation. I left out the developing topic of experimental realizations of the model, and neglected other closely related topics which are quantum information and quantum communication. As a result of narrowing the scope of this paper, I hope it has gained the benefit of being an almost self contained introduction to the exciting field of quantum computation. The review begins with background on theoretical computer science, Turing machines and Boolean circuits. In light of these models, I define quantum computers, and discuss the issue of universal quantum gates. Quantum algorithms, including Shor's factorization algorithm and Grover's algorithm for searching databases, are explained. I will devote much attention to understanding what the origins of the quantum computational power are, and what the limits of this power are. Finally, I describe the recent theoretical results which show that quantum computers maintain their complexity power even in the presence of noise, inaccuracies and finite precision. I tried to put all results in their context, asking what the implications to other issues in computer science and physics are. In the end of this review I make these connections explicit, discussing the possible implications of quantum computation on fundamental physical questions, such as the transition from quantum to classical physics.
The basic ideas of quantum computation are introduced by a brief discussion of Bennett (1973, 1982) and Fredkin's (1982, 1997) ideas of reversible computation. After some remarks about Deutsch's (1985) pioneering work on quantum complexity and Shor's (1996) factorisation algorithm, quantum logic gates, qubits and registers are discussed. The role of quantum entanglement is stressed and Grover's (1997) quantum search algorithm described in detail. The paper ends with a review of the current experimental status of quantum computers.
“An Introduction to Quantum Algorithms” provides an introduction to quantum algorithms, starting with the fundamentals of quantum computing. It covers the basics of quantum mechanics, the potential for quantum speedup, and the challenges and limitations of quantum computing. The chapter also highlights the key differences between classical and quantum computing, focusing on concepts such as bits and qubits, quantum measurement, superposition, and qubit properties, with a detailed explanation of qubit states on the Bloch sphere. Additionally, it explores quantum gates and algorithms, including single-qubit and multiple-qubit gates, the Quantum Fourier Transform (QFT), and important quantum algorithms such as Shor's algorithm for factoring, Grover's algorithm for searching, and Simon's algorithm for collision finding.
In this diploma paper we present the Shor’s algorithm for factorising numbers, which runs on quantum computers.
Initially, we explain the basics of quantum computing. Afterwards, we present a general review of the Fourier and the discrete Fourier transform, from which we derive the quantum Fourier transform.
In the last part, we first give a short introduction to modular arithmetics. Later on, we describe the concept of factorization that is used in Shor’s algorithm. Diploma thesis ends with a detailed review of how the algorithm works on quantum computers and a simple example.
A challenging question in the overlap of computer science, mathematics, and physics, is the exploration of potential capabilities of quantum computers. Milestones were the factoring algorithm of Shor (1994) and the search algorithm of Grover (1996). So far, major research was concentrated on discrete and algebraic problems. Much less was known about computational problems of analysis, including such a prominent example as high dimensional numerical integration, which is well-studied in the classical settings. We seek to understand how efficiently this and related problems can be solved in the quantum model of computation (i.e., on a quantum computer) and how the outcome compares to the efficiency of deterministic or randomized algorithms on a classical (i.e. non-quantum) computer. In this paper we give a survey of the state of the art in this field, including also a brief introduction to the general ideas of quantum computing. Introduction A quantum computer is a computing device based on quantum mechanical laws of the (sub)atomic world. The idea of such a computer was developed by Feynman [8] in 1982. He emphasized that simulating quantum mechanics on a classical computer is extremely hard, probably infeasible. So why not try to simulate quantum mechanics using quantum devices themselves. (Thoughts in this direction were also expressed by Manin [21] in 1980, see also [22].) In 1985 Deutsch [6] presented a formal model of computation for quantum computing.
Quantum Information and Quantum Computation are rapidly evolving domains in their theoretical foundations, implementations and applications. The main scope of the present book is to give the basic ideas of this field to undergraduate students in Physics. A rigorous approach is used to provide the key concepts and methods. Many examples are discussed. To be self-contained, the principles of Quantum Mechanics are reviewed. The discussion is aimed to the specific, but paradigmatic, factorization problem of integers, dealt by the Quantum Shor’s Algorithm. Thus, notions of the Number Theory are given in the first Chapter, while the exposition of the algorithm and its implementation is reserved to the last Section.