Sub-universal variational circuits for combinatorial optimization
  problems
Gal Weitz Lirandë Pira Chris Ferrie Joshua Combes
Quantum variational circuits have gained significant attention due to their
applications in the quantum approximate optimization algorithm and quantum
machine learning research. This work introduces a novel class of classical
probabilistic circuits designed for generating approximate solutions to
combinatorial optimization problems constructed using two-bit stochastic
matrices. Through a numerical study, we investigate the performance of our
proposed variational circuits in solving the Max-Cut problem on various graphs
of increasing sizes. Our classical algorithm demonstrates improved performance
for several graph types to the quantum approximate optimization algorithm. Our
findings suggest that evaluating the performance of quantum variational
circuits against variational circuits with sub-universal gate sets is a
valuable benchmark for identifying areas where quantum variational circuits can
excel.