Quantum mechanics is fundamentally linear and unitary. While this makes quantum computers exceptionally well-suited for simulating physical systems, it presents a major hurdle for general numerical algorithms. Most practical computational tasks—such as solving differential equations, optimizing machine learning models, or evaluating statistical properties—require non-unitary operations. We frequently need to invert a matrix, compute its square root, or apply a nonlinear function to its spectrum.
To bridge this gap, modern quantum algorithms rely on a powerful paradigm: Block-Encoding and Quantum Singular Value Transformation (QSVT). Together, these techniques provide a unified framework for executing non-unitary matrix algebra inside a unitary quantum computer.
The Foundation: Block-Encoding and Matrix Embedding
How do you perform a non-unitary operation on a unitary machine? The core insight is to embed the target matrix into a larger, unitary operator.
In block-encoding, an arbitrary matrix $A$ (scaled such that its spectral norm is less than or equal to 1) is placed in the upper-left block of a larger unitary matrix $U$:
$$U = \begin{pmatrix} A & \sqrt{I - AA^\dagger} \\ \sqrt{I - A^\dagger A} & -A^\dagger \end{pmatrix}$$
When this unitary $U$ acts on a quantum state where a set of auxiliary (ancilla) qubits is initialized to $|0\rangle$, the system evolves as:
$$U (|0\rangle \otimes |\psi\rangle) = |0\rangle \otimes (A|\psi\rangle) + |\perp\rangle$$
Here, $|\perp\rangle$ represents a state where the ancilla qubits are orthogonal to $|0\rangle$. By measuring the ancilla qubits and post-selecting on the $|0\rangle$ outcome, we successfully apply the non-unitary matrix $A$ to our target state $|\psi\rangle$.
As shown by Nana Liu et al., block-encoding allows quantum computers to manipulate complex matrix functions, such as matrix geometric means and algebraic Riccati equations, with exponential speedups in matrix dimension. For mixed quantum states, Zhicheng Zhang et al. demonstrate that treating density operators directly as block-encodings bypasses the need for costly condition-number dependencies, enabling highly efficient fidelity estimation for low-rank states.
Ancilla Qubits: |0⟩ -----[ ]----- |0⟩ (Success: A|ψ⟩ applied)
[ U ]
Target State: |ψ⟩ -----[ ]----- A|ψ⟩
When dealing with dense or full-rank physical systems, constructing these encodings efficiently can be challenging. To address this, Bobak Kiani et al. utilized the Linear Combination of Unitaries (LCU) framework to aggregate multiple hierarchical levels of a matrix into a single block-encoding, extending these speedups to dense operators.
Furthermore, if the matrix is not square or Hermitian, it can be embedded into a larger Hermitian matrix. As detailed by Liming Zhao et al. and Xinying Li et al., this Hermitian embedding ensures compatibility with unitary gates, allowing algorithms designed for Hermitian systems to compute matrix powers ($A^K$) and scalar properties like traces or determinants.
Transforming the Spectrum: Quantum Signal Processing and QSVT
Block-encoding gives us access to $A$, but how do we compute a function of $A$, such as $A^{-1}$ or $e^{A}$? This is where Quantum Signal Processing (QSP) and its generalization, Quantum Singular Value Transformation (QSVT), come into play.
As emphasized by Anna Lopatnikova et al., QSVT serves as a grand unifying framework for quantum algorithms. The underlying mechanism relies on a remarkable geometric property: if you interleave applications of a block-encoded matrix $U$ with precise phase rotations $\Phi = \{\phi_1, \phi_2, \dots, \phi_d\}$ applied solely to the ancilla qubits, the overall circuit constructs Chebyshev polynomials of the singular values of $A$.
Mathematically, if $A$ has a singular value decomposition $A = \sum_i \sigma_i |w_i\rangle \langle v_i|$, the interleaved sequence transforms the block-encoded operator into:
$$F(A) = \begin{pmatrix} f(A) & * \\ * & * \end{pmatrix}$$
where $f(\sigma)$ is a polynomial function applied directly to each singular value $\sigma_i$. By choosing the sequence of phase angles $\Phi$ correctly, the circuit can approximate virtually any continuous function via polynomial expansion.
For instance, Davide Orsucci et al. employ QSP to implement the matrix inverse function ($f(x) = 1/x$), achieving a quadratic runtime improvement with respect to the matrix's condition number when solving positive-definite linear systems.
|0⟩ ---[ R(φ₁) ]---[ U ]---[ R(φ₂) ]---[ U† ]---[ R(φ₃) ]--- ... --- Yields f(A)
A major practical hurdle in standard QSVT is the high memory and computational cost of calculating these rotation angles classically. To mitigate this, François Le Gall et al. developed a space-efficient version of QSVT using Chebyshev polynomial approximations and the LCU framework, demonstrating that matrix functions can be applied with constant qubit overhead.
Overcoming Linearity: Nonlinear Amplitude Transformations
While QSVT is traditionally used to transform the singular values of an operator, a fascinating extension applies these nonlinear transformations directly to the amplitudes of a quantum state. Because quantum mechanics is strictly linear, mapping an input state $\sum c_i |i\rangle$ to a nonlinearly transformed state $\sum f(c_i) |i\rangle$ is inherently difficult.
To solve this, Kosuke Mitarai et al. introduced the block-encoding of amplitudes technique. Instead of treating the state amplitudes as a vector, they encode the amplitudes into a specific subspace of a larger unitary operator. Once the amplitudes reside inside the matrix structure of an operator, standard QSVT can be applied to execute arbitrary polynomial transformations on them. This technique bypasses the linearity constraint without relying on low-probability measurements, opening new avenues for quantum machine learning and quantum data processing.
Broad Applications Across Quantum Domains
The ability to systematically apply polynomial functions to matrices has made QSVT the preferred subroutine for a wide variety of quantum applications:
- Distribution and Property Testing: András Gilyén et al. utilize QSVT to apply specific polynomial functions to operators representing probability distributions. By mapping singular values to statistical metrics, they achieve significant speedups for testing distribution closeness, independence, and entropy.
- Entropy and Fidelity Estimation: Min-Hsiu Hsieh et al. combine QSVT with trace estimation models to construct block-encodings of the power function $p^\alpha$ of a density matrix, enabling the estimation of $\alpha$-Rényi entropies with multiplicative precision.
- Trace Distance Estimation: Qisheng Wang et al. demonstrate that QSVT is an ideal tool for approximating the step-like sign function ($f(x) = \text{sign}(x)$), which is a critical mathematical component for estimating the trace distance between low-rank quantum states.
- Optimization and Game Theory: In optimization, Brandon Augustino et al. leverage block-encodings to construct the Newton systems required for quantum interior point methods. In game theory, Adam Bouland et al. integrate singular value transformations to stably implement matrix-based polynomials, providing faster quantum algorithms for finding Nash equilibria in zero-sum games.
- Complexity Theory: Beyond practical algorithms, QSVT serves as a foundational tool for theoretical proofs. Vahid R. Asadi et al. employ QSVT to integrate complex quantum subroutines, establishing the first quantum worst-case to average-case reductions for all linear problems.
Dual-Sided Matrix Access
A final piece of intuition for why these matrix frameworks are so versatile lies in how quantum states interact with operators. Classically, multiplying a matrix from the left ($A \cdot v$) or from the right ($v^T \cdot A$) can have asymmetric computational costs depending on storage layouts.
In the quantum domain, Andrew M. Childs et al. showed that a quantum computer can simulate an oracle query to a matrix's transpose ($A^T$) using a single query to the original matrix $A$. By utilizing the Quantum Fourier Transform to map input and output states, the quantum system can seamlessly access the matrix from either side without additional query overhead. This dual-sided flexibility underpins the seamless execution of the alternating projections that make QSVT work.
Key Foundational Work
Quantum anomaly detection with density estimation and multivariate Gaussian distribution (2019) — contributed 2 concept elements to this direction.
Distributional property testing in a quantum world (2019) — contributed 1 concept elements to this direction.
Recursive formulation of the multiconfigurational time-dependent Hartree method for fermions, bosons and mixtures thereof in terms of one-body density operators (2011) — contributed 1 concept elements to this direction.