Options
Optimizing the depth of variational quantum algorithms is strongly QCMA-hard to approximate
Citation Link: https://doi.org/10.15480/882.13946
Publikationstyp
Conference Paper
Date Issued
2023-07-10
Sprache
English
TORE-DOI
First published in
Number in series
264
Citation
38th Computational Complexity Conference (CCC 2023)
Contribution to Conference
Publisher DOI
ArXiv ID
Publisher
Schloss Dagstuhl - Leibniz-Zentrum für Informatik GmbH
ISBN
978-3-95977-282-2
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 ϵ>0, it is QCMA-hard to approximate the optimal depth of a VQA ansatz within multiplicative factor N¹⁻ϵ, 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].
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¹⁻ϵ, 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].
Subjects
Quantum Physics
Quantum Physics
Computer Science - Computational Complexity
DDC Class
004: Computer Sciences
Loading...
Name
LIPIcs.CCC.2023.34.pdf
Type
Main Article
Size
956 KB
Format
Adobe PDF