Qubit-Efficient Randomized Quantum Algorithms for Linear Algebra

We propose a class of randomized quantum algorithms for the task of sampling from matrix functions, without the use of quantum block encodings or any other coherent oracle access to the matrix elements. As such, our use of qubits is purely algorithmic and no additional qubits are required for quantum data structures. Our algorithms start from a classical data structure in which the matrix of interest is specified in the Pauli basis. For $N\times N$ Hermitian matrices, the space cost is $\log (N)+1$ qubits and, depending on the structure of the matrices, the gate complexity can be comparable to state-of-the-art methods that use quantum data structures of up to size $O(N^2)$, when considering equivalent end-to-end problems. Within our framework, we present a quantum linear system solver that allows one to sample properties of the solution vector, as well as algorithms for sampling properties of ground states and Gibbs states of Hamiltonians. As a concrete application, we combine these subroutines to present a scheme for calculating Green’s functions of quantum many-body systems.

Popular Summary

With the advent of quantum computers, many different quantum algorithms have been proposed that could provide an advantage over their classical counterparts. In one regime, near-term algorithms such as variational quantum algorithms have been proposed, of which small instances can already be run on the quantum computers we have today. These approaches can be very hardware efficient, but they tend to lack generic runtime guarantees. At the other end of the spectrum, there has been a longstanding study of so-called “fault-tolerant” algorithms, which do have runtime guarantees, but they often have large hardware requirements. This motivates the study of early fault-tolerant approaches that maintain the runtime guarantees of fault-tolerant schemes but reduce hardware requirements, in order to bridge the gap and potentially accelerate the advent of quantum algorithms with speedup over classical approaches.

In this work, we reduce the hardware requirements of fault-tolerant algorithms by reducing their qubit usage. This is specifically achieved by using a randomization approach and by removing the requirement for quantum “oracles,” which are black boxes that other algorithms need to call in order to access classically encoded data. These quantum oracles can require a lot of qubits to implement, and so removing them saves qubits. We give a recipe to construct algorithms with these features that can sample properties of functions of matrices, given two conditions. First, we require a Fourier series approximation of the function. Second, we require a decomposition of the matrix in the Pauli matrix basis. We present concrete examples for the quantum linear systems problem and for sampling properties of ground states and Gibbs states of Hamiltonians.

As the size and quality of quantum computers improve, we envisage the need to find quantum computing applications that accommodate restricted hardware requirements, in order to reach for quantum advantage in the earliest possible time frame. We consider this work an early step toward this goal.

Figure 1

The motivation of our work. We reduce quantum hardware requirements for quantum algorithms on classical data by removing the need for quantum data structures or quantum oracles. This is achieved by replacing coherent access to the data with a classical description of the data in the Pauli basis and utilizing a randomized algorithm that samples the outputs of many quantum circuits. These circuits are chosen independently and thus in theory can also be parallelized, trading reduced total run time for additional space cost in the form of many quantum processors. Our approach uses circuits with at most $\log N+1$ qubits when processing data from $N\times N$ Hermitian matrices. This can be compared to other algorithms that utilize quantum data-access models that may have significantly greater qubit overhead overall.

Figure 2

The circuits used in our algorithms. We sample strings of quantum gates, consisting of specified Pauli operators and Pauli rotations, and perform quantum circuit runs with controlled versions of these gates. (a) The Hadamard test circuit. Measuring the expectation value of $Z$ on the first register returns Re($⟨\psi |U|\psi ⟩$) and Im($⟨\psi |U|\psi ⟩$ for choices of $G=\mathbb{1}$ and $G=S^{†}:=|0⟩⟨0|-i|1⟩⟨1|$, respectively. (b) The generalized Hadamard test circuit. Applying controlled-$U$ and anticontrolled-$V$, followed by measurement of the observable $X\otimes O$ yields $\frac{1}{2}(⟨\psi |U^{†}OV|\psi ⟩+⟨\psi |V^{†}OU|\psi ⟩)$.

Figure 3

The generalized Hadamard test. We use this circuit along with a modified measurement in Algorithm 5 to sample from the solution vector. Rather than measuring the observable $Z\otimes O$, we measure all qubits in the computational basis.