We explore the impact of quantum algorithms on classical-data problems if quantum algorithms can be implemented on quantum computers. It is underlined in this paper that both state estimator design problems for classical linear systems and quantum state tomography can be considered as classical-data problems. Our recent research indicated that the time complexity of state estimator design problems can be reduced to O(qn) in comparison to the time complexity O(n6) in traditional classical algorithms when quantum states can be efficiently prepared, the system matrix is sparse, and both the condition number κ and the reciprocal of precision ε are small in size O(poly log(n)), where n is the dimension of the state x(t) and q is the dimension of the input u(t). This is in contrast to the further observation that the time complexity of state estimator design problems is O(n2) when quantum states cannot be efficiently prepared. The time complexity of quantum state tomography with dimension d is O(d4) when classical algorithms are adopted. We have demonstrated that if the system matrix is sparse, and both the condition number κ and the reciprocal of precision ε are small in size O(poly log(d)), quantum algorithms can reduce the time complexity of quantum state tomography to O(dpoly log d) or O(d3) when quantum states can or cannot be efficiently prepared. In other words, preparing quantum states efficiently has become a bottleneck constraint for quantum acceleration. Our recent researches can be regarded as a novel attempt of enriching application area of quantum computation.
We explore the impact of quantum algorithms on classical-data problems if quantum algorithms can be implemented on quantum computers. It is underlined in this paper that both state estimator design problems for classical linear systems and quantum state tomography can be considered as classical-data problems. Our recent research indicated that the time complexity of state estimator design problems can be reduced to O(qn) in comparison to the time complexity O(n6) in traditional classical algorithms when quantum states can be efficiently prepared, the system matrix is sparse, and both the condition number κ and the reciprocal of precision ε are small in size O(poly log(n)), where n is the dimension of the state x(t) and q is the dimension of the input u(t). This is in contrast to the further observation that the time complexity of state estimator design problems is O(n2) when quantum states cannot be efficiently prepared. The time complexity of quantum state tomography with dimension d is O(d4) when classical algorithms are adopted. We have demonstrated that if the system matrix is sparse, and both the condition number κ and the reciprocal of precision ε are small in size O(poly log(d)), quantum algorithms can reduce the time complexity of quantum state tomography to O(dpoly log d) or O(d3) when quantum states can or cannot be efficiently prepared. In other words, preparing quantum states efficiently has become a bottleneck constraint for quantum acceleration. Our recent researches can be regarded as a novel attempt of enriching application area of quantum computation.
We investigate the dividing line between classical and quantum computational power in estimating properties of matrix functions. More precisely, we study the computational complexity of two primitive problems: given a function f and a Hermitian matrix A , we compute a matrix element of f ( A ) or a local measurement on f ( A ) | 0 ⟩ ⊗ n , with | 0 ⟩ ⊗ n being an n -qubit reference state vector, in both cases up to additive approximation error. We consider four functions—monomials, Chebyshev polynomials, the time evolution function, and the inverse function—and probe the complexity across a broad landscape covering different problem input regimes. Namely, we consider two types of matrix inputs (sparse and Pauli access), matrix properties (norm and sparsity), the approximation error, and function-specific parameters. We identify BQP- forms of both problems for each function and then toggle the problem parameters to easier regimes to see where hardness remains, or where the problem becomes classically easy. As part of our results, we make concrete a hierarchy of hardness across the functions; in parameter regimes where we have classically efficient algorithms for monomials, all three other functions remain robustly BQP-, or hard under usual computational complexity assumptions. In identifying classically easy regimes, among others, we show that for any polynomial of degree poly ( n ) , both problems can be efficiently classically simulated when A has O ( log n ) nonzero coefficients in the Pauli basis. This contrasts with the fact that the problems are BQP- in the sparse access model even for constant row sparsity, whereas the stated Pauli access efficiently constructs sparse access with row sparsity O ( log n ) . Our work provides a catalog of efficient quantum and classical algorithms for fundamental linear-algebra tasks.
Abstract Linear regression is one of the most important and common analytical methods in mathematical statistics. The letter studies a general model of linear regression problem based on least squares method, and investigates the impact of quantum algorithms on the time complexity of solving linear regression problem when quantum algorithms can be implemented on quantum computers. With the help of the general model of linear regression problem in terms of least squares method, we propose a novel simplified quantum scheme for solving linear regression equation based on the sparsity-independent quantum singular value estimation algorithm. For a linear regression equation with dimension n, our scheme can reduce the time complexity from O(Nn 2) to O ( N log N ) when both the condition number κ of related matrices and the reciprocal of precision ∈ are small in size O(play logN), where m is the dimension of the input u and N is the number of samples.
We present a quantum algorithm to solve systems of linear equations of the form Ax = b , where A is a tridiagonal Toeplitz matrix and b results from discretizing an analytic function, with a circuit complexity of O (1/√ε, poly (log κ, log N )), where N denotes the number of equations, ε is the accuracy, and κ the condition number. The repeat-until-success algorithm has to be run O (κ/(1-ε)) times to succeed, leveraging amplitude amplification, and needs to be sampled O (1/ε 2 ) times. Thus, the algorithm achieves an exponential improvement with respect to N over classical methods. In particular, we present efficient oracles for state preparation, Hamiltonian simulation, and a set of observables together with the corresponding error and complexity analyses. As the main result of this work, we show how to use Richardson extrapolation to enhance Hamiltonian simulation, resulting in an implementation of Quantum Phase Estimation (QPE) within the algorithm with 1/√ε circuits that can be run in parallel each with circuit complexity 1/√ ε instead of 1/ε. Furthermore, we analyze necessary conditions for the overall algorithm to achieve an exponential speedup compared to classical methods. Our approach is not limited to the considered setting and can be applied to more general problems where Hamiltonian simulation is approximated via product formulae, although our theoretical results would need to be extended accordingly. All the procedures presented are implemented with Qiskit and tested for small systems using classical simulation as well as using real quantum devices available through the IBM Quantum Experience.
Recently, we try to answer the following question: what will happen to our life if quantum computers can be physically realized. In this research, we explore the impact of quantum algorithms on the time complexity of quantum state tomography based on the linear regression algorithm if quantum states can be efficiently prepared by classical information and quantum algorithms can be implemented on quantum computers. By studying current quantum algorithms based on quantum singular value decomposition (SVE) of calculating matrix multiplication, solving linear equations and eigenvalue and eigenstate estimation and so on, we propose a novel scheme to complete the mission of quantum state tomography. We show the calculation based on our algorithm as an example at last. Although quantum state preparations and extra measurements are indispensable in our quantum algorithm scheme compared with the existing classical algorithm, the time complexity of quantum state tomography can be remarkably declined. For a quantum system with dimension d, the entire quantum scheme can reduce the time complexity of quantum state tomography from \begin{document}$ O(d^{4}) $\end{document} to \begin{document}$ O(d\mathrm{poly}\log d) $\end{document} when both the condition number \begin{document}$ \kappa $\end{document} of related matrices and the reciprocal of precision \begin{document}$ \varepsilon $\end{document} are \begin{document}$ O(\mathrm{poly}\log d) $\end{document} , and quantum states of the same order \begin{document}$ O(d) $\end{document} can be simultaneously prepared. This is in contrast to the observation that quantum algorithms can reduce the time complexity of quantum state tomography to \begin{document}$O(d^3) $\end{document} when quantum states can not be efficiently prepared. In other words, the preparing of quantum states efficiently has become a bottleneck constraining the quantum acceleration.
Abstract How to efficiently encode classical data is a fundamental task in quantum computing. While many existing works treat classical data encoding as a black box in oracle-based quantum algorithms, their explicit constructions are crucial for the efficiency of practical algorithm implementations. Here, we unveil the mystery of the classical data encoding black box and study the Clifford + T complexity in constructing several typical quantum access models. For general matrices (even including sparse ones), we prove that sparse-access input models and block-encoding both require nearly linear circuit complexities relative to the matrix dimension. We also give construction protocols achieving near-optimal gate complexities. On the other hand, the construction becomes efficient with respect to the data qubit when the matrix is a linear combination of polynomial terms of efficiently implementable unitaries. As a typical example, we propose improved block-encoding when these unitaries are Pauli strings. Our protocols are built upon improved quantum state preparation and a select oracle for Pauli strings, which hold independent values. Our access model constructions provide considerable flexibility, allowing for tunable ancillary qubit numbers and offering corresponding space-time trade-offs.
Abstract Efficient implementation of fundamental matrix operations on quantum computers, such as matrix products and Hadamard operations, holds significant potential for accelerating machine learning algorithms. A critical prerequisite for quantum implementations is the effective encoding of classical data into quantum states. We propose two quantum computing frameworks for preparing the distinct encoded states corresponding to matrix operations, including the matrix product, matrix sum, matrix Hadamard product and division. Quantum algorithms based on the digital encoding computing framework are capable of implementing the matrix Hadamard operation with a time complexity of O (poly log( mn / ε )) and the matrix product with a time complexity of O (poly log( mnl / ε )), achieving an exponential speedup in contrast to the classical methods of O ( mn ) and O ( mnl ). Quantum algorithms based on the analog-encoding framework are capable of implementing the matrix Hadamard operation with a time complexity of O ( k 1 m n ⋅ poly log ( m n / ε ) ) and the matrix product with a time complexity of O ( k 2 l ⋅ poly log ( m n l / ε ) ) , where k 1 and k 2 are coefficients correlated with the elements of the matrix, achieving a square speedup in contrast to the classical counterparts. As applications, we construct an oracle that can access the trace of a matrix within logarithmic time, and propose several algorithms to respectively estimate the trace of a matrix, the trace of the product of two matrices, and the trace inner product of two matrices within logarithmic time.