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:2309.09839

Non-Linear Transformations of Quantum Amplitudes: Exponential Improvement, Generalization, and Applications

Arthur G. Rattew, Patrick Rebentrost

Published Sep 18, 2023• 3 citations
arXivHTMLPDF

Abstract

Quantum algorithms manipulate the amplitudes of quantum states to find solutions to computational problems. In this work, we present a framework for applying a general class of non-linear functions to the amplitudes of quantum states, with up-to an exponential improvement over the previous work. Our framework accepts a state preparation unitary (or block-encoding), specified as a quantum circuit, defining an $N$-dimensional quantum state. We then construct a diagonal block-encoding of the amplitudes of the quantum state, building on and simplifying previous work. Techniques from the QSVT literature are then used to process this block-encoding. The source of our exponential speedup comes from the quantum analog of importance sampling. We then derive new error-bounds relevant for end-to-end applications, giving the error in terms of $\ell_2$-norm error. We demonstrate the power of this framework with four key applications. First, our algorithm can apply the important function $\tanh(x)$ to the amplitudes of an arbitrary quantum state with at most an $\ell_2$-norm error of $ε$, with worst-case query complexity of $O(\log(N/ε))$, in comparison to the $O(\sqrt{N}\log(N/ε))$ of prior work. Second, we present an algorithm solving a new formulation of maximum finding in the unitary input model. Third, we prove efficient end-to-end complexities in applying a number of common non-linear functions to arbitrary quantum states. Finally, we generalize and unify existing quantum arithmetic-free state-preparation techniques. Our work provides an important and efficient algorithmic building block with potentially numerous applications in areas such as optimization, state preparation, quantum chemistry, and machine learning.

DOI
10.48550/arxiv.2309.09839

Related papers

Efficient quantum amplitude encoding of polynomial functions

Javier Gonzalez-Conde, Thomas W. Watts, Pablo Rodriguez-Grasa +1 more

Loading functions into quantum computers represents an essential step in several quantum algorithms, such as quantum partial differential equation solvers. Therefore, the inefficiency of this process leads to a major bottleneck for the application of these algorithms. Here, we present and compare two efficient methods for the amplitude encoding of real polynomial functions on n qubits. This case holds special relevance, as any continuous function on a closed interval can be uniformly approximated with arbitrary precision by a polynomial function. The first approach relies on the matrix product state representation (MPS). We study and benchmark the approximations of the target state when the bond dimension is assumed to be small. The second algorithm combines two subroutines. Initially we encode the linear function into the quantum registers either via its MPS or with a shallow sequence of multi-controlled gates that loads the linear function's Hadamard-Walsh series, and we explore how truncating the Hadamard-Walsh series of the linear function affects the final fidelity. Applying the inverse discrete Hadamard-Walsh transform converts the state encoding the series coefficients into an amplitude encoding of the linear function. Thus, we use this construction as a building block to achieve an exact block encoding of the amplitudes corresponding to the linear function on k0 qubits and apply the quantum singular value transformation that implements a polynomial transformation to the block encoding of the amplitudes. This unitary together with the Amplitude Amplification algorithm will enable us to prepare the quantum state that encodes the polynomial function on k0 qubits. Finally we pad n−k0 qubits to generate an approximated encoding of the polynomial on n qubits, analyzing the error depending on k0 . In this regard, our methodology proposes a method to improve the state-of-the-art complexity by introducing controllable errors.

arXiv:2307.10917•Quantum•Mar 21, 2024•40 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

Quantum Eigenvalue Processing

Guang Hao Low, Yuan Su

Many problems in linear algebra-such as those arising from non-Hermitian physics, transcorrelated quantum chemistry and differential equations-can be solved on a quan-tum computer by processing eigenvalues of the non-normal input matrices. However, the existing Quantum Singular Value Transformation (QSVT) framework is ill-suited to this task, as eigenvalues and singular values are different in general. We present a Quantum EigenValue Transformation (QEVT) framework for applying arbitrary polynomial transformations on eigenvalues of block-encoded non-normal operators, and a related Quantum EigenValue Estimation (QEVE) algorithm for operators with real spectra. QEVT has query complexity to the block encoding nearly recovering that of the QSVT for a Hermitian input, and QEVE achieves the Heisenberg-limited scaling for diagonalizable input matrices. As applications, we develop a linear differential equation solver with strictly linear time query complexity for average-case diagonalizable operators, as well as a ground state preparation algorithm that upgrades previous nearly optimal results for Hermitian Hamiltonians to diagonalizable matrices with real spectra. Underpinning our algorithms is an efficient method to prepare a quantum super-position of Faber polynomials, which generalize the nearly-best uniform approximation properties of Chebyshev polynomials to the complex plane. Of independent interest, we also develop techniques to generate$n$Fourier coefficients with 0 (poly log ($n$)) gates compared to prior approaches with linear cost.

Annual Symposium on Foundations of Computer Science•Oct 27, 2024•12 citations

Nonlinear transformation of complex amplitudes via quantum singular value transformation

Naixu Guo, Kosuke Mitarai, Keisuke Fujii

Due to the linearity of quantum operations, it is not straightforward to implement nonlinear transformations on a quantum computer, making some practical tasks like a neural network hard to achieve. In this paper, we define a task called and provide an algorithm to achieve this task. Specifically, we construct a block encoding of complex amplitudes from a state preparation unitary. This allows us to transform the complex amplitudes by using quantum singular value transformation. We evaluate the required overhead in terms of input dimension and precision, which reveals that the algorithm depends on the roughly square root of input dimension and achieves an exponential speedup on precision compared with previous work. We also discuss its possible applications to quantum machine learning, where complex amplitudes encoding classical or quantum data are processed by the proposed method. In this paper, we provide a promising way to introduce the highly complex nonlinearity of the quantum states, which is essentially missing in quantum mechanics. Published by the American Physical Society 2024

arXiv:2107.10764•Physical Review Research•Dec 2, 2024•17 citations

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 Eigenvalue Transformations for Arbitrary Matrices

Xabier Gutiérrez, Lorenzo Laneve, Mikel Sanz

Quantum Signal Processing (QSP) and Quantum Singular Value Transformation (QSVT) provide an efficient framework for implementing polynomials of block-encoded matrices, and thus offer a systematic approach to quantum algorithm design. However, despite a number of recent advances, important limitations remain. In particular, QSP can only transform unitary matrices, by applying a polynomial to their eigenvalues, while QSVT is a singular-value transformation and thus one can only obtain the polynomial of Hermitian matrices. As a consequence, these techniques do not directly apply to an arbitrary non-Hermitian matrix that is not diagonalizable. In this work, we propose a simple yet powerful method to extend these ideas to arbitrary square matrices by acting on their eigenvalues. To this end, we introduce the notion of an $n$-regular block encoding, namely, a block encoding whose $k$-th power reproduces the $k$-th power of the encoded matrix for every $0 < k < n$. We show that applying QSP to any unitary with this property is equivalent to applying a polynomial of degree at most $n$ to the block-encoded matrix, independently of its internal structure. Moreover, we provide a simple construction that transforms any block encoding into an $n$-regular one using only $O(\log n)$ ancillary qubits and operations. Finally, we show that this construction induces the desired transformation on the eigenvalues associated with the Jordan normal form of the matrix; for non-diagonalizable matrices this yields the full matrix function $P(A)$, whose action on each Jordan block involves the derivatives of $P$, and not merely the map $λ\mapsto P(λ)$.

quant-pharXiv:2604.19688•Apr 22, 2026•0 citations
Quantum algorithms manipulate the amplitudes of quantum states to find solutions to computational problems. In this work, we present a framework for applying a general class of non-linear functions to the amplitudes of quantum states, with up-to an exponential improvement over the previous work. Our framework accepts a state preparation unitary (or block-encoding), specified as a quantum circuit, defining an NNN-dimensional quantum state. We then construct a diagonal block-encoding of the amplitudes of the quantum state, building on and simplifying previous work. Techniques from the QSVT literature are then used to process this block-encoding. The source of our exponential speedup comes from the quantum analog of importance sampling. We then derive new error-bounds relevant for end-to-end applications, giving the error in terms of ℓ2\ell_2ℓ2​-norm error. We demonstrate the power of this framework with four key applications. First, our algorithm can apply the important function tanh⁡(x)\tanh(x)tanh(x) to the amplitudes of an arbitrary quantum state with at most an ℓ2\ell_2ℓ2​-norm error of εεε, with worst-case query complexity of O(log⁡(N/ε))O(\log(N/ε))O(log(N/ε)), in comparison to the O(Nlog⁡(N/ε))O(\sqrt{N}\log(N/ε))O(N​log(N/ε)) of prior work. Second, we present an algorithm solving a new formulation of maximum finding in the unitary input model. Third, we prove efficient end-to-end complexities in applying a number of common non-linear functions to arbitrary quantum states. Finally, we generalize and unify existing quantum arithmetic-free state-preparation techniques. Our work provides an important and efficient algorithmic building block with potentially numerous applications in areas such as optimization, state preparation, quantum chemistry, and machine learning.
Loading functions into quantum computers represents an essential step in several quantum algorithms, such as quantum partial differential equation solvers. Therefore, the inefficiency of this process leads to a major bottleneck for the application of these algorithms. Here, we present and compare two efficient methods for the amplitude encoding of real polynomial functions on n qubits. This case holds special relevance, as any continuous function on a closed interval can be uniformly approximated with arbitrary precision by a polynomial function. The first approach relies on the matrix product state representation (MPS). We study and benchmark the approximations of the target state when the bond dimension is assumed to be small. The second algorithm combines two subroutines. Initially we encode the linear function into the quantum registers either via its MPS or with a shallow sequence of multi-controlled gates that loads the linear function's Hadamard-Walsh series, and we explore how truncating the Hadamard-Walsh series of the linear function affects the final fidelity. Applying the inverse discrete Hadamard-Walsh transform converts the state encoding the series coefficients into an amplitude encoding of the linear function. Thus, we use this construction as a building block to achieve an exact block encoding of the amplitudes corresponding to the linear function on k0 qubits and apply the quantum singular value transformation that implements a polynomial transformation to the block encoding of the amplitudes. This unitary together with the Amplitude Amplification algorithm will enable us to prepare the quantum state that encodes the polynomial function on k0 qubits. Finally we pad n−k0 qubits to generate an approximated encoding of the polynomial on n qubits, analyzing the error depending on k0 . In this regard, our methodology proposes a method to improve the state-of-the-art complexity by introducing controllable errors.
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.
Many problems in linear algebra-such as those arising from non-Hermitian physics, transcorrelated quantum chemistry and differential equations-can be solved on a quan-tum computer by processing eigenvalues of the non-normal input matrices. However, the existing Quantum Singular Value Transformation (QSVT) framework is ill-suited to this task, as eigenvalues and singular values are different in general. We present a Quantum EigenValue Transformation (QEVT) framework for applying arbitrary polynomial transformations on eigenvalues of block-encoded non-normal operators, and a related Quantum EigenValue Estimation (QEVE) algorithm for operators with real spectra. QEVT has query complexity to the block encoding nearly recovering that of the QSVT for a Hermitian input, and QEVE achieves the Heisenberg-limited scaling for diagonalizable input matrices. As applications, we develop a linear differential equation solver with strictly linear time query complexity for average-case diagonalizable operators, as well as a ground state preparation algorithm that upgrades previous nearly optimal results for Hermitian Hamiltonians to diagonalizable matrices with real spectra. Underpinning our algorithms is an efficient method to prepare a quantum super-position of Faber polynomials, which generalize the nearly-best uniform approximation properties of Chebyshev polynomials to the complex plane. Of independent interest, we also develop techniques to generatennnFourier coefficients with 0 (poly log (nnn)) gates compared to prior approaches with linear cost.
Due to the linearity of quantum operations, it is not straightforward to implement nonlinear transformations on a quantum computer, making some practical tasks like a neural network hard to achieve. In this paper, we define a task called and provide an algorithm to achieve this task. Specifically, we construct a block encoding of complex amplitudes from a state preparation unitary. This allows us to transform the complex amplitudes by using quantum singular value transformation. We evaluate the required overhead in terms of input dimension and precision, which reveals that the algorithm depends on the roughly square root of input dimension and achieves an exponential speedup on precision compared with previous work. We also discuss its possible applications to quantum machine learning, where complex amplitudes encoding classical or quantum data are processed by the proposed method. In this paper, we provide a promising way to introduce the highly complex nonlinearity of the quantum states, which is essentially missing in quantum mechanics. Published by the American Physical Society 2024
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 Signal Processing (QSP) and Quantum Singular Value Transformation (QSVT) provide an efficient framework for implementing polynomials of block-encoded matrices, and thus offer a systematic approach to quantum algorithm design. However, despite a number of recent advances, important limitations remain. In particular, QSP can only transform unitary matrices, by applying a polynomial to their eigenvalues, while QSVT is a singular-value transformation and thus one can only obtain the polynomial of Hermitian matrices. As a consequence, these techniques do not directly apply to an arbitrary non-Hermitian matrix that is not diagonalizable. In this work, we propose a simple yet powerful method to extend these ideas to arbitrary square matrices by acting on their eigenvalues. To this end, we introduce the notion of an nnn-regular block encoding, namely, a block encoding whose kkk-th power reproduces the kkk-th power of the encoded matrix for every 0<k<n0 < k < n0<k<n. We show that applying QSP to any unitary with this property is equivalent to applying a polynomial of degree at most nnn to the block-encoded matrix, independently of its internal structure. Moreover, we provide a simple construction that transforms any block encoding into an nnn-regular one using only O(log⁡n)O(\log n)O(logn) ancillary qubits and operations. Finally, we show that this construction induces the desired transformation on the eigenvalues associated with the Jordan normal form of the matrix; for non-diagonalizable matrices this yields the full matrix function P(A)P(A)P(A), whose action on each Jordan block involves the derivatives of PPP, and not merely the map λ↦P(λ)λ\mapsto P(λ)λ↦P(λ).