Quantum Legendre-Fenchel Transform

Understand

We present a quantum algorithm to compute the discrete Legendre-Fenchel transform.

• Given access to a convex function evaluated at $N$ points, the algorithm outputs a quantum-mechanical representation of its corresponding discrete Legendre-Fenchel transform evaluated at $K$ points in the transformed space.
• For a fixed regular discretization of the dual space the expected running time scales as $O(\sqrt{\kappa}\,\mathrm{polylog}(N,K))$, where $\kappa$ is the condition number of the function.
• If the discretization of the dual space is chosen adaptively with $K$ equal to $N$, the running time reduces to $O(\mathrm{polylog}(N))$.