Quantum algorithms for viscosity solutions to nonlinear Hamilton-Jacobi equations based on an entropy penalisation method

This paper presents a quantum framework, based on an entropy penalisation method, that efficiently extracts viscosity solutions to nonlinear Hamilton-Jacobi equations with convex Hamiltonians by reformulating them into linear dynamics suitable for quantum simulation, thereby overcoming the typical obstacles of nonlinearity and long-time evolution in quantum PDE algorithms.

The Gist

Imagine you are trying to navigate a massive, foggy mountain range to find the absolute lowest valley (the "optimal" path). This is a problem faced by everything from self-driving cars avoiding traffic to AI learning how to play games. In mathematics, this navigation problem is described by a complex equation called the Hamilton-Jacobi equation.

The trouble is, this equation is nonlinear. In plain English, this means the rules of the game change depending on where you are. If you try to solve it on a normal computer, the "fog" (mathematical singularities) gets so thick that the computer crashes or gets stuck. If you try to solve it on a quantum computer (which is incredibly fast but usually only good at simple, linear tasks), the nonlinearity breaks the quantum machine's logic.

This paper presents a clever new "bridge" that allows us to use quantum computers to solve these messy, nonlinear mountain-navigation problems efficiently.

Here is the breakdown of their solution using simple analogies:

1. The Problem: The "Spiky" Mountain

Think of the solution to the equation as a landscape. Initially, it's smooth. But as time goes on, the landscape develops sharp spikes and cliffs (called caustics or singularities).

• Classical computers struggle here because they try to calculate the exact height at every point, and the spikes cause infinite errors.
• Quantum computers usually only understand smooth, straight lines (linear equations). They get confused by the spikes.

2. The Trick: The "Entropy Penalty" (Adding a Little Heat)

The authors use a method called Entropy Penalisation.

• The Metaphor: Imagine the mountain landscape is made of ice. The sharp spikes are dangerous. To make it safe to walk on, you turn on a tiny heater. The ice melts just enough to smooth out the sharp spikes into gentle, rolling hills.
• The Science: They add a tiny bit of "artificial viscosity" (like friction or heat) to the equation. This turns the jagged, impossible-to-solve problem into a smooth, "viscous" one.
• The Result: Even though the landscape is slightly smoothed out, the lowest valley (the answer we care about) remains in almost the exact same spot.

3. The Magic Wand: The "Cole-Hopf" Transformation

Once the landscape is smoothed out, the authors perform a mathematical magic trick called the Cole-Hopf transformation (generalized for their needs).

• The Metaphor: Imagine you have a tangled ball of yarn (the nonlinear equation). You pull one specific string, and suddenly, the whole ball unravels into a perfectly straight, long thread (a linear equation).
• Why it matters: Quantum computers are wizards at solving problems involving straight threads (linear equations), like heat spreading out or waves moving. They are terrible at tangled yarn. This transformation turns the "tangled yarn" of the mountain problem into a "straight thread" that a quantum computer can handle easily.

4. The Quantum Simulation: The "Ghost" Wave

Now that the problem is a straight thread (a linear heat-like equation), they use a quantum computer to simulate it.

• The Metaphor: Instead of calculating the height of the mountain at every single point (which takes forever), the quantum computer creates a "ghost wave" that flows over the landscape.
• The Magic: This wave naturally settles into the lowest points. Because the quantum computer is simulating a wave, it doesn't need to check every single rock; it just "feels" the shape of the whole valley at once.

5. Reading the Answer: The "Flashlight"

Once the quantum computer has the "ghost wave" (the solution), how do we get the answer? We can't just look at the whole wave; we need specific numbers.

• The Metaphor: Imagine shining a flashlight on the wave.
  • Point Value: Shine the light on one spot to see the height.
  • Gradient (Slope): Shine the light to see how steep the hill is at that spot (useful for knowing which way to turn).
  • The Minimum: The wave naturally piles up in the deepest valley. By measuring how much "light" (probability) is in the valley, the computer tells you the depth of the lowest point without needing to map the whole mountain.
  • Value at the Bottom: If you want to know the temperature or cost at the very bottom of the valley, the quantum computer can tell you that directly too.

Why is this a Big Deal?

1. No More "Curse of Dimensionality": Classical computers get slower and slower as you add more variables (like adding more dimensions to the mountain). This quantum method doesn't care how many dimensions you have; it scales efficiently.
2. Long-Term Stability: Most quantum methods for nonlinear problems only work for a split second before breaking. This method works for arbitrarily long times. You can simulate the mountain for years, and the quantum computer won't crash.
3. Real-World Applications: This isn't just math theory. It applies to:
   • Self-driving cars: Finding the safest, fastest path.
   • AI and Machine Learning: Optimizing neural networks.
   • Finance: Managing risk in complex markets.
   • Physics: Understanding how fluids move or how light bends.

In Summary:
The authors found a way to take a messy, broken, nonlinear problem that breaks both classical and quantum computers, "smooth it out" with a little heat, turn it into a straight line using a mathematical trick, and then let a quantum computer solve it like a wave. Finally, they built special tools to read the specific answers (like the lowest point) directly from the wave, skipping the need to map the entire universe.

Technical Summary

1. Problem Statement

The paper addresses the challenge of simulating nonlinear partial differential equations (PDEs) on quantum computers, specifically focusing on Hamilton-Jacobi (HJ) equations.

• The Core Difficulty: Most existing quantum algorithms are restricted to linear systems. Nonlinear PDEs, particularly HJ equations, pose two major hurdles:
  1. Nonlinearity and Singularities: HJ equations often develop finite-time singularities (caustics) where classical solutions break down. Physically relevant solutions in these regimes are viscosity solutions, which are weak solutions defined beyond the singularity.
  2. Curse of Dimensionality: Classical numerical methods for viscosity solutions (often involving high-order schemes with numerical viscosity or slope limiters) suffer from the curse of dimensionality, making them intractable for high-dimensional problems common in optimal control, mean-field games, and machine learning.
• The Gap: While some quantum algorithms exist for linear representations of nonlinear PDEs (e.g., via level set methods), they often fail to capture essential nonlinear features like shocks or caustics, or they are limited to weak nonlinearity. There is a lack of efficient quantum algorithms that can handle strong nonlinearity and weak dissipation (characteristic of viscosity solutions) while remaining valid for arbitrarily long times.

2. Methodology

The authors propose a unified framework that transforms the nonlinear viscous Hamilton-Jacobi equation into a linear parabolic PDE, which is amenable to efficient quantum simulation. The methodology consists of three main stages:

A. Linear Formulation via Entropy Penalisation

Instead of using standard numerical viscosity (which is nonlinear and difficult to simulate quantumly), the authors employ an artificial linear viscosity approach combined with the entropy penalisation method (Gomes and Valdinoci).

1. Viscous HJ Equation: They start with the regularized equation:
   $$\frac{\partial S_\nu}{\partial t} + H(t, x, \nabla S_\nu) = 2a\nu \Delta S_\nu$$
   where $\nu$ is a small viscosity coefficient.
2. Cole-Hopf Generalization:
   • For quadratic Hamiltonians, the classical Cole-Hopf transform ($S_\nu = -2\nu \ln u$) maps the nonlinear equation exactly to a linear heat equation.
   • For general convex Hamiltonians, the authors generalize this using the entropy penalisation method. They introduce a discrete-time evolution operator that approximates the nonlinear dynamics. Through a discrete-time process involving a Lagrangian $L(x,v)$, they construct a linear operator $\mathcal{L}$ such that the solution $u(t,x)$ evolves linearly:
     $$u(t, x) \approx \text{solution to a linear parabolic PDE}$$
   • The relationship is maintained via the transformation: $S_\nu(t, x) = -2\nu \ln u(t, x)$.
3. Continuous-Time Limit: The discrete-time linear scheme is shown to converge to a continuous-time linear parabolic PDE of the form:
   $$\frac{\partial u}{\partial t} = \sum \mu_i \frac{\partial u}{\partial x_i} + \sum \nu_{jk} \frac{\partial^2 u}{\partial x_j \partial x_k}$$
   This linear PDE can be simulated efficiently on quantum hardware.

B. Quantum Simulation (Schrödingerisation)

To simulate the resulting linear parabolic PDE, the authors utilize the Schrödingerisation protocol.

• Mechanism: This method embeds the solution of the non-unitary linear PDE into a unitary quantum evolution by introducing an auxiliary (ancilla) dimension.
• Implementation:
  • Analog: Uses continuous-variable (CV) quantum systems (qumodes) where the spatial variable $x$ is continuous. The PDE is mapped to a Schrödinger-like equation $du/dt = -iA(t)u$.
  • Digital: Discretizes space and time, mapping the problem to a qubit-based system. The algorithm uses block-encoding or sparse-access Hamiltonian simulation techniques.
• Normalization: A key feature of the Schrödingerisation protocol used here is its ability to estimate the normalization constant $\|u(t)\|$ as a byproduct of the simulation, which is crucial for recovering the physical solution $S_\nu$.

C. Extraction of Physical Quantities

Since full state tomography is inefficient, the paper develops specific quantum protocols to extract physically relevant observables directly from the quantum state $|u(t)\rangle$ without reconstructing the full wavefunction:

1. Pointwise Value $S(t, x_a)$: Estimated via the probability amplitude $|\langle x_a | u(t) \rangle|^2$ and the normalization constant.
2. Gradient $\nabla S(t, x_a)$: Estimated using weak measurement techniques. An ancilla state interacts with the system via a controlled-unitary gate, and the shift in the ancilla's quadrature (or qubit state) reveals the gradient.
3. Global Minimum $S_{min}$: Estimated using the normalization constant $\|u(t)\|^2$. In the limit of small $\nu$, $-\nu \ln \|u(t)\|^2$ approximates the minimum value of the solution (related to the LogSumExp function).
4. Function Value at Minimum $f(x^*)$: Estimated by measuring the expectation value $\langle u(t) | f(\hat{x}) | u(t) \rangle$. Due to the concentration of the probability density around the minimum as $\nu \to 0$, this expectation value converges to $f(x^*)$.

3. Key Contributions

• Generalized Linear Formulation: The paper extends the Cole-Hopf transform to general convex Hamiltonians (not just quadratic) using the entropy penalisation method. This allows for a linear representation of nonlinear viscous HJ equations that captures essential nonlinear features (like shocks) globally in time.
• Quantum Algorithms for Viscosity Solutions: It provides the first comprehensive set of quantum algorithms (both analog and digital) specifically designed to extract viscosity solutions and their derivatives, overcoming the nonlinearity barrier that plagues most other quantum PDE algorithms.
• Efficient Observable Extraction: The authors design protocols to extract pointwise values, gradients, global minima, and function evaluations at minima without full state tomography. These protocols rely on measuring normalization constants and weak measurements, offering polynomial speedups over classical methods in high dimensions.
• Error Analysis: The paper provides rigorous error bounds, showing that the approximation error depends on the viscosity parameter $\nu$ and the discretization step $h$. It demonstrates that for a target precision $\epsilon$, the required resources scale polynomially with the dimension $d$ (avoiding the curse of dimensionality) under specific conditions on $\nu$ and $h$.

4. Results

• Theoretical Validity: The framework is proven valid for arbitrary nonlinearity corresponding to convex Hamiltonians and for arbitrarily long times.
• Complexity:
  • The quantum simulation of the linear parabolic PDE achieves a query complexity of $\tilde{O}(\alpha_A t \ln(1/\epsilon) / \|u(t)\|)$, where $\alpha_A$ depends on the dimension and the Hamiltonian properties.
  • To achieve precision $\epsilon$ for the solution $S$, the viscosity parameter must be chosen as $\nu = O((\epsilon/d)^2)$.
  • For gradient estimation, the grid size must scale as $\Delta x = O(\epsilon/d^{3/2})$.
• Application to Burgers' Equation: The method is shown to directly apply to the forced Burgers' equation (the gradient of the HJ equation), a fundamental model in fluid dynamics.
• Numerical Stability: The use of linear artificial viscosity avoids the numerical oscillations associated with nonlinear slope limiters, ensuring convergence to the unique viscosity solution.

5. Significance

• Bridging Nonlinearity and Quantum Computing: This work represents a significant step forward in quantum computing for PDEs by demonstrating that strongly nonlinear problems with weak dissipation (viscosity solutions) can be mapped to linear quantum dynamics. This challenges the prevailing view that quantum algorithms are limited to linear or weakly nonlinear systems.
• High-Dimensional Applications: By avoiding the curse of dimensionality, this framework opens the door to solving high-dimensional problems in optimal control, mean-field games, and machine learning (e.g., Hamilton-Jacobi-Bellman equations) that are currently intractable for classical computers.
• Practical Protocols: The development of specific, efficient protocols for extracting gradients and minima makes the theoretical framework practically applicable, moving beyond just state preparation to useful physical output.
• Foundation for Future Work: The paper sets a foundation for applying these methods to specific real-world problems, such as front propagation and reinforcement learning, suggesting a new paradigm for quantum-enhanced scientific computing in nonlinear dynamics.