论文标题
量子查询复杂性的变分学习算法
Variational learning algorithms for quantum query complexity
论文作者
论文摘要
量子查询复杂性在研究量子算法中起重要作用，该量子算法捕获了最著名的量子算法，例如搜索和周期发现。查询算法应用$ u_to_x \ cdots u_1o_xu_0 $上的某些输入状态，其中$ o_x $是oracle取决于某些输入变量$ x $的oracle，$ u_i $ s是独立于$ x $的单一操作，随后进行了一些读数的测量。在这项工作中，我们通过将$ u_i $ S作为参数化量子电路制定$ u_i $ s来开发各种学习算法来研究量子查询复杂性，并引入了由查询算法的误差概率直接给出的损耗函数。我们应用我们的方法来分析各种量子查询复杂性，包括一种新算法解决锤式模量问题，价格为$ 4 $ $ QUERIES，价格为$ 5 $ -bit Modulo $ 5 $，回答了Arxiv中提出的一个空旷的问题：2112.14682，结果由半际（Semidefinite）编程（SeideFinite）Algsming（Sdp）进一步证实。与SDP算法相比，我们的方法可以轻松地在近期嘈杂的中间尺度量子（NISQ）设备上实现，并且更灵活地适应其他情况，例如分数查询模型。
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.
