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

Cambridge University Press eBooks

Quantum linear algebra

Alexander M. Dalzell, Sam McArdle, Mario Berta, Przemyslaw Bienias, Chi-Fang Chen, András Gilyén, Connor T. Hann, Michael J. Kastoryano, Emil T. Khabiboulline, Aleksander Kubica, Grant Salton, Samson Wang, Fernando G. S. L. Brandão

Published Apr 24, 2025• 0 citations
Publisher

Abstract

This chapter covers quantum algorithmic primitives related to linear algebra. We discuss block-encodings, a versatile and abstract access model that features in many quantum algorithms. We explain how block-encodings can be manipulated, for example by taking products or linear combinations. We discuss the techniques of quantum signal processing, qubitization, and quantum singular value transformation, which unify many quantum algorithms into a common framework.

DOI
10.1017/9781009639651.013

Related papers

From Block-encoding to Generalized Quantum Signal Processing: Principles, Algorithms and Applications

Tal Gurfinkel, Kaushika De Silva, Anuradha Mahasinghe +9 more

Modern quantum algorithms are increasingly formulated as coherent procedures for implementing polynomial transformations of operators and singular values. This perspective provides a powerful and unifying language for quantum algorithm design, connecting a wide range of distinct problems through five closely related key tools: block-encoding, qubitization, QSP, QSVT and GQSP. Block-encoding embeds non-unitary matrices into larger unitaries; qubitization converts block-encodings into structured operators; QSP, QSVT and GQSP enable polynomial transformations with near-optimal query complexity. Together, these techniques form a general toolkit for transforming matrix functions into implementable quantum circuits. This paper develops these techniques from first principles as a unified framework for constructing quantum algorithms. We apply this framework to representative applications to highlight design principles and demonstrate how distinct algorithms can be constructed from a unified sequence of operator transformations. A central contribution is a systematic decision workflow for selecting the appropriate approach according to the operator structure and the desired transformation polynomial. This perspective clarifies when direct GQSP or through qubitization, or Laurent expansion, or QSVT is most appropriate. We organize algorithmic design into an end-to-end pipeline: identifying the target matrix function, constructing an appropriate block-encoding, determining the relevant spectral domain, designing a polynomial or Laurent-polynomial approximation, synthesizing the phase factors, and translating the transformation into an executable quantum circuit. By applying this unified framework to example applications, we showcase a practical methodology for reasoning, designing, and implementing quantum algorithms based on polynomial transformations.

quant-pharXiv:2609.09977•Sep 10, 2026•0 citations

Quantum algorithms: Block encodings and quantum singular value transformations

Lier Urquijo Santamaría

[EN] An introduction to the basics of quantum computing is presented. A technique to work with matrices in a quantum computer (block encoding) is introduced, along with two methods to implement it. A new framework for designing quantum algorithms (Quantum Singular Value Transformation, QSVT) using block encodings is then explained. All of these concepts are put into practice through simulations in Mathematica.

•Jun 19, 2025•0 citations

Quantum element-wise transforms

Zane M. Rossi, Rahul Sarkar

Quantum algorithms for basic numerical linear algebraic tasks have proven essential for translating diverse problems to a unified quantum computational context. Many of these tasks---e.g., applying a function to the spectrum of a matrix embedded in a unitary process (a so-called block encoding), or taking linear combinations of block encodings---are well-addressed by techniques like quantum singular value transformation or linear combination of unitaries. However, there exist useful matrix transforms whose realization is unclear or inefficient. In this work we construct improved quantum algorithms for some of these transforms, the simplest of which is a polynomial function applied element-wise. We show the space required to compute quantum element-wise transforms (QEWTs) can be reduced exponentially in the degree of the applied function compared to prior work, and rectify errors in previous constructions. We prove novel space and query lower bounds for QEWTs, construct useful function families nearly saturating these bounds, and establish the hardness of QEWT dequantization. This represents the first sound theoretical treatment of QEWTs, and brings their resource requirements on par with other practical block encoding techniques. We present our algorithms alongside concrete applications to machine learning inference and signal processing.

quant-pharXiv:2606.06456•Jun 5, 2026•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

Quantum Signal Processing and Quantum Singular Value Transformation on U ( N )

Xi Lu, Yuan Liu, Hongwei Lin

Quantum signal processing and quantum singular value transformation are powerful tools to implement polynomial transformations of block-encoded matrices on quantum computers, and has achieved asymptotically optimal complexity in many prominent quantum algorithms. We propose a framework of quantum signal processing and quantum singular value transformation on U ( N ) , which realizes multiple polynomials simultaneously from a block-encoded input, as a generalization of those on U ( 2 ) in the original frameworks. We provide a comprehensive characterization of achievable polynomial matrices and give recursive algorithms to construct the quantum circuits that realize desired polynomial transformations. As three example applications, we propose a framework to realize bi-variate polynomial functions, demonstrate N -interval decision achieving O ( d ) query complexity with a log 2 ⁡ N improvement over iterative U ( 2 ) -QSP requiring O ( d log 2 ⁡ N ) queries, and present a quantum amplitude estimation algorithm achieving the Heisenberg limit without adaptive measurements.

arXiv:2408.01439•Quantum•Mar 27, 2026•1 citation

Scalable Quantum Computational Science: A Perspective from Block-Encodings and Polynomial Transformations

Kevin J. Joven, Elin Ranjan Das, Joel Bierman +3 more

Significant developments made in quantum hardware and error correction recently have been driving quantum computing towards practical utility. However, gaps remain between abstract quantum algorithmic development and practical applications in computational sciences. In this Perspective article, we propose several properties that scalable quantum computational science methods should possess. We further discuss how block-encodings and polynomial transformations can potentially serve as a unified framework with the desired properties. Recent advancements on these topics are presented including construction and assembly of block-encodings, and various generalizations of quantum signal processing (QSP) algorithms to perform polynomial transformations. The scalability of QSP methods on parallel and distributed quantum architectures is also highlighted. Promising applications in simulation and observable estimation in chemistry, physics, and optimization problems are presented. We hope this Perspective serves as a gentle introduction of state-of-the-art quantum algorithms to the computational science community, and inspires future development on scalable quantum computational science methodologies that bridge theory and practice.

quant-pharXiv:2511.16738•APL Computational Physics•Nov 24, 2025•2 citations
This chapter covers quantum algorithmic primitives related to linear algebra. We discuss block-encodings, a versatile and abstract access model that features in many quantum algorithms. We explain how block-encodings can be manipulated, for example by taking products or linear combinations. We discuss the techniques of quantum signal processing, qubitization, and quantum singular value transformation, which unify many quantum algorithms into a common framework.
Modern quantum algorithms are increasingly formulated as coherent procedures for implementing polynomial transformations of operators and singular values. This perspective provides a powerful and unifying language for quantum algorithm design, connecting a wide range of distinct problems through five closely related key tools: block-encoding, qubitization, QSP, QSVT and GQSP. Block-encoding embeds non-unitary matrices into larger unitaries; qubitization converts block-encodings into structured operators; QSP, QSVT and GQSP enable polynomial transformations with near-optimal query complexity. Together, these techniques form a general toolkit for transforming matrix functions into implementable quantum circuits. This paper develops these techniques from first principles as a unified framework for constructing quantum algorithms. We apply this framework to representative applications to highlight design principles and demonstrate how distinct algorithms can be constructed from a unified sequence of operator transformations. A central contribution is a systematic decision workflow for selecting the appropriate approach according to the operator structure and the desired transformation polynomial. This perspective clarifies when direct GQSP or through qubitization, or Laurent expansion, or QSVT is most appropriate. We organize algorithmic design into an end-to-end pipeline: identifying the target matrix function, constructing an appropriate block-encoding, determining the relevant spectral domain, designing a polynomial or Laurent-polynomial approximation, synthesizing the phase factors, and translating the transformation into an executable quantum circuit. By applying this unified framework to example applications, we showcase a practical methodology for reasoning, designing, and implementing quantum algorithms based on polynomial transformations.
Quantum algorithms for basic numerical linear algebraic tasks have proven essential for translating diverse problems to a unified quantum computational context. Many of these tasks---e.g., applying a function to the spectrum of a matrix embedded in a unitary process (a so-called block encoding), or taking linear combinations of block encodings---are well-addressed by techniques like quantum singular value transformation or linear combination of unitaries. However, there exist useful matrix transforms whose realization is unclear or inefficient. In this work we construct improved quantum algorithms for some of these transforms, the simplest of which is a polynomial function applied element-wise. We show the space required to compute quantum element-wise transforms (QEWTs) can be reduced exponentially in the degree of the applied function compared to prior work, and rectify errors in previous constructions. We prove novel space and query lower bounds for QEWTs, construct useful function families nearly saturating these bounds, and establish the hardness of QEWT dequantization. This represents the first sound theoretical treatment of QEWTs, and brings their resource requirements on par with other practical block encoding techniques. We present our algorithms alongside concrete applications to machine learning inference and signal processing.
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.
Quantum signal processing and quantum singular value transformation are powerful tools to implement polynomial transformations of block-encoded matrices on quantum computers, and has achieved asymptotically optimal complexity in many prominent quantum algorithms. We propose a framework of quantum signal processing and quantum singular value transformation on U ( N ) , which realizes multiple polynomials simultaneously from a block-encoded input, as a generalization of those on U ( 2 ) in the original frameworks. We provide a comprehensive characterization of achievable polynomial matrices and give recursive algorithms to construct the quantum circuits that realize desired polynomial transformations. As three example applications, we propose a framework to realize bi-variate polynomial functions, demonstrate N -interval decision achieving O ( d ) query complexity with a log 2 ⁡ N improvement over iterative U ( 2 ) -QSP requiring O ( d log 2 ⁡ N ) queries, and present a quantum amplitude estimation algorithm achieving the Heisenberg limit without adaptive measurements.
Significant developments made in quantum hardware and error correction recently have been driving quantum computing towards practical utility. However, gaps remain between abstract quantum algorithmic development and practical applications in computational sciences. In this Perspective article, we propose several properties that scalable quantum computational science methods should possess. We further discuss how block-encodings and polynomial transformations can potentially serve as a unified framework with the desired properties. Recent advancements on these topics are presented including construction and assembly of block-encodings, and various generalizations of quantum signal processing (QSP) algorithms to perform polynomial transformations. The scalability of QSP methods on parallel and distributed quantum architectures is also highlighted. Promising applications in simulation and observable estimation in chemistry, physics, and optimization problems are presented. We hope this Perspective serves as a gentle introduction of state-of-the-art quantum algorithms to the computational science community, and inspires future development on scalable quantum computational science methodologies that bridge theory and practice.