Southwest Quantum Information and Technology

Optimizing over orthogonal groups with quantum states

Presenting Author: Andrew Zhao, Google
Contributing Author(s): Nicholas Rubin

Quadratic optimization over the (special) orthogonal group encompasses a broad class of optimization problems such as group synchronization, point-set registration, and simultaneous localization and mapping. Such problems are instances of the little noncommutative Grothendieck problem (LNCG), a natural generalization of the MAXCUT problem. In this work, we establish an encoding of LNCG onto a quantum Hamiltonian and investigate its approximation quality compared to standard classical approaches. This encoding is accomplished by identifying orthogonal matrices with quantum states via a Clifford-algebraic construction. We further connect this representation to the theory of free fermions, which leads to a natural interpretation of the LNCG Hamiltonian terms as two-body interactions. Notably, this quantum formalism features an explicit restriction to the special orthogonal group, whereas classically optimizing over this subgroup can involve expensive determinant constraints.

(Session 5 : Thursday from 5:00 pm - 7:00 pm)