講演情報

[9p-N304-13]All Valid States HOBO Encoding for Travelling Salesperson Problem in Quantum Computing

〇Juncheng Wang1, Daisuke Tsukayama1, Takumi Kanezashi1, Jun-ichi Shirakashi1, Tetsuo Shibuya2, Hiroshi Imai2 (1.Tokyo Univ.Agr.&Tech., 2.Tokyo Univ.)

キーワード:

Gate-Based Quantum Computer ( Gate-Based Quantum Computer)、Quantum-Classical Hybrid Algorithm ( Quantum-Classical Hybrid Algorithm )、Variational Quantum Eigensolver ( Variational Quantum Eigensolver )

Researchers are committed to applying quantum computing to practical problems. In this context, we turn our attention to the Traveling Salesperson Problem (TSP), a classical combinatorial optimization problem that closely resembles real-world scenarios. When addressing combinatorial optimization problems in quantum computing, the Quadratic Unconstrained Binary Optimization (QUBO) model is often the first choice. However, due to the limited number of available qubits, the more efficient Higher-Order Binary Optimization (HOBO) model has been proposed, which reduces the required qubits from O(N 2) to O(N log N) by employing a more compact binary encoding. Nevertheless, the Hamiltonian constructed using this method often includes invalid states that cannot be utilized. To address this issue, we propose a cyclic mapping approach that effectively repurposes all invalid states.