@article {2021, title = {Efficient quantum algorithms for analyzing large sparse electrical networks}, journal = {Quantum Information \& Computation}, volume = {17}, year = {2017}, month = {2017/07/21}, pages = {987-1026}, abstract = {

Analyzing large sparse electrical networks is a fundamental task in physics, electrical engineering and computer science. We propose two classes of quantum algorithms for this task. The first class is based on solving linear systems, and the second class is based on using quantum walks. These algorithms compute various electrical quantities, including voltages, currents, dissipated powers and effective resistances, in time poly(d, c,log(N),1/λ,1/ε), where N is the number of vertices in the network, d is the maximum unweighted degree of the vertices, c is the ratio of largest to smallest edge resistance, λ is the spectral gap of the normalized Laplacian of the network, and ε is the accuracy. Furthermore, we show that the polynomial dependence on 1/λ is necessary. This implies that our algorithms are optimal up to polynomial factors and cannot be signficantly improved.

}, url = {https://arxiv.org/abs/1311.1851}, author = {Guoming Wang} } @article {1923, title = {Quantum algorithm for linear differential equations with exponentially improved dependence on precision}, journal = {Communications in Mathematical Physics}, volume = {356}, year = {2017}, month = {2017/12/01}, pages = {1057-1081}, abstract = {

We present a quantum algorithm for systems of (possibly inhomogeneous) linear ordinary differential equations with constant coefficients. The algorithm produces a quantum state that is proportional to the solution at a desired final time. The complexity of the algorithm is polynomial in the logarithm of the inverse error, an exponential improvement over previous quantum algorithms for this problem. Our result builds upon recent advances in quantum linear systems algorithms by encoding the simulation into a sparse, well-conditioned linear system that approximates evolution according to the propagator using a Taylor series. Unlike with finite difference methods, our approach does not require additional hypotheses to ensure numerical stability.

}, url = {https://arxiv.org/abs/1701.03684}, author = {Dominic W. Berry and Andrew M. Childs and Aaron Ostrander and Guoming Wang} } @article {2020, title = {Quantum Algorithm for Linear Regression}, journal = {Physical Review A}, volume = {96}, year = {2017}, month = {2017/07/31}, pages = {012335}, abstract = {

We present a quantum algorithm for fitting a linear regression model to a given data set using the least squares approach. Different from previous algorithms which only yield a quantum state encoding the optimal parameters, our algorithm outputs these numbers in the classical form. So by running it once, one completely determines the fitted model and then can use it to make predictions on new data at negligible cost. Moreover, our algorithm does not require the design matrix to be sparse or need any help from additional state preparation procedures. It runs in time poly(log(N), d, κ, 1/), where N is the size of the data set, d is the number of adjustable parameters, κ is the condition number of the design matrix, and  is the desired precision in the output. We also show that the polynomial dependence on d and κ is necessary. Thus, our algorithm cannot be significantly improved. Furthermore, we also give a quantum algorithm that estimates the quality of the least-squares fit without computing its parameters explicitly. This algorithm runs faster than the one for finding this fit, and can be used to check whether the given data set qualifies for linear regression in the first place.

}, url = {https://arxiv.org/abs/1402.0660}, author = {Guoming Wang} } @article {1785, title = {Tensor network non-zero testing}, journal = {Quantum Information \& Computation}, volume = {15}, year = {2015}, month = {2015/07/01}, pages = {885-899}, abstract = {Tensor networks are a central tool in condensed matter physics. In this paper, we initiate the study of tensor network non-zero testing (TNZ): Given a tensor network T, does T represent a non-zero vector? We show that TNZ is not in the Polynomial-Time Hierarchy unless the hierarchy collapses. We next show (among other results) that the special cases of TNZ on non-negative and injective tensor networks are in NP. Using this, we make a simple observation: The commuting variant of the MA-complete stoquastic k-SAT problem on D-dimensional qudits is in NP for logarithmic k and constant D. This reveals the first class of quantum Hamiltonians whose commuting variant is known to be in NP for all (1) logarithmic k, (2) constant D, and (3) for arbitrary interaction graphs.}, url = {http://arxiv.org/abs/1406.5279}, author = {Sevag Gharibian and Zeph Landau and Seung Woo Shin and Guoming Wang} } @article {1786, title = {Quantum Algorithms for Curve Fitting}, year = {2014}, month = {2014/04/02}, abstract = {We present quantum algorithms for estimating the best-fit parameters and the quality of least-square curve fitting. The running times of these algorithms are polynomial in logn, d, κ, ν, χ, 1/Φ and 1/ϵ, where n is the number of data points to be fitted, d is the dimension of feature vectors, κ is the condition number of the design matrix, ν and χ are some parameters reflecting the variances of the design matrix and response vector, Φ is the fit quality, and ϵ is the tolerable error. Different from previous quantum algorithms for these tasks, our algorithms do not require the design matrix to be sparse, and they do completely determine the fitted curve. They are developed by combining phase estimation and the density matrix exponentiation technique for dense Hamiltonian simulation.}, url = {http://arxiv.org/abs/1402.0660}, author = {Guoming Wang} }