Adaptive ground state preparation through randomization

Variational quantum algorithms (VQAs) operate by using classical and quantum computing resources in tandem to solve, in an iterative loop, an optimization problem. However, several challenges associated with ansatz selection, rugged optimization landscapes, and noise exist. Rather than fixing a parameterized quantum circuit as an ansatz to solve the optimization problem, adaptive quantum algorithms aim to overcome these issues by adaptively creating the quantum circuit that minimizes the objective function. However, since the optimization problem is typically non-convex, similar to traditional VQAs, adaptive strategies can get stuck in sub-optimal solutions.

Here we address this issue by arguing that for ground state problems, randomized adaptive quantum algorithms converge to the global optimum almost surely for almost all initial states. We compare different strategies to create randomness, including creating random directions through unitary 2-designs and randomly sampling from a pool of operators, with deterministic strategies for solving the combinatorial optimization problem MaxCut. Finally, we discuss the scalability of the randomized adaptive strategies by drawing a connection to the theory of barren plateaus and investigating robustness to noise on IBM’s quantum hardware.