• 文献检索
  • 文档翻译
  • 深度研究
  • 学术资讯
  • Suppr Zotero 插件Zotero 插件
  • 邀请有礼
  • 套餐&价格
  • 历史记录
应用&插件
Suppr Zotero 插件Zotero 插件浏览器插件Mac 客户端Windows 客户端微信小程序
定价
高级版会员购买积分包购买API积分包
服务
文献检索文档翻译深度研究API 文档MCP 服务
关于我们
关于 Suppr公司介绍联系我们用户协议隐私条款
关注我们

Suppr 超能文献

核心技术专利：CN118964589B侵权必究
粤ICP备2023148730 号-1Suppr @ 2026

文献检索

告别复杂PubMed语法，用中文像聊天一样搜索，搜遍4000万医学文献。AI智能推荐，让科研检索更轻松。

立即免费搜索

文件翻译

保留排版，准确专业，支持PDF/Word/PPT等文件格式，支持 12+语言互译。

免费翻译文档

深度研究

AI帮你快速写综述，25分钟生成高质量综述，智能提取关键信息，辅助科研写作。

立即免费体验

Exponential complexity of the quantum adiabatic algorithm for certain satisfiability problems.

作者信息

Hen Itay, Young A P

机构信息

Department of Physics, University of California, Santa Cruz, California 95064, USA.

出版信息

Phys Rev E Stat Nonlin Soft Matter Phys. 2011 Dec;84(6 Pt 1):061152. doi: 10.1103/PhysRevE.84.061152. Epub 2011 Dec 29.

DOI:10.1103/PhysRevE.84.061152
PMID:22304085
Abstract

We determine the complexity of several constraint satisfaction problems using the quantum adiabatic algorithm in its simplest implementation. We do so by studying the size dependence of the gap to the first excited state of "typical" instances. We find that, at large sizes N, the complexity increases exponentially for all models that we study. We also compare our results against the complexity of the analogous classical algorithm WalkSAT and show that the harder the problem is for the classical algorithm, the harder it is also for the quantum adiabatic algorithm.

摘要

相似文献

1
Exponential complexity of the quantum adiabatic algorithm for certain satisfiability problems.
Phys Rev E Stat Nonlin Soft Matter Phys. 2011 Dec;84(6 Pt 1):061152. doi: 10.1103/PhysRevE.84.061152. Epub 2011 Dec 29.
2
Complexity of several constraint-satisfaction problems using the heuristic classical algorithm WalkSAT.
Phys Rev E Stat Nonlin Soft Matter Phys. 2011 Jul;84(1 Pt 1):011102. doi: 10.1103/PhysRevE.84.011102. Epub 2011 Jul 6.
3
Size dependence of the minimum excitation gap in the quantum adiabatic algorithm.
Phys Rev Lett. 2008 Oct 24;101(17):170503. doi: 10.1103/PhysRevLett.101.170503. Epub 2008 Oct 23.
4
Experimental implementation of local adiabatic evolution algorithms by an NMR quantum information processor.利用核磁共振量子信息处理器对局部绝热演化算法进行实验实现。
J Magn Reson. 2005 Dec;177(2):285-98. doi: 10.1016/j.jmr.2005.08.004. Epub 2005 Sep 19.
5
Quantum adiabatic algorithm and scaling of gaps at first-order quantum phase transitions.量子绝热算法与一级量子相变间隙的标度。
Phys Rev Lett. 2012 Jul 20;109(3):030502. doi: 10.1103/PhysRevLett.109.030502. Epub 2012 Jul 19.
6
First-order phase transition in the quantum adiabatic algorithm.量子绝热算法中的一级相变。
Phys Rev Lett. 2010 Jan 15;104(2):020502. doi: 10.1103/PhysRevLett.104.020502. Epub 2010 Jan 14.
7
Quantum adiabatic optimization and combinatorial landscapes.量子绝热优化与组合景观
Phys Rev E Stat Nonlin Soft Matter Phys. 2004 Sep;70(3 Pt 2):036702. doi: 10.1103/PhysRevE.70.036702. Epub 2004 Sep 16.
8
A quantum adiabatic evolution algorithm applied to random instances of an NP-complete problem.一种应用于NP完全问题随机实例的量子绝热演化算法。
Science. 2001 Apr 20;292(5516):472-5. doi: 10.1126/science.1057726.
9
First-order transitions and the performance of quantum algorithms in random optimization problems.一阶相变与量子算法在随机优化问题中的性能。
Phys Rev Lett. 2010 May 21;104(20):207206. doi: 10.1103/PhysRevLett.104.207206. Epub 2010 May 20.
10
Experimental implementation of an adiabatic quantum optimization algorithm.绝热量子优化算法的实验实现
Phys Rev Lett. 2003 Feb 14;90(6):067903. doi: 10.1103/PhysRevLett.90.067903.

引用本文的文献

1
Quantum annealing with special drivers for circuit fault diagnostics.用于电路故障诊断的具有特殊驱动程序的量子退火
Sci Rep. 2022 Jul 8;12(1):11691. doi: 10.1038/s41598-022-14804-8.
2
Quantum machine learning: a classical perspective.量子机器学习：一种经典视角。
Proc Math Phys Eng Sci. 2018 Jan;474(2209):20170551. doi: 10.1098/rspa.2017.0551. Epub 2018 Jan 17.
3
Unraveling Quantum Annealers using Classical Hardness.利用经典硬度剖析量子退火器
Sci Rep. 2015 Oct 20;5:15324. doi: 10.1038/srep15324.