Quantum speedup of the Travelling Salesman Problem for bounded-degree graphs
Quantum speedup of the Travelling Salesman Problem for bounded-degree graphs
复制标题
有界度图旅行商问题的量子加速
DOI：
--
复制
发表时间：
2016
期刊：
影响因子：
--
通讯作者：
A. Montanaro
中科院分区：
文献类型：
--
作者：
Alexandra E. Moylett;N. Linden;A. Montanaro
旅行推销员问题是一个标志性的路线寻找任务，从芯片设计到规划和物流都有应用。在这里，作者表明，如果要访问的城市的图是低度的，一个旅行推销员配备了量子卫星导航可以找到最佳路线的平方比使用任何已知的经典方法更快。
The traveling-salesman problem is an iconic route-finding task, with applications from chip design to planning and logistics. Here the authors show that if the graph of cities to be visited is of low degree, a traveling salesman armed with a quantum satnav can find the best route quadratically faster than using any known classical method.