Variational learning algorithms for quantum query complexity

Abstract

Quantum query complexity plays an important role in studying quantum algorithms, which captures the most known quantum algorithms, such as search and period finding. A query algorithm applies $U_t{O}_x\cdots U_1{O}_x{U}_0$ to some input state, where $O_x$ is the oracle dependent on some input variable $x$, and $U_i$s are unitary operations that are independent of $x$, followed by some measurements for readout. In this work, we develop variational learning algorithms to study quantum query complexity, by formulating $U_i$s as parameterized quantum circuits and introducing a loss function that is directly given by the error probability of the query algorithm. We apply our method to analyze various cases of quantum query complexity, including a new algorithm solving the Hamming modulo problem with $4$ queries for the case of $5$-bit modulo $5$, answering an open question raised in arXiv:2112.14682, and the result is further confirmed by a Semidefinite Programming (SDP) algorithm. Compared with the SDP algorithm, our method can be readily implemented on the near-term Noisy Intermediate-Scale Quantum (NISQ) devices and is more flexible to be adapted to other cases such as the fractional query models.