Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

Accelerating linear algebra and machine learning with quantum computers

AG Rattew

Published Jan 1, 2025• 0 citations
Publisher

Abstract

In this thesis, I develop the theory required to use quantum computers to accelerate linear algebra and machine learning, in a manner akin to how GPUs are used today. I begin by analysing quantum random access memory (QRAM), the mechanism by which quantum algorithms can access classical (non-quantum) data. When used for linear algebra applications, I show that QRAM has substantial challenges making it harder to construct than an error-corrected quantum computer. Should QRAM prove to be unrealistic, I ask what types of classical data can be efficiently loaded into quantum computers, and prove that discretized continuous functions are one such option. Next, I introduce a framework for manipulating vectors with quantum computers. The primary result of this framework is a technique allowing for the non-linear transformations of vectors to be enacted efficiently for a broad class of functions, despite the underlying unitary (and thus linear) nature of quantum algorithms. In the final chapter, utilizing the preceding results and further developing the vector encoding framework, I demonstrate that quantum computers can accelerate inference for multilayer neural networks under a range of scenarios of QRAM feasibility. This chapter also notes a plausible path towards constructing a practically useful QRAM.

DOI
10.5287/ora-ozgvoo5rb

Related papers

Quantum Random Access Memory (QRAM) for Accelerating Machine Learning

Jincheng Zhang

The burgeoning field of machine learning (ML) is increasingly reliant on massive datasets for training complex models, particularly deep neural networks. However, the retrieval of data from conventional memory systems represents a significant bottleneck, limiting the scalability and efficiency of ML algorithms. This research proposes a Quantum Random Access Memory (QRAM) architecture designed to overcome this limitation by leveraging quantum mechanical principles. The core concept involves encoding data into qubits and utilizing quantum random access to achieve near-instantaneous data retrieval. This paper details a novel QRAM architecture, focusing on qubit arrangement, control mechanisms, and strategies for minimizing decoherence – a primary challenge in quantum computing. The theoretical framework explores the potential acceleration achievable through QRAM in deep neural network training, with the primary goal of dramatically reducing training times. We present a detailed mathematical model outlining the data encoding process, quantum access protocols, and the expected performance gains. The architecture incorporates error mitigation techniques and discusses the scalability of the design for increasingly complex datasets. The research highlights the transformative potential of QRAM in accelerating ML, addressing a fundamental constraint within the current landscape of computational learning.

•Sep 7, 2026•0 citations

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, 2020•0 citations

Quantum RAM for existing Quantum Machine Learning methods

Ainhoa Hernandez Serrano

Using quantum algorithms to carry out ML tasks is what is known as Quantum Machine Learning (QML) and the methods developed within this field have the potential to outperform their classical counterparts in solving certain learning problems. The development of the field is partly dependent on that of a functional quantum random access memory (QRAM), called for by some of the algorithms devised. Such a device would store data in a superposition and could then be queried when algorithms require it, similarly to its classical counterpart, allowing for efficient data access. Taking an axiomatic approach to QRAM, this thesis provides the main considerations, assumptions and results regarding QRAM and yields a QRAM handbook and comprehensive introduction to the literature pertaining to it.

Työväentutkimus Vuosikirja•Jan 1, 2023•0 citations

Quantum Machine Learning: Theory, Algorithms, and Practical Implementation

Hamid D. Ismail

Quantum machine learning (QML) has emerged as a rapidly developing field at the intersection of quantum computing, artificial intelligence, and data science. As quantum hardware and algorithms continue to advance, there is a growing need for a rigorous and accessible text that explains how quantum principles can be used to design, analyze, and implement machine learning models. This book is intended for graduate students, researchers, and practitioners in computer science, physics, engineering, mathematics, and related disciplines. This book provides a comprehensive introduction to the foundations and modern methods of QML. It begins with the principles of quantum information, Hilbert spaces, quantum circuits, and quantum algorithms relevant to learning tasks. Then, it develops the major paradigms of the field, including quantum data encoding, quantum feature maps and kernels, variational quantum circuits, quantum neural networks, quantum generative models, quantum reinforcement learning, quantum transfer learning, and quantum linear algebra techniques. The text emphasizes both theory and implementation, with programming examples and computational workflows using Qiskit, PennyLane, TensorFlow Quantum, and PyTorch. Additional chapters address tensor network-inspired learning, error mitigation, graphics processing unit (GPU)-accelerated simulation, benchmarking, hybrid quantum-classical architectures, and applications in chemistry, genomics, finance, optimization, and natural language processing. Distinctive in both scope and organization, the book integrates mathematical foundations, algorithmic development, software implementation, and emerging research directions within a single coherent framework, making it suitable both as a graduate-level textbook and as a practical reference for researchers working in QML.

CRC Press eBooks•Nov 4, 2026•0 citations

Quantum Algorithms for Feedforward Neural Networks

Jonathan Allcock, Chang‐Yu Hsieh, Iordanis Kerenidis +1 more

Quantum machine learning has the potential for broad industrial applications, and the development of quantum algorithms for improving the performance of neural networks is of particular interest given the central role they play in machine learning today. We present quantum algorithms for training and evaluating feedforward neural networks based on the canonical classical feedforward and backpropagation algorithms. Our algorithms rely on an efficient quantum subroutine for approximating inner products between vectors in a robust way, and on implicitly storing intermediate values in quantum random access memory for fast retrieval at later stages. The running times of our algorithms can be quadratically faster in the size of the network than their standard classical counterparts since they depend linearly on the number of neurons in the network, and not on the number of connections between neurons. Furthermore, networks trained by our quantum algorithm may have an intrinsic resilience to overfitting, as the algorithm naturally mimics the effects of classical techniques used to regularize networks. Our algorithms can also be used as the basis for new quantum-inspired classical algorithms with the same dependence on the network dimensions as their quantum counterparts but with quadratic overhead in other parameters that makes them relatively impractical.

arXiv:1812.03089•ACM Transactions on Quantum Computing•Oct 2, 2020•61 citations

Quantum Algorithms for Linear Algebra and Machine Learning.

Anupam Prakash

Most quantum algorithms offering speedups over classical algorithms are based on the three techniques of phase estimation, amplitude estimation and Hamiltonian simulation. In spite of the linear algebraic nature of the postulates of quantum mechanics, until recent work by Lloyd and coauthors cite{LMR13, LMR13a, LMR13b} no quantum algorithms achieving speedups for linear algebra or machine learning had been proposed. A quantum machine learning algorithm must address three issues: encoding of classical data into a succinct quantum representation, processing the quantum representation and extraction of classically useful information from the processed quantum state. In this dissertation, we make progress on all three aspects of the quantum machine learning problem and obtain quantum algorithms for low rank approximation and regularized least squares. The oracle $QRAM$, the standard model studied in quantum query complexity, requires time $O(sqrt{n})$ to encode vectors $v in R^{n}$ into quantum states. We propose simple hardware augmentations to the oracle $QRAM$, that enable vectors $v in R^{n}$ to be encoded in time $O(log n)$, with pre-processing. The augmented $QRAM$ incurs minimal hardware overheads, the pre-processing can be parallelized and is a flexible model that allows storage of multiple vectors and matrices. It provides a framework for designing quantum algorithms for linear algebra and machine learning. Using the augmented $QRAM$ for vector state preparation, we present two different algorithms for singular value estimation where given singular vector $ket{v}$ for $A in R^{mtimes n}$, the singular value $sigma_{i}$ is estimated within additive error $epsilon norm{A}_{F}$. The first algorithm requires time $wt{1/epsilon^{3}}$ and uses the approach for simulating $e^{-i rho}$ in cite{LMR13}. However, the analysis cite{LMR13} does not establish the coherence of outputs, we provide a qualitatively different analysis that uses the quantum Zeno effect to establish coherence and reveals the probabilistic nature of the simulation technique. The second algorithm has a running time $wt{1/epsilon}$ and uses Jordan's lemma from linear algebra and the augmented $QRAM$ to implement reflections. We use quantum singular value estimation to obtain algorithms for low rank approximation by column selection, the algorithms are based on importance sampling from the leverage score distribution. We obtain quadratic speedups for a large class of linear algebra algorithms that rely on importance sampling from the leverage score distribution including approximate least squares and $CX$ and $CUR$ decompositions. Classical algorithms for these problems require time $O(mn log n + poly(1/epsilon))$, the quantum algorithms have running time $O(sqrt{m}poly(1/epsilon, k, Delta))$ where $k, Delta$ are the rank and spectral gap. The running time of the quantum $CX$ decomposition algorithm does not depend on $m$, it is polynomial in problem parameters. We also provide quantum algorithms for $ell_{2}$ regularized regression problems, the quantum ridge regression algorithm requires time $wt{1/mu^{2} delta}$ to output a quantum state that is $delta$ close to the solution, where $mu$ is the regularization parameter.

•Jan 1, 2014•51 citations
In this thesis, I develop the theory required to use quantum computers to accelerate linear algebra and machine learning, in a manner akin to how GPUs are used today. I begin by analysing quantum random access memory (QRAM), the mechanism by which quantum algorithms can access classical (non-quantum) data. When used for linear algebra applications, I show that QRAM has substantial challenges making it harder to construct than an error-corrected quantum computer. Should QRAM prove to be unrealistic, I ask what types of classical data can be efficiently loaded into quantum computers, and prove that discretized continuous functions are one such option. Next, I introduce a framework for manipulating vectors with quantum computers. The primary result of this framework is a technique allowing for the non-linear transformations of vectors to be enacted efficiently for a broad class of functions, despite the underlying unitary (and thus linear) nature of quantum algorithms. In the final chapter, utilizing the preceding results and further developing the vector encoding framework, I demonstrate that quantum computers can accelerate inference for multilayer neural networks under a range of scenarios of QRAM feasibility. This chapter also notes a plausible path towards constructing a practically useful QRAM.
The burgeoning field of machine learning (ML) is increasingly reliant on massive datasets for training complex models, particularly deep neural networks. However, the retrieval of data from conventional memory systems represents a significant bottleneck, limiting the scalability and efficiency of ML algorithms. This research proposes a Quantum Random Access Memory (QRAM) architecture designed to overcome this limitation by leveraging quantum mechanical principles. The core concept involves encoding data into qubits and utilizing quantum random access to achieve near-instantaneous data retrieval. This paper details a novel QRAM architecture, focusing on qubit arrangement, control mechanisms, and strategies for minimizing decoherence – a primary challenge in quantum computing. The theoretical framework explores the potential acceleration achievable through QRAM in deep neural network training, with the primary goal of dramatically reducing training times. We present a detailed mathematical model outlining the data encoding process, quantum access protocols, and the expected performance gains. The architecture incorporates error mitigation techniques and discusses the scalability of the design for increasingly complex datasets. The research highlights the transformative potential of QRAM in accelerating ML, addressing a fundamental constraint within the current landscape of computational learning.
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.
Using quantum algorithms to carry out ML tasks is what is known as Quantum Machine Learning (QML) and the methods developed within this field have the potential to outperform their classical counterparts in solving certain learning problems. The development of the field is partly dependent on that of a functional quantum random access memory (QRAM), called for by some of the algorithms devised. Such a device would store data in a superposition and could then be queried when algorithms require it, similarly to its classical counterpart, allowing for efficient data access. Taking an axiomatic approach to QRAM, this thesis provides the main considerations, assumptions and results regarding QRAM and yields a QRAM handbook and comprehensive introduction to the literature pertaining to it.
Quantum machine learning (QML) has emerged as a rapidly developing field at the intersection of quantum computing, artificial intelligence, and data science. As quantum hardware and algorithms continue to advance, there is a growing need for a rigorous and accessible text that explains how quantum principles can be used to design, analyze, and implement machine learning models. This book is intended for graduate students, researchers, and practitioners in computer science, physics, engineering, mathematics, and related disciplines. This book provides a comprehensive introduction to the foundations and modern methods of QML. It begins with the principles of quantum information, Hilbert spaces, quantum circuits, and quantum algorithms relevant to learning tasks. Then, it develops the major paradigms of the field, including quantum data encoding, quantum feature maps and kernels, variational quantum circuits, quantum neural networks, quantum generative models, quantum reinforcement learning, quantum transfer learning, and quantum linear algebra techniques. The text emphasizes both theory and implementation, with programming examples and computational workflows using Qiskit, PennyLane, TensorFlow Quantum, and PyTorch. Additional chapters address tensor network-inspired learning, error mitigation, graphics processing unit (GPU)-accelerated simulation, benchmarking, hybrid quantum-classical architectures, and applications in chemistry, genomics, finance, optimization, and natural language processing. Distinctive in both scope and organization, the book integrates mathematical foundations, algorithmic development, software implementation, and emerging research directions within a single coherent framework, making it suitable both as a graduate-level textbook and as a practical reference for researchers working in QML.
Quantum machine learning has the potential for broad industrial applications, and the development of quantum algorithms for improving the performance of neural networks is of particular interest given the central role they play in machine learning today. We present quantum algorithms for training and evaluating feedforward neural networks based on the canonical classical feedforward and backpropagation algorithms. Our algorithms rely on an efficient quantum subroutine for approximating inner products between vectors in a robust way, and on implicitly storing intermediate values in quantum random access memory for fast retrieval at later stages. The running times of our algorithms can be quadratically faster in the size of the network than their standard classical counterparts since they depend linearly on the number of neurons in the network, and not on the number of connections between neurons. Furthermore, networks trained by our quantum algorithm may have an intrinsic resilience to overfitting, as the algorithm naturally mimics the effects of classical techniques used to regularize networks. Our algorithms can also be used as the basis for new quantum-inspired classical algorithms with the same dependence on the network dimensions as their quantum counterparts but with quadratic overhead in other parameters that makes them relatively impractical.
Most quantum algorithms offering speedups over classical algorithms are based on the three techniques of phase estimation, amplitude estimation and Hamiltonian simulation. In spite of the linear algebraic nature of the postulates of quantum mechanics, until recent work by Lloyd and coauthors cite{LMR13, LMR13a, LMR13b} no quantum algorithms achieving speedups for linear algebra or machine learning had been proposed. A quantum machine learning algorithm must address three issues: encoding of classical data into a succinct quantum representation, processing the quantum representation and extraction of classically useful information from the processed quantum state. In this dissertation, we make progress on all three aspects of the quantum machine learning problem and obtain quantum algorithms for low rank approximation and regularized least squares. The oracle QRAMQRAMQRAM, the standard model studied in quantum query complexity, requires time O(sqrtn)O(sqrt{n})O(sqrtn) to encode vectors vinRnv in R^{n}vinRn into quantum states. We propose simple hardware augmentations to the oracle QRAMQRAMQRAM, that enable vectors vinRnv in R^{n}vinRn to be encoded in time O(logn)O(log n)O(logn), with pre-processing. The augmented QRAMQRAMQRAM incurs minimal hardware overheads, the pre-processing can be parallelized and is a flexible model that allows storage of multiple vectors and matrices. It provides a framework for designing quantum algorithms for linear algebra and machine learning. Using the augmented QRAMQRAMQRAM for vector state preparation, we present two different algorithms for singular value estimation where given singular vector ketvket{v}ketv for AinRmtimesnA in R^{mtimes n}AinRmtimesn, the singular value sigmaisigma_{i}sigmai​ is estimated within additive error epsilonnormAFepsilon norm{A}_{F}epsilonnormAF​. The first algorithm requires time wt1/epsilon3wt{1/epsilon^{3}}wt1/epsilon3 and uses the approach for simulating e−irhoe^{-i rho}e−irho in cite{LMR13}. However, the analysis cite{LMR13} does not establish the coherence of outputs, we provide a qualitatively different analysis that uses the quantum Zeno effect to establish coherence and reveals the probabilistic nature of the simulation technique. The second algorithm has a running time wt1/epsilonwt{1/epsilon}wt1/epsilon and uses Jordan's lemma from linear algebra and the augmented QRAMQRAMQRAM to implement reflections. We use quantum singular value estimation to obtain algorithms for low rank approximation by column selection, the algorithms are based on importance sampling from the leverage score distribution. We obtain quadratic speedups for a large class of linear algebra algorithms that rely on importance sampling from the leverage score distribution including approximate least squares and CXCXCX and CURCURCUR decompositions. Classical algorithms for these problems require time O(mnlogn+poly(1/epsilon))O(mn log n + poly(1/epsilon))O(mnlogn+poly(1/epsilon)), the quantum algorithms have running time O(sqrtmpoly(1/epsilon,k,Delta))O(sqrt{m}poly(1/epsilon, k, Delta))O(sqrtmpoly(1/epsilon,k,Delta)) where k,Deltak, Deltak,Delta are the rank and spectral gap. The running time of the quantum CXCXCX decomposition algorithm does not depend on mmm, it is polynomial in problem parameters. We also provide quantum algorithms for ell2ell_{2}ell2​ regularized regression problems, the quantum ridge regression algorithm requires time wt1/mu2deltawt{1/mu^{2} delta}wt1/mu2delta to output a quantum state that is deltadeltadelta close to the solution, where mumumu is the regularization parameter.