Quantum Algorithms and Quantum Optimal Transport

Overview

Optimal transport asks for the cheapest way to move one pile of goods into another arrangement, given a cost for moving each unit between locations. It underlies the Wasserstein distance, which measures how different two probability distributions are by how much work it takes to turn one into the other, and it is widely used in machine learning, logistics, and image processing.

There are two quantum angles. The first uses quantum optimization or linear algebra to solve classical optimal transport problems faster. The second, called quantum optimal transport, defines transport distances between quantum states and quantum channels, which gives new loss functions for training quantum models. Both are active research areas, and neither has produced a proven end-to-end speedup for practical problems.

The problem it solves

Determining the most efficient way to redistribute resources, mass, or probability from one configuration to a target configuration, minimizing total movement cost.

History and background

Classical optimal transport traces back to Gaspard Monge in 1781 and Leonid Kantorovich in the 1940s. The field changed in 2013 when Marco Cuturi showed that adding entropy to the problem allows fast approximate solutions with the Sinkhorn algorithm, which made the Wasserstein distance popular in machine learning.

Quantum versions appeared more recently. Golse, Mouhot, and Paul proposed a quantum Wasserstein distance in 2016 in the context of mean-field limits. De Palma, Marvian, Trevisan, and Lloyd defined a quantum Wasserstein distance of order 1 in 2021, and De Palma and Trevisan extended it to quantum channels the same year. Cole, Eckstein, Friedland, and Życzkowski studied quantum optimal transport in 2023. On the algorithms side, Chakrabarti, Huang, Li, Feizi, and Wu introduced quantum Wasserstein GANs at NeurIPS in 2019, and quantum interior point methods for linear and semidefinite programs, developed by Kerenidis and Prakash, Augustino and coauthors, and others, offer a route to solving the transport linear program.

How it works

Reformulates the classical optimal transport linear program using quantum optimization or quantum linear algebra subroutines, aiming to reduce the computational cost of large-scale transport problems.

In discrete optimal transport you have supply at several sources and demand at several sinks, and a table of costs per unit shipped between each pair. The goal is a shipping plan, a matrix of how much goes from each source to each sink, that matches supply and demand at minimum total cost. That is a linear program with one variable per source-sink pair.

Quantum linear-programming methods, such as quantum interior point algorithms, speed up certain steps by using quantum linear algebra for the matrix computations. Their advantage depends on assumptions, such as sparse, well-conditioned matrices and quantum access to data, and on the precision required, so for transport problems the benefit is conditional and has not been demonstrated at scale.

Quantum optimal transport instead asks how far apart two quantum states are. Because quantum states are density matrices, not probability lists, the cost of moving one into another has to respect their non-commuting structure. De Palma and coauthors define a distance in which states differing on one qubit are at distance of order 1, which behaves well for many-qubit systems and is used as a training objective for quantum generative models.

Step by step

1. For classical transport, write the problem as a linear program with supply and demand constraints and a cost matrix, or add entropic regularization to enable Sinkhorn iterations.
2. For a quantum solver, encode the constraint matrix and cost vector as quantum-accessible data, using block encodings or quantum random access memory.
3. Run a quantum interior point or multiplicative weights routine, in which quantum subroutines estimate the quantities needed for each iteration.
4. Read out the approximate solution or its cost, accepting that the output is an estimate and may be a state rather than the full plan.
5. For quantum optimal transport, define the cost between two quantum states as a Wasserstein-type distance and estimate it from measurement data.
6. Use the distance as a loss for a quantum generative model, and update the model parameters with a classical optimizer.

A worked example

Suppose three warehouses must supply four stores with given demands. The classical problem has 12 shipping variables and is solved instantly. For a billion sources and sinks, a quantum solver would need to access the cost matrix coherently, which is only feasible if the costs have a simple structure, and then output only a summary quantity such as the total cost.

In the quantum Wasserstein GAN of Chakrabarti and coauthors, the generator produces a quantum state and the loss is a Wasserstein-type distance between the generated and target states. On small problems, such as learning a two-qubit mixed state, the approach trains more stably than a loss based on fidelity alone.

Complexity and resources

What hardware it needs

• For quantum linear-programming approaches, fault-tolerant hardware and efficient quantum data access.
• For quantum Wasserstein GANs, near-term variational circuits suffice for small demonstrations.
• Classical optimization loops and measurement resources to estimate distances.

Applications

• Training quantum generative models with Wasserstein-type losses.
• Comparing quantum states and channels in quantum information theory.
• Logistics and resource allocation, if quantum linear-programming speedups materialize.
• Machine learning tasks that use Wasserstein distances, such as domain adaptation, if quantum access to data is available.

Limitations and caveats

• No end-to-end quantum speedup for practical transport problems has been shown.
• Classical methods such as Sinkhorn and network simplex are very fast and well engineered.
• Quantum linear-programming speedups depend on data access, condition numbers, and precision.
• Quantum Wasserstein distances are harder to compute than classical ones and several competing definitions exist.

Common misconceptions

• Quantum optimal transport is not just optimal transport run on a quantum computer. It is also a theory of distances between quantum states.
• There is no proof that a quantum computer solves transport problems exponentially faster.

How it compares

• Classical Sinkhorn iterations are the practical standard for approximate transport in machine learning.
• Quantum semidefinite programming and interior point methods supply the algorithmic tools.
• Fidelity-based losses are simpler but can be less informative for training than Wasserstein-type losses.

Real-world impact

An emerging research area connecting quantum computing to a mathematical framework already widely used in classical machine learning, economics, and logistics planning.

Why it matters

Optimal transport has become a central tool in modern machine learning, so any real quantum advantage for it would matter widely. Meanwhile, quantum Wasserstein distances give theorists and practitioners new ways to compare quantum states and train quantum models.

The topic is a good example of a research frontier in which the definitions are still being settled and claims should be read carefully.

Frequently asked questions

Keep learning

• Related algorithm: Quantum Algorithms for Semidefinite Programming
• Related algorithm: Quantum GAN (QGAN)
• Related algorithm: Quantum Gradient Descent
• Related algorithm: Quantum Kernel Estimation

This page is written for educational purposes. Complexity statements describe the best known results at the time of review (September 30, 2026), and research in this area moves quickly, so check recent papers before relying on a specific bound.

← Back to Algorithms Database