Study network-related optimization problems using quantum alternating optimization ansatz

Network-related connectivity optimization problems are underlying a wide range of applications and are of high computational complexity. We consider studying network optimization problems using quantum heuristics. In particular, we consider Quantum Alternating Operator Ansatz, an extension of the Quantum Approximate Optimization Algorithms, in which a cost-function based unitary and a non-commuting mixing unitary are applied alternately. We present mappings for a few network optimization problems, including variants of finding the optimal spanning-tree or spanning-graph of a graph. We give special focus on the design of mixers based on the constraints in the problem such that the system evolution remains in a subspace of the full Hilbert space where all constraints are satisfied. In the spanning-tree problem, one such constraint is that a mixer applied to a spanning tree needs also be a spanning tree. This involves checking the connectivity of a subgraph, which is a global condition common for most network-related problems. We show how this feature can be efficiently represented in the mixer in a quantum coherent way, based on manipulation of a descendant-matrix and an adjacent matrix. We further develop a mixer for the spanning-graphs based on the spanning-tree mixer.