arXiv:2010.15776 · Physical Review A

Quantum advantage for differential equation analysis

Bobak T. Kiani, Giacomo De Palma, Dirk Englund, William M. Kaminsky, Milad Marvian, Seth Lloyd

Published Feb 14, 2022• 18 citations

Abstract

Quantum algorithms for differential equation solving, data processing, and machine learning potentially offer an exponential speedup over all known classical algorithms. However, there also exist obstacles to obtaining this potential speedup in useful problem instances. The essential obstacle for quantum differential equation solving is that outputting useful information may require difficult postprocessing, and the essential obstacle for quantum data processing and machine learning is that inputting the data is a difficult task just by itself. In this study, we demonstrate that, when combined, these difficulties solve one another. We show how the output of quantum differential equation solving can serve as the input for quantum data processing and machine learning, allowing dynamical analysis in terms of principal components, power spectra, and wavelet decompositions. To illustrate this, we consider continuous-time Markov processes on epidemiological and social networks. These quantum algorithms provide an exponential advantage over existing classical Monte Carlo methods.

DOI: 10.1103/physreva.105.022415

Related papers

Quantum algorithm for dynamic mode decomposition integrated with a quantum differential equation solver

Yuta Mizuno, Tamiki Komatsuzaki

We present a quantum algorithm that analyzes time series data simulated by a quantum differential equation solver. The proposed algorithm is a quantum version of a dynamic mode decomposition algorithm used in diverse fields such as fluid dynamics, molecular dynamics, and epidemiology. Our quantum algorithm can also compute matrix eigenvalues and eigenvectors by analyzing the corresponding linear dynamical system. Our algorithm handles a broad range of matrices, particularly those with complex eigenvalues. The complexity of our quantum algorithm is O ( poly log N ) for an N -dimensional system. This is an exponential speedup over known classical algorithms with at least O ( N ) complexity. Thus, our quantum algorithm is expected to enable high-dimensional dynamical systems analysis and large matrix eigenvalue decomposition, intractable for classical computers. Published by the American Physical Society 2024

arXiv:2310.17783Physical Review ResearchOct 11, 20245 citations

Quantum Advantage in Learning Quantum Dynamics via Fourier coefficient extraction

Barthe, Alice, Rad, Mahtab Yaghubi, Grossi, Michele +1 more

One of the key challenges in quantum machine learning is finding relevant machine learning tasks with a provable quantum advantage. A natural candidate for this is learning unknown Hamiltonian dynamics. Here, we tackle the supervised learning version of this problem, where we are given random examples of the inputs to the dynamics as classical data, paired with the expectation values of some observable after the time evolution, as corresponding output labels. The task is to replicate the corresponding input-output function. We prove that this task can yield provable exponential classical-quantum learning advantages under common complexity assumptions in natural settings. To design our quantum learning algorithms, we introduce a new method, which we term \textit{\subroutine}~algorithm for parametrized circuit functions, and which may be of independent interest. Furthermore, we discuss the limitations of generalizing our method to arbitrary quantum dynamics while maintaining provable guarantees. We explain that significant generalizations are impossible under certain complexity-theoretic assumptions, but nonetheless, we provide a heuristic kernel method, where we trade-off provable correctness for broader applicability.

arXiv:2506.17089Jun 20, 20250 citations

Quantum algorithm for nonlinear differential equations

Seth Lloyd, Giacomo De Palma, Can Gokler +5 more

Quantum computers are known to provide an exponential advantage over classical computers for the solution of linear differential equations in high-dimensional spaces. Here, we present a quantum algorithm for the solution of nonlinear differential equations. The quantum algorithm provides an exponential advantage over classical algorithms for solving nonlinear differential equations. Potential applications include the Navier-Stokes equation, plasma hydrodynamics, epidemiology, and more.

arXiv:2011.06571Nov 12, 202058 citations

An efficient quantum algorithm for generative machine learning

Xun Gao, Zhengyu Zhang, Luming Duan

A central task in the field of quantum computing is to find applications where quantum computer could provide exponential speedup over any classical computer. Machine learning represents an important field with broad applications where quantum computer may offer significant speedup. Several quantum algorithms for discriminative machine learning have been found based on efficient solving of linear algebraic problems, with potential exponential speedup in runtime under the assumption of effective input from a quantum random access memory. In machine learning, generative models represent another large class which is widely used for both supervised and unsupervised learning. Here, we propose an efficient quantum algorithm for machine learning based on a quantum generative model. We prove that our proposed model is exponentially more powerful to represent probability distributions compared with classical generative models and has exponential speedup in training and inference at least for some instances under a reasonable assumption in computational complexity theory. Our result opens a new direction for quantum machine learning and offers a remarkable example in which a quantum algorithm shows exponential improvement over any classical algorithm in an important application field.

arXiv:1711.02038Nov 6, 201717 citations

Investigating Hybrid Algorithms for Quantum Computing in Machine Learning: Improving Data Processing Speed and Handling Complex Problems

K Nandini, Davinder Pal Singh, Velayutham Rethnagurusamy Kavitha +3 more

Quantum computers acting as ML accelerators have attracted considerable interest as a promising avenue for addressing the limitations of classical computing confronted with solving complex, high-dimensional problems and handling large data sets. The most exciting aspect of quantum computing lies in its quantum advantage via techniques such as quantum parallelism, superposition, and entanglement which allows not only for rapid data processing, but also a means to resolve complex optimization problems beyond the capacity of classical algorithms. Nevertheless, the usage of quantum computing in machine learning is still a fledgling domain, with challenges concerning quantum noise, hardware restrictions, and algorithmic development. In particular, this research is concerned with the development of and study on hybrid quantum-classical algorithms that target to improve ML models in terms of computational capabilities by making use of the best of both worlds. To address this, researchers are developing hybrid algorithms that leverage the strengths of quantum computing for specific tasks, like optimization and pattern recognition, while still relying on classical computing for more flexible and larger-scale processing, ultimately achieving more efficient machine learning systems that can handle large datasets and complex problem-solving more effectively. It includes potential hybrid approaches like quantum-enhanced optimization algorithms, quantum neural networks, and quantum support vector machines, and examines how such algorithms can be used for practical ML problems including data classification, regression and clustering. Furthermore, the paper proposes that hybrid quantum algorithms offer several advantages over their classical counterparts, such as faster convergence rates, higher accuracy in high-dimensional spaces, and improved handling of non-linear and complex problem landscapes. Key advancements in the area of data processing speed and efficiency in problem-solving with and without quantum in the machine learning workflow are also highlighted in the research through comparative analysis and simulation studies. Lastly, the paper concludes by outlining the obstacles yet to be surmounted and the opportunities that lie ahead for hybrid quantum-classical algorithms, such as further improvement of quantum hardware and error mitigation methods, as well as the design of new algorithmic paradigms that seamlessly integrates the classical and quantum computing spaces.

International Conference on Networks and Cryptology (NETCRYPT)May 29, 20251 citation

Quantum Algorithms for Matrix Problems and Machine Learning

Sathyawageeswar Subramanian

This dissertation presents a study of quantum algorithms for problems that can be posed as matrix function tasks. In Chapter 1 we demonstrate a simple unifying framework for implementing of smooth functions of matrices on a quantum computer. This framework captures a variety of problems that can be solved by evaluating properties of some function of a matrix, and we identify speedups over classical algorithms for some problem classes. The analysis combines ideas from the classical theory of function approximation with the quantum algorithmic primitive of implementing linear combinations of unitary operators. In Chapter 2 we continue this study by looking at the role of sparsity of input matrices in constructing efficient quantum algorithms. We show that classically pre-processing an input matrix by spectral sparsification can be profitable for quantum Hamiltonian simulation algorithms, without compromising the simulation error or complexity. Such preprocessing incurs a one time cost linear in the size of the matrix, but can be exploited to exponentially speed up subsequent subroutines such as inversion. In Chapter 3, we give an application of this theory of matrix functions to the problem of estimating the Renyi entropy of an unknown quantum state. We combine matrix function techniques with mixed state quantum computation in the one-clean qubit model, and are able to bound of the expected runtime of our algorithm in terms of the unknown target quantity. In addition to the theme of analysing the complexity of our algorithms, we also identify instances that are of practical relevance, leading us to some problems of machine learning. In Chapter 4 we investigate kernel based learning methods using random features. We work with the QRAM input model suitable for big data, and show how matrix functions and the quantum Fourier transform can be used to devise a quantum algorithm for sampling random features that are optimised for given input data and choice of kernel. We obtain a potential exponential speedup over the best known classical algorithm even without explicit assumptions of sparsity or low rank. Finally in Chapter 5 we consider the technique of beamsearch decoding used in natural language processing. We work in the query model, and show how quantum search with advice can be used to construct a quantum search decoder that can find the optimal parse (which may for instance be a best translation, or text-to-speech transcript) at least quadratically faster than the best known classical algorithms, and obtain super-quadratic speedups in the expected runtime.

Jul 24, 20200 citations