62 citations · 281 across the 27 of their papers we have counts for
27 papers
Quantum speedup of leverage score sampling and its application
Changpeng Shao
Leverage score sampling is crucial to the design of randomized algorithms for large-scale matrix problems, while the computation of leverage scores is a bottleneck of many applicat…
Quantum communication complexity of linear regression
Ashley Montanaro, Changpeng Shao
Quantum computers may achieve speedups over their classical counterparts for solving linear algebra problems. However, in some cases -- such as for low-rank matrices -- dequantized…
A deterministic Kaczmarz algorithm for solving linear systems
Changpeng Shao
We propose a new deterministic Kaczmarz algorithm for solving consistent linear systems . Basically, the algorithm replaces orthogonal projections with refl…
Faster quantum-inspired algorithms for solving linear systems
Changpeng Shao, Ashley Montanaro
We establish an improved classical algorithm for solving linear systems in a model analogous to the QRAM that is used by quantum linear solvers. Precisely, for the linear system $A…
Quantum-accelerated multilevel Monte Carlo methods for stochastic differential equations in mathematical finance
Dong An, Noah Linden, Jin-Peng Liu +3
Inspired by recent progress in quantum algorithms for ordinary and partial differential equations, we study quantum algorithms for stochastic differential equations (SDEs). Firstly…
Quantum algorithms for learning a hidden graph and beyond
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 re…
Quantum algorithms for spectral sums
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 , for a function , is defined as $…
Solving generalized eigenvalue problems by ordinary differential equations on a quantum computer
Changpeng Shao, Jin-Peng Liu
Many eigenvalue problems arising in practice are often of the generalized form $A\x=λB\x$. One particularly important case is symmetric, namely are Hermitian and is posi…
Quantum vs. classical algorithms for solving the heat equation
Noah Linden, Ashley Montanaro, Changpeng Shao
Quantum computers are predicted to outperform classical ones for solving partial differential equations, perhaps exponentially. Here we consider a prototypical PDE - the heat equat…
Computing eigenvalues of diagonalizable matrices in a quantum computer
Changpeng Shao
Solving linear systems and computing eigenvalues are two fundamental problems in linear algebra. For solving linear systems, many efficient quantum algorithms have been discovered.…
Data classification by quantum radial basis function networks
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…
Randomized Row and Column Iterative Methods with a Quantum Computer
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 matri…
An Improved Algorithm for Quantum Principal Component Analysis
Changpeng Shao
Principal component analysis is an important dimension reduction technique in machine learning. In [S. Lloyd, M. Mohseni and P. Rebentrost, Nature Physics 10, 631-633, (2014)], a q…
Building quantum neural networks based on swap test
Jian Zhao, Yuan-Hang Zhang, Chang-Peng Shao +3
Artificial neural network, consisting of many neurons in different layers, is an important method to simulate humain brain. Usually, one neuron has two operations: one is linear, t…
Quantum Regularized Least Squares Solver with Parameter Estimate
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…
A Quantum Model for Multilayer Perceptron
Changpeng Shao
Multilayer perceptron is the most common used class of feed-forward artificial neural network. It contains many applications in diverse fields such as speech recognition, image rec…
From linear combination of quantum states to Grover's searching algorithm
Changpeng Shao
Linear combination of unitaries (LCU for short) is one of the most important techniques in designing quantum algorithms. In this paper, we propose a new quantum algorithm in three…
Quantum Arnoldi and conjugate gradient iteration algorithm
Changpeng Shao
Arnoldi method and conjugate gradient method are important classical iteration methods in solving linear systems and estimating eigenvalues. Their efficiency often affected by the…
Quantum Circulant Preconditioner for Linear System of Equations
Changpeng Shao, Hua Xiang
We consider the quantum linear solver for with the circulant preconditioner . The main technique is the singular value estimation (SVE) introduced in [I. Kerenidis and A.…
Quantum Algorithm to Cubic Spline Interpolation
Changpeng Shao
HHL algorithm \cite{harrow} to solve linear system is a powerful and efficient quantum technique to deal with many matrix operations (such as matrix multiplication, powers and inve…
Reconsider HHL algorithm and its related quantum machine learning algorithms
Changpeng Shao
HHL quantum algorithm to solve linear systems is one of the most important subroutines in many quantum machine learning algorithms. In this work, we present and analyze several oth…
Quantum Algorithms to Matrix Multiplication
Changpeng Shao
In this paper, we study quantum algorithms of matrix multiplication from the viewpoint of inputting quantum/classical data to outputting quantum/classical data. The main target is…
Generalization of Quantum Fourier Transformation
Changpeng Shao
Quantum Fourier transformation is important in many quantum algorithms. In this paper, we generalize quantum Fourier transformation over the Abelian group from two d…
Quantum speedup to some types of polynomial equations
Changpeng Shao
In this paper, we consider three types of polynomial equations in quantum computer: linear divisibility equation, which belongs to a special type of binary-quadratic Diophantine eq…