MINIMIZING POLYNOMIAL FUNCTIONS ON QUANTUM COMPUTERS

摘要

This expository paper reviews some of the recent uses of computational algebraic geometry in classical and quantum optimization. The paper assumes an elementary background in algebraic geometry and adiabatic quantum computing (AQC), and concentrates on presenting concrete examples (with Python codes tested on a quantum computer) of applying algebraic geometry constructs: solving binary optimization, factoring, and compiling. Reversing the direction, we also briefly describe a novel use of quantum computers to compute Groebner bases for toric ideals. We also show how Groebner bases play a role in studying AQC at a fundamental level within a Morse theory framework. We close by placing our work in perspective, by situating this leg of the journey, as part of a marvelous intellectual expedition that began with our ancients over 4000 years ago.