Solving various NP-hard problems using exponentially fewer qubits on a quantum computer

量子位元 量子计算机 指数增长 计算机科学 量子 数学 量子力学 物理
作者
Yagnik Chatterjee,Eric Bourreau,Marko J. Rančić
出处
期刊:Physical review 卷期号:109 (5) 被引量:8
标识
DOI:10.1103/physreva.109.052441
摘要

NP-hard problems are not believed to be exactly solvable through general polynomial time algorithms. Hybrid quantum-classical algorithms to address such combinatorial problems have been of great interest in the past few years. Such algorithms are heuristic in nature and aim to obtain an approximate solution. Significant improvements in computational time and/or the ability to treat large problems are some of the principal promises of quantum computing in this regard. The hardware, however, is still in its infancy and the current noisy intermediate-scale quantum (NISQ) computers are not able to optimize industrially relevant problems. Moreover, the storage of qubits and introduction of entanglement require extreme physical conditions. An issue with quantum optimization algorithms such as the quantum approximate optimization algorithm is that they scale linearly with problem size. In this paper, we build upon a proprietary methodology which scales logarithmically with problem size---opening an avenue for treating optimization problems of unprecedented scale on gate-based quantum computers. To test the performance of the algorithm, we first find a way to apply it to a handful of NP-hard problems: Maximum Cut, Minimum Partition, Maximum Clique, Maximum Weighted Independent Set. Subsequently, these algorithms are tested on a quantum simulator with graph sizes of over a hundred nodes and on a real quantum computer up to graph sizes of 256. To our knowledge, these constitute the largest realistic combinatorial optimization problems ever run on a NISQ device, overcoming previous problem sizes by almost tenfold.
最长约 10秒,即可获得该文献文件

科研通智能强力驱动
Strongly Powered by AbleSci AI
更新
大幅提高文件上传限制,最高150M (2024-4-1)

科研通是完全免费的文献互助平台,具备全网最快的应助速度,最高的求助完成率。 对每一个文献求助,科研通都将尽心尽力,给求助人一个满意的交代。
实时播报
我爱康康文献完成签到 ,获得积分10
刚刚
chenbin完成签到,获得积分10
2秒前
陈米花完成签到,获得积分10
3秒前
yyjl31完成签到,获得积分10
3秒前
Simon_chat完成签到,获得积分10
3秒前
4秒前
三木完成签到 ,获得积分10
7秒前
Aprilzhou完成签到,获得积分10
8秒前
吐司炸弹完成签到,获得积分10
9秒前
mayfly完成签到,获得积分10
9秒前
萧水白应助科研通管家采纳,获得10
11秒前
哭泣老三发布了新的文献求助10
11秒前
13秒前
天天快乐应助平常向雪采纳,获得10
19秒前
淡然的芷荷完成签到 ,获得积分10
24秒前
25秒前
勤恳的雪卉完成签到,获得积分10
27秒前
bkagyin应助平常从蓉采纳,获得10
30秒前
司空天德发布了新的文献求助10
31秒前
积极冷松完成签到 ,获得积分10
32秒前
victory_liu完成签到,获得积分10
33秒前
L_x完成签到 ,获得积分10
56秒前
56秒前
TTTHANKS完成签到 ,获得积分10
59秒前
聂立双完成签到 ,获得积分10
1分钟前
平常从蓉发布了新的文献求助10
1分钟前
郑雅柔完成签到 ,获得积分10
1分钟前
娇娇大王完成签到,获得积分10
1分钟前
Binbin完成签到 ,获得积分10
1分钟前
斯文败类应助john采纳,获得10
1分钟前
WXM完成签到 ,获得积分10
1分钟前
mia完成签到,获得积分10
1分钟前
wujiwuhui完成签到 ,获得积分10
1分钟前
Huang完成签到 ,获得积分0
1分钟前
Jessica完成签到,获得积分10
1分钟前
TT完成签到,获得积分10
1分钟前
candice624完成签到 ,获得积分10
1分钟前
研友_西门孤晴完成签到,获得积分10
1分钟前
1分钟前
H_C发布了新的文献求助10
1分钟前
高分求助中
Sustainability in Tides Chemistry 1500
TM 5-855-1(Fundamentals of protective design for conventional weapons) 1000
Gerard de Lairesse : an artist between stage and studio 500
Digging and Dealing in Eighteenth-Century Rome 500
Queer Politics in Times of New Authoritarianisms: Popular Culture in South Asia 500
Livre et militantisme : La Cité éditeur 1958-1967 500
Retention of title in secured transactions law from a creditor's perspective: A comparative analysis of selected (non-)functional approaches 500
热门求助领域 (近24小时)
化学 医学 生物 材料科学 工程类 有机化学 生物化学 物理 内科学 纳米技术 计算机科学 化学工程 复合材料 基因 遗传学 催化作用 物理化学 免疫学 量子力学 细胞生物学
热门帖子
关注 科研通微信公众号,转发送积分 3063230
求助须知:如何正确求助?哪些是违规求助? 2717989
关于积分的说明 7456754
捐赠科研通 2364300
什么是DOI,文献DOI怎么找? 1253400
科研通“疑难数据库(出版商)”最低求助积分说明 608585
版权声明 596606