arrow
返回

A quantum algorithm for solving 0-1 Knapsack problems

delete2025-08-26
delete0
delete
OA
AI
S
Sören Wilkening *
A
Andreea-Iulia Lefterovici
L
Lennart Binkowski
M
Michael Perk
S
Sándor P. Fekete
T
Tobias J. Osborne
DOI:10.1038/s41534-025-01097-8delete
delete原文链接
delete分享
delete收藏
查看原文
摘要

摘要

En 中文
我们提出了两项新颖的贡献,用于实现和评估在解决困难优化问题方面的量子优势,无论是在理论层面还是在可预见的实践中。(1) 我们引入了“量子树生成器”(Quantum Tree Generator),用于在叠加态中生成给定0-1背包实例的所有可行解;结合振幅放大技术,这可以识别最优解。假设存在全连接的逻辑量子比特和可比的量子时钟速度,QTG为拥有仅100个变量的实例提供了与经典最优背包求解器竞争的运行时间。(2) 通过引入一种利用经典求解器日志数据的新技术,我们可以预测我们方法的运行时间,远超现有量子平台和模拟器的范围,适用于包含多达600个变量的基准实例。在给定假设条件下,我们证明了QTG对于此类实例的潜在实际量子优势,表明了一种有效解决困难组合优化问题的有前景方法。
AI总结

AI总结

对已上传原文的论文进行重点信息的提取,主要内容包括:简要概述、研究摘要、背景介绍、关键亮点、图文解析、展望与总结。

期刊

npj Quantum Information 封面图
npj Quantum Information
IF:
8.3
论文数:
1.4K
被引数:
9.4K

机构

I
institut für betriebssysteme und rechnerverbund
学者数:
2
论文数: 1
被引数: 1
I
institut für theoretische physik
学者数:
0
论文数: 1
被引数: 27
引用论文

引用论文

Nested quantum search and structured problems
err2000-02-09
err0
errOAAI
errNicolas J. Cerf; Lov K. Grover; Colin P. Williams
err分享
err收藏
From the Quantum Approximate Optimization Algorithm to a Quantum Alternating Operator Ansatz从量子近似优化算法到量子交替算子Ansatz
err2019-02-12
err0
errOAAI
errStuart Hadfield; Zhihui Wang; Bryan O’Gorman; Eleanor G. Rieffel; Davide Venturelli; Rupak Biswas
err分享
err收藏
Quantum annealing in the transverse Ising model
err1998-11-01
err0
errOAAI
errTadashi Kadowaki; Hidetoshi Nishimori
err分享
err收藏
Quantum supremacy using a programmable superconducting processor使用可编程超导处理器实现量子霸权
errNature
IF48.5
err2019-10-23
err0
PREAI
errFrank Arute; Kunal Arya; Ryan Babbush; Dave Bacon; Joseph C. Bardin; Rami Barends; Rupak Biswas; Sergio Boixo; Fernando G. S. L. Brandao; David A. Buell; Brian Burkett; Yu Chen; Zijun Chen; Ben Chiaro; Roberto Collins; William Courtney; Andrew Dunsworth; Edward Farhi; Brooks Foxen; Austin Fowler; Craig Gidney; Marissa Giustina; Rob Graff; Keith Guerin; Steve Habegger; Matthew P. Harrigan; Michael J. Hartmann; Alan Ho; Markus Hoffmann; Trent Huang; Travis S. Humble; Sergei V. Isakov; Evan Jeffrey; Zhang Jiang; Dvir Kafri; Kostyantyn Kechedzhi; Julian Kelly; Paul V. Klimov; Sergey Knysh; Alexander Korotkov; Fedor Kostritsa; David Landhuis; Mike Lindmark; Erik Lucero; Dmitry Lyakh; Salvatore Mandrà; Jarrod R. McClean; Matthew McEwen; Anthony Megrant; Xiao Mi; Kristel Michielsen; Masoud Mohseni; Josh Mutus; Ofer Naaman; Matthew Neeley; Charles Neill; Murphy Yuezhen Niu; Eric Ostby; Andre Petukhov; John C. Platt; Chris Quintana; Eleanor G. Rieffel; Pedram Roushan; Nicholas C. Rubin; Daniel Sank; Kevin J. Satzinger; Vadim Smelyanskiy; Kevin J. Sung; Matthew D. Trevithick; Amit Vainsencher; Benjamin Villalonga; Theodore White; Z. Jamie Yao; Ping Yeh; Adam Zalcman; Hartmut Neven; John M. Martinis
err分享
err收藏
err
IF0
err
err0
errOAAI
err
err分享
err收藏
err
IF0
err
err0
errOAAI
err
err分享
err收藏
err分享
err收藏
err分享
err收藏
学者 查看更多内容