Options
Optimizing the depth of variational quantum algorithms is strongly QCMA-hard to approximate
Publikationstyp
Conference Paper
Publikationsdatum
2023-07-10
Sprache
English
First published in
Number in series
264
Citation
Computational Complexity Conference (CCC 2023)
Contribution to Conference
Computational Complexity Conference (CCC 2023)
Publisher DOI
ArXiv ID
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].
Schlagworte
Quantum Physics
Quantum Physics
Computer Science - Computational Complexity
DDC Class
004: Computer Sciences