Most combinatorial optimization problems from theoretical computer science have a natural framing as optimization of polynomials in commuting variables. Noncommutativity is one of the defining features of quantum mechanics. So it is not surprising that noncommutative polynomial optimization plays an equally important role in quantum computer science. Our main goal here is to understand the relative hardness of commutative versus noncommutative polynomial optimization. At a first glance it might seem that noncommutative polynomial optimization must be more complex. However this is not always true and this question of relative hardness is substantially more subtle than might appear at the outset.
First in this thesis we show that the general noncommutative polynomial optimization is complete for the class $\Pi_2$; this class is in the second level of the arithmetical hierarchy and strictly contains both the set of recursively enumerable languages and its complement. On the other hand, commutative polynomial optimization is decidable and belongs to $\PSPACE$. We then provide evidence that for polynomials arising from a large class of constraint satisfaction problems the situation is reversed: the noncommutative polynomial optimization is an easier computational problem compared to its commutative analogue.
A second question we are interested in is about whether we could extract good commutative solutions from noncommutative solutions? This brings us to the second theme of this thesis which is about understanding the algebraic structure of the solutions of noncommutative polynomial optimization. We show that this structural insight then could shed light on the optimal commutative solutions and thereby paves the path in understanding the relationships between the commutative and noncommutative solutions.
Here we first use the sum-of-squares framework to understand the algebraic relationships that are present between operators in any optimal noncommutative solution of a class of polynomial optimization problems arising from certain constraint satisfaction problems. We then show how we can design approximation algorithms for these problems so that some algebraic structures of our choosing is present. Finally we propose a rounding scheme for extracting good commutative solutions from noncommutative ones.
| Identifer | oai:union.ndltd.org:columbia.edu/oai:academiccommons.columbia.edu:10.7916/x62q-ha25 |
| Date | January 2023 |
| Creators | Mousavi Haji, Seyyed Hamoon |
| Source Sets | Columbia University |
| Language | English |
| Detected Language | English |
| Type | Theses |
Page generated in 0.0658 seconds