Optimizing the depth of variational quantum algorithms is strongly QCMA-hard to approximate
| Autor: | Bittel, Lennart, Gharibian, Sevag, Kliesch, Martin |
|---|---|
| Rok vydání: | 2022 |
| Předmět: | |
| Zdroj: | 38th Computational Complexity Conference (CCC 2023), 34:1--34:24 |
| Druh dokumentu: | Working Paper |
| DOI: | 10.4230/LIPIcs.CCC.2023.34 |
| Popis: | 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 $\epsilon>0$, it is QCMA-hard to approximate the optimal depth of a VQA ansatz within multiplicative factor $N^{1-\epsilon}$, 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. Comment: 31 pages, 2 figures |
| Databáze: | arXiv |
| Externí odkaz: |
|