Minisymposium on Quantum Optimization and Geometry (February 2024)

Date: Thursday, February 1, 2024
Place: Centrum Wiskunde & Informatica, L016 (see here for directions)

We are organizing a half-day mini-symposium on the occasion of Harold Nieuwboer’s PhD defense, covering some recent directions in quantum optimization and algorithmic mathematics. Please feel warmly invited to participate; if you decide to do so, please let us know by sending a short e-mail to hani@math.ku.dk.

Schedule

Abstracts

Peter Bürgisser, Kaehler package for algebra of Grassmann zonoids

The Grassmann zonoid algebra G(V) of a Euclidean space V, introduced by Breiding, Buergisser, Lerario and Mathis (Adv. Math. 2022) is a graded commutative Banach algebra giving a new perspective on classical objects in convex geometry. Its elements of degree k are the real Radon measures on the Grassmannian G(k,V) of k-planes; alternatively, they can be seen as formal differences of certain zonoids in the k-th exterior power of V. The multiplication in the zonoid algebra captures the mixed volume of zonoids, and the Alexandrov-Fenchel inequality for zonoids expresses the Hodge-Riemann property of the zonoid multiplication in degree one. The reduced Grassmann zonoid algebra A(V) is the commutative graded Banach algebra obtained by factoring out the kernels of the Radon transforms for Grassmannians. Nonnegative measures with full support on projective space G(1,V) define a positive cone in A^1(V). We prove that A(V) satisfies the Kaehler package with respect to this positive cone (Poincare duality, mixed hard Lefschetz property, mixed Hodge-Riemann relations). The algebra A(V) is closely related to the algebra of even, translation-invariant, smooth valuations (with Alesker’s product), for which the properties of the Kaehler package recently were proven by Bernig, Kotrbaty and Wannerer (2023).

Omar Fawzi, Certified algorithms for equilibrium states of local quantum Hamiltonians

We design algorithms for computing expectation values of observables in the equilibrium states of local quantum Hamiltonians, both at zero and positive temperature. The algorithms are based on hierarchies of convex relaxations over the positive semidefinite cone and the matrix relative entropy cone, and give certified and converging upper and lower bounds on the desired expectation value. In the thermodynamic limit of infinite lattices, this shows that expectation values of local observables can be approximated in finite time, which contrasts with recent undecidability results about properties of infinite quantum lattice systems. In addition, when the Hamiltonian is commuting on a 2-dimensional lattice, we prove fast convergence of the hierarchy at high temperature leading to a runtime guarantee for the algorithm that is polynomial in the desired error.

Sander Gribling, Quantum speedups for linear programming via interior point methods

We describe a quantum algorithm based on an interior point method for solving a linear program with n inequality constraints on d variables. The algorithm explicitly returns a feasible solution that is ϵ-close to optimal, and runs in time sqrt(n) * poly(d, log(n), log(1/ε)), which is sublinear for tall linear programs (i.e., n ≫ d). Our algorithm speeds up the Newton step in the state-of-the-art interior point method of Lee and Sidford [FOCS ‘14]. This requires us to efficiently approximate the Hessian and gradient of the barrier function, and these are our main contributions.

To approximate the Hessian, we describe a quantum algorithm for the spectral approximation of ATA for a tall nxd matrix A. The algorithm uses leverage score sampling in combination with Grover search, and returns a δ-approximation by making O(sqrt(nd)/δ) row queries to A. This generalizes an earlier quantum speedup for graph sparsification by Apers and de Wolf [FOCS ‘20]. To approximate the gradient, we use a recent quantum algorithm for multivariate mean estimation by Cornelissen, Hamoudi and Jerbi [STOC ‘22]. While a naive implementation introduces a dependence on the condition number of the Hessian, we avoid this by pre-conditioning our random variable using our quantum algorithm for spectral approximation.