Quantum Algorithms for Dense and Non-Hermitian Matrices

23 concepts11 papers1 proposal

Early breakthroughs in quantum numerical linear algebra promised exponential speedups for solving linear systems and simulating matrix equations. However, these foundational algorithms came with strict caveats: the matrices had to be sparse (containing mostly zeros) and Hermitian (self-adjoint).

In real-world applications—ranging from machine learning kernel methods and covariance analysis to relational knowledge graphs—data matrices are rarely sparse or Hermitian. They are typically dense, full-rank, and often non-square or non-Hermitian. To bridge this gap, a powerful suite of quantum techniques has emerged to exponentiate, simulate, and decompose general, dense, and non-Hermitian matrices, unlocking exponential speedups for broad data science applications.

Density Matrix Exponentiation: Turning Data into Hamiltonians

In standard quantum simulation, to evolve a quantum state under a unitary operator $U = e^{-iHt}$, the Hamiltonian $H$ must be a known, sparse matrix engineered directly into the quantum hardware's controls. But what if the matrix we want to exponentiate is an unknown, dense data matrix?

The core insight that solves this is Density Matrix Exponentiation (DME), introduced by Seth Lloyd et al. in Quantum principal component analysis. Instead of compiling a matrix into hardware gates, the data matrix is encoded directly as a quantum state—a density matrix $\rho$.

To understand why this works, imagine we have a target state $\sigma$ and multiple copies of our data state $\rho$. If we apply an infinitesimal SWAP operator ($S$) between $\sigma$ and one copy of $\rho$ for a tiny slice of time $\epsilon$, the joint state evolves. When we trace out the copy of $\rho$, the target state $\sigma$ transforms as:

$$\sigma \to \sigma - i\epsilon[\rho, \sigma] + O(\epsilon^2)$$

This is mathematically identical to the Taylor expansion of $e^{-i\rho\epsilon}\sigma e^{i\rho\epsilon}$. By repeating this interaction using fresh copies of $\rho$, we effectively force the unknown density matrix $\rho$ to act as the Hamiltonian generating the evolution. Because this process does not rely on row-by-row sparsity, it achieves a runtime that scales logarithmically with the matrix dimension, yielding an exponential speedup over classical methods for dense matrices.

This mechanism serves as a foundational engine for quantum machine learning on general datasets. For instance, Zekun Ye et al. integrated DME into quantum linear solvers to handle dense data matrices for Quantum speedup of twin support vector machines. Similarly, Nana Liu leveraged DME in Quantum machine learning for quantum anomaly detection to simulate evolution under a dataset's underlying covariance or kernel structure, allowing the quantum system to actively participate in its own structural analysis.

Bypassing Hermiticity via Matrix Embedding

While DME handles dense matrices, it still requires the matrix to be a valid density operator, which must be Hermitian. General datasets, spectral estimation problems, and directed graphs often involve non-Hermitian or non-square matrices.

To apply quantum tools like Quantum Phase Estimation (QPE)—which inherently requires a unitary or Hermitian operator—the authors of An efficient quantum algorithm for spectral estimation developed a strategy called matrix embedding. If $A$ is an arbitrary non-Hermitian matrix, it can be embedded into a larger, artificial Hermitian matrix $H_A$:

$$H_A = \begin{pmatrix} 0 & A \\ A^\dagger & 0 \end{pmatrix}$$

This extended matrix structure possesses a clean mathematical symmetry: its non-zero eigenvalues always come in pairs, $\pm \sigma_i$, where $\sigma_i$ are exactly the singular values of the original matrix $A$.

As demonstrated by Adrian Steffens et al. in Quantum singular-value decomposition of nonsparse low-rank matrices, running QPE on this extended Hermitian matrix allows a quantum computer to extract the singular values and singular vectors of non-sparse, non-square matrices. This generalizes standard quantum matrix algebra into a fully realized Quantum Singular Value Decomposition (QSVD).

This capability is particularly potent for multi-dimensional data structures. Volker Tresp and Yunpu Ma extended these subroutines to relational data in Quantum Machine Learning Algorithm for Knowledge Graphs, showing that tensor SVD can be computed with a polylogarithmic runtime relative to the graph's dimensions, bypassing the classical curse of dimensionality.

Alternative Structural and Variational Paradigms

When dense matrices are full-rank and cannot be easily compressed into low-rank representations or prepared as simple density states, researchers exploit alternative structural properties or variational approximations.

Hierarchical Matrix Block-Encoding

Instead of assuming low rank globally, many physical dense matrices (such as those derived from differential equations or smooth kernels) exhibit local decay properties. In Block-encoding dense and full-rank kernels using hierarchical matrices: applications in quantum numerical linear algebra, Bobak Kiani et al. demonstrated that dense, full-rank kernels can be efficiently block-encoded if they possess a hierarchical matrix structure—where off-diagonal blocks are low-rank. This allows the system to be solved in polylogarithmic time, matching or exceeding classical fast multipole methods.

Quantum Preconditioning

Another approach to handling difficult dense matrices is to transform them into a more mathematically favorable form before solving. Davide Orsucci and Vedran Dunjko adapted classical Cholesky decomposition to the quantum domain in On solving classes of positive-definite quantum linear systems with quadratically improved runtime in the condition number. By factoring a positive-definite matrix $A$ into $LL^\dagger$, they showed how to precondition quantum linear systems, quadratically reducing the condition number and significantly accelerating convergence.

Variational QSVD for Near-Term Hardware

Because exact QPE requires deep, fault-tolerant quantum circuits, executing it on today's noisy intermediate-scale quantum (NISQ) devices is impractical. To bring non-Hermitian matrix algebra to near-term hardware, Xin Wang et al. designed Variational Quantum Singular Value Decomposition. By leveraging the Ky Fan Theorem, the authors constructed a cost function that trains two separate quantum neural networks to iteratively learn the left and right singular vectors of an arbitrary matrix, eliminating the need for deep phase estimation circuits entirely.

Key Foundational Work

An efficient quantum algorithm for spectral estimation (2017) — contributed 7 concept elements to this direction.
Quantum principal component analysis (2014) — contributed 2 concept elements to this direction.
QSWalk: A Mathematica package for quantum stochastic walks on arbitrary graphs (2017) — contributed 2 concept elements to this direction.
History & citationVersion 1 · 2026-10-04

Current · Permanent link

View frozen version 1

Cite this direction

Latest version (a living page):

@misc{lacuna_density_matrix_exponentiation_2217174e,
  title = {density matrix exponentiation},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/density-matrix-exponentiation/rdr_2217174e036e4cbd99dec20fd6fd5376},
  note = {Latest version of a living research direction; cite a version for a fixed text. Accessed 2026-11-19},
}

This exact version (version 1, frozen text):

@misc{lacuna_density_matrix_exponentiation_2217174e_v1,
  title = {density matrix exponentiation},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/density-matrix-exponentiation/rdr_2217174e036e4cbd99dec20fd6fd5376/v/1},
  note = {Version 1, frozen 2026-10-04. Accessed 2026-11-19},
}
About

These directions overlap with this one through shared papers.

See something wrong? Report a mistake