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

arXiv:1710.01984 · International Journal of Quantum Information

Efficient quantum algorithms for state measurement and linear algebra applications

Apoorva D. Patel, Anjani Priyadarsini

Published Sep 1, 2018• 4 citations
arXivHTMLPDF

Abstract

We present an algorithm for measurement of [Formula: see text]-local operators in a quantum state, which scales logarithmically both in the system size and the output accuracy. The key ingredients of the algorithm are a digital representation of the quantum state, and a decomposition of the measurement operator in a basis of operators with known discrete spectra. We then show how this algorithm can be combined with (a) Hamiltonian evolution to make quantum simulations efficient, (b) the Newton–Raphson method based solution of matrix inverse to efficiently solve linear simultaneous equations, and (c) Chebyshev expansion of matrix exponentials to efficiently evaluate thermal expectation values. The general strategy may be useful in solving many other linear algebra problems efficiently.

DOI
10.1142/s021974991850048x

Related papers

Optimization of quantum Hamiltonian evolution: From two projection operators to local Hamiltonians

Apoorva D. Patel, Anjani Priyadarsini

Given a quantum Hamiltonian and its evolution time, the corresponding unitary evolution operator can be constructed in many different ways, corresponding to different trajectories between the desired end-points and different series expansions. A choice among these possibilities can then be made to obtain the best computational complexity and control over errors. It is shown how a construction based on Grover's algorithm scales linearly in time and logarithmically in the error bound, and is exponentially superior in error complexity to the scheme based on the straightforward application of the Lie–Trotter formula. The strategy is then extended first to simulation of any Hamiltonian that is a linear combination of two projection operators, and then to any local efficiently computable Hamiltonian. The key feature is to construct an evolution in terms of the largest possible steps instead of taking small time steps. Reflection operations and Chebyshev expansions are used to efficiently control the total error on the overall evolution, without worrying about discretization errors for individual steps. We also use a digital implementation of quantum states that makes linear algebra operations rather simple to perform.

arXiv:1503.01755•International Journal of Quantum Information•Sep 13, 2016•2 citations

Efficient quantum algorithm for linear matrix differential equations and applications to open quantum systems

Sophia Simon, Dominic W. Berry, Rolando D. Somma

We present an efficient, nearly optimal quantum algorithm for solving linear matrix differential equations, with applications to the simulation of open quantum systems and beyond. For unitary or dissipative dynamics, the algorithm computes an entry of the solution matrix with query complexity $\widetilde{\mathcal{O}}(ν\mathcal{L} t/ε)$, where the constant $ν$ depends on the problem parameters, $\mathcal{L}$ involves a time integral of upper bounds on the norms of evolution operators, and $ε$ is the error. In particular, $ν\mathcal{L}$ is linear in $t$ for unitary dynamics and can be a constant for dissipative dynamics. Our result contrasts prior quantum approaches for differential equations that typically require exponential time for this problem due to the encoding in a quantum state, which can lead to exponentially small amplitudes. We demonstrate the utility of the algorithm through an end-to-end application, namely the simulation of dissipative dynamics for non-interacting fermions, which can be extended to other quantum and classical systems. We compare with classical algorithms and give evidence of polynomial quantum speedups for systems in a lattice, which become more pronounced for systems with long-range interactions and can be shown to be exponential in general. We also provide a lower bound of $Ω(ν\mathcal{L} t/ε)$ for unitary or dissipative dynamics that proves our algorithm is optimal up to logarithmic factors.

quant-pharXiv:2605.16195•May 18, 2026•2 citations

Basic linear algebra methods for quantum problems

Aaron Dayton, Kiana Gallagher, Sarah E. Huber +1 more

Making new methods for quantum problems often relies on using basic operations in linear algebra. Often these routines are hidden behind well-known libraries that have been optimized over decades. Attempting to improve on those basic routines would be highly time-consuming. We aim in this article to review those basic routines and provide a knowledge foundation for how to perform basic operations on a computer that would be inaccessible with pen and paper. Elementary details on the solutions to linear algebra problems and computational complexity are reviewed. The focus is on solving eigenvalue problems for quantum systems, but the discussion is generic to many other applications. Common matrix forms relevant to quantum systems and their solution strategies are covered. The discussion extends to computational numerical methods for which the most efficient functions exist in freely available libraries. These include eigenvalue, Schur, QR, LU, LDL, Cholesky, and singular value decompositions. The algorithms for obtaining some of these decompositions are discussed, with focus being placed on those used in modern libraries.

arXiv:2604.25625•Apr 28, 2026•1 citation

Optimal quantum measurements of expectation values of observables

Emanuel H. Knill, Gerardo Ortíz, Rolando D. Somma

Experimental characterizations of a quantum system involve the measurement of expectation values of observables for a preparable state $\ensuremath{\mid}\ensuremath{\psi}⟩$ of the quantum system. Such expectation values can be measured by repeatedly preparing $\ensuremath{\mid}\ensuremath{\psi}⟩$ and coupling the system to an apparatus. For this method, the precision of the measured value scales as $\frac{1}{\sqrt{N}}$ for $N$ repetitions of the experiment. For the problem of estimating the parameter $\ensuremath{\phi}$ in an evolution ${e}^{\ensuremath{-}i\ensuremath{\phi}H}$, it is possible to achieve precision $\frac{1}{N}$ [the quantum metrology limit; see Giovannetti et al., Phys. Rev. Lett. 96, 010401 (2006)] provided that sufficient information about $H$ and its spectrum is available. We consider the more general problem of estimating expectations of operators $A$ with minimal prior knowledge of $A$. We give explicit algorithms that approach precision $\frac{1}{N}$ given a bound on the eigenvalues of $A$ or on their tail distribution. These algorithms are particularly useful for simulating quantum systems on quantum computers because they enable efficient measurement of observables and correlation functions. Our algorithms are based on a method for efficiently measuring the complex overlap of $\ensuremath{\mid}\ensuremath{\psi}⟩$ and $U\ensuremath{\mid}\ensuremath{\psi}⟩$, where $U$ is an implementable unitary operator. We explicitly consider the issue of confidence levels in measuring observables and overlaps and show that, as expected, confidence levels can be improved exponentially with linear overhead. We further show that the algorithms given here can typically be parallelized with minimal increase in resource usage.

arXiv:quant-ph/0607019•Physical Review A•Jan 24, 2007•207 citations

Sign Embedding Quantum Algorithms for Matrix Equations and Matrix Functions

Yanqiao Wang, Jin-Peng Liu

We develop operator-output quantum algorithms for matrix equations and matrix functions using matrix-sign embeddings. For each problem, an augmented matrix $M$ is chosen so that the target operator is a block of $\text{sign}(M)$ or is recovered from blocks of $(I-\text{sign}(M))/2$. We approximate the half-plane sign by a logarithmic-sinc formula and implement the shifted inverse families by scaled multiplexing with node-dependent rebalancing. For ordinary Sylvester equations, this yields a block-encoding of the solution with query complexity linear in the relevant conditioning parameters and logarithmic in the inverse error tolerance, under either a field-of-values (FoV) gap or a strip-resolvent bound. The same method extends to generalized Sylvester and Lyapunov equations, principal square and inverse square roots, matrix geometric means, and continuous-time algebraic Riccati equations (CARE), with explicit query-complexity and block-encoding-normalization bounds that cover non-normal and non-diagonalizable cases.

quant-pharXiv:2604.25333•Apr 29, 2026•10 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
We present an algorithm for measurement of [Formula: see text]-local operators in a quantum state, which scales logarithmically both in the system size and the output accuracy. The key ingredients of the algorithm are a digital representation of the quantum state, and a decomposition of the measurement operator in a basis of operators with known discrete spectra. We then show how this algorithm can be combined with (a) Hamiltonian evolution to make quantum simulations efficient, (b) the Newton–Raphson method based solution of matrix inverse to efficiently solve linear simultaneous equations, and (c) Chebyshev expansion of matrix exponentials to efficiently evaluate thermal expectation values. The general strategy may be useful in solving many other linear algebra problems efficiently.
Given a quantum Hamiltonian and its evolution time, the corresponding unitary evolution operator can be constructed in many different ways, corresponding to different trajectories between the desired end-points and different series expansions. A choice among these possibilities can then be made to obtain the best computational complexity and control over errors. It is shown how a construction based on Grover's algorithm scales linearly in time and logarithmically in the error bound, and is exponentially superior in error complexity to the scheme based on the straightforward application of the Lie–Trotter formula. The strategy is then extended first to simulation of any Hamiltonian that is a linear combination of two projection operators, and then to any local efficiently computable Hamiltonian. The key feature is to construct an evolution in terms of the largest possible steps instead of taking small time steps. Reflection operations and Chebyshev expansions are used to efficiently control the total error on the overall evolution, without worrying about discretization errors for individual steps. We also use a digital implementation of quantum states that makes linear algebra operations rather simple to perform.
We present an efficient, nearly optimal quantum algorithm for solving linear matrix differential equations, with applications to the simulation of open quantum systems and beyond. For unitary or dissipative dynamics, the algorithm computes an entry of the solution matrix with query complexity O~(νLt/ε)\widetilde{\mathcal{O}}(ν\mathcal{L} t/ε)O(νLt/ε), where the constant ννν depends on the problem parameters, L\mathcal{L}L involves a time integral of upper bounds on the norms of evolution operators, and εεε is the error. In particular, νLν\mathcal{L}νL is linear in ttt for unitary dynamics and can be a constant for dissipative dynamics. Our result contrasts prior quantum approaches for differential equations that typically require exponential time for this problem due to the encoding in a quantum state, which can lead to exponentially small amplitudes. We demonstrate the utility of the algorithm through an end-to-end application, namely the simulation of dissipative dynamics for non-interacting fermions, which can be extended to other quantum and classical systems. We compare with classical algorithms and give evidence of polynomial quantum speedups for systems in a lattice, which become more pronounced for systems with long-range interactions and can be shown to be exponential in general. We also provide a lower bound of Ω(νLt/ε)Ω(ν\mathcal{L} t/ε)Ω(νLt/ε) for unitary or dissipative dynamics that proves our algorithm is optimal up to logarithmic factors.
Making new methods for quantum problems often relies on using basic operations in linear algebra. Often these routines are hidden behind well-known libraries that have been optimized over decades. Attempting to improve on those basic routines would be highly time-consuming. We aim in this article to review those basic routines and provide a knowledge foundation for how to perform basic operations on a computer that would be inaccessible with pen and paper. Elementary details on the solutions to linear algebra problems and computational complexity are reviewed. The focus is on solving eigenvalue problems for quantum systems, but the discussion is generic to many other applications. Common matrix forms relevant to quantum systems and their solution strategies are covered. The discussion extends to computational numerical methods for which the most efficient functions exist in freely available libraries. These include eigenvalue, Schur, QR, LU, LDL, Cholesky, and singular value decompositions. The algorithms for obtaining some of these decompositions are discussed, with focus being placed on those used in modern libraries.
Experimental characterizations of a quantum system involve the measurement of expectation values of observables for a preparable state $\ensuremath{\mid}\ensuremath{\psi}⟩$ of the quantum system. Such expectation values can be measured by repeatedly preparing $\ensuremath{\mid}\ensuremath{\psi}⟩$ and coupling the system to an apparatus. For this method, the precision of the measured value scales as 1N\frac{1}{\sqrt{N}}N​1​ for NNN repetitions of the experiment. For the problem of estimating the parameter $\ensuremath{\phi}$ in an evolution ${e}^{\ensuremath{-}i\ensuremath{\phi}H}$, it is possible to achieve precision 1N\frac{1}{N}N1​ [the quantum metrology limit; see Giovannetti et al., Phys. Rev. Lett. 96, 010401 (2006)] provided that sufficient information about HHH and its spectrum is available. We consider the more general problem of estimating expectations of operators AAA with minimal prior knowledge of AAA. We give explicit algorithms that approach precision 1N\frac{1}{N}N1​ given a bound on the eigenvalues of AAA or on their tail distribution. These algorithms are particularly useful for simulating quantum systems on quantum computers because they enable efficient measurement of observables and correlation functions. Our algorithms are based on a method for efficiently measuring the complex overlap of $\ensuremath{\mid}\ensuremath{\psi}⟩$ and $U\ensuremath{\mid}\ensuremath{\psi}⟩$, where UUU is an implementable unitary operator. We explicitly consider the issue of confidence levels in measuring observables and overlaps and show that, as expected, confidence levels can be improved exponentially with linear overhead. We further show that the algorithms given here can typically be parallelized with minimal increase in resource usage.
We develop operator-output quantum algorithms for matrix equations and matrix functions using matrix-sign embeddings. For each problem, an augmented matrix MMM is chosen so that the target operator is a block of sign(M)\text{sign}(M)sign(M) or is recovered from blocks of (I−sign(M))/2(I-\text{sign}(M))/2(I−sign(M))/2. We approximate the half-plane sign by a logarithmic-sinc formula and implement the shifted inverse families by scaled multiplexing with node-dependent rebalancing. For ordinary Sylvester equations, this yields a block-encoding of the solution with query complexity linear in the relevant conditioning parameters and logarithmic in the inverse error tolerance, under either a field-of-values (FoV) gap or a strip-resolvent bound. The same method extends to generalized Sylvester and Lyapunov equations, principal square and inverse square roots, matrix geometric means, and continuous-time algebraic Riccati equations (CARE), with explicit query-complexity and block-encoding-normalization bounds that cover non-normal and non-diagonalizable cases.
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.