UC Berkeley

Recent years have seen rapid progress in the field of quantum algorithms for linear algebra problems. These algorithms can solve important problems in quantum chemistry, condensed matter physics, and quantum field theory simulation, with potentially exponential speedup compared to classical algorithms. The progress is in part due to the development of new methods to implement matrix functions on a quantum computer. Examples include the linear combination of unitaries (LCU) method, quantum signal processing (QSP), and quantum singular value transformation (QSVT), which is closely related to QSP. Using these methods, one can construct matrix functions to filter out unwanted eigenstates of a given Hermitian matrix, and thereby obtain a target eigenstate on a quantum computer. This technique we call quantum eigenstate filtering.

We focus our attention on two specific problems: ground state preparation and energy estimation, and solving linear systems. For the ground state preparation problem, we want to prepare the ground state, i.e., the lowest eigenstate of the Hamiltonian $H$, while for ground state energy estimation, we want to estimate the ground state energy, i.e., the the lowest eigenvalue of the Hamiltonian $H$. The ground state energy estimation problem is cannot be solved in polynomial time even on a quantum computer in the worst case. However, this problem becomes tractable with additional assumptions, which may be satisfied in many real-world applications. In this work we assume access to a good initial guess of the ground state, such that its overlap with the ground state is lower bounded by a parameter $\gamma$. Under this assumption, we present quantum algorithms based on the quantum eigenstate filtering technique to estimate the ground state energy and to prepare the ground state, with nearly optimal scaling with respect to both $\gamma$ and the precision.

The above mentioned algorithms work in the setting where the quantum computers are fully fault-tolerant, i.e., the noise is sufficiently suppressed through quantum error correction. We also present an algorithm to estimate the ground state energy in the early fault-tolerant setting, in which the the algorithm is limited by the number of qubits available and the coherence time. In this setting our algorithm uses a simple circuit and lower circuit depth at the expense of longer runtime. However the algorithm can still achieve the optimal Heisenberg-limited precision scaling despite these restrictions.

The quantum eigenstate filtering technique is also useful in solving the quantum linear system problem, in which we are asked to solve $Ax=b$ on a quantum computer. We show that the problem can be solved with a query complexity almost matching its lower bound by traversing the adiabatic path using quantum eigenstate filtering.

Chapter 1 introduces the basic problem setup and provides an overview of the results in this paper. Chapter 2 presents the nearly optimal algorithms for ground state preparation and energy estimation. Chapter 3 discussed implementation on early fault-tolerant devices. Chapter 4 applies quantum eigenstate filtering to solve the quantum linear system problem. Chapters 2, 3, and 4 are based on [Lin, Tong, Quantum 4 (2020), p.~372], [Lin, Tong, PRX Quantum 3.1 (2022), p.~010318], [Lin, Tong, Quantum 4 (2020), p.~361] respectively, all of which are published under CC BY 4.0.