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

SIAM Journal on Matrix Analysis and Applications

Multivariate Trace Estimation Using Quantum State Space Linear Algebra

Liron Mor-Yosef, Shashanka Ubaru, Lior Horesh C, Haim Avron

Published Jan 10, 2025• 2 citations
Publisher

Abstract

Abstract. In this paper, we present a quantum algorithm for approximating multivariate traces, i.e., the traces of matrix products. Our research is motivated by the extensive utility of multivariate traces in elucidating spectral characteristics of matrices, as well as by recent advancements in leveraging quantum computing for faster numerical linear algebra. Central to our approach is a direct translation of a multivariate trace formula into a quantum circuit, achieved through a sequence of low-level circuit construction operations. To facilitate this translation, we introduce quantum matrix states linear algebra (qMSLA), a framework tailored for the efficient generation of state preparation circuits via primitive matrix algebra operations. Our algorithm relies on sets of state preparation circuits for input matrices as its primary inputs and yields two state preparation circuits encoding the multivariate trace as output. These circuits are constructed utilizing qMSLA operations, which enact the aforementioned multivariate trace formula. We emphasize that our algorithm’s inputs consist solely of state preparation circuits, eschewing harder to synthesize constructs such as block encodings. Furthermore, our approach operates independently of the availability of specialized hardware like QRAM, underscoring its versatility and practicality.

DOI
10.1137/24m1654749

Related papers

Multivariate trace estimation using quantum state space linear algebra

Liron Mor-Yosef, Shashanka Ubaru, Lior Horesh C +1 more

In this paper, we present a quantum algorithm for approximating multivariate traces, i.e. the traces of matrix products. Our research is motivated by the extensive utility of multivariate traces in elucidating spectral characteristics of matrices, as well as by recent advancements in leveraging quantum computing for faster numerical linear algebra. Central to our approach is a direct translation of a multivariate trace formula into a quantum circuit, achieved through a sequence of low-level circuit construction operations. To facilitate this translation, we introduce \emph{quantum Matrix States Linear Algebra} (qMSLA), a framework tailored for the efficient generation of state preparation circuits via primitive matrix algebra operations. Our algorithm relies on sets of state preparation circuits for input matrices as its primary inputs and yields two state preparation circuits encoding the multivariate trace as output. These circuits are constructed utilizing qMSLA operations, which enact the aforementioned multivariate trace formula. We emphasize that our algorithm's inputs consist solely of state preparation circuits, eschewing harder to synthesize constructs such as Block Encodings. Furthermore, our approach operates independently of the availability of specialized hardware like QRAM, underscoring its versatility and practicality.

arXiv:2405.01098•May 2, 2024•0 citations

Efficient state preparation for multivariate Monte Carlo simulation

Hitomi Mori, Kosuke Mitarai, Keisuke Fujii

Quantum state preparation is a task to prepare a state with a specific function encoded in the amplitude, which is an essential subroutine in many quantum algorithms. In this paper, we focus on multivariate state preparation, as it is an important extension for many application areas. Specifically in finance, multivariate state preparation is required for multivariate Monte Carlo simulation, which is used for important numerical tasks such as risk aggregation and multi-asset derivative pricing. Using existing methods, multivariate quantum state preparation requires the number of gates exponential in the number of variables $D$. For this task, we propose a quantum algorithm that only requires the number of gates linear in $D$. Our algorithm utilizes multivariable quantum signal processing (M-QSP), a technique to perform the multivariate polynomial transformation of matrix elements. Using easily prepared block-encodings corresponding to each variable, we apply the M-QSP to construct the target function. In this way, our algorithm prepares the target state efficiently for functions achievable with M-QSP.

arXiv:2409.07336•Sep 11, 2024•0 citations

Explicit Quantum Circuits for Block Encodings of Certain Sparse Matrices

Daan Camps, Lin Lin, Roel Van Beeumen +1 more

Abstract. Many standard linear algebra problems can be solved on a quantum computer by using recently developed quantum linear algebra algorithms that make use of block encodings and quantum eigenvalue/singular value transformations. A block encoding embeds a properly scaled matrix of interest [Formula: see text] in a larger unitary transformation [Formula: see text] that can be decomposed into a product of simpler unitaries and implemented efficiently on a quantum computer. Although quantum algorithms can potentially achieve exponential speedup in solving linear algebra problems compared to the best classical algorithm, such a gain in efficiency ultimately hinges on our ability to construct an efficient quantum circuit for the block encoding of [Formula: see text], which is difficult in general, and not trivial even for well structured sparse matrices. In this paper, we give a few examples on how efficient quantum circuits can be explicitly constructed for some well structured sparse matrices and discuss a few strategies used in these constructions. We also provide implementations of these quantum circuits in MATLAB.

arXiv:2203.10236•SIAM Journal on Matrix Analysis and Applications•Mar 11, 2024•78 citations

Multivariate Quantum Signal Processing

Guang Hao Low

We develop Multivariate Quantum Signal Processing for designing matrix-valued transformations of multiple noncommuting nonnormal block-encoded matrices. Our framework equips quantum transducers with the analytic structure of multiport Infinite-Impulse-Response (IIR) filters and establishes a transfer-function methodology for designing quantum query algorithms. Efficiently computable analytic bounds that hold uniformly across the oracle promise yield efficient quantum circuits with logarithmic error dependence and near-unity success probability, paralleling the approximation-theoretic guarantees of univariate QSP/QSVT. We provide a complete characterization of achievable transfer functions and a principled library of analytic IIR components. Our modular designs greatly improve or resolve the per-oracle query complexity of open multi-oracle problems: (1) Hamiltonian simulation under $H=\sum_j H_j$ with weighted quasinorm cost $\approx t\langle\vecλ,\vec C\rangle_{1/2}+\mathcal{O}(\|\vec C\|_1\log(1/ε))$ for block-encoding normalizations $\vecλ$ and costs $\vec C$; (2) sparse simulation with optimal time--norm $Θ(\sqrt{d}\|H\|_{\rm 1\to2}t)$ and additive error dependence; (3) solving linear systems and (4) differential equations under minimal matrix assumptions with optimal weighted state-preparation and multi-term cost; (5) ground-state preparation and energy estimation; (6) generalized eigenvalue problems. We apply these to exactly simulate downfolded Hamiltonians with leading cost $t\langle\vecλ_{\rm eff},\vec C_{\rm eff}\rangle_{1/2}$ further reduced by fractional dynamic correlation energy contributions from coarse-grained Hamiltonians, and show similar classical-data-input-reduction results for multiscale graph classification via Kron reduction. We also show the online generalization with anisotropic Kalman filtering of streaming quantum data.

quant-pharXiv:2610.01125•Oct 2, 2026•0 citations

Quantum Algorithms for Multivariable Polynomial Transformations: From Efficient Synthesis to Quantum Channel Transformations

Zheyu Shen, Yusen Wu, Xiao Yuan +2 more

Polynomial transformations are basic primitives in quantum algorithms: quantum signal processing and singular value transformation compile univariate polynomials into circuits with query complexity essentially set by degree. Multivariable transformations of noncommuting matrices, however, lack a comparable synthesis theory. We develop a complete constructive theory under joint block access for all polynomials contractive on the prescribed matrix domain. Given a compact finite-state description of a degree-$D$ polynomial $P$ and $0<τ<1$, we synthesize $P$ with $(1+τ)$-optimal normalization using $O(D/\sqrtτ)$ queries, and exactly $D$ under row-block access, matching a degree lower bound. The complete circuit realization is classically computable in polynomial time with polylogarithmic dependence on accuracy. The key to our construction is a finite algorithmic Schur--Agler theorem: the coefficient recurrence defines a polynomial-dimensional continuation space supporting a complete semidefinite certificate for contractivity on the prescribed domain. Factoring this certificate yields the contractive realization underlying the query algorithm. Beyond matrix transformations, our framework lifts multivariable polynomial synthesis to quantum channel transformations. Given coherent Kraus access $K=\{K_a\}_a$, we synthesize any finite jointly contractive family of noncommutative polynomial maps $K\mapsto\{F_b(K)\}_b$ as completely positive operations, allowing coherent interference among Kraus histories. Furthermore, channel-level transformations specified by causal Choi data can be synthesized explicitly as fixed-order quantum combs. Collectively, these results point to a broader program: multivariable approximation as a language for multi-operator quantum algorithms and higher-order quantum information processing.

quant-pharXiv:2610.08714•Oct 7, 2026•0 citations

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

Kaitian Gao, Youlong Yang, Zhenye Du

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.

Chinese Physics B•Jun 12, 2025•0 citations
Abstract. In this paper, we present a quantum algorithm for approximating multivariate traces, i.e., the traces of matrix products. Our research is motivated by the extensive utility of multivariate traces in elucidating spectral characteristics of matrices, as well as by recent advancements in leveraging quantum computing for faster numerical linear algebra. Central to our approach is a direct translation of a multivariate trace formula into a quantum circuit, achieved through a sequence of low-level circuit construction operations. To facilitate this translation, we introduce quantum matrix states linear algebra (qMSLA), a framework tailored for the efficient generation of state preparation circuits via primitive matrix algebra operations. Our algorithm relies on sets of state preparation circuits for input matrices as its primary inputs and yields two state preparation circuits encoding the multivariate trace as output. These circuits are constructed utilizing qMSLA operations, which enact the aforementioned multivariate trace formula. We emphasize that our algorithm’s inputs consist solely of state preparation circuits, eschewing harder to synthesize constructs such as block encodings. Furthermore, our approach operates independently of the availability of specialized hardware like QRAM, underscoring its versatility and practicality.
In this paper, we present a quantum algorithm for approximating multivariate traces, i.e. the traces of matrix products. Our research is motivated by the extensive utility of multivariate traces in elucidating spectral characteristics of matrices, as well as by recent advancements in leveraging quantum computing for faster numerical linear algebra. Central to our approach is a direct translation of a multivariate trace formula into a quantum circuit, achieved through a sequence of low-level circuit construction operations. To facilitate this translation, we introduce \emph{quantum Matrix States Linear Algebra} (qMSLA), a framework tailored for the efficient generation of state preparation circuits via primitive matrix algebra operations. Our algorithm relies on sets of state preparation circuits for input matrices as its primary inputs and yields two state preparation circuits encoding the multivariate trace as output. These circuits are constructed utilizing qMSLA operations, which enact the aforementioned multivariate trace formula. We emphasize that our algorithm's inputs consist solely of state preparation circuits, eschewing harder to synthesize constructs such as Block Encodings. Furthermore, our approach operates independently of the availability of specialized hardware like QRAM, underscoring its versatility and practicality.
Quantum state preparation is a task to prepare a state with a specific function encoded in the amplitude, which is an essential subroutine in many quantum algorithms. In this paper, we focus on multivariate state preparation, as it is an important extension for many application areas. Specifically in finance, multivariate state preparation is required for multivariate Monte Carlo simulation, which is used for important numerical tasks such as risk aggregation and multi-asset derivative pricing. Using existing methods, multivariate quantum state preparation requires the number of gates exponential in the number of variables DDD. For this task, we propose a quantum algorithm that only requires the number of gates linear in DDD. Our algorithm utilizes multivariable quantum signal processing (M-QSP), a technique to perform the multivariate polynomial transformation of matrix elements. Using easily prepared block-encodings corresponding to each variable, we apply the M-QSP to construct the target function. In this way, our algorithm prepares the target state efficiently for functions achievable with M-QSP.
Abstract. Many standard linear algebra problems can be solved on a quantum computer by using recently developed quantum linear algebra algorithms that make use of block encodings and quantum eigenvalue/singular value transformations. A block encoding embeds a properly scaled matrix of interest [Formula: see text] in a larger unitary transformation [Formula: see text] that can be decomposed into a product of simpler unitaries and implemented efficiently on a quantum computer. Although quantum algorithms can potentially achieve exponential speedup in solving linear algebra problems compared to the best classical algorithm, such a gain in efficiency ultimately hinges on our ability to construct an efficient quantum circuit for the block encoding of [Formula: see text], which is difficult in general, and not trivial even for well structured sparse matrices. In this paper, we give a few examples on how efficient quantum circuits can be explicitly constructed for some well structured sparse matrices and discuss a few strategies used in these constructions. We also provide implementations of these quantum circuits in MATLAB.
We develop Multivariate Quantum Signal Processing for designing matrix-valued transformations of multiple noncommuting nonnormal block-encoded matrices. Our framework equips quantum transducers with the analytic structure of multiport Infinite-Impulse-Response (IIR) filters and establishes a transfer-function methodology for designing quantum query algorithms. Efficiently computable analytic bounds that hold uniformly across the oracle promise yield efficient quantum circuits with logarithmic error dependence and near-unity success probability, paralleling the approximation-theoretic guarantees of univariate QSP/QSVT. We provide a complete characterization of achievable transfer functions and a principled library of analytic IIR components. Our modular designs greatly improve or resolve the per-oracle query complexity of open multi-oracle problems: (1) Hamiltonian simulation under H=∑jHjH=\sum_j H_jH=∑j​Hj​ with weighted quasinorm cost ≈t⟨λ⃗,C⃗⟩1/2+O(∥C⃗∥1log⁡(1/ε))\approx t\langle\vecλ,\vec C\rangle_{1/2}+\mathcal{O}(\|\vec C\|_1\log(1/ε))≈t⟨λ,C⟩1/2​+O(∥C∥1​log(1/ε)) for block-encoding normalizations λ⃗\vecλλ and costs C⃗\vec CC; (2) sparse simulation with optimal time--norm Θ(d∥H∥1→2t)Θ(\sqrt{d}\|H\|_{\rm 1\to2}t)Θ(d​∥H∥1→2​t) and additive error dependence; (3) solving linear systems and (4) differential equations under minimal matrix assumptions with optimal weighted state-preparation and multi-term cost; (5) ground-state preparation and energy estimation; (6) generalized eigenvalue problems. We apply these to exactly simulate downfolded Hamiltonians with leading cost t⟨λ⃗eff,C⃗eff⟩1/2t\langle\vecλ_{\rm eff},\vec C_{\rm eff}\rangle_{1/2}t⟨λeff​,Ceff​⟩1/2​ further reduced by fractional dynamic correlation energy contributions from coarse-grained Hamiltonians, and show similar classical-data-input-reduction results for multiscale graph classification via Kron reduction. We also show the online generalization with anisotropic Kalman filtering of streaming quantum data.
Polynomial transformations are basic primitives in quantum algorithms: quantum signal processing and singular value transformation compile univariate polynomials into circuits with query complexity essentially set by degree. Multivariable transformations of noncommuting matrices, however, lack a comparable synthesis theory. We develop a complete constructive theory under joint block access for all polynomials contractive on the prescribed matrix domain. Given a compact finite-state description of a degree-DDD polynomial PPP and 0<τ<10<τ<10<τ<1, we synthesize PPP with (1+τ)(1+τ)(1+τ)-optimal normalization using O(D/τ)O(D/\sqrtτ)O(D/τ​) queries, and exactly DDD under row-block access, matching a degree lower bound. The complete circuit realization is classically computable in polynomial time with polylogarithmic dependence on accuracy. The key to our construction is a finite algorithmic Schur--Agler theorem: the coefficient recurrence defines a polynomial-dimensional continuation space supporting a complete semidefinite certificate for contractivity on the prescribed domain. Factoring this certificate yields the contractive realization underlying the query algorithm. Beyond matrix transformations, our framework lifts multivariable polynomial synthesis to quantum channel transformations. Given coherent Kraus access K={Ka}aK=\{K_a\}_aK={Ka​}a​, we synthesize any finite jointly contractive family of noncommutative polynomial maps K↦{Fb(K)}bK\mapsto\{F_b(K)\}_bK↦{Fb​(K)}b​ as completely positive operations, allowing coherent interference among Kraus histories. Furthermore, channel-level transformations specified by causal Choi data can be synthesized explicitly as fixed-order quantum combs. Collectively, these results point to a broader program: multivariable approximation as a language for multi-operator quantum algorithms and higher-order quantum information processing.
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.