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

Chinese Physics B

Preparation of digital-encoded and analog-encoded quantum states corresponding to matrix operations

Kaitian Gao, Youlong Yang, Zhenye Du

Published Jun 12, 2025• 0 citations
Publisher

Abstract

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.

DOI
10.1088/1674-1056/ade3ad

Related papers

Quantum linear system algorithm with optimal queries to initial state preparation

Guang Hao Low, Yuan Su

Quantum algorithms for linear systems produce the solution state A − 1 | b ⟩ by querying two oracles: O A that block encodes the coefficient matrix and O b that prepares the initial state. We present a quantum linear system algorithm making Θ ( 1 / p ) queries to O b , which is optimal in the success probability, and O ( κ log ⁡ ( 1 / p ) ( log ⁡ log ⁡ ( 1 / p ) + log ⁡ ( 1 / ϵ ) ) ) queries to O A , nearly optimal in all parameters including the condition number and accuracy. Notably, our complexity scaling of initial state preparation holds even when p is not known a priori . This contrasts with recent results achieving O ( κ log ⁡ ( 1 / ϵ ) ) complexity to both oracles, which, while optimal in O A , is highly suboptimal in O b as κ can be arbitrarily larger than 1 / p . In various applications such as solving differential equations, preparing ground states of operators with real spectra, and estimating and transforming eigenvalues of non-normal matrices, we can further improve the dependence on p using a block preconditioning scheme to nearly match or outperform best p

arXiv:2410.18178•Quantum•Mar 23, 2026•1 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, 2020•0 citations

Quantum analog-digital conversion

Kosuke Mitarai, Masahiro Kitagawa, Keisuke Fujii

Many quantum algorithms, such as the Harrow-Hassidim-Lloyd (HHL) algorithm, depend on oracles that efficiently encode classical data into a quantum state. The encoding of the data can be categorized into two types: analog encoding, where the data are stored as amplitudes of a state, and digital encoding, where they are stored as qubit strings. The former has been utilized to process classical data in an exponentially large space of a quantum system, whereas the latter is required to perform arithmetics on a quantum computer. Quantum algorithms such as HHL achieve quantum speedups with a sophisticated use of these two encodings. In this work, we present algorithms that convert these two encodings to one another. While quantum digital-to-analog conversions have implicitly been used in existing quantum algorithms, we reformulate it and give a generalized protocol that works probabilistically. On the other hand, we propose a deterministic algorithm that performs a quantum analog-to-digital conversion. These algorithms can be utilized to realize high-level quantum algorithms such as a nonlinear transformation of amplitudes of a quantum state. As an example, we construct a ``quantum amplitude perceptron,'' a quantum version of the neural network that hence has a possible application in the area of quantum machine learning.

arXiv:1805.11250•Physical Review A•Jan 2, 2019•81 citations

Row and column iteration methods to solve linear systems on a quantum computer

Changpeng Shao, Hua Xiang

We consider the quantum implementations of two classical iterative solvers for a system of linear equations, including the row (Kaczmarz) method which utilizes a row of the coefficient matrix in each iteration step, and the column (coordinate descent) method which uses a column instead. These two methods are widely applied in big data science due to their simple iteration schemes. We propose fast quantum algorithms for these two approaches by constructing efficient unitary operators in each iteration step based on the block-encoding technique. The construction is based on the unitaries to prepare the quantum states of rows or columns of the coefficient matrix. If the quantum states are efficiently prepared, for example, by qRAM, then the quantum iterative methods achieve an exponential speedup in the problem size $n$ over the classical versions. Meanwhile the dependence on the number of steps is linear, which is the same as the classical counterparts. The complexity of the quantum iterative linear solvers is $O({\ensuremath{\kappa}}_{s}^{2}(logn)\left(log\frac{1}{\ensuremath{\epsilon}}\right))$, where ${\ensuremath{\kappa}}_{s}$ is the scaled condition number, and $\ensuremath{\epsilon}$ is the error. The quantum iterative linear solvers do not depend on Hamiltonian simulations and quantum phase estimation, and also work for the dense case.

arXiv:1905.11686•Physical Review A•Feb 19, 2020•17 citations

Reducing the Complexity of Matrix Multiplication by Quantum Computing

Jiaqi Yao, Tianjian Huang, Tonghe Zhang +1 more

Matrix multiplication is a fundamental operation in compute-intensive tasks and a key component of modern quantum acceleration frameworks. Here we present a quantum matrix multiplication algorithm based on quantum kernels (QKMM), achieving an elementary gate complexity of \(O(N^2\log_2N)\), with amplitude encoding overhead explicitly included and without assuming a QRAM oracle. This scaling is asymptotically lower than that of the best-known classical matrix multiplication algorithm \(O(N^{2.371339})\). Building upon QKMM, we establish a family of quantum linear algebra operators, including Quantum Vector Inner Product (V${\scriptstyle 2}$V), Quantum Vector-Matrix Multiplication (V${\scriptstyle 2}$M), QKMM (M${\scriptstyle 2}$M), Quantum One-to-Many Matrix Multiplication(O${\scriptstyle 2}$M) and Quantum Sequential Matrix Multiplication (SMM), providing a unified framework from vector operations to parallel and sequential matrix transformations. Through noiseless simulations, realistic noise modelling and experiments on a superconducting quantum processor, we systematically characterize the numerical accuracy, resource requirements and hardware execution limits of this operator framework. Furthermore, we integrate SMM into deep neural-network inference, enabling intermediate features to propagate coherently across layers without repeated measurement and re-encoding. These results establish a pathway from quantum circuit-level algorithm design to end-to-end coherent computation, providing a quantum computing framework for matrix-centric compute-intensive applications.

quant-pharXiv:2602.05541•Feb 6, 2026•0 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•47 citations
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.
Quantum algorithms for linear systems produce the solution state A − 1 | b ⟩ by querying two oracles: O A that block encodes the coefficient matrix and O b that prepares the initial state. We present a quantum linear system algorithm making Θ ( 1 / p ) queries to O b , which is optimal in the success probability, and O ( κ log ⁡ ( 1 / p ) ( log ⁡ log ⁡ ( 1 / p ) + log ⁡ ( 1 / ϵ ) ) ) queries to O A , nearly optimal in all parameters including the condition number and accuracy. Notably, our complexity scaling of initial state preparation holds even when p is not known a priori . This contrasts with recent results achieving O ( κ log ⁡ ( 1 / ϵ ) ) complexity to both oracles, which, while optimal in O A , is highly suboptimal in O b as κ can be arbitrarily larger than 1 / p . In various applications such as solving differential equations, preparing ground states of operators with real spectra, and estimating and transforming eigenvalues of non-normal matrices, we can further improve the dependence on p using a block preconditioning scheme to nearly match or outperform best p
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.
Many quantum algorithms, such as the Harrow-Hassidim-Lloyd (HHL) algorithm, depend on oracles that efficiently encode classical data into a quantum state. The encoding of the data can be categorized into two types: analog encoding, where the data are stored as amplitudes of a state, and digital encoding, where they are stored as qubit strings. The former has been utilized to process classical data in an exponentially large space of a quantum system, whereas the latter is required to perform arithmetics on a quantum computer. Quantum algorithms such as HHL achieve quantum speedups with a sophisticated use of these two encodings. In this work, we present algorithms that convert these two encodings to one another. While quantum digital-to-analog conversions have implicitly been used in existing quantum algorithms, we reformulate it and give a generalized protocol that works probabilistically. On the other hand, we propose a deterministic algorithm that performs a quantum analog-to-digital conversion. These algorithms can be utilized to realize high-level quantum algorithms such as a nonlinear transformation of amplitudes of a quantum state. As an example, we construct a ``quantum amplitude perceptron,'' a quantum version of the neural network that hence has a possible application in the area of quantum machine learning.
We consider the quantum implementations of two classical iterative solvers for a system of linear equations, including the row (Kaczmarz) method which utilizes a row of the coefficient matrix in each iteration step, and the column (coordinate descent) method which uses a column instead. These two methods are widely applied in big data science due to their simple iteration schemes. We propose fast quantum algorithms for these two approaches by constructing efficient unitary operators in each iteration step based on the block-encoding technique. The construction is based on the unitaries to prepare the quantum states of rows or columns of the coefficient matrix. If the quantum states are efficiently prepared, for example, by qRAM, then the quantum iterative methods achieve an exponential speedup in the problem size nnn over the classical versions. Meanwhile the dependence on the number of steps is linear, which is the same as the classical counterparts. The complexity of the quantum iterative linear solvers is $O({\ensuremath{\kappa}}_{s}^{2}(logn)\left(log\frac{1}{\ensuremath{\epsilon}}\right))$, where ${\ensuremath{\kappa}}_{s}$ is the scaled condition number, and $\ensuremath{\epsilon}$ is the error. The quantum iterative linear solvers do not depend on Hamiltonian simulations and quantum phase estimation, and also work for the dense case.
Matrix multiplication is a fundamental operation in compute-intensive tasks and a key component of modern quantum acceleration frameworks. Here we present a quantum matrix multiplication algorithm based on quantum kernels (QKMM), achieving an elementary gate complexity of O(N2log⁡2N)O(N^2\log_2N)O(N2log2​N), with amplitude encoding overhead explicitly included and without assuming a QRAM oracle. This scaling is asymptotically lower than that of the best-known classical matrix multiplication algorithm O(N2.371339)O(N^{2.371339})O(N2.371339). Building upon QKMM, we establish a family of quantum linear algebra operators, including Quantum Vector Inner Product (V2{\scriptstyle 2}2V), Quantum Vector-Matrix Multiplication (V2{\scriptstyle 2}2M), QKMM (M2{\scriptstyle 2}2M), Quantum One-to-Many Matrix Multiplication(O2{\scriptstyle 2}2M) and Quantum Sequential Matrix Multiplication (SMM), providing a unified framework from vector operations to parallel and sequential matrix transformations. Through noiseless simulations, realistic noise modelling and experiments on a superconducting quantum processor, we systematically characterize the numerical accuracy, resource requirements and hardware execution limits of this operator framework. Furthermore, we integrate SMM into deep neural-network inference, enabling intermediate features to propagate coherently across layers without repeated measurement and re-encoding. These results establish a pathway from quantum circuit-level algorithm design to end-to-end coherent computation, providing a quantum computing framework for matrix-centric compute-intensive applications.
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.