English (United Kingdom)

https://curated-unify.zendy.io/wp-json/zendy-region/v1/featured_content/oa?rat=en

https://curated-unify.zendy.io/wp-json/zendy-region/v1/highlighted_journal/

Global: Zendy Tools annual

Presents the keyphrase highlighting as premium feature

Keyphrase Highlighting

Presents the summarisation as premium feature

Summarisation

Insights

Presents the pdf analysis as premium feature

PDF Analysis

Presents the zaia usage as premium feature

ZAIA

Global: Zendy Tools monthly

Global: Zendy Plus monthly

Presents the access of premium content as premium feature

Premium Content

Global: Zendy Plus annual

Global: Zendy Free Plan

Variational Quantum Algorithms (VQAs), such as the Quantum ApproximateOptimization Algorithm (QAOA) of [Farhi, Goldstone, Gutmann, 2014], have seenintense study towards near-term applications on quantum hardware. A crucialparameter for VQAs is the \emph{depth} of the variational ``ansatz'' used --the smaller the depth, the more amenable the ansatz is to near-term quantumhardware in that it gives the circuit a chance to be fully executed before thesystem decoheres. In this work, we show that approximating the optimal depthfor 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 ansatzwithin multiplicative factor $N^{1-\epsilon}$, for $N$ denoting the encodingsize of the VQA instance. (Here, Quantum Classical Merlin-Arthur (QCMA) is aquantum generalization of NP.) We then show that this hardness persists in theeven ``simpler'' QAOA-type settings. To our knowledge, this yields the firstnatural QCMA-hard-to-approximate problems.

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