Variational learning algorithms for quantum query complexity

Quantum query complexity plays an important role in studying quantum algorithms, which cap-

tures the most known quantum algorithms, such as search and period finding. A query algorithm

applies U_tO_x · · · U₁O_xU₀ to some input state, where Ox is the oracle dependent on some input vari-

able x, and Uis 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 com-

plexity, by formulating Uis 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 ana-

lyze 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.