Cambridge University Press eBooks

Complex Algorithms

Robert Hundt

Published Feb 28, 2022• 0 citations

Abstract

This chapter details many of the fundamental quantum algorithms with full mathematical derivations and code. It discusses the quantum Fourier transform (QFT), arithmetic in the Fourier domain quantum phase estimation,Shor’s famous factorization algorithm and its quantum order-finding component, Grover’s search algorithm, amplitude amplification, and quantum counting, as well as quantum random walks. From the field of quantum simulation, the chapter discusses the variational quantum eigensolver, measurement in the Pauli bases, the quantum approximate optimization algorithm (QAOA), the NP-complete graph Max-Cut problem, and the related Subset Sum problem. The chapter concludes with an in-depth discussion of the elegant Solovay–Kitaev algorithm for gate approximation.

DOI: 10.1017/9781009099974.008

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

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

THEORETICAL FRAMEWORK AND ALGORITHMIC IMPLEMENTATION OF THE QUANTUM FOURIER TRANSFORM AND PHASE ESTIMATION

Medak Srinivas

The Quantum Fourier Transform (QFT)andQuantumPhaseEstimation (QPE)are twofundamental algorithmic frameworks in quantum computation, and they provide the mathematical basis of many exponential-speedup quan tum algorithms, such as Shor’s factoring algorithm and quantum simulation techniques. In this work we present a detailed theoretical and computational study of the Quantum Fourier Transform and its integration in the Quan tum Phase Estimation. The discussion begins with the linear algebraic structure of the Hilbert spaces, the unitary transformations, and the complex vector representations that enable quantum interference and superposition. The QFT is studied as the unitary transform of computational basis states in the amplitudes in the frequency domain by phase rotations and tensor-product decompositions. The efficient circuit implementation in terms of Hadamard and controlled phase gates of this transform is discussed. The advantage of the transform in terms of polynomial time complexity over the classical discrete Fourier transform in some quantum scenarios is discussed.The QFT is implemented and the Quantum Phase Estimation algorithm is proposed to obtain the eigenphase information of the unitary operators. In the report the mathematical representation of QPE is derived by using the controlled unitary evolution, the inverse Fourier transforms and the measurement theory in finite dimensional Hilbert spaces. We discuss the probabilistic interpretation of phase extraction in detail and the convergence properties of the bi nary phase approximation. We also discuss the relation of QPE to eigenvalue problems in quantum mechanics and its applications to Hamiltonian simulation, quantum chemistry, cryptography, and hidden subgroup prob lems.Implementation aspects of these algorithms are studied using quantum circuit representations and oracle based computation models. We also discuss error sensitivity, qubit precision requirements, decoherence limita tions and practical constraints of Noisy Intermediate-Scale Quantum (NISQ) hardware. The work synthesizes the mathematical foundations, computational complexity analysis and physical realizations of the QFT and the QPE, demonstrating how the Fourier-based quantum transformations provide the essential mechanism underlying modern quantum algorithmic speedups and scalable quantum information processing.

Iterative International Publishers eBooksMay 1, 20260 citations

Algorithms Using Quantum Fourier Transform

Robert Hundt

The quantum Fourier transform is another fundamental quantum algorithm. The section begins with a simple phase-kick circuit and expands to quantum phase estimation before detailing the quantum Fourier transform itself. A short section on arithmetic in the quantum domain introduces techniques that are used in a final detailed section on Shor’s famous algorithm for number factorization.

Cambridge University Press eBooksNov 20, 20250 citations

Optimization Algorithms

Robert Hundt

This section details several optimization algorithms. The variational quantum eigensolver is presented, which allows finding a minimum eigenvalue for a given Hamiltonian. This section also includes extensive notes on performing measurements in arbitrary bases. After a brief introduction of the quantum approximate optimization algorithm, the chapter further discusses the quantum maximum cut algorithm and the quantum subset sum algorithm in great detail.

Cambridge University Press eBooksNov 20, 20250 citations

Algorithms Using Amplitude Amplification

Robert Hundt

This chapter discusses Grover’s fundamental algorithm, which enables searching over a domain of N elements with complexity of the square root of N. Several derivative algorithms and applications are being discussed, including amplitude amplification, amplitude estimation, quantum counting, Boolean satisfiability, graph coloring, and quantum mean, medium, and minimum finding.

Cambridge University Press eBooksNov 20, 20250 citations