Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

Oxford University Press eBooks

Introductory Quantum Algorithms

Phillip Kaye, Raymond Laflamme, Michele Mosca

Published Nov 16, 2006• 0 citations
Publisher

Abstract

In this chapter we will describe some of the early quantum algorithms. These algorithms are simple and illustrate the main ingredients behind the more useful and powerful quantum algorithms we describe in the subsequent chapters. Since quantum algorithms share some features with classical probabilistic algorithms, we will start with a comparison of the two algorithmic paradigms. Classical probabilistic algorithms were introduced in Chapter 1. In this section we will see how quantum computation can be viewed as a generalization of probabilistic computation. We begin by considering a simple probabilistic computation. Figure 6.1 illustrates the first two steps of such a computation on a register that can be in one of the four states, labelled by the integers 0, 1, 2, and 3. Initially the register is in the state 0. After the first step of the computation, the register is in the state j with probability p0,j . For example, the probability that the computation is in state 2 after the first step is p0,2. In the second step of the computation, the register goes from state j to state k with probability qj,k. For example, in the second step the computation proceeds from state 2 to state 3 with probability q2,3. Suppose we want to find the total probability that the computation ends up in state 3 after the second step. This is calculated by first determining the probability associated with each computation ‘path’ that could end up at the state 3, and then by adding the probabilities for all such paths. There are four computation paths that can leave the computation in state 3 after the first step. The computation can proceed from state 0 to state j and then from state j to state 3, for any of the four j ∊ {0, 1, 2, 3}. The probability associated with any one of these paths is obtained by multiplying the probability p0,j of the transition from state 0 to state j, with the probability qj,3 of the transition from state j to state 3.

DOI
10.1093/oso/9780198570004.003.0009

Related papers

Randomness

Scott Aaronson

In the last two chapters, we talked about computational complexity up till the early 1970s. Here, we'll add a new ingredient to our already simmering stew – something that was thrown in around the mid-1970s, and that now pervades complexity to such an extent that it's hard to imagine doing anything without it. This new ingredient is randomness . Certainly, if you want to study quantum computing, then you first have to understand randomized computing. I mean, quantum amplitudes only become interesting when they exhibit some behavior that classical probabilities don't : contextuality, interference, entanglement (as opposed to correlation), etc. So we can't even begin to discuss quantum mechanics without first knowing what it is that we're comparing against. Alright, so what is randomness? Well, that’s a profound philosophical question, but I’m a simpleminded person. So, you’ve got some probability p , which is a real number in the unit interval [0, 1]. That’s randomness. But wasn’t it a big achievement when Kolmogorov put probability on an axiomatic basis in the 1930s? Yes, it was! But in this chapter, we’ll only care about probability distributions over finitely many events, so all the subtle questions of integrability, measurability, and so on won’t arise. In my view, probability theory is yet another example where mathematicians immediately go to infinite-dimensional spaces, in order to solve the problem of having a nontrivial problem to solve! And that’s fine – whatever floats your boat. I’m not criticizing that. But in theoretical computer science, we’ve already got our hands full with 2n choices. We need 2ℵ0 choices like we need a hole in the head.

Cambridge University Press eBooks•Mar 14, 2013•0 citations

Elementary quantum algorithms

Jonathan A. Jones, Dieter Jaksch

Although the basic ideas of quantum computation are fairly straightforward, the detailed manipulations required to extract a useful result from an entangled superposition of answers can be rather complicated. There are, however, a small number of algorithms which are simple enough to explain using only elementary methods. The best example is Deutsch's algorithm: as this only requires two qubits its properties are amenable to brute-force matrix calculations, and these calculations can be simplified using a variety of short cuts, which also give some insight into how and why the algorithm works. We will also explore the simplest case of Grover's quantum search algorithm, which is once again simple enough to be tacked by brute force. Finally we will look briefly at two methods used to stabilize quantum computers against errors. Deutsch's algorithm The invention of Deutsch's algorithm can be taken as defining the start of modern quantum computation, and it remains a key example, exhibiting many of the key properties of quantum algorithms in a particularly simple form. (Note, however, that the version of Deutsch's algorithm described here is not in fact the original but a later modification which is both more powerful and easier to understand.) Consider a binary function f from one bit to one bit, that is a function which takes in either 0 or 1 as its input and returns either 0 or 1 as its output. There are four such functions which may be conveniently labeled by their outputs as shown in Table 8.1.

Cambridge University Press eBooks•Jul 19, 2012•0 citations

Quantum Probabilities: What Are They?

Simon Friederich

The previous chapter addressed the challenge of making sense of the notion of a quantum state assignment being performed correctly without thereby acknowledging the notion of a quantum state a quantum system ‘is in’. The present chapter discusses what interpretation of quantum probabilities goes best with the account that I have called the ‘Rule Perspective’ and started to develop in the previous chapter. The first section considers what quantum probabilities should be taken to be probabilities of in the Rule Perspective; the second investigates what philosophical interpretation of probabilities applies best to quantum probabilities thus conceived. The third section considers two objections to the resulting account of quantum probabilities. 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.

Palgrave Macmillan UK eBooks•Jan 1, 2015•0 citations

Chapter 2: Early examples of quantum algorithms

Giacomo Nannicini

In this chapter we explore some of the principles of quantum algorithm design, together with a discussion of some of the (chronologically) first algorithms providing evidence of a quantum speedup of some type. These algorithms are not directly useful for optimization, but they serve the purpose of familiarizing the reader with, and building intuition on, the analysis of quantum algorithms; for this purpose, it is generally helpful to start from simple algorithms.

Society for Industrial and Applied Mathematics eBooks•Dec 17, 2025•0 citations

AN INTRODUCTION TO QUANTUM COMPUTING ALGORITHMS

Mr. Gajendra K. Shirsale, Dr. Deepak S. Sharma, Dr. Yogita D. Patil

With the increasing accessibility of quantum computers to the wider population, there is a growing demand for the education and training of a group of quantum programmers. This cohort predominantly consists of individuals who have primarily focused on the development of classical computer programs throughout their professional careers. Although existing quantum computers currently possess fewer than 100 qubits, it is widely anticipated that the quantum computing hardware will experience significant advancements in terms of qubit quantity, quality, and connectivity. The objective of this review is to elucidate the fundamental principles of quantum programming, which diverge significantly from classical programming. This will be achieved through the utilization of concise algebraic expressions, allowing for an optional comprehension of the captivating underlying principles of quantum mechanics. This paper provides an overview of quantum computing algorithms and their practical implementation on physical quantum hardware. In this study, we undertake a comprehensive examination of various quantum algorithms, with the objective of providing concise and self-contained descriptions for each. In this study, we demonstrate the practical implementation of the aforementioned algorithms on IBM's quantum computer. For each algorithm, we thoroughly analyze and compare the outcomes obtained from the implementation on the quantum computer with those obtained from the simulator. This analysis focuses on identifying and discussing any disparities that arise between the results obtained from the simulator and the actual hardware runs. This article serves as an introduction to quantum algorithms for computer scientists, physicists, and engineers, offering a comprehensive guide for their practical implementation.

International Engineering Journal For Research & Development•Mar 8, 2024•0 citations

Brownian Movement and Quantum Computers

Agnieszka Habel

This problem in lieu of thesis is a discussion of two topics: Brownian movement and quantum computers. Brownian movement is a physical phenomenon in which the particle velocity is constantly undergoing random fluctuations. Chapters 2, 3 and 4, describe Brownian motion from three different perspectives. The next four chapters are devoted to the subject of quantum computers, which are the signal of a new era of technology and science combined together. In the first chapter I present to a reader the two topics of my problem in lieu of thesis. In the second chapter I explain the idea of Brownian motion, its interpretation as a stochastic process and I find its distribution function. The next chapter illustrates the probabilistic picture of Brownian motion, where the statistical averages over trajectories are related to the probability distribution function. Chapter 4 shows how to derive the Langevin equation, introduced in chapter 1, using a Hamiltonian picture of a bath with infinite number of harmonic oscillators. The chapter 5 explains how the idea of quantum computers was developed and how step-by-step all the puzzles for the field of quantum computers were created. The next chapter, chapter 6, discus the basic quantum unit of information namely, the so called qubit and its properties. Chapter 7 is devoted to quantum logic gates, which are important for conducting logic operation in quantum computers. This chapter explains how they were developed and how they are different from classical ones. Chapter 8 is about the quantum algorithm, Shor's algorithm. Quantum algorithm in quantum computers enables one to solve problems that are hard to solve on digital computers. The last chapter contains conclusions on Brownian movement and the field of quantum computers.

•Dec 1, 2004•0 citations
In this chapter we will describe some of the early quantum algorithms. These algorithms are simple and illustrate the main ingredients behind the more useful and powerful quantum algorithms we describe in the subsequent chapters. Since quantum algorithms share some features with classical probabilistic algorithms, we will start with a comparison of the two algorithmic paradigms. Classical probabilistic algorithms were introduced in Chapter 1. In this section we will see how quantum computation can be viewed as a generalization of probabilistic computation. We begin by considering a simple probabilistic computation. Figure 6.1 illustrates the first two steps of such a computation on a register that can be in one of the four states, labelled by the integers 0, 1, 2, and 3. Initially the register is in the state 0. After the first step of the computation, the register is in the state j with probability p0,j . For example, the probability that the computation is in state 2 after the first step is p0,2. In the second step of the computation, the register goes from state j to state k with probability qj,k. For example, in the second step the computation proceeds from state 2 to state 3 with probability q2,3. Suppose we want to find the total probability that the computation ends up in state 3 after the second step. This is calculated by first determining the probability associated with each computation ‘path’ that could end up at the state 3, and then by adding the probabilities for all such paths. There are four computation paths that can leave the computation in state 3 after the first step. The computation can proceed from state 0 to state j and then from state j to state 3, for any of the four j ∊ {0, 1, 2, 3}. The probability associated with any one of these paths is obtained by multiplying the probability p0,j of the transition from state 0 to state j, with the probability qj,3 of the transition from state j to state 3.
In the last two chapters, we talked about computational complexity up till the early 1970s. Here, we'll add a new ingredient to our already simmering stew – something that was thrown in around the mid-1970s, and that now pervades complexity to such an extent that it's hard to imagine doing anything without it. This new ingredient is randomness . Certainly, if you want to study quantum computing, then you first have to understand randomized computing. I mean, quantum amplitudes only become interesting when they exhibit some behavior that classical probabilities don't : contextuality, interference, entanglement (as opposed to correlation), etc. So we can't even begin to discuss quantum mechanics without first knowing what it is that we're comparing against. Alright, so what is randomness? Well, that’s a profound philosophical question, but I’m a simpleminded person. So, you’ve got some probability p , which is a real number in the unit interval [0, 1]. That’s randomness. But wasn’t it a big achievement when Kolmogorov put probability on an axiomatic basis in the 1930s? Yes, it was! But in this chapter, we’ll only care about probability distributions over finitely many events, so all the subtle questions of integrability, measurability, and so on won’t arise. In my view, probability theory is yet another example where mathematicians immediately go to infinite-dimensional spaces, in order to solve the problem of having a nontrivial problem to solve! And that’s fine – whatever floats your boat. I’m not criticizing that. But in theoretical computer science, we’ve already got our hands full with 2n choices. We need 2ℵ0 choices like we need a hole in the head.
Although the basic ideas of quantum computation are fairly straightforward, the detailed manipulations required to extract a useful result from an entangled superposition of answers can be rather complicated. There are, however, a small number of algorithms which are simple enough to explain using only elementary methods. The best example is Deutsch's algorithm: as this only requires two qubits its properties are amenable to brute-force matrix calculations, and these calculations can be simplified using a variety of short cuts, which also give some insight into how and why the algorithm works. We will also explore the simplest case of Grover's quantum search algorithm, which is once again simple enough to be tacked by brute force. Finally we will look briefly at two methods used to stabilize quantum computers against errors. Deutsch's algorithm The invention of Deutsch's algorithm can be taken as defining the start of modern quantum computation, and it remains a key example, exhibiting many of the key properties of quantum algorithms in a particularly simple form. (Note, however, that the version of Deutsch's algorithm described here is not in fact the original but a later modification which is both more powerful and easier to understand.) Consider a binary function f from one bit to one bit, that is a function which takes in either 0 or 1 as its input and returns either 0 or 1 as its output. There are four such functions which may be conveniently labeled by their outputs as shown in Table 8.1.
The previous chapter addressed the challenge of making sense of the notion of a quantum state assignment being performed correctly without thereby acknowledging the notion of a quantum state a quantum system ‘is in’. The present chapter discusses what interpretation of quantum probabilities goes best with the account that I have called the ‘Rule Perspective’ and started to develop in the previous chapter. The first section considers what quantum probabilities should be taken to be probabilities of in the Rule Perspective; the second investigates what philosophical interpretation of probabilities applies best to quantum probabilities thus conceived. The third section considers two objections to the resulting account of quantum probabilities. 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.
With the increasing accessibility of quantum computers to the wider population, there is a growing demand for the education and training of a group of quantum programmers. This cohort predominantly consists of individuals who have primarily focused on the development of classical computer programs throughout their professional careers. Although existing quantum computers currently possess fewer than 100 qubits, it is widely anticipated that the quantum computing hardware will experience significant advancements in terms of qubit quantity, quality, and connectivity. The objective of this review is to elucidate the fundamental principles of quantum programming, which diverge significantly from classical programming. This will be achieved through the utilization of concise algebraic expressions, allowing for an optional comprehension of the captivating underlying principles of quantum mechanics. This paper provides an overview of quantum computing algorithms and their practical implementation on physical quantum hardware. In this study, we undertake a comprehensive examination of various quantum algorithms, with the objective of providing concise and self-contained descriptions for each. In this study, we demonstrate the practical implementation of the aforementioned algorithms on IBM's quantum computer. For each algorithm, we thoroughly analyze and compare the outcomes obtained from the implementation on the quantum computer with those obtained from the simulator. This analysis focuses on identifying and discussing any disparities that arise between the results obtained from the simulator and the actual hardware runs. This article serves as an introduction to quantum algorithms for computer scientists, physicists, and engineers, offering a comprehensive guide for their practical implementation.
This problem in lieu of thesis is a discussion of two topics: Brownian movement and quantum computers. Brownian movement is a physical phenomenon in which the particle velocity is constantly undergoing random fluctuations. Chapters 2, 3 and 4, describe Brownian motion from three different perspectives. The next four chapters are devoted to the subject of quantum computers, which are the signal of a new era of technology and science combined together. In the first chapter I present to a reader the two topics of my problem in lieu of thesis. In the second chapter I explain the idea of Brownian motion, its interpretation as a stochastic process and I find its distribution function. The next chapter illustrates the probabilistic picture of Brownian motion, where the statistical averages over trajectories are related to the probability distribution function. Chapter 4 shows how to derive the Langevin equation, introduced in chapter 1, using a Hamiltonian picture of a bath with infinite number of harmonic oscillators. The chapter 5 explains how the idea of quantum computers was developed and how step-by-step all the puzzles for the field of quantum computers were created. The next chapter, chapter 6, discus the basic quantum unit of information namely, the so called qubit and its properties. Chapter 7 is devoted to quantum logic gates, which are important for conducting logic operation in quantum computers. This chapter explains how they were developed and how they are different from classical ones. Chapter 8 is about the quantum algorithm, Shor's algorithm. Quantum algorithm in quantum computers enables one to solve problems that are hard to solve on digital computers. The last chapter contains conclusions on Brownian movement and the field of quantum computers.