Pauli Correlation Encoding for Balanced MinCut with initial testing on VLSI implementations

Abstract

This master thesis centers on solving the balanced MinCut problem for (hyper)graphs via Quantum Variational Algorithms. This is achieved by compressing the binary variables in the problem for various network sizes with few qubits using Pauli Correlation Encoding. We adapt an existing heuristic algorithm for hyperparameter tuning to our problem, showing empirical evidence for convergence on feasible solutions. The thesis explores relevant formulations for the problem that can be translated directly for this specific encoding. We compare our solutions to the ones provided by well known classical methods, and identify future improvements to make this quantum optimization scheme be on par with these refined classical solutions. Finally, we test this methodology on real chip design applications, where we find opportunities for better adaptation in this design problem, so the proposed mechanism can eventually be used to solve real applications in this field.