⚛️ quantum physics

Linear combination of unitaries with exponential convergence

This paper introduces a Fourier extension-based method for decomposing non-unitary operators into linear combinations of unitaries with exponentially decaying coefficients, achieving exponential convergence and significantly improved subnormalization scaling compared to existing techniques.

Original authors: Peter Brearley, Thomas Howarth

Published 2026-01-27

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Peter Brearley, Thomas Howarth

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

The Big Picture: The "Non-Unitary" Problem

Imagine you are trying to build a machine that performs a specific task, like sorting a deck of cards or mixing paint. In the world of quantum computers, the "machines" (gates) they have available are like perfectly reversible magic tricks. If you do the trick forward, you can always do it backward to get exactly what you started with. These are called Unitary operators.

However, many real-world problems (like simulating how heat spreads, how a chemical decays, or how a system loses energy) are not reversible. They are "Non-Unitary." You can't just "undo" a cup of coffee cooling down.

The challenge this paper addresses is: How do we use a machine that only knows how to do reversible magic tricks to simulate something that is irreversible?

The Old Way: The "Taylor Series" Approach

Previously, scientists tried to approximate these irreversible tasks by stacking a few reversible tricks together. Think of it like trying to draw a perfect circle using only straight lines.

The Method: They used a short formula (like a few straight lines) to approximate the curve.
The Flaw: To make the circle look smoother (reduce the error), you had to make the lines shorter. But making the lines shorter made the whole drawing incredibly fragile. In quantum terms, the "signal" (the chance of the computer actually working) dropped drastically.
The Result: To get a very accurate result, you had to try the experiment millions of times because the success rate was so low. It was like trying to hit a bullseye with a wobbly arrow; you needed a huge number of arrows just to get one hit.

The New Way: The "Fourier Extension" Approach

The authors of this paper propose a smarter way to draw that circle. Instead of using short, straight lines, they use a smooth, wavy sine wave that naturally fits the shape.

The Smooth Curve: They use a mathematical technique called "Fourier Extension." Imagine you want to draw a straight line, but you are only allowed to draw it on a small piece of paper. Instead of forcing a jagged line, you imagine the paper is part of a much larger, smooth, repeating pattern (like a sine wave).
Exponential Convergence: Because this wave is so smooth, you don't need thousands of lines to get it right. You only need a few waves to get an incredibly accurate picture. In math terms, the error drops exponentially (very, very fast) as you add more waves.
The Magic Trick: They figured out how to turn these smooth waves into a combination of the reversible "magic tricks" (unitaries) that quantum computers can actually perform.

The "Subnormalisation" Problem: The Volume Knob

In this quantum world, there is a catch. When you combine these tricks, the "volume" of your signal often gets turned down. This is called subnormalisation.

The Old Problem: In the old method, if you wanted to turn the error down by a factor of 10, you had to turn the volume knob down by a factor of 100. The signal became so quiet you couldn't hear it.
The New Solution: This new method is like having a high-quality amplifier. Even if you want to make the error tiny, the volume knob only turns down very slightly.
- Analogy: Imagine the old method required you to whisper a secret so softly that you needed a million people to shout it back to hear it. The new method lets you speak at a normal volume, so you only need a few people to hear it clearly.

The "Regularisation" Trick: Finding the Best Mix

The paper also introduces a clever strategy called Regularisation.

The Situation: Because the new method uses a "smooth wave" approach, there are actually many different ways to mix the waves to get the same result. It's like having a recipe with 10 ingredients where you can swap some amounts around and still get the same taste.
The Strategy: The authors found a way to pick the specific mix of ingredients that not only tastes good (low error) but also keeps the volume as loud as possible (low subnormalisation).
The Counter-Intuitive Result: Usually, adding more ingredients (more unitaries) makes things more complex. But here, adding more waves actually gave them more freedom to adjust the recipe, allowing them to lower the volume penalty while keeping the accuracy high.

Summary of Results

Accuracy: The method gets incredibly accurate very quickly (exponential convergence).
Efficiency: The "cost" (how many times you have to run the experiment) grows very slowly, only related to the double logarithm of the error. This is a massive improvement over the old polynomial relationship.
Practicality: They tested this on a simulated quantum system (a single qubit losing energy). They showed that they could get very high accuracy without killing the signal strength, making it feasible for real quantum computers.

The Bottom Line

This paper provides a new, highly efficient "translator" that allows quantum computers to simulate messy, real-world, irreversible processes using their native, reversible tools. It does this by swapping jagged, inefficient approximations for smooth, mathematical waves, resulting in a method that is both highly accurate and much less "noisy" than previous techniques.

Technical Summary: Linear Combination of Unitaries with Exponential Convergence

Problem Statement
Linear Combination of Unitaries (LCU) is a foundational primitive in quantum computing used to construct unitary block encodings for non-unitary operators, enabling applications such as solving linear systems, simulating open quantum dynamics, and Quantum Singular Value Transformation (QSVT). However, existing general decomposition methods face a significant scalability bottleneck. The prevailing approach approximates non-unitary operators using low-order Taylor expansions (e.g., finite differences), which requires the subnormalisation factor $\alpha$ (the scaling factor required to embed the non-unitary operator into a unitary) to grow polynomially with the inverse of the target error ( $\alpha = \text{poly}(1/\epsilon)$ ). This relationship penalizes the success probability of post-selection or necessitates expensive amplitude amplification, rendering general LCU impractical for high-precision applications or those with fixed error budgets. While exact constructions exist for sparse or structured operators, efficient general techniques for arbitrary non-unitary operators remain limited.

Methodology
The authors propose a general decomposition method based on the Fourier extension method. Instead of relying on local Taylor expansions, the method approximates the identity map $f(\tau) = \tau$ on a subinterval $[-\pi/\eta, \pi/\eta]$ of a larger periodic domain $[-\pi, \pi]$ using a smooth, periodic extension.

Fourier Sine Series: The function $f(\tau) = \tau$ is approximated by a sine series $\sum a_k \sin(k\tau)$ with coefficients $a_k$ derived via continuous least-squares optimization. By choosing a domain extension factor $\eta > 1$ , the function becomes smooth and periodic on the extended domain, enabling exponential convergence of the coefficients $a_k$ as the number of terms $m$ increases.
Operator Decomposition: The sine series is applied to matrix inputs. Using the identity $\sin(k\tau H) = (e^{ik\tau H} - e^{-ik\tau H}) / 2i$ , the method expresses a Hermitian operator $H$ as a linear combination of unitaries. For a general non-unitary operator $A$ , the authors decompose it into Hermitian ( $H_1$ ) and anti-Hermitian ( $iH_2$ ) components. The final approximation involves $4m$ unitary operators:
$A \approx \sum_{k=1}^m \frac{a_k}{2\tau} \left( i e^{-ik\tau H_1} - e^{-ik\tau H_2} - i e^{ik\tau H_1} + e^{ik\tau H_2} \right)$
Coefficient Optimization: The paper introduces two strategies for selecting coefficients:
- Least-Squares (LS): Minimizes the approximation error $\epsilon$ , yielding exponential convergence.
- Regularized Fitting: Exploits the overcompleteness of the Fourier extension basis (where $\eta > 1$ ) to minimize the subnormalisation $\alpha$ (the $L_1$ -norm of coefficients) for a fixed error budget. This traces a Pareto front between error and subnormalisation, allowing for the selection of coefficients that reduce $\alpha$ without sacrificing fidelity.

Key Contributions

Exponential Convergence with Doubly Logarithmic Subnormalisation: The primary theoretical contribution is a decomposition where the approximation error decays exponentially with the number of unitaries $m$ ( $m = O(\log(1/\epsilon))$ ), while the subnormalisation $\alpha$ scales only as $O(\log \log(1/\epsilon))$ . This represents a dramatic improvement over the polynomial scaling ( $\alpha = \text{poly}(1/\epsilon)$ ) of existing finite-difference methods.
Regularization Strategy: The authors demonstrate that by treating the Fourier extension basis as overcomplete, one can solve a regularized optimization problem to find coefficient vectors that significantly reduce $\alpha$ . This allows for high-fidelity block encodings with lower subnormalisation than standard least-squares approaches.
Circuit Implementation: The paper details a quantum circuit implementation using $O(\log m)$ ancilla qubits to control the $4m$ unitary terms, achieving an $(\alpha, n_a, \epsilon)$ -block encoding.

Results
Numerical simulations using statevector representations of a Markovian open quantum system (a driven qubit with pure dephasing) validate the theoretical claims:

Convergence: The error in the block encoding exhibits exponential convergence with respect to $m$ , reaching double-precision floating-point accuracy ( $\epsilon \approx 10^{-12}$ ) with $m=16$ .
Subnormalisation: For the least-squares coefficients, $\alpha$ grows slowly ( $\approx 5$ ) as $m$ increases. However, for the regularized coefficients, $\alpha$ decreases as $m$ increases, reaching values as low as $\approx 2$ for $m=32$ and $m=64$ .
Cost Efficiency: The "cost" metric $\alpha m$ (representing the resource overhead) shows that regularized coefficients can achieve target errors with significantly lower subnormalisation than least-squares coefficients, reducing the reliance on amplitude amplification. For instance, at $m=16$ , regularized coefficients offer comparable accuracy to $m=8$ least-squares terms but with a 1.74-fold reduction in amplification requirements.

Significance and Claims
The paper claims that Fourier-LCU provides a versatile and accurate framework for non-unitary quantum computing that is not restricted by specific structural symmetries or sparsity patterns. By decoupling the error decay from the subnormalisation growth, the method offers a "global approximation strategy" that is superior to local Taylor expansions.

The authors emphasize that while the asymptotic algorithmic advantage (exponential convergence) is theoretically robust, the practical utility lies in the ability to construct high-quality block encodings with manageable subnormalisation. This is critical for hardware with fixed error budgets or noise floors, where excessive subnormalisation renders the signal indistinguishable from noise. The method serves as a robust access point for QSVT and other algorithms requiring non-unitary maps. The authors note that the end-to-end advantage is contingent on the ability to implement the underlying controlled Hamiltonian simulations ( $e^{\pm ik\tau H}$ ) at acceptable circuit depths, a problem-specific challenge that remains the logical next step for deployment.