Researchers at EPFL and IBM Quantum present a quantum algorithm to compute the discrete Legendre-Fenchel Transform (LFT).
Most currently known quantum algorithms use a few basic building blocks as subroutines. Examples of these building blocks are: the Quantum Fourier Transform, Grover’s algorithm for unstructured search, or Quantum Phase Estimation. It is a major scientific challenge to identify more quantum algorithms that outperform their classical counterparts. In particular, the discovery of novel quantum subroutines could help the development of further quantum algorithms.
In this paper the team presents a quantum algorithm for a task that is known in the classical world, but had not been quantized before: the computation of the Legendre-Fenchel Transform (LFT).
The LFT, also known as convex conjugate or simply as Legendre Transform, is used in a variety of different disciplines, such as: thermodynamics, where the LFT is used to switch between potentials; classical mechanics, where the LFT serves as a bridge between the Hamiltonian and the Lagrangian formalism; and large deviation theory, where the LFT provides the link between the moment generating function, and a corresponding rate function via Cramér’s theorem.
In convex analysis, the LFT has an importance similar to that of the Fourier transform in signal processing. One of the main reasons behind the relevance of the LFT in convex analysis is the fact that the infimal convolution (also called epi-sum) is equivalent to a simple addition in the Legendre-Fenchel space, whereas the analogous property for the Fourier transform is that the convolution operator is equivalent to a product in the Fourier space.
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 discretizaton of the dual space the expected running time scales as O(√κ polylog(N,K)), where κ 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(polylog(N)).
They explain how to extend the presented algorithm to the multivariate setting and prove lower bounds for the query complexity, showing that their quantum algorithm is optimal up to polylogarithmic factors.
For certain scenarios, such as computing an expectation value of an efficiently-computable observable associated with a Legendre-Fenchel-transformed convex function, the quantum algorithm provides an exponential speedup compared to any classical algorithm.
The paper can be read there.
