Grand Unification of Quantum Algorithms

By J. Martyn, Zane M. Rossi, Andrew K. Tan, Isaac L. Chuang. PRX Quantum, 2021

455 citations recorded by the source corpus.

Quantum algorithms offer significant speedups over their classical counterparts for a variety of problems. The strongest arguments for this advantage are borne by algorithms for quantum search, quantum phase estimation, and Hamiltonian simulation, which appear as subroutines for large families of composite quantum algorithms. A number of these quantum algorithms were recently tied together by a novel technique known as the quantum singular value transformation (QSVT), which enables one to perform a polynomial transformation of the singular values of a linear operator embedded in a unitary matrix. In the seminal GSLW'19 paper on QSVT [Gily\'en, Su, Low, and Wiebe, ACM STOC 2019], many algorithms are encompassed, including amplitude amplification, methods for the quantum linear systems problem, and quantum simulation. Here, we provide a pedagogical tutorial through these developments, first illustrating how quantum signal processing may be generalized to the quantum eigenvalue transform, from which QSVT naturally emerges. Paralleling GSLW'19, we then employ QSVT to construct intuitive quantum algorithms for search, phase estimation, and Hamiltonian simulation, and also showcase algorithms for the eigenvalue threshold problem and matrix inversion. This overview illustrates how QSVT is a single framework comprising the three major quantum algorithms, thus suggesting a grand unification of quantum algorithms.

Subfields: Artificial Intelligence, Hardware and Architecture

View Paper: https://www.semanticscholar.org/paper/5e923adaaa94deb6b039c243f2dd4ea7854258a6

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

1. Danial Motlagh
2. Nathan Wiebe
3. Guang Hao Low
4. Maria Schuld

In Hardware and Architecture

1. Danial Motlagh
2. Nathan Wiebe
3. Guang Hao Low

Citations in the corpus

• Generalized Quantum Signal Processing (2023, background): “…insight: the majority of prominent quantum algorithms, such as Hamiltonian simulation [1–4], quantum search [5–7], factoring [8], and quantum walks [7, 9], can be fundamentally reduced to the central task of implementing a matrix function of a Hamiltonian, f ( H ), this was shown in [10, 11].”