Nonlinear transformation of complex amplitudes via quantum singular value transformation

Naixu Guo, Kosuke Mitarai, Keisuke Fujii

TL;DR

Quantum mechanics is fundamentally linear, making it notoriously difficult to implement nonlinear operations—like neural network activation functions—directly on a quantum computer. This paper introduces an efficient algorithm for the Nonlinear Transformation of Complex Amplitudes (NTCA) by cleverly combining block-encoding with Quantum Singular Value Transformation (QSVT). The proposed method achieves an exponential speedup in precision over previous techniques, paving the way for true deep quantum neural networks.

What Problem Does This Paper Address?

In classical computing, nonlinearity is everywhere. It is the secret sauce that allows deep neural networks to learn complex patterns and enables us to solve nonlinear differential equations. Quantum computing, however, is bound by the laws of quantum mechanics, which are strictly linear. The only standard way to introduce nonlinearity is through measurement, which collapses the quantum state and is inherently destructive.

While previous researchers found ways to apply nonlinear transformations to the eigenvalues of matrices, doing so directly to the amplitudes of a quantum state has remained a major challenge. Prior state-of-the-art methods relied on Quantum Phase Estimation (QPE) to extract amplitudes into a register, apply a function arithmetically, and uncompute. However, QPE scales poorly, requiring a number of operations that grows polynomially with the desired precision ($O(1/\epsilon)$).

The authors tackle this bottleneck, seeking a method to apply arbitrary nonlinear functions directly to state amplitudes with high efficiency and minimal qubit overhead.

Methods

The authors introduce a task called Nonlinear Transformation of Complex Amplitudes (NTCA). Given a state preparation oracle $U$ that creates a state $|0\rangle \to \sum c_k |k\rangle$ (where $c_k = x_k + iyk$), the goal is to map this to a new state where the amplitudes are transformed by arbitrary nonlinear functions, i.e., $\sum (P(x_k) + Q(y_k))|k\rangle$.

To achieve this without expensive phase estimation, the authors develop a three-step framework:

  1. Block-Encoding of Amplitudes: They construct a novel quantum circuit that embeds the real ($x_k$) or imaginary ($y_k$) parts of the state amplitudes as the singular values of a larger, hidden operator. This is done using a sequence of controlled oracle calls ($W$ and $G$).
FIG. 1. Definition of operation W in Theorem 4

By building the operator $\tilde{G} = \frac{1}{2}(G + G^\dagger)$, they effectively cancel out the unwanted imaginary parts, leaving a clean block-encoding of the real amplitudes.

  1. Quantum Singular Value Transformation (QSVT): With the amplitudes successfully cast as singular values of a block-encoded matrix, the authors apply QSVT. QSVT allows one to apply a polynomial approximation of any continuous function directly to the singular values of a block-encoded matrix extremely efficiently.
  2. Linear Combination and Post-Selection: Finally, the transformations for the real and imaginary parts are combined using a unified circuit architecture.
FIG. 4. Quantum circuit for the nonlinear transformation of part of complex amplitudes

Because the overall transformation is probabilistic, the authors utilize amplitude amplification to quadratically boost the success probability of measuring the correct, nonlinearly transformed state.

Datasets

Not discussed in the paper. This is a purely theoretical and algorithmic paper; no empirical datasets or numerical simulations were conducted.

Key Insights and Ideas

  • Amplitudes as Singular Values: The core "aha!" moment of the paper is realizing that state amplitudes can be mapped into the singular values of an artificial matrix constructed from the state preparation oracle. This bridges the gap between state manipulation and matrix manipulation, unlocking the full power of QSVT for amplitude transformation.
  • Exponential Precision Scaling: By replacing Quantum Phase Estimation with QSVT, the algorithm's dependence on precision ($\epsilon$) drops from polynomial ($1/\epsilon$) to logarithmic ($\log(1/\epsilon)$). This makes high-precision nonlinear transformations practically viable for the first time.
  • Qubit Economy: Traditional arithmetic methods require large ancilla registers to store binary representations of amplitudes. Because QSVT manipulates singular values implicitly within the quantum state space, this method drastically reduces the ancilla qubit overhead to a clean $O(n)$ scaling.

Key Results

  • Complexity Bounds: For an input dimension $N$ and functions approximated by a $d$-degree polynomial, the algorithm requires: $$O\left(d\gamma \sqrt{\frac{N}{\sum_{k=1}^N |P'(x_k) + Q'(y_k)|^2}}\right)$$ calls to the controlled state preparation oracle in expectation.

  • The Precision Speedup: For a target precision $\epsilon$, the polynomial degree scales as $d = O(\log(N/\epsilon))$. Compared to the previous state-of-the-art complexity of $\tilde{O}(N/\epsilon)$, this represents an exponential speedup with respect to precision.

  • Application to Quantum Machine Learning: The authors demonstrate how this can be used to construct a true multi-layer quantum neural network (QNN). By alternating trainable unitary weight matrices ($V^{(\ell)}$) with NTCA steps acting as activation functions (like $\tanh(x)$), deep quantum neural networks can be executed directly on quantum amplitudes.

Limitations and Future Work

  • Oracle Dependency: The algorithm relies heavily on having access to a controlled state preparation oracle ($U$) and its inverse ($U^\dagger$). In practice, constructing these oracles for arbitrary classical data can be highly complex and resource-intensive (often requiring QRAM).
  • Probabilistic Overhead: Because the transformation is non-unitary, it relies on post-selection. If the norm of the target state after the nonlinear transformation is extremely small, the amplitude amplification step will require significantly more queries, degrading performance.
  • Quantum Advantage Open Question: While the scaling is exponentially better than prior quantum methods, it remains an open question whether using complex amplitudes as neural network nodes provides a definitive, provable advantage over classical deep learning for standard classical datasets. The authors note that the most immediate advantage will likely be found when processing natively quantum data (e.g., states generated by molecular or material Hamiltonians).

Summary updated

Abstract

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 be achieved. In this work, we define a task called nonlinear transformation of complex amplitudes 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. This paper provides a promising way to introduce highly complex nonlinearity of the quantum states, which is essentially missing in quantum mechanics.
BibTeX
@misc{guo2021nonlinear,
  author = {Naixu Guo and Kosuke Mitarai and Keisuke Fujii},
  title = {{Nonlinear transformation of complex amplitudes via quantum singular value transformation}},
  year = {2021},
  eprint = {2107.10764},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2107.10764},
}
Figure