Speaker
Description
Exact solutions to combinatorial optimization problems are challenging to obtain using classical computing. The current tenet in the field is that quantum computers can address these problems more efficiently. While promising algorithms require fault-tolerant quantum hardware, variational algorithms have emerged as viable candidates for near-term devices. The success of these algorithms hinges on multiple factors, with the design of the ansatz having utmost importance. In this work, we propose a variational ansatz inspired by quantum imaginary time evolution (QITE) to solve the MaxCut problem. We introduce a tree arrangement of the parametrized quantum gates, enabling the exact solution of arbitrary tree graphs using the one-round QITE-inspired ansatz. For randomly generated $D$-regular graphs, we numerically demonstrate that the QITE-inspired ansatz solves the MaxCut problem with a small constant number of rounds and sublinear depth, outperforming the quantum approximate optimization algorithm (QAOA), which requires increasing rounds with system size. Furthermore, our ansatz improves the approximation ratio gap by at least 4.8 times for graphs with up to 24 nodes and $D \leq 5$ compared to the classical near-optimal Goemans-Williamson algorithm. Lastly, we prove that the constant-round QITE-inspired ansatz for regular graphs avoids the barren plateaus.
| I am | student/ postdoc |
|---|
