Yuxuan Zhang, UT-Austin
"A Quantum Approximate Optimization Algorithm for Edge-Disjoint Paths Problem"
Abstract: The Quantum Approximate Optimization Algorithm (QAOA) is a class of promising quantum-classical hybrid algorithms for near-term quantum device implementations, for it naturally requires low circuit depth. In this work, we present a QAOA method to solve a specific type of combinatorial optimization problem, the edge-disjoint paths (EDP) problem on planar graphs. Given a graph and k-pairs of vertices, the goal of the EDP problem is to find k-disjoint paths to connect each pair of vertices. By introducing a lattice QED inspired mixing Hamiltonian, we are guaranteed to always obtain feasible solutions from the algorithm.