Grand Unification of Quantum Algorithms

Quantum algorithms offer significant speed-ups 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 have recently been 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 the QSVT [Gilyén et al., 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 the QSVT naturally emerges. Paralleling GSLW’19, we then employ the 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 the QSVT is a single framework comprising the three major quantum algorithms, suggesting a grand unification of quantum algorithms.

Popular Summary

Quantum computers can provide speed-ups over classical computers for a variety of problems, the most historically prominent of which are factoring large numbers, searching unstructured databases, and simulating quantum systems. At face value, these problems appear to share little structure and speed-ups attained by the corresponding quantum algorithms seem to have disparate origins. Recent work, however, reveals that all of these algorithms are actually instances of a single unifying algorithm: the quantum singular-value transformation (QSVT). This single algorithm provides intuitive solutions to the factoring, search, and simulation problems, suggesting a ”grand unification of quantum algorithms,” as presented in this tutorial.

The QSVT was introduced by Gilyén et al. in 2019 and enables one to perform polynomial transformations of the singular values of a linear operator embedded within a unitary matrix. Even in light of this broad capability, it is remarkable that the QSVT can subsume such a wide spectrum of quantum algorithms. In fact, the QSVT provides a series of well-defined dials that can be adjusted to smoothly transform from one algorithm to the next. This tutorial seeks to convey and illustrate the intuition behind the QSVT, including what polynomials have been found for useful transformations of singular values and how to find the dial settings needed for new polynomial transforms. This intuition and transform flexibility will likely be of considerable interest to those who wish to extend known quantum algorithms to novel settings and those seeking new quantum algorithms.

Figure 1

The transition probabilities for $|0⟩\to |0⟩$ after the application of $\exp (i\theta X/2)$ (uniform dashed) and the QSP sequence for the BB1 protocol (dotted dashed). The latter transition probability is seen to be near one for a wider range of $\theta$.

Figure 2

An illustration of amplitude amplification, where one desires to prepare the state $|A_0⟩$ (here, the north pole of some Bloch sphere) obliviously to this state, given only $|B_0⟩$, an operator $U$ the $⟨A_0|U|B_0⟩=a$ component of which is nonzero, and the ability to rotate about the states $|B_0⟩$ (blue) and $|A_0⟩$ (black) through chosen angles. The standard Grover iterate can be recovered in this model if one desires, by producing a simple rotation by $\theta =2{\cos }^{-1}\left(\sqrt{1-a^2}\right)=2{\sin }^{-1}a$ (red) toward $|A_0⟩$.

Figure 3

The circuit used to realize the projector-controlled phase shift ${\mathrm{\Pi }}_{\varphi }$, also termed the “phased iterate,” in analogy to the bare $\exp (i\varphi Z)$ operation used in QSP, used as the signal-processing rotation operator.

Figure 4

A simple block-encoding quantum circuit, showing how such a block encoding of a unitary $A$ is notated. Observe that the empty circle on the control qubit (top line) indicates a $|0⟩$ control, whereas a filled-in circle would correspond to a $|1⟩$ control.

Figure 5

The construction of $|1⟩$-controlled-$A$ (for $A$ a single-qubit operator) given access to $|\lambda ⟩$ a $(+1)$ eigenvector of $A$, $|\xi ⟩$ the control qubit, and $|\psi ⟩$ the target state. Note that $A$ may in general act on a large Hilbert space, in which case the controlled-swap operator is suitably generalized. The swaps can be made $|0⟩$ controlled to emulate Fig. 4. We note that this is a similar construction to the circuits employed in Ref. [40] for matrix element measurement.

Figure 6

An illustration of $\mathrm{\Theta }(x)$ (solid) and its polynomial approximation, $P_{ϵ,\mathrm{\Delta }}^{\mathrm{\Theta }}(x)$ (dashed). Note how $P_{ϵ,\mathrm{\Delta }}^{\mathrm{\Theta }}(x)$ stays within $ϵ$ of the sign function outside of the region $(\mathrm{\Delta }/2,\mathrm{\Delta }/2)$, while deviating from $\mathrm{\Theta }(x)$ within this region. The shifted version of this function is constructed in much the same way.

Figure 7

A simple circuit for block encoding $\frac{1}{2}(\mathcal{H}/\alpha +I)$, the projectors for which are, following QSVT conventions, $|0⟩⟨0|\otimes \mathrm{\Pi }$ and $|0⟩⟨0|\otimes \tilde{\mathrm{\Pi }}$.

Figure 8

The circuit that, upon measuring the auxiliary qubit, can be used to solve the eigenvalue threshold problem with high probability as in Algorithm 33.

Figure 9

The quantum circuit used to evaluate ${\phi }_{j+1}$ at each iteration of the phase estimation-by-QSVT procedure.

Figure 10

A quantum circuit that achieves a unitary block encoding of $A_j(\theta )$, which we denote by $W_j(\theta )$ and incorporate into Algorithm 34.

Figure 11

An abstract overview of the circuit performing phase estimation through the QSVT (Algorithm 34). The double lines indicate that measurement results are fed forward (via the parameter $\theta$) to all future controlled QSVT operations, where this adaptive process is unpacked in Fig. 12. In essence, the circuit systematically computes the least significant bit of an unknown quantum phase, adaptively bit shifts this phase, and repeats. Note the similarity of this operation to the inverse quantum Fourier transform, a connection on which we elaborate in Sec. 5d.

Figure 12

A quantum circuit for performing phase estimation using the QSVT, following Algorithm 34. The dotted controlled operators, denoted by $W_j$ at step $j$, represent a composite gadget (unwrapped in the inset block) that depends on the states of $(n-j-2)$ controlling qubits above it. Here, controlled-${\varphi }_j$ gates represent controlled-$Z$ rotations by angle ${\varphi }_j$. Additionally, this figure depicts only the even-$d$ case of Theorem 4. This circuit terminates by measuring all auxiliary qubits in the computational basis. Also depicted is an expanded view of a subroutine in the circuit depicted for phase estimation. Note that the $W_j$ operator is the unitary that block encodes $A_j$, as depicted in Fig. 10. Note also that each $R_{\ell }$ operator is defined as in Eq. (73). The controlled $R_{\ell }$ operations serve to adaptively zero out the currently estimated phase to the $(n-j-2)\mathrm{th}$ bit.

Figure 13

The simplification of QSP phase control for the case when the block-encoded operator has an accessible control qubit.

Figure 14

An illustration of three-qubit quantum phase estimation using QSP.

Figure 15

An illustration of three-qubit quantum phase estimation using QSP, in the simplified case when $d=1$.

Figure 16

An illustration of three-qubit quantum phase estimation using QSP, in the simplified case when $d=1$, with gates slid along wires to highlight the three-qubit inverse QFT circuit which emerges (gates in dotted rectangular box).

Figure 17

One quantum circuit that can be used to construct the time evolution operator $\cos (\mathcal{H}t)-i\sin (\mathcal{H}t)=e^{-i\mathcal{H}t}$ and apply it to $|{\psi }_0⟩$, for use in Hamiltonian simulation as described in Algorithm 35. Note that the correct evolution of the input state $|{\psi }_0⟩$ is achieved only upon postselection of the auxiliary qubit in the $|0⟩$ state. One can achieve this with either repetition or fixed-point amplitude amplification, similar to projecting into the desired block of the QSVT sequence operator as discussed at the end of Sec. 5d.

Figure 18

A depiction of a finite-sized $\mathrm{\Delta }$ region and the resulting values of $\mathrm{\Theta }$. The shaded regions indicate where the application of the QSVT sequence returns an indeterminate measurement result (equivalently, where the sign function is poorly approximated).

Figure 19

A sketch of (a) $P_{\frac{1}{2}ϵ,2\kappa }^{1/x}(x)$, (b) $P_{{ϵ}^{\prime },\kappa }^{\mathrm{rect}}(x)$, and (c) $P_{ϵ,\kappa }^{\mathrm{MI}}(x)$ for $\kappa =2.5$. The resulting polynomial, $P_{ϵ,\kappa }^{\mathrm{MI}}(x)$, is a degree-$77$ approximation to the inverse function.

Figure 20

The transition probability using the polynomial for oblivious amplification for $d=10$ and $\delta =0.5$.

Figure 21

The response function for the polynomial approximation to the sign function with $d=19$ and $k=10$.

Figure 22

The response function for the polynomial approximation to the inverse function with $\kappa =3$ and $ϵ=0.3$.

Figure 23

The response function for the polynomial approximation to the cosine function with $t=5$ and $ϵ=0.1$.

Figure 24

The response function for the polynomial approximation to the sine function with $t=5$ and $ϵ=0.1$.

Figure 25

The response function for the polynomial approximation to the threshold function with $k=10$ and $d=18$.

Figure 26

The response function for the linear amplification polynomial with $\mathrm{\Gamma }=0.25$ and $d=19$.

Figure 27

The response function for the real phase estimation polynomial with $\mathrm{\Delta }=10$ and $d=18$ in the $(W_x,S_z,⟨+|\cdot |+⟩)$-QSP convention.

Figure 28

The response function for a degree-$18$ polynomial approximation to the phase estimation function in the $(W_x,S_z,⟨0|\cdot |0⟩)$ convention.

Figure 29

The response function for the polynomial approximation to the eigenstate filtering function with $\delta =0.3$ and $d=30$.

Figure 30

The response function for the polynomial approximation to the Gibbs distribution for $a>0$ with $\beta =3.5$ using a degree-$(d=20)$ polynomial. The response is scaled to maximize $\mathrm{Poly}(a)$. Note that the approximation deviates from the target near $a=0$, as the symmetrized version of the Gibbs distribution is nonanalytic about that point.

Figure 31

The response function for the polynomial approximation to the ReLU function with $\delta =0.6$ and $\mathrm{\Delta }=15$.

Figure 32

Unstructured Search by QSVT.

Figure 33

The Eigenvalue Threshold Problem by the QSVT.

Figure 34

Phase Estimation by QSVT.

Figure 35

Hamiltonian Simulation by QSVT.

Figure 36

Matrix Inversion by QSVT.