Different hybrid quantum-classical algorithms have recently been developed as a near-term way to solve linear systems of equations on quantum devices. However, the focus has so far been mostly on the methods, rather than the problems that they need to tackle. In fact, these algorithms have been run on real hardware only for problems in quantum physics, such as Hamiltonians of a few qubits systems. These problems are particularly favorable for quantum hardware, since their matrices are the sum of just a few unitary terms and since only shallow quantum circuits are required to estimate the cost function. However, for many interesting problems in linear algebra, it appears far less trivial to find an efficient decomposition and to trade it off with the depth of the cost quantum circuits. A first simple yet interesting instance to consider are tridiagonal systems of equations. These arise, for instance, in the discretization of one-dimensional finite element analyses. This work presents a method to solve a class of tridiagonal systems of equations with the variational quantum linear solver (VQLS), a recently proposed variational hybrid algorithm for solving linear systems. In particular, we present a new decomposition for this class of matrices based on both Pauli strings and multi--qubit gates, resulting in less terms than those obtained by just using Pauli gates. Based on this decomposition, we discuss the tradeoff between the number of terms and the near-term implementability of the quantum circuits. Furthermore, we present the first simulated and real-hardware results obtained by solving tridiagonal linear systems with VQLS, using the decomposition proposed.
Previously proposed quantum algorithms for solving linear systems of equations cannot be implemented in the near term due to the required circuit depth. Here, we propose a hybrid quantum-classical algorithm, called Variational Quantum Linear Solver (VQLS), for solving linear systems on near-term quantum computers. VQLS seeks to variationally prepare | x ⟩ such that A | x ⟩ ∝ | b ⟩ . We derive an operationally meaningful termination condition for VQLS that allows one to guarantee that a desired solution precision ϵ is achieved. Specifically, we prove that C ⩾ ϵ 2 / κ 2 , where C is the VQLS cost function and κ is the condition number of A . We present efficient quantum circuits to estimate C , while providing evidence for the classical hardness of its estimation. Using Rigetti's quantum computer, we successfully implement VQLS up to a problem size of 1024 × 1024 . Finally, we numerically solve non-trivial problems of size up to 2 50 × 2 50 . For the specific examples that we consider, we heuristically find that the time complexity of VQLS scales efficiently in ϵ , κ , and the system size N .
Finite-element methods are industry standards for finding numerical solutions to partial differential equations. However, the application scale remains pivotal to the practical use of these methods, even for modern-day supercomputers. Large, multi-scale applications, for example, can be limited by their requirement of prohibitively large linear system solutions. It is therefore worthwhile to investigate whether near-term quantum algorithms have the potential for offering any kind of advantage over classical linear solvers. In this study, we investigate the recently proposed variational quantum linear solver (VQLS) for discrete solutions to partial differential equations. This method was found to scale polylogarithmically with the linear system size, and the method can be implemented using shallow quantum circuits on noisy intermediate-scale quantum (NISQ) computers. Herein, we utilize the hybrid VQLS to solve both the steady Poisson equation and the time-dependent heat and wave equations.
The Variational Quantum Linear Solver (VQLS), a hybrid quantum-classical algorithm for solving linear systems, faces a practical scalability bottleneck: the Linear Combination of Unitaries (LCU) decomposition requires
O(L2) circuit evaluations per optimizer iteration, where
L can grow to
4n in the worst case for an
n-qubit system. We address this computational bottleneck through two complementary strategies. First, we present a distributed VQLS (D-VQLS) framework (https://code.ornl.gov/olcf-qcfd/DVQLS.git), built on NVIDIA CUDA-Q, that enables asynchronous, scalable distribution of the
O(L2) cost evaluations. Second, a fast Walsh--Hadamard transform (FWHT)-based Pauli decomposition with coefficient-amplitude pruning threshold
τ=0.01 curbs LCU growth for the structured Toeplitz family, reducing
L from
O(2n) to 64 for
n>6 and compressing the circuit complexity per optimizer iteration from
O(n4n) to
O(n). We derive the exact top-
L Frobenius error and connect it to worst-case solution error. For a 10-qubit tridiagonal Toeplitz system, the
L=64 pruning yields a
256× reduction---from 23 million to 90k circuits per optimizer iteration.
The D-VQLS framework is validated on the NERSC Perlmutter supercomputer using multi-node, multi-GPU ideal state-vector simulations, achieving over
99.99% fidelity against classical solutions on tridiagonal Toeplitz and Hele--Shaw flow benchmarks, with near-ideal strong scaling up to 24 GPUs and
95.3% weak scaling efficiency at 96 GPUs processing more than 360k circuits per optimizer iteration (from larger-
L pruning) for the 10-qubit system. Systematic profiling identifies the optimal resource allocation for distributed quantum circuit workloads, yielding a
2.52× speedup for the configurations studied.
Solving a Poisson equation is generally reduced to solving a linear system with a coefficient matrix
A of entries
aij,i,j=1,2,...,n, from the discretized Poisson equation. Although the variational quantum algorithms are promising algorithms to solve the discretized Poisson equation, they generally require that
A be decomposed into a sum of
O[poly(log2n)] simple operators in order to evaluate efficiently the loss function. A tensor product decomposition of
A with
2log2n+1 terms has been explored in previous works. In this paper, based on the decomposition of sparse Hamiltonians we greatly reduce the number of terms. We first write the loss function in terms of the operator ${\ensuremath{\sigma}}_{x}\ensuremath{\bigotimes}A$ with ${\ensuremath{\sigma}}_{x}$ denoting the standard Pauli operator. Then for the one-dimensional Poisson equations with different boundary conditions and for the
d-dimensional Poisson equations with Dirichlet boundary conditions, we decompose ${\ensuremath{\sigma}}_{x}\ensuremath{\bigotimes}A$ into a sum of at most 7 and
(4d+1) Hermitian, one-sparse, and self-inverse operators, respectively. We design explicitly the quantum circuits to evaluate efficiently the loss function. The decomposition method and the design of quantum circuits can also be easily extended to linear systems with Hermitian and sparse coefficient matrices satisfying
ai,i+c=ac for $c=0,1,...,n\ensuremath{-}1$ and $i=0,\ensuremath{\cdots},n\ensuremath{-}1\ensuremath{-}c$.
Abstract To solve the Poisson equation it is usually possible to discretize it into solving the corresponding linear system Ax = b. Variational quantum algorithms (VQAs) for the discretized Poisson equation have been studied before. We present a VQA based on the banded Toeplitz systems for solving the Poisson equation with respect to the structural features of matrix A. In detail, we decompose the matrices A and A 2 into a linear combination of the corresponding banded Toeplitz matrix and sparse matrices with only a few non-zero elements. For the one-dimensional Poisson equation with different boundary conditions and the d-dimensional Poisson equation with Dirichlet boundary conditions, the number of decomposition terms is less than that reported in [Phys. Rev. A 2023 108, 032 418 ]. Based on the decomposition of the matrix, we design quantum circuits that efficiently evaluate the cost function. Additionally, numerical simulation verifies the feasibility of the proposed algorithm. Finally, the VQAs for linear systems of equations and matrix-vector multiplications with the K-banded Toeplitz matrix T n K are given, where T n K ∈ R n × n and K ∈ O ( ploylog n ) .
This work develops simulation methods that enable the application of the variational quantum linear solver (VQLS) to simulate quantum transport in nanoscale semiconductor devices. Most previous work on VQLS applications in semiconductor device simulations focuses on solving the Poisson equation, where the coefficient matrix of the sparse linear system is real and symmetric. Solving the quantum transport equation, however, leads to coefficient matrices that are complex and non-symmetric. This work addresses the challenges of applying VQLS to quantum transport simulations. We propose new forms of cost functions to solve complex and non-symmetric linear systems with faster computing speed. We further develop efficient decomposition methods for cost function evaluation, which target reducing the quantum circuit complexity and improving noise robustness when solving the quantum transport equation using the nonequilibrium Green's function method. While classical computation faces the challenge of the “curse of dimensionality” as the spatial-energy numerical grid dimensions grow, the proposed quantum-computing-based method scales logarithmically with the grid size, which offers a promising opportunity for addressing the computational challenges of solving quantum transport in semiconductor devices.