Unification of Computation

"A Grand Unification of Quantum Algorithms"

Published by John M. Martyn, Zane M. Rossi, Andrew K. Tan, Isaac L. Chuang (MIT), 12th May 2021

Unification of Computation

Both classical and quantum computation involves a basic set of building blocks, where algorithms can be implemented to process information. In classical computation, the basic blocks are typically Boolean circuit components, while in quantum computation, the quantum circuits are realized by unitary operations on one or multiple quantum systems, for example two-state systems (qubits). A significant difference between quantum and classical algorithms is that the former performs unitary transformations that are invertible in contrast to the classical Boolean functions, which are mostly irreversible. Because of that distinction, many researchers have proposed methods to make such Boolean functions reversible. This can be achieved by first embedding the desired function into a reversible Boolean circuit and then constructing a quantum circuit realizing this invertible transform. A popular example of this construction is the well-known Shor's algorithm. Nevertheless, reversibility is not a requirement for the unification of quantum and classical algorithms. Actually, there has already been demonstrated by quantum algorithms in Hamiltonian simulation and quantum search (Grover's algorithm) that quantum speedup can be achieved without reversible Boolean functions.

The latest consensus on unification lies in the realization of irreversible, non-linear functions given the fact that the dynamical behavior of a subsystem of a quantum system can be non-unitary. Recently, a number of frameworks have been proposed to carry out such quantum subsystem transforms. One such approach is Quantum Signal Processing (QSP), which involves interleaving of two kinds of single qubit rotations and can be applied in generalized problems based on composite pulse sequences. Another promising approach is Quantum Singular Value Transformations (QSVT), which is a generalization of QSP. In QSVT, the process involves embedding a non-unitary linear operator (that governs a sub-system which can be in a mixed state) in a larger unitary operator and efficiently applies a polynomial transform to its singular values, thereby providing one lens through which one can analyze the source of quantum advantage.

In this work, the authors present an analysis of these modern approaches to quantum search, factoring, and simulation, focusing on unifying these three central quantum algorithms, in a review/overview style. The objective is to develop a framework based on QSP, establish quantum eigenvalue transformations and eventually implement QSVT for a range of problems such as search problem and phase estimation, eigenvalue threshold problem, amplitude amplification, matrix inversion and other Hamiltonian simulations.

The examples in this work show that multi-qubit problems can be simplified by identifying qubit-like subsystems, which can then be solved using QSP. While utilizing concepts like qubitization, the theorems of QSVT can be generalized for application in Amplitude Amplification and Search problem by accomplishing a polynomial transform of one specific amplitude. This polynomial transform can actually be performed over an entire vector space, not just a one-dimensional matrix element and hence can assist in quantum eigenvalue transforms. Furthermore, it is shown that QSP sequences can be used to polynomially transform all the singular values of a matrix which has been encoded into a block of a unitary matrix. The polynomial runtime shown for these algorithms suggests that QRAM based QSVT can attain a significant polynomial speedup, but achieving exponential speedup over classical algorithms is not always possible. Since QRAM based architectures require resources that grow exponentially with the numbers of the qubits, while more efficient architectures are an active area of research, it is wise to explore the alternative ways of block-encoding matrices.

Such demonstrations provide significant insights on how most of the known quantum algorithms can be constructed by simply adjusting the parameters of QSVT and thus utilizing QSVT for grand unification of quantum algorithms. So far, QSVT has shown great promise in generalizing QSP and applying a polynomial transformation to the singular values of a linear operator. Apart from the problems mentioned earlier, further applications of QSVT have been realized in the areas of quantum machine learning, quantum walks, fractional query implementation, and Gibbs state preparation. However, popular quantum algorithms such as variational algorithms like the variational quantum eigensolver or the quantum approximate optimization algorithm have not yet been constructed from QSVT-based subroutines. In the near future, it would be interesting to explore if the scope of QSVT can encompass these hybrid quantum algorithms. Lastly, an inherent goal of this work is the realization of the applications of QSVT in creating novel algorithms or extending previously known algorithms within novel noise settings. Thus, utilizing a flexible framework like QSVT can potentially bring us closer to the unification of quantum and classical algorithms.