按年被提到
20242024 · 2 次2026
物理与量子›量子计算·arXiv:2407.17207 · quant-ph

Solving The Travelling Salesman Problem Using A Single Qubit

Kapil Goswami, Gagan Anekonda Veereshi, Peter Schmelcher, Rick Mukherjee · 2024
开始阅读 ↗PDFalphaXiv 讨论
被提及 · 2 人首次 2024-07-25 · 最近 2024-08-01
2不同的人
2活跃月份
2讨论串
7被引(OpenAlex)
arXiv 摘要(候选层不写导读)

The travelling salesman problem (TSP) is a popular NP-hard-combinatorial optimization problem that requires finding the optimal way for a salesman to travel through different cities once and return to the initial city. The existing methods of solving TSPs on quantum systems are either gate-based or binary variable-based encoding. Both approaches are resource-expensive in terms of the number of qubits while performing worse compared to existing classical algorithms even for small-size problems. We present an algorithm that solves an arbitrary TSP using a single qubit by invoking the principle of quantum parallelism. The cities are represented as quantum states on the Bloch sphere while the preparation of superposition states allows us to traverse multiple paths at once. The underlying framework of our algorithm is a quantum version of the classical Brachistochrone approach. Optimal control methods are employed to create a selective superposition of the quantum states to find the shortest route of a given TSP. The numerical simulations solve a sample of four to nine cities for which exact solutions are obtained. The algorithm can be implemented on any quantum platform capable of efficiently rotating a qubit and allowing state tomography measurements. For the TSP problem sizes considered in this work, our algorithm is more resource-efficient and accurate than existing quantum algorithms with the potential for scalability. A potential speed-up of polynomial time over classical algorithms is discussed.

候选层:至少 2 个不同的人、在 2 个不同月份提到过,还没到主书架的 3 人 3 个月。没有做立场标注,所以只写“被提及”。

HN 书评

没有评论直接链到它;下面是它被提交的讨论串里回复最多的评论(不计入统计)

讨论串里没有 ≥100 字的评论,只有提交记录。

被提交为 story · 2 次