论文标题
优化变异量子算法的深度是QCMA-HARD的近似值
Optimizing the depth of variational quantum algorithms is strongly QCMA-hard to approximate
论文作者
论文摘要
[Farhi，Goldstone，Gutmann，2014]的量子量子算法（VQA）（例如，量子近似优化算法（QAOA））已经看到了对量子硬件的近期应用。 VQAS的关键参数是使用``Ansatz''所使用的\ emph {depth} - 深度越小，ANSATZ越适合近期量子硬件，因为它使电路在系统脱位之前可以完全执行电路。在这项工作中，我们表明，给定VQA Ansatz的最佳深度近似是棘手的。正式地，我们表明，对于任何常数$ε> 0 $，QCMA-HARD近似于在乘法因子$ n^{1-ε} $中近似vqa ansatz的最佳深度，对于$ n $表示VQA实例的编码大小。 （在这里，量子经典的Merlin-Arthur（QCMA）是NP的量子概括。）然后，我们证明这种硬度持续存在于偶数''simple''QAOA型设置中。据我们所知，这产生了第一个天然的QCMA- hard-hard-to-Approximate问题。
Variational Quantum Algorithms (VQAs), such as the Quantum Approximate Optimization Algorithm (QAOA) of [Farhi, Goldstone, Gutmann, 2014], have seen intense study towards near-term applications on quantum hardware. A crucial parameter for VQAs is the \emph{depth} of the variational ``ansatz'' used -- the smaller the depth, the more amenable the ansatz is to near-term quantum hardware in that it gives the circuit a chance to be fully executed before the system decoheres. In this work, we show that approximating the optimal depth for a given VQA ansatz is intractable. Formally, we show that for any constant $ε>0$, it is QCMA-hard to approximate the optimal depth of a VQA ansatz within multiplicative factor $N^{1-ε}$, for $N$ denoting the encoding size of the VQA instance. (Here, Quantum Classical Merlin-Arthur (QCMA) is a quantum generalization of NP.) We then show that this hardness persists in the even ``simpler'' QAOA-type settings. To our knowledge, this yields the first natural QCMA-hard-to-approximate problems.
