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.