An Efficient Quantum Algorithm for Linear System Problem in Tensor Format

Introduction

The paper discusses the potential of quantum algorithms to solve certain problems faster than classical algorithms. It mentions various quantum algorithms, including Shor's algorithm for integer factorization, Grover's algorithm for database search, the Quantum Approximate Optimization Algorithm (QAOA) for combinatorial optimization problems, and Quantum Linear System Algorithms (QLSAs) for solving quantum linear system problems. QLSAs, in particular, demonstrate exponential convergence speed-up compared to classical methods like Cholesky factorization.

Due to the significance of solving linear systems in numerical computation, researchers have focused on using QLSAs to speed up classical algorithms, such as classical PDE algorithms and classical optimization algorithms. However, a crucial challenge is the efficient quantum circuit implementation of the oracles required for preprocessing the input data and building quantum circuits from classical system descriptions.

The paper studies the use of QLSAs for solving a class of linear systems whose coefficient matrix and right-hand-side vector can be represented as a linear combination of a few tensor products of 2-by-2 matrices and 2-dimensional vectors, respectively. This problem is a special case of the linear system problem in tensor format (LSP-TF), which is frequently encountered in discretized PDE problems.

While some classical algorithms have been proposed to solve LSP-TF, they modify Krylov subspace methods by approximating the tensor format, sacrificing accuracy while keeping the complexity polylogarithmic in the problem size. However, their total complexity is unknown and unlikely to be better than the original Krylov subspace methods.

The paper's main contribution is to show that such linear systems can be efficiently solved using a quantum computer, and it provides a full and explicit circuit implementation of the algorithm.

Problem Definition

The provided text introduces notations used in the paper, including vectors, matrices, Pauli matrices, norms, and quantum state representations. It then defines the linear system problem (LSP) and the tensor-factored linear system problem (LSP-TF), which arises frequently in high-dimensional discretized PDEs.

The paper proposes applying Algorithm 1 to solve LSP-TF for a special case where the matrix A and vector b have tensor product structures. The authors assume the matrices and vectors satisfy certain norm bounds (Assumption 2.1) and the tensor ranks of A and b are constant (Assumption 2.2). The main contribution is a Hamiltonian decomposition for Algorithm 1 and a detailed circuit implementation with polylogarithmic depth in the problem dimension (Theorem 2.1).

The text then briefly introduces the quantum linear system algorithm (QLSA) proposed in previous work, which Algorithm 1 is based on. It explains how Algorithm 1 turns the continuous adiabatic evolution into a discretized piece-wise evolution using phase randomization.

Finally, the Trotterization method is introduced as a way to approximate the Hamiltonian evolution by decomposing the Hamiltonian into a sum of easily implementable terms. Lemmas on the error bounds of Trotterization and guidance on choosing the Trotter number are provided.

QLSA Circuit Design for LSP-TF

The provided section describes how to implement quantum circuits for simulating the time evolution of two types of Hamiltonians that arise when applying a specific algorithm (Algorithm 1) to the linear swap preserving tensor format (LSP-TF) problem.

The first type, called Type-1 Hamiltonians, are tensor products of Pauli and Hermitian matrices. The authors give a detailed algorithm (Algorithm 2) to implement the time evolution operator for these Hamiltonians using quantum multipliers and phase gates controlled by the binary representation of certain parameters.

The second type, called Type-2 Hamiltonians, are more complicated as they are not in tensor product form initially. The authors show how to decompose these Hamiltonians into a product of three matrices, where the outer two are unitaries that can be implemented efficiently, and the inner matrix is a tensor product that can be handled similarly to the Type-1 case using Algorithm 2.

Cost estimates in terms of number of operations and circuit depths are provided for implementing both types of Hamiltonians. A key assumption made is that certain parameters can be represented exactly using a fixed number of qubits, which is discussed further in Section 4.1 of the paper.

Circuit Cost Analysis

The section analyzes the total cost required to implement Algorithm 1 using the proposed quantum circuits. It is divided into three parts:

The first part estimates the cost when the data (σH1,i and σH2,j) cannot be represented exactly using p qubits. It introduces the concept of ϵ-approximate binary representation and shows that p = ⌈1−log2(ϵ)⌉ qubits suffice to obtain an ϵ-approximation. It then bounds the error introduced in the quantum circuit due to this approximation.

The second part analyzes the error from the Trotterization method used to implement the time evolution operator e^(-itH). It bounds this error in terms of the commutative factor α and shows that choosing the Trotter number r = O(m^2d^4κ^2/ϵ) ensures the error is O(ϵ^2/log^2κ).

The third part combines the errors from data approximation and Trotterization to bound the total error. It shows that the proposed implementation of Algorithm 1 produces an O(ϵ)-approximate solution using O(κ^2 log(N) log^2(κ)/ϵ^2) arithmetic operations, single qubit gates, and calls to a p-qubit multiplier with depth O(p^3). The cost of preparing the initial state is shown to be negligible.

Overall, the analysis provides bounds on the resources (number of operations, gates, gate depth) required to implement Algorithm 1 up to a given precision ϵ, taking into account errors from data approximation and Trotterization.

Conclusion

This paper explores using an adiabatic inspired quantum linear system algorithm (QLSA) to solve linear systems in tensor format. The focus is on linear systems where the matrices are linear combinations of tensor products of 2x2 Hermitian matrices, and the vectors are linear combinations of tensor products of 2-dimensional vectors.

The paper explicitly describes the quantum circuit components used in implementing the QLSA, which only requires single-qubit unitary circuits, p-qubit quantum multipliers, and their controlled versions. The number of classical arithmetic operations and these gates is polynomial in n, m, and d, making the time complexity polylogarithmic in the system's dimension – better than classical algorithms for general linear systems.

Compared to a classical algorithm for tensor-formatted linear systems, the total complexity of this quantum approach is comparable to that algorithm's single-step complexity in terms of problem dimension. Potential future work could extend these results to higher dimensional components and cases where components are in different subspaces. Further investigation into improving the dependence on condition number and accuracy for structured problems is also suggested.

Acknowledgement

The authors express gratitude to Faisal Alam and Muqing Zheng for their insightful discussions. This research was financially supported by the Defense Advanced Research Projects Agency through the project "The Quantum Computing Revolution and Optimization: Challenges and Opportunities." Additional funding came from the National Science Foundation's CAREER program and the U.S. Department of Energy's Office of Electricity Advanced Grid Modeling program. The computational resources utilized were provided by the Oak Ridge Leadership Computing Facility, a user facility operated by the Department of Energy's Office of Science.