Variational learning algorithms for quantum query complexity
Autor: | Wu, Zipeng, Hou, Shi-Yao, Zhang, Chao, Li, Lvzhou, Zeng, Bei |
---|---|
Rok vydání: | 2022 |
Předmět: | |
Druh dokumentu: | Working Paper |
DOI: | 10.1088/1367-2630/ad309c |
Popis: | 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_tO_x\cdots U_1O_xU_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. |
Databáze: | arXiv |
Externí odkaz: |
načítá se...