The Poisson equation has wide applications in many areas of science and engineering. Although there are some quantum algorithms that can efficiently solve the Poisson equation, they generally require a fault-tolerant quantum computer, which is beyond the current technology. We propose a variational quantum algorithm (VQA) to solve the Poisson equation, which can be executed on noisy intermediate-scale quantum devices. In detail, we first adopt the finite-difference method to transform the Poisson equation into a linear system. Then, according to the special structure of the linear system, we find an explicit tensor product decomposition, with only $(2{log}_{2}n+1)$ items, of its coefficient matrix under a specific set of simple operators, where $n$ is the dimension of the coefficient matrix. This implies that the proposed VQA needs fewer quantum measurements, which dramatically reduces the required quantum resources. Additionally, we design observables to efficiently evaluate the expectation values of the simple operators on a quantum computer. Numerical experiments demonstrate that our algorithm can solve the Poisson equation.

Matrices with the displacement structures of circulant, Toeplitz, and Hankel types as well as matrices with structures generalizing these types are omnipresent in computations of sciences and engineering. In this paper we present efficient and memory-reduced quantum algorithms for solving linear systems with such structures by devising an approach to implement the block-encodings of these structured matrices. More specifically, by decomposing $n\times n$ dense matrices into linear combinations of displacement matrices, we first deduce the parametrized representations of the matrices with displacement structures so that they can be treated similarly. With such representations, we then construct $\epsilon$-approximate block-encodings of these structured matrices in two different data access models, i.e., the black-box model and the quantum random access memory (QRAM) data structure model. It is shown the quantum linear system solvers based on the proposed block-encodings provide a quadratic speedup with respect to the dimension over classical algorithms in the black-box model and an exponential speedup in the QRAM data structure model. In particular, these linear system solvers subsume known results with significant improvements and also can motivate new instances where there was no specialized quantum algorithm before. As an application, one of the quantum linear system solvers is applied to the linear prediction of time series, which justifies the claimed quantum speedup is achievable for problems of practical interest.

Most existing quantum private query (QPQ) protocols can hardly work in the presence of noise. The user Alice may obtain a false database item in noisy environments and both participants may cheat under the disguise of noise, so dealing with the noise needs an overall consideration of error correction, user privacy and database security. However, the only two existing protocols aiming to correct errors in QPQ lack such an overall consideration (at least one party's privacy can be revealed), and they did not estimate what extent of errors can be tolerated (actually, noise is seldom discussed in quantum two-party secure computations, and to the best of our knowledge, relevant bounds on tolerable errors remain unattainable so far). To solve this problem, we first exemplify how one participant reveals the other party's privacy in the existing QPQ protocols aiming to correct errors. Then we propose a practical protocol which can really work via noisy channel, that is, the error rate of the retrieved database item is reduced significantly and both parties' privacy are well protected. Besides, we deduce that the final error rate, user privacy and database security are pairwise in a “trade-off” relationship. By balancing them according to the required level of security and reliability, we obtain an upper bound on tolerable errors.

Dimensionality reduction algorithms, which reduce the dimensionality of a given data set whereas preserving the information of the original data set as well as possible, play an important role in machine learning and data mining. Duan et al. proposed a quantum version of the A-optimal projection algorithm (AOP) for dimensionality reduction [ Phys. Rev. A 99, 032311 (2019)] and claimed that the algorithm has exponential speedups on the dimensionality of the original feature space $n$ and the dimensionality of the reduced feature space $k$ over the classical algorithm. In this paper, we correct the time complexity of the algorithm of Duan et al. to $O\left[\frac{{\kappa }^{4s}\sqrt{k^s}}{{\epsilon }^s}{\mathrm{polylog}}^s\left(\frac{mn}{\epsilon }\right)\right]$, where $\kappa$ is the condition number of a matrix that related to the original data set, $s$ is the number of iterations, $m$ is the number of data points, and $\epsilon$ is the desired precision of the output state. Since the time complexity has an exponential dependence on $s$, the quantum algorithm can only be beneficial for high-dimensional problems with a small number of iterations $s$. To get a further speedup, we propose an improved quantum AOP algorithm with time complexity $O\left[\frac{s{\kappa }^6\sqrt{k}}{\epsilon }\mathrm{polylog}\left(\frac{nm}{\epsilon }\right)+\frac{s^2{\kappa }^4}{\epsilon }\mathrm{polylog}\left(\frac{\kappa k}{\epsilon }\right)\right]$ and space complexity $O[{log}_2(nk/\epsilon )+s]$. With space complexity slightly worse, our algorithm achieves, at least, a polynomial speedup compared to the algorithm of Duan et al.. Also, our algorithm shows exponential speedups in $n$ and $m$ compared with the classical algorithm when $\kappa ,k$, and $1/\epsilon$ are $O\left[\mathrm{polylog}\right(nm\left)\right]$.