Reachability Constraints in Variational Quantum Circuits: Optimization within Polynomial Group Module
For researchers in quantum computing, it reveals fundamental limitations of variational quantum circuits and provides a classical alternative for certain problems.
This work identifies a necessary condition for variational quantum algorithms to reach exact ground states, showing that module weights of the solution must be known in advance. For problems with classical bit-string solutions, this enables a classical surrogate with O(n^5) time per step, as illustrated on Maximum Cut.
This work identifies a necessary condition for any variational quantum approach to reach the exact ground state. Briefly, the norms of the projections of the input and the ground state onto each group module must match, implying that module weights of the solution state have to be known in advance in order to reach the exact ground state. An exemplary case is provided by matchgate circuits applied to problems whose solutions are classical bit strings, since all computational basis states share the same module-wise weights. Combined with the known classical simulability of quantum circuits for which observables lie in a small linear subspace, this implies that certain problems admit a classical surrogate for exact solution with each step taking $O(n^5)$ time. The Maximum Cut problem serves as an illustrative example.