Speaker
Description
Combinatorial optimization (CO) has many important applications in business and science. Many CO problems are NP-hard and are routinely solved by classical heuristics. It is widely believed that quantum computers cannot solve such problems efficiently, but significant effort is put into designing quantum algorithms that provide fast and reliable approximate solutions. In the era of noisy intermediate-state quantum (NISQ) computers, two candidates are the variational quantum eigensolver (VQE) and the quantum approximate optimization algorithm (QAOA). Both algorithms use a parameterized quantum circuit $|\psi(\vartheta)\rangle$ to minimize the expectation value $\langle H(\vartheta) \rangle = \langle \psi(\vartheta)|H|\psi(\vartheta)\rangle$ of a given Hamiltonian $H$ by solving $\min_{\vartheta} \langle H(\vartheta) \rangle$.
While QAOA utilizes a quantum circuit that implements problem structure to apply trotterized time evolution, VQE circuits typically use problem agnostic designs that are tuned to run efficiently on NISQ hardware. In this empirical study, we test a variety of ansatz structures to address the weighted Max-Cut problem on 3-regular graphs for small instances and typical VQE settings. We do not observe a strong dependence of the algorithm's performance in terms of approximation ratio and probability of measuring the ground state on circuit design. Since solutions to CO problems are classical, the role of circuit expressibility and entanglement capabilitites are not clear. There are no correlations between expressibility and entanglement capabilities of the circuits and the algorithm's performance visible in our experiments. This suggests that these common circuit properties are not useful for designing circuits for CO and problem inspired designs, such as QAOA, are to be preferred.
