Cambridge University Press eBooks

Simple Algorithms

Robert Hundt

Published Feb 28, 2022• 0 citations

Abstract

Armed with the knowledge and infrastructure from the previous chapters, the first set of quantum algorithms is introduced. The algorithms in this chapter are typically shorter and require less preparation than those in later chapters. Additionally, the mathematical derivations are developed with great detail. The chapter starts with the simplest possible algorithm: a quantum random number generator. This is followed by several gate equivalences, a classical full adder implemented with quantum gates, and the Swap Test to measure similarity between states. Two algorithms that utilize entanglement come next: quantum teleportation and superdense coding. After this, three so-called oracle algorithms are discussed,the Bernstein–Vazirani algorithm, Deutsch’s algorithm, and Deutsch–Jozsa’s algorithm. These are the first quantum algorithms that perform better than their classical counterparts. Oracle construction itself is discussed at great length.

DOI: 10.1017/9781009099974.005

Related papers

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.11565Jul 14, 20250 citations

Algorithms Exploiting Entanglement

Robert Hundt

This chapter presents the first real algorithm – a quantum "Hello World" program, which is just a simple random number generator. The chapter then details quantum teleportation, superdense coding, and entanglement swapping algorithms, as well as the CHSH game. This game is a simplified version of the Bell inequalities, which established that quantum entanglement cannot be explained by classical theories assuming hidden states

Cambridge University Press eBooksNov 20, 20250 citations

Black-Box Algorithms

Robert Hundt

The algorithms presented in this chapter were the first to establish a query complexity advantage for quantum algorithms. The list of algorithms includes the Bernstein-Vazirani algorithm, Deutsch’s algorithm, and Deutsch-Jozsa algorithm. Quantum oracles and their construction are being introduced.

Cambridge University Press eBooksNov 20, 20250 citations

Quantum Advantage with Deutsch-Jozsa, Bernstein-Vazirani, and Simon’s Algorithms

Vladimir Silva

In this chapter, we study three algorithms of little practical use but important because they were the first to show that quantum computers can solve problems significantly faster than classical ones. Consider the time complexities O(n) for the algorithms: classical vs. quantum in Table 9-1 (where n is the size of the input).

Apress eBooksDec 18, 20230 citations

Seminal Quantum Algorithms Description and Programming

Ahcène Bounceur, Mohammad Ali A. Hammoudeh, Bamidele Adebisi +1 more

This chapter expounds on quantum algorithms, outlining fundamental concepts and their practical implementations. It starts with an explanation of core quantum principles such as functions and oracles. Then, it introduces Qiskit, an IBM-developed open-source quantum computing software framework. The discussion integrates theoretical underpinnings with empirical demonstrations, providing readers with an understanding of quantum programming intricacies. Through the utilisation of practical examples implemented in Qiskit, readers are given firsthand exposure, thereby reinforcing their comprehension of the subject matter. The overarching objective is to equip readers with a comprehensive knowledge base, thereby fostering proficiency in navigating the theoretical underpinnings and practical applications of quantum computing. To this end, the chapter ends with an examination of three seminal quantum algorithms: Deutsch, Deutsch-Jozsa, and Bernstein-Vazirani. These algorithms serve as keystones in the quantum computing domain, illustrating the efficacy and adaptability of quantum computation in resolving diverse computational problems.

CRC Press eBooksDec 9, 20240 citations

Quantum Computing for Programmers

Robert Hundt

This introduction to quantum computing from a classical programmer's perspective is meant for students and practitioners alike. Over 25 fundamental algorithms are explained with full mathematical derivations and classical code for simulation, using an open-source code base developed from the ground up in Python and C++. After presenting the basics of quantum computing, the author focuses on algorithms and the infrastructure to simulate them efficiently, beginning with quantum teleportation, superdense coding, and Deutsch-Jozsa. Coverage of advanced algorithms includes the quantum supremacy experiment, quantum Fourier transform, phase estimation, Shor's algorithm, Grover's algorithm with derivatives, quantum random walks, and the Solovay–Kitaev algorithm for gate approximation. Quantum simulation is explored with the variational quantum eigensolver, quantum approximate optimization, and the Max-Cut and Subset-Sum algorithms. The book also discusses issues around programmer productivity, quantum noise, error correction, and challenges for quantum programming languages, compilers, and tools, with a final section on compiler techniques for transpilation.

Cambridge University Press eBooksFeb 28, 20225 citations