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

Quantum computation

This chapter introduces the basic principles of quantum computation. We shall adhere to the quantum circuit model of computation, with which it is easy to work and which is close to physical implementations. We shall not discuss the more abstract quantum Turing machine model, which, however, has been shown to be equivalent to the circuit model. The elementary unit of quantum information and the basic building block of quantum computation is the qubit, a two-level quantum system that can be prepared, manipulated and measured in a controlled way. A quantum computer can be seen as a collection of n qubits and therefore its wave function resides in a 2 n -dimensional complex Hilbert space. As far as coupling to the environment may be neglected, its evolution in time is unitary and governed by the Schrödinger equation. A quantum computation is composed of three basic steps: preparation of the input state, implementation of the desired unitary transformation acting on this state and measurement of the output state. The output of the measurement process is inherently probabilistic and the probabilities of the different possible outputs are set by the basic postulates of quantum mechanics. Therefore, in a quantum algorithm we must, in general, repeat several times the algorithm to obtain the correct solution of our problem with probability as close to one as desired. In this sense, quantum algorithms are analogous to classical probabilistic algorithms. However, the superposition principle and quantum entanglement open up new possibilities for computation. Quantum computers are potentially more powerful than classical (deterministic or probabilistic) computers due to quantum interference and entanglement. We show that, analogously to classical computation, there exists a small set of gates that are universal, that is, any unitary transformation can be decomposed into a sequence of these gates. We then discuss the implementation of the basic Boolean functions and arithmetic operations on a quantum computer.

WORLD SCIENTIFIC eBooks•Dec 1, 2018•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

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

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

Mathematical Ideas in Quantum Computing

Ruge Lin

[eng] This thesis can be classified into the research field of quantum algorithms. A typical paper in this field usually focuses on what kind of things we can do with a quantum computer, whether they are useful or advantageous compared to classical computers, and how we can do it more efficiently. Since the ideal fault-tolerant large-scale quantum computer will not be available soon, many papers focus on noisy intermediate-scale quantum (NISQ) devices, how to characterize them through various benchmarking protocols, and how to make them useful through error mitigation or variational algorithms. Most probably, anyone who ends up opening this thesis is already an expert in certain topics, but they can still find some “out of the box" elements in one chapter or another. The results presented in the thesis might not be directly useful, but hopefully, these elements can provide insights and inspiration. The main body of this thesis is organized into six independent chapters. Each chapter is complete and self-consistent. All these chapters share a similarity: They provide some mathematical ideas of quantum computing in one aspect or another. Since part of the research is conducted in collaboration, the pronoun “we" is used throughout the work. In the first chapter, we focus on actions that transform quantum states into quantum states. We begin with a more theoretical approach. These actions naturally process a group structure. And we ask, under what conditions is this group finite? Given an arbitrary finite group, how can we construct these actions? How can these actions be useful to quantum computing? The set of these actions is named "Quantum representation of finite group," and answers to these questions are provided in the main text. Then, in the second chapter, we switch to a more practical scenario. The inspiration came from a problem that appeared in post-quantum cryptography, the dihedral coset problem, which uses quantum algorithms to recover a secret of the group hidden in quantum states. We simplified this problem and designed an interactive protocol for verifying the computational capacity of a quantum device. Holding a small quantum computer, the verifier prepares quantum state samples that encode a secret and sends them one by one to the prover via a one-way quantum channel. The prover then uses his quantum device to recover the secret with a certain probability. The device’s capacity is then reflected in the accuracy of the solution. This interactive protocol can be used locally on a single device as a benchmarking protocol. In the third chapter, we explore quantum entanglement. We present a new method for visualizing entanglement during a quantum evolution, such as the execution of a quantum algorithm. We name this method "Entanglement trajectory" and show that it can provide a "fingerprint" for each quantum process. We determine the boundaries of these trajectories with Random Matrix Theory and use different examples and entanglement measurements to show that this trajectory has an intrinsic quantum meaning and provides more information about the system. In the fourth chapter, we elaborate on the entanglement presented in a succession of numbers. First, we give a numerical and analytical description of the average entropy of succession, which can provide a standard for studying any successions. Then, we simulate the example of k-almost primes and its unions for different system sizes and explore their particular feature. In the fifth chapter, we will show three different methods of using a quantum annealer to solve Multivariate Quadratic (MQ) problems. In the sixth chapter, we present a data encoder in the fixed Hamming weight subspace, which is parameter-optimal and can be extended to a sparse and binary data encoder. We will give a small summary for each chapter. At the end of this thesis, we will provide an overall conclusion for our readers as “take-home messages".

•May 15, 2025•0 citations

Lecture Notes on Quantum Algorithms

Muhammad Faryad

These notes begin in Chapter 1 with a review of linear algebra and the postulates of quantum mechanics, leading to an explanation of single- and multi-qubit gates. Chapter 2 explores the challenge of constructing arbitrary quantum states from given initial states, and introduces circuits for building oracles. Chapter 3 presents foundational algorithms such as entanglement creation, quantum teleportation, Deutsch-Jozsa, Bernstein-Vazirani, and Simon's algorithm. Chapters 4 and 5 cover algorithms based on the quantum Fourier transform, including phase estimation, period finding, factoring, and logarithm computation. These chapters also include complexity analysis and detailed quantum circuits suitable for implementation in code. Chapter 6 introduces Grover's algorithm for quantum search and amplitude amplification, including its realization via Hamiltonian simulation and a method for derandomization. Chapter 7 discusses basic techniques for Hamiltonian simulation, such as Lie-Trotter decomposition, sparse Hamiltonians, and the linear combination of unitaries. It also provides example circuits for simulating Hamiltonians expressed as linear combinations of Pauli operators. Chapter 8 introduces variational quantum algorithms, and Chapter 9 presents an algorithm for simulating fermionic many-particle systems, with an emphasis on molecular Hamiltonians. It also outlines the key transformations needed to map a molecular Hamiltonian to a form suitable for simulation on a quantum computer.

arXiv:2507.11565•Jul 14, 2025•1 citation
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.
This chapter introduces the basic principles of quantum computation. We shall adhere to the quantum circuit model of computation, with which it is easy to work and which is close to physical implementations. We shall not discuss the more abstract quantum Turing machine model, which, however, has been shown to be equivalent to the circuit model. The elementary unit of quantum information and the basic building block of quantum computation is the qubit, a two-level quantum system that can be prepared, manipulated and measured in a controlled way. A quantum computer can be seen as a collection of n qubits and therefore its wave function resides in a 2 n -dimensional complex Hilbert space. As far as coupling to the environment may be neglected, its evolution in time is unitary and governed by the Schrödinger equation. A quantum computation is composed of three basic steps: preparation of the input state, implementation of the desired unitary transformation acting on this state and measurement of the output state. The output of the measurement process is inherently probabilistic and the probabilities of the different possible outputs are set by the basic postulates of quantum mechanics. Therefore, in a quantum algorithm we must, in general, repeat several times the algorithm to obtain the correct solution of our problem with probability as close to one as desired. In this sense, quantum algorithms are analogous to classical probabilistic algorithms. However, the superposition principle and quantum entanglement open up new possibilities for computation. Quantum computers are potentially more powerful than classical (deterministic or probabilistic) computers due to quantum interference and entanglement. We show that, analogously to classical computation, there exists a small set of gates that are universal, that is, any unitary transformation can be decomposed into a sequence of these gates. We then discuss the implementation of the basic Boolean functions and arithmetic operations on a quantum computer.
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.
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.
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.
[eng] This thesis can be classified into the research field of quantum algorithms. A typical paper in this field usually focuses on what kind of things we can do with a quantum computer, whether they are useful or advantageous compared to classical computers, and how we can do it more efficiently. Since the ideal fault-tolerant large-scale quantum computer will not be available soon, many papers focus on noisy intermediate-scale quantum (NISQ) devices, how to characterize them through various benchmarking protocols, and how to make them useful through error mitigation or variational algorithms. Most probably, anyone who ends up opening this thesis is already an expert in certain topics, but they can still find some “out of the box" elements in one chapter or another. The results presented in the thesis might not be directly useful, but hopefully, these elements can provide insights and inspiration. The main body of this thesis is organized into six independent chapters. Each chapter is complete and self-consistent. All these chapters share a similarity: They provide some mathematical ideas of quantum computing in one aspect or another. Since part of the research is conducted in collaboration, the pronoun “we" is used throughout the work. In the first chapter, we focus on actions that transform quantum states into quantum states. We begin with a more theoretical approach. These actions naturally process a group structure. And we ask, under what conditions is this group finite? Given an arbitrary finite group, how can we construct these actions? How can these actions be useful to quantum computing? The set of these actions is named "Quantum representation of finite group," and answers to these questions are provided in the main text. Then, in the second chapter, we switch to a more practical scenario. The inspiration came from a problem that appeared in post-quantum cryptography, the dihedral coset problem, which uses quantum algorithms to recover a secret of the group hidden in quantum states. We simplified this problem and designed an interactive protocol for verifying the computational capacity of a quantum device. Holding a small quantum computer, the verifier prepares quantum state samples that encode a secret and sends them one by one to the prover via a one-way quantum channel. The prover then uses his quantum device to recover the secret with a certain probability. The device’s capacity is then reflected in the accuracy of the solution. This interactive protocol can be used locally on a single device as a benchmarking protocol. In the third chapter, we explore quantum entanglement. We present a new method for visualizing entanglement during a quantum evolution, such as the execution of a quantum algorithm. We name this method "Entanglement trajectory" and show that it can provide a "fingerprint" for each quantum process. We determine the boundaries of these trajectories with Random Matrix Theory and use different examples and entanglement measurements to show that this trajectory has an intrinsic quantum meaning and provides more information about the system. In the fourth chapter, we elaborate on the entanglement presented in a succession of numbers. First, we give a numerical and analytical description of the average entropy of succession, which can provide a standard for studying any successions. Then, we simulate the example of k-almost primes and its unions for different system sizes and explore their particular feature. In the fifth chapter, we will show three different methods of using a quantum annealer to solve Multivariate Quadratic (MQ) problems. In the sixth chapter, we present a data encoder in the fixed Hamming weight subspace, which is parameter-optimal and can be extended to a sparse and binary data encoder. We will give a small summary for each chapter. At the end of this thesis, we will provide an overall conclusion for our readers as “take-home messages".
These notes begin in Chapter 1 with a review of linear algebra and the postulates of quantum mechanics, leading to an explanation of single- and multi-qubit gates. Chapter 2 explores the challenge of constructing arbitrary quantum states from given initial states, and introduces circuits for building oracles. Chapter 3 presents foundational algorithms such as entanglement creation, quantum teleportation, Deutsch-Jozsa, Bernstein-Vazirani, and Simon's algorithm. Chapters 4 and 5 cover algorithms based on the quantum Fourier transform, including phase estimation, period finding, factoring, and logarithm computation. These chapters also include complexity analysis and detailed quantum circuits suitable for implementation in code. Chapter 6 introduces Grover's algorithm for quantum search and amplitude amplification, including its realization via Hamiltonian simulation and a method for derandomization. Chapter 7 discusses basic techniques for Hamiltonian simulation, such as Lie-Trotter decomposition, sparse Hamiltonians, and the linear combination of unitaries. It also provides example circuits for simulating Hamiltonians expressed as linear combinations of Pauli operators. Chapter 8 introduces variational quantum algorithms, and Chapter 9 presents an algorithm for simulating fermionic many-particle systems, with an emphasis on molecular Hamiltonians. It also outlines the key transformations needed to map a molecular Hamiltonian to a form suitable for simulation on a quantum computer.