Scholarlink

<p>We show a relation between quantum learning theory and algorithmic hardness. We use the existence of efficient, local learning algorithms for energy estimation—such as the classical shadows algorithm—to prove that finding near-ground states of disordered quantum systems exhibiting a certain topological property is impossible in the average case for Lipschitz quantum algorithms. A corollary of our result is that many standard quantum algorithms fail to find near-ground states of these systems, including time-<i>T</i> Lindbladian dynamics from an arbitrary initial state, time-<i>T</i> quantum annealing, phase estimation to <i>T</i> bits of precision, and depth-<i>T</i> variational quantum algorithms, whenever <i>T</i> is less than some universal constant times the logarithm of the system size. To achieve this, we introduce a generalization of the overlap gap property (OGP) for quantum systems that we call the <i>quantum overlap gap property</i> (QOGP). This property is defined by a specific topological structure over representations of low-energy quantum states as output by an efficient local learning algorithm. We prove that preparing low-energy states of systems which exhibit the QOGP is intractable for quantum algorithms whose outputs are stable under perturbations of their inputs. We then prove that the QOGP is satisfied for a sparsified variant of the quantum <i>p</i>-spin model, giving the first known algorithmic hardness-of-approximation result for quantum algorithms in finding the ground state of a non-stoquastic, noncommuting quantum system. Our resulting lower bound for quantum algorithms optimizing this model using Lindbladian evolution matches (up to constant factors) the best-known time lower bound for classical Langevin dynamics optimizing classical <i>p</i>-spin models. For this reason we suspect that finding ground states of typical instances of these quantum spin models using quantum algorithms is, in practice, as intractable as the classical <i>p</i>-spin model is for classical algorithms. Inversely, we show that the Sachdev–Ye–Kitaev model does not exhibit the QOGP, consistent with previous evidence that the model is rapidly mixing at low temperatures.</p>

错误：搜索内容不能为空，请输入英文关键词
错误：关键词超出字数限制，请精简
高级检索

Quantum Glassiness from Efficient Learning

  • 期刊论文

  • 发表日期：

    2026年1月14日

查看全文
  • Eric R. Anschuetz

摘要

We show a relation between quantum learning theory and algorithmic hardness. We use the existence of efficient, local learning algorithms for energy estimation—such as the classical shadows algorithm—to prove that finding near-ground states of disordered quantum systems exhibiting a certain topological property is impossible in the average case for Lipschitz quantum algorithms. A corollary of our result is that many standard quantum algorithms fail to find near-ground states of these systems, including time-T Lindbladian dynamics from an arbitrary initial state, time-T quantum annealing, phase estimation to T bits of precision, and depth-T variational quantum algorithms, whenever T is less than some universal constant times the logarithm of the system size. To achieve this, we introduce a generalization of the overlap gap property (OGP) for quantum systems that we call the quantum overlap gap property (QOGP). This property is defined by a specific topological structure over representations of low-energy quantum states as output by an efficient local learning algorithm. We prove that preparing low-energy states of systems which exhibit the QOGP is intractable for quantum algorithms whose outputs are stable under perturbations of their inputs. We then prove that the QOGP is satisfied for a sparsified variant of the quantum p-spin model, giving the first known algorithmic hardness-of-approximation result for quantum algorithms in finding the ground state of a non-stoquastic, noncommuting quantum system. Our resulting lower bound for quantum algorithms optimizing this model using Lindbladian evolution matches (up to constant factors) the best-known time lower bound for classical Langevin dynamics optimizing classical p-spin models. For this reason we suspect that finding ground states of typical instances of these quantum spin models using quantum algorithms is, in practice, as intractable as the classical p-spin model is for classical algorithms. Inversely, we show that the Sachdev–Ye–Kitaev model does not exhibit the QOGP, consistent with previous evidence that the model is rapidly mixing at low temperatures.