Changpeng Shao

Changpeng Shao, Hua Xiang

We consider the quantum implementations of the two classical iterative solvers for a system of linear equations, including the Kaczmarz method which uses a row of coefficient matrix in each iteration step, and the coordinate descent method which utilizes a column instead. These two methods are widely applied in big data science due to their very simple iteration schemes. In this paper we use the block-encoding technique and propose fast quantum implementations for these two approaches, under the assumption that the quantum states of each row or each column can be efficiently prepared. The quantum algorithms achieve exponential speed up at the problem size over the classical versions, meanwhile their complexity is nearly linear at the number of steps.

Changpeng Shao, Hua Xiang

In this paper we propose a quantum algorithm to determine the Tikhonov regularization parameter and solve the ill-conditioned linear equations, for example, arising from the finite element discretization of linear or nonlinear inverse problems. For regularized least squares problem with a fixed regularization parameter, we use the HHL algorithm and work on an extended matrix with smaller condition number. For the determination of the regularization parameter, we combine the classical L-curve and GCV function, and design quantum algorithms to compute the norms of regularized solution and the corresponding residual in parallel and locate the best regularization parameter by Grover's search. The quantum algorithm can achieve a quadratic speedup in the number of regularization parameters and an exponential speedup in the dimension of problem size.

Yuxin Zhang, Changpeng Shao

Gradient descent is one of the most basic algorithms for solving continuous optimization problems. In [Jordan, PRL, 95(5):050501, 2005], Jordan proposed the first quantum algorithm for estimating gradients of functions close to linear, with exponential speedup in the black-box model. This quantum algorithm was greatly enhanced and developed by [Gilyén, Arunachalam, and Wiebe, SODA, pp. 1425-1444, 2019], providing a quantum algorithm with optimal query complexity $\widetildeΘ(\sqrt{d}/\varepsilon)$ for a class of smooth functions of $d$ variables, where $\varepsilon$ is the accuracy. This is quadratically faster than classical algorithms for the same problem. In this work, we continue this research by proposing a new quantum algorithm for another class of functions, namely, analytic functions $f(\boldsymbol{x})$ which are well-defined over the complex field. Given phase oracles to query the real and imaginary parts of $f(\boldsymbol{x})$ respectively, we propose a quantum algorithm that returns an $\varepsilon$-approximation of its gradient with query complexity $\widetilde{O}(1/\varepsilon)$. As an extension, we also propose two quantum algorithms for Hessian estimation, aiming to improve quantum analogs of Newton's method. The two algorithms have query complexity $\widetilde{O}(d/\varepsilon)$ and $\widetilde{O}(d^{1.5}/\varepsilon)$, respectively, under different assumptions. Moreover, if the Hessian is promised to be $s$-sparse, we then have two new quantum algorithms with query complexity $\widetilde{O}(s/\varepsilon)$ and $\widetilde{O}(sd/\varepsilon)$, respectively. We also prove a lower bound of $\widetildeΩ(d)$ for Hessian estimation in the general case.

Zhengfeng Ji, Tongyang Li, Changpeng Shao et al.

We study the computational complexity of estimating the normalized trace $2^{-n}Tr[f(A)]$ for a log-local Hamiltonian $A$ acting on $n$ qubits. This problem arises naturally in the DQC1 model, yet its complexity is only understood for a limited class of functions $f(x)$. We show that if $f(x)$ is a continuous function with approximate degree $Ω({\rm poly}(n))$, then estimating $2^{-n}Tr[f(A)]$ up to constant additive error is DQC1-complete, under a technical condition on the polynomial approximation error of $f(x)$. This condition holds for a broad class of functions, including exponentials, trigonometric functions, logarithms, and inverse-type functions. We further prove that when $A$ is sparse, the classical query complexity of this problem is exponential in the approximate degree, assuming a conjectured lower bound for a trace variant of the $k$-Forrelation problem in the DQC1 query model. Together, these results identify the approximate degree as the key parameter governing the complexity of normalized trace estimation: it characterizes both the quantum complexity (via efficient DQC1 algorithms) and, conditionally, the classical hardness, yielding an exponential quantum-classical separation. Our proof develops a unified framework that cleanly combines circuit-to-Hamiltonian constructions, periodic Jacobi operators, and tools from polynomial approximation theory, including the Chebyshev equioscillation theorem.

Ashley Montanaro, Changpeng Shao

We study the problem of learning an unknown graph provided via an oracle using a quantum algorithm. We consider three query models. In the first model ("OR queries"), the oracle returns whether a given subset of the vertices contains any edges. In the second ("parity queries"), the oracle returns the parity of the number of edges in a subset. In the third model, we are given copies of the graph state corresponding to the graph. We give quantum algorithms that achieve speedups over the best possible classical algorithms in the OR and parity query models, for some families of graphs, and give quantum algorithms in the graph state model whose complexity is similar to the parity query model. For some parameter regimes, the speedups can be exponential in the parity query model. On the other hand, without any promise on the graph, no speedup is possible in the OR query model. A main technique we use is the quantum algorithm for solving the combinatorial group testing problem, for which a query-efficient quantum algorithm was given by Belovs. Here we additionally give a time-efficient quantum algorithm for this problem, based on the algorithm of Ambainis et al.\ for a "gapped" version of the group testing problem. We also give simple time-efficient quantum algorithms based on Fourier sampling and amplitude amplification for learning the exact-half and majority functions, which almost match the optimal complexity of Belovs' algorithms.

Alessandro Luongo, Changpeng Shao

We propose new quantum algorithms for estimating spectral sums of positive semi-definite (PSD) matrices. The spectral sum of an PSD matrix $A$, for a function $f$, is defined as $ \text{Tr}[f(A)] = \sum_j f(λ_j)$, where $λ_j$ are the eigenvalues of $A$. Typical examples of spectral sums are the von Neumann entropy, the trace of $A^{-1}$, the log-determinant, and the Schatten $p$-norm, where the latter does not require the matrix to be PSD. The current best classical randomized algorithms estimating these quantities have a runtime that is at least linearly in the number of nonzero entries of the matrix and quadratic in the estimation error. Assuming access to a block-encoding of a matrix, our algorithms are sub-linear in the matrix size, and depend at most quadratically on other parameters, like the condition number and the approximation error, and thus can compete with most of the randomized and distributed classical algorithms proposed in the literature, and polynomially improve the runtime of other quantum algorithms proposed for the same problems. We show how the algorithms and techniques used in this work can be applied to three problems in spectral graph theory: approximating the number of triangles, the effective resistance, and the number of spanning trees within a graph.

Changpeng Shao

Radial basis function (RBF) network is a third layered neural network that is widely used in function approximation and data classification. Here we propose a quantum model of the RBF network. Similar to the classical case, we still use the radial basis functions as the activation functions. Quantum linear algebraic techniques and coherent states can be applied to implement these functions. Differently, we define the state of the weight as a tensor product of single-qubit states. This gives a simple approach to implement the quantum RBF network in the quantum circuits. Theoretically, we prove that the training is almost quadratic faster than the classical one. Numerically, we demonstrate that the quantum RBF network can solve binary classification problems as good as the classical RBF network. While the time used for training is much shorter.