Optimizing the depth of variational quantum algorithms is strongly QCMA-hard to approximate

L. Bittel, S. Gharibian, M. Kliesch, ArXiv:2211.12519 (2022).

Download
No fulltext has been uploaded.
Preprint | English
Author
Bittel, Lennart; Gharibian, SevagLibreCat ; Kliesch, Martin
Abstract
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 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. This potential for depth reduction has made VQAs a staple of Noisy Intermediate-Scale Quantum (NISQ)-era research. 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 even in the "simpler" setting of QAOAs. To our knowledge, this yields the first natural QCMA-hard-to-approximate problems. To achieve these results, we bypass the need for a PCP theorem for QCMA by appealing to the disperser-based NP-hardness of approximation construction of [Umans, FOCS 1999].
Publishing Year
Journal Title
arXiv:2211.12519
LibreCat-ID

Cite this

Bittel L, Gharibian S, Kliesch M. Optimizing the depth of variational quantum algorithms is strongly  QCMA-hard to approximate. arXiv:221112519. Published online 2022.
Bittel, L., Gharibian, S., & Kliesch, M. (2022). Optimizing the depth of variational quantum algorithms is strongly  QCMA-hard to approximate. In arXiv:2211.12519.
@article{Bittel_Gharibian_Kliesch_2022, title={Optimizing the depth of variational quantum algorithms is strongly  QCMA-hard to approximate}, journal={arXiv:2211.12519}, author={Bittel, Lennart and Gharibian, Sevag and Kliesch, Martin}, year={2022} }
Bittel, Lennart, Sevag Gharibian, and Martin Kliesch. “Optimizing the Depth of Variational Quantum Algorithms Is Strongly  QCMA-Hard to Approximate.” ArXiv:2211.12519, 2022.
L. Bittel, S. Gharibian, and M. Kliesch, “Optimizing the depth of variational quantum algorithms is strongly  QCMA-hard to approximate,” arXiv:2211.12519. 2022.
Bittel, Lennart, et al. “Optimizing the Depth of Variational Quantum Algorithms Is Strongly  QCMA-Hard to Approximate.” ArXiv:2211.12519, 2022.

Export

Marked Publications

Open Data LibreCat

Sources

arXiv 2211.12519

Search this title in

Google Scholar