Abstract Quantum computers are predicted to outperform classical ones for solving partial differential equations, perhaps exponentially. Here we consider a prototypical PDE—the heat equation in rectangular region—and compare detail the complexities of ten and quantum algorithms it, sense approximately computing amount given region. We find that, spatial dimension $$d \ge 2$$ <mml:math...

An artificial neural network, consisting of many neurons in different layers, is an important method to simulate the human brain. Usually, one neuron has two operations: linear, other nonlinear. The linear operation inner product and nonlinear represented by activation function. In this work, we introduce a kind quantum whose inputs outputs are states. operator can be realized circuits. Based on neuron, propose model network which weights between all We also construct circuit realize model....

Quantum-inspired classical algorithms provide us with a new way to understand the computational power of quantum computers for practically-relevant problems, especially in machine learning. In past several years, numerous efficient various tasks have been found, while an analysis lower bounds is still missing. Using communication complexity, this work we propose first method study these tasks. We mainly focus on solving linear regressions, supervised clustering, principal component analysis,...

We establish an improved classical algorithm for solving linear systems in a model analogous to the QRAM that is used by quantum solvers. Precisely, system \( A{\bf x}= {\bf b} \) , we show there outputs data structure x} allowing sampling and querying entries, where such \Vert x}- A^{+}{\bf b}\Vert \le \epsilon . This output can be viewed as analogue of The complexity our \widetilde{O}(\kappa _F^6 \kappa ^2/\epsilon ^2) _F = A\Vert _F\Vert A^{+}\Vert improves previous best [Gilyén, Song...

We propose a new deterministic Kaczmarz algorithm for solving consistent linear systems $A\mathbf{x}=\mathbf{b}$. Basically, the replaces orthogonal projections with reflections in original scheme of Stefan Kaczmarz. Building on this, we give geometric description solutions systems. Suppose $A$ is $m\times n$, show that generates series points distributed patterns an $(n-1)$-sphere centered solution. These lie evenly $2m$ lower-dimensional spheres $\{\S_{k0},\S_{k1}\}_{k=1}^m$, property any...

Let A be an s-sparse Hermitian matrix, f(x) a univariate function, and i, j two indices. In this work, we investigate the query complexity of approximating i f(A) j. We show that for any continuous function f(x):[−1,1]→ [−1,1], quantum computing j± ε/4 is lower bounded by Ω(degε(f)). The upper bound at most quadratic in degε(f) linear under certain mild assumptions on A. Here approximate degree minimum such there polynomial f up to additive error ε interval [−1,1]. also classical...

In this paper, we study quantum algorithms of matrix multiplication from the viewpoint inputting quantum/classical data to outputting data. The main target is trying overcome input and output problem, which are not easy solve many will encounter, operations in computer with high efficiency. And solving be first step. We propose three based on swap test, SVE HHL. From point making fewer assumptions, test method works best than other two. also show that algorithm classical by achieves...

We consider the quantum linear solver for $Ax=b$ with circulant preconditioner $C$. The main technique is singular value estimation (SVE) introduced in [I. Kerenidis and A. Prakash, Quantum recommendation system, ITCS 2017]. However, some modifications of SVE should be made to solve preconditioned system $C^{-1} Ax = C^{-1} b$. Moreover, different from considered [B. D. Clader, B. C. Jacobs, R. Sprouse, Preconditioned algorithm, Phys. Rev. Lett., 2013], easy construct can directly applied...

Computing eigenvalues of matrices is ubiquitous in numerical linear algebra problems. Currently, fast quantum algorithms for estimating Hermitian and unitary are known. However, the general case far from fully understood case. Based on a algorithm solving ordinary differential equations, we show how to estimate diagonalizable that only have real eigenvalues. The output superposition eigenpairs, overall complexity polylog dimension sparse matrices. Under an assumption, extend with complex

Quantum computers may achieve speedups over their classical counterparts for solving linear algebra problems. However, in some cases—such as low-rank matrices—dequantized algorithms demonstrate that there cannot be an exponential quantum speedup. In this work, we show have provable polynomial and terms of communication complexity fundamental problems if is no restriction on the rank. We mainly focus regression Hamiltonian simulation. case, task to prepare state result. To allow a fair...

We consider the quantum implementations of two classical iterative solvers for a system linear equations, including row (Kaczmarz) method which utilizes coefficient matrix in each iteration step, and column (coordinate descent) uses instead. These methods are widely applied big data science due to their simple schemes. propose fast algorithms these approaches by constructing efficient unitary operators step based on block-encoding technique. The construction is unitaries prepare states rows...

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 and machine translation software. To cater for fast development quantum learning, this paper, we propose a new model to study multilayer computer. This tasks prepare state output signal each layer establish version learning algorithm about weights layer. We will show that corresponding versions can achieve at least...

Radial-basis-function (RBF) networks are third-layered neural that widely used in function approximation and data classification. Here we propose a quantum model for RBF networks. As the classical case, use radial basis functions as activation functions; linear algebraic techniques coherent states can be applied to implement these functions. We define state of weight tensor product single-qubit states. This gives simple approach network circuits. In this prove training is almost...

Variational hybrid quantum classical algorithms to optimizations are important applications for near-term computing. This paper proposes two (the second one is variational) training neural networks. Both of them obtain exponential speedup at the number samples and polynomial dimension over algorithms. Moreover, proposed return information weight so that outputs can be used directly solve other problems. For practicality, we draw circuits implement Finally, as an inspiration, show how apply...

Quantum computers are predicted to outperform classical ones for solving partial differential equations, perhaps exponentially. Here we consider a prototypical PDE - the heat equation in rectangular region and compare detail complexities of ten quantum algorithms it, sense approximately computing amount given region. We find that, spatial dimension $d \ge 2$, there is an at most quadratic speedup using approach based on applying amplitude estimation accelerated random walk. However,...

Inspired by recent progress in quantum algorithms for ordinary and partial differential equations, we study stochastic equations (SDEs). Firstly provide a algorithm that gives quadratic speed-up multilevel Monte Carlo methods general setting. As applications, apply it to compute expectation values determined classical solutions of SDEs, with improved dependence on precision. We demonstrate the use this variety applications arising mathematical finance, such as Black-Scholes Local Volatility...

HHL quantum algorithm to solve linear systems is one of the most important subroutines in many machine learning algorithms. In this work, we present and analyze several other caveats algorithm, which have been ignored past. Their influences on efficiency, accuracy practicability related algorithms will be discussed. We also found that these affect much deeper than already noticed caveats. order obtain more practical with less assumptions based should pay attention

Data classification is a fundamental problem in machine learning. We study quantum speedup of the supervised data algorithms (quadratic, linear and naïve Bayes classifiers) based on Bayes' theory. The main technique we use to achieve block-encoding. However, apply this effectively, propose general method construct As an application, show that all three classifiers exponential at number samples over their classical counterparts. for dimension space, quadratic varying degrees polynomial...

The line geometric model of 3-D projective geometry has the nice property that Lie algebra sl(4) transformations is isomorphic to bivector CL(3,3), and closely related classical screw theory for rigid-body motions. canonical homomorphism from SL(4) Spin(3,3) not satisfying because it surjective, negative determinant do induce orthogonal in Plücker coordinate space lines. This paper presents our contributions developing a rigorous convenient algebraic framework study with Clifford algebra. To...

Linear combination of unitaries (LCU for short) is one the most important techniques in designing quantum algorithms. In this paper, we propose a new algorithm three different forms to achieve LCU. Different from previous algorithms [Childs-linear-system,Clader,Long11], complexity now only depends on number and precision. So it will play more role design when small, such as iteration %Since algorithms, $m$ often refers steps, which small if are efficient. Moreover, an application LCU,...

Radial basis function (RBF) network is a simple but useful neural model that contains wide applications in machine learning. The training of an RBF reduces to solve linear system, which time consuming classically. Based on HHL algorithm, we propose two quantum algorithms train networks. To apply the choose using Hamiltonian simulation algorithm proposed [P. Rebentrost, A. Steffens, I. Marvian and S. Lloyd, Phys. Rev. A 97, 012327, 2018]. However, use this result, oracle query entries matrix...