Curator's Take
This article presents a significant breakthrough in quantum algorithm design by extending the powerful Quantum Signal Processing and Quantum Singular Value Transformation frameworks to work with arbitrary matrices, not just the special cases of unitary or Hermitian matrices they were previously limited to. The innovation lies in their "n-regular block encoding" technique, which cleverly transforms any matrix into a form where these established quantum algorithms can operate on its eigenvalues using only logarithmic overhead in ancillary qubits. This advancement could unlock new quantum algorithms for a much broader class of linear algebra problems, including those involving non-diagonalizable matrices that appear frequently in machine learning, differential equations, and network analysis. The work essentially removes a major bottleneck that has constrained quantum algorithm designers, potentially opening the door to quantum advantages in applications that were previously out of reach.
— Mark Eatherly
Summary
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.