Quantum Eigenvalue Transformations for Arbitrary Matrices

1. Problem Statement

Current quantum algorithm design frameworks, specifically Quantum Signal Processing (QSP) and Quantum Singular Value Transformation (QSVT), are powerful but limited in scope:

• QSP applies polynomial transformations to the eigenvalues of unitary matrices.
• QSVT applies polynomial transformations to the singular values of block-encoded matrices.
• The Gap: Neither method directly supports eigenvalue transformations for arbitrary non-Hermitian square matrices (especially those that are non-diagonalizable).
  • For a general block-encoded matrix $A$, applying a QSP polynomial to the encoding unitary $U_A$ does not yield a block-encoding of $P(A)$ because $U_A^k$ generally does not block-encode $A^k$ due to "garbage" terms accumulating in the ancillary registers.
  • Existing alternatives, such as Linear Combination of Unitaries (LCU) or history state constructions, suffer from high qubit overhead, complex circuit synthesis, and severe subnormalization issues (reducing success probabilities).

The authors aim to bridge this gap by providing a systematic method to apply polynomial transformations to the eigenvalues (and Jordan blocks) of any square matrix, regardless of whether it is Hermitian, unitary, or diagonalizable.

---

2. Methodology

The proposed solution relies on two core concepts: $n$-regular block encodings and a regularization construction using a quantum incrementer.

A. $n$-Regular Block Encoding

The authors define a specific property for block encodings:

• Definition: An $(a, \epsilon)$-block encoding $U$ of a matrix $A$ is called $n$-regular if $U^k$ is an $(a, k\epsilon)$-block encoding of $A^k$ for all $0 \leq k \leq n$.
• Significance: If $U$ is $n$-regular, applying a QSP polynomial $P(z)$ of degree $n$ to $U$ results in a block encoding of $P(A)$. This effectively lifts the scalar polynomial transformation to the matrix level without needing to explicitly diagonalize $A$.

B. Regularization via "Dumping Branches"

Since arbitrary block encodings are not naturally $n$-regular (powers of $U$ introduce garbage states that contaminate the top-left block), the authors propose a construction to transform any block encoding into an $n$-regular one.

• The Construction:
  1. Introduce a new register of $b = \lceil \log_2 n \rceil$ ancillary qubits.
  2. Use a Quantum Incrementer ($Q_n$) that cycles through states $|0\rangle \to |1\rangle \to \dots \to |n-1\rangle \to |0\rangle$.
  3. The circuit applies the original block encoding $U_A$ conditioned on the state of the new register. Specifically, if the original ancillas are in the "failure" state (non-zero), the incrementer shifts the new register, preventing the failure branches from ever re-interfering with the "success" branch (where original ancillas are $|0\rangle$) for up to $n$ applications.
• Mechanism: This "dumping" of branches ensures that for the first $n$ powers, the top-left block of the modified unitary remains a clean encoding of $A^k$.

C. Application to Jordan Normal Form

The method does not require $A$ to be diagonalizable. The polynomial transformation $P(A)$ is understood via the Jordan decomposition ($A = SJS^{-1}$). The construction effectively applies the polynomial to the Jordan blocks $J_i$, handling both the eigenvalues and the nilpotent parts (derivatives) correctly.

---

3. Key Contributions

1. Definition of $n$-regularity: A formal criterion ensuring that powers of a unitary encoding correspond to powers of the encoded matrix.
2. Efficient Regularization Algorithm: A construction that converts any block encoding into an $n$-regular one using only $O(\log n)$ additional ancillary qubits and $O(\log n)$ extra operations (via the incrementer).
3. General Eigenvalue Transformation: A unified framework (Theorem 6) that allows applying any polynomial $P(z)$ to an arbitrary square matrix $A$ using standard GQSP techniques, provided the $n$-regularity condition is met.
4. Theoretical Proof: Rigorous proofs showing that the error scales favorably ($\sim \sqrt{n^3}\epsilon$) and that the method works for non-diagonalizable matrices by acting on Jordan blocks.

---

4. Results

• Complexity: To implement a polynomial transformation of degree $n$ on an $n \times n$ matrix:
  • Qubits: Requires $O(\log n)$ additional ancilla qubits.
  • Operations: Requires $O(n \log n)$ elementary operations.
  • Calls: Requires $n$ calls to the original block encoding of $A$.
• Examples Demonstrated:
  • Shifted Inverse: Approximating $(cI - A)^{-1}$ using a geometric series (Taylor expansion) without needing a block encoding of $cI - A$.
  • Matrix Exponential: Implementing $e^A$ (or $e^{tA}$) with fewer copies of $A$ than previous LCHS methods, capable of handling unstable evolutions.
• Convergence: The paper provides a theorem (Theorem 7) bounding the Taylor series truncation error for functions analytic on the unit disk, ensuring $O(\log(1/\epsilon))$ copies of $A$ are sufficient for precision $\epsilon$.

---

5. Significance and Impact

• Unification: This work unifies eigenvalue and singular value transformations, extending the QSP/QSVT paradigm to the most general class of square matrices (non-Hermitian, non-diagonalizable).
• Algorithmic Efficiency: It avoids the high overhead and subnormalization issues associated with LCU-based methods, offering a more resource-efficient path for simulating non-unitary dynamics.
• Broad Applications: The technique enables quantum algorithms for:
  • Simulating general inhomogeneous differential equations.
  • Modeling dissipative dynamics (via Carleman linearization).
  • Solving partial differential equations (PDEs).
  • Simulating open quantum systems.
• Practicality: By requiring only logarithmic overhead in qubits, the method is highly scalable and compatible with near-term and fault-tolerant quantum hardware architectures.

In conclusion, the paper presents a "simple yet powerful" regularization technique that removes the primary barrier preventing QSP from being applied to arbitrary matrices, thereby significantly expanding the toolkit for quantum algorithm design.