Quantum annealing for combinatorial optimization: a benchmarking study

doi:10.1038/s41534-025-01020-1

2025-05-16

Seongmin Kim

Sang Il Ahn

In‐Saeng Suh

Alexander W. Dowling *

Luo, Tengfei *

DOI：10.1038/s41534-025-01020-1

原文链接

原文求助

摘要

En 中文

量子退火（QA）在求解组合优化问题时，相比经典优化方法，具有显著提升解质量并降低时间复杂度的潜力。然而，由于量子比特数量有限及其连接性限制，过去在基准测试研究中，QA硬件并未展现出对经典方法的此类优势。近期量子退火在量子比特数量超过5000个、量子比特连接性增强以及混合架构方面的进展，有望实现量子优势。在此，我们采用具有最先进技术的量子退火机，并将其性能与经典求解器进行基准测试。为比较两者性能，我们使用量子与经典求解器，求解由大型且密集的哈密顿矩阵表示的50多个优化问题实例。结果表明，最先进的量子求解器相比最佳经典求解器，具有更高的精度（约0.013%）和显著更快的解决问题时间（约6561倍）。我们的研究突出了利用量子退火相对于经典方法的优越性，特别是在混合配置下，能够实现高精度及大幅缩短大规模实际优化问题的求解时间。

Keyword:

DESIGN

期刊

npj Quantum Information

IF:

8.3

论文数:

1.4K

被引数:

8.1K

机构

暂无机构信息

引用论文

Quantum annealing-aided design of an ultrathin-metamaterial optical diode

NANO CONVERGENCE

IF11

2024-05-09

OAAI

Kim, Seongmin; Park, Su-Jin; Moon, Seunghyun; Zhang, Qiushi; Hwang, Sanghyo; Kim, Sun-Kyung; Luo, Tengfei; Lee, Eungkyu

Theory of Quantum Annealing of an Ising Spin Glass

Science

IF0

2002-03-29

OAAI

Giuseppe E. Santoro; Roman Martoňák; Erio Tosatti; Roberto Car

Design of a High-Performance Titanium Nitride Metastructure-Based Solar Absorber Using Quantum Computing-Assisted Optimization

ACS APPLIED MATERIALS & INTERFACES

IF8.2

2023-08-18

PREAI

Kim, Seongmin; Wu, Shiwen; Jian, Ruda; Xiong, Guoping; Luo, Tengfei

A comparison of simulated annealing schedules for constructal design of complex cavities intruded into conductive walls with internal heat generation

ENERGY

IF9.4

2015-12-01

PREAI

Gonzales, G. V.; Estrada, E. da S. D.; Emmendorfer, L. R.; Isoldi, L. A.; Xie, G.; Rocha, L. A. O.; dos Santos, E. D.

Searching for optimal experimental parameters with D-Wave quantum annealer for fabrication of Au atomic junctions 使用D-Wave量子退火机搜索制备Au原子结的最佳实验参数

Applied Physics Express

IF0

2023-05-02

PREAI

Yuri Yoneda; Moe Shimada; Asaki Yoshida; Jun-ichi Shirakashi

Quantum supremacy using a programmable superconducting processor 使用可编程超导处理器实现量子霸权

Nature

IF0

2019-10-23

OAAI

Frank 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

Quantum annealing in the transverse Ising model

Physical Review E

IF0

1998-11-01

OAAI

Tadashi Kadowaki; Hidetoshi Nishimori

Hybrid quantum annealing via molecular dynamics 基于分子动力学的混合量子退火

SCIENTIFIC REPORTS

IF3.9

2021-04-19

OAAI

Irie, Hirotaka; Liang, Haozhao; Doi, Takumi; Gongyo, Shinya; Hatsuda, Tetsuo