講演情報
[23p-A302-4]Binary Encoding for Solving Traveling Salesman Problem Using Variational Quantum Eigensolver
〇Juncheng Wang1, Daisuke Tsukayama1, Shanchuan Li1, Jun-ichi Shirakashi1, Hiroshi Imai2 (1.Tokyo Univ. Agr. & Tech., 2.Univ. Tokyo)
キーワード：
Gate-Based Quantum Computer、Quantum-Classical Hybrid Algorithm、Variational Quantum Eigensolver
Quadratic unconstrained binary optimization (QUBO) is a well-known formulation that can represent a wide range of combinational optimization problems. For solving traveling salesman problem (TSP) over N cities, QUBO requires N2 bits. On the other way, in recent years, higher-order binary optimization (HOBO) was used with quantum approximate optimization algorithm (QAOA) for solving TSP. HOBO reduces the number of qubits from O(N2) to O(N log N), however, the number of gates needed is O(N3).We previously proposed that variational quantum eigensolver (VQE), which has a lower circuit cost compared to QAOA, can solve combinatorial optimization problems with higher accuracy. In this study, we introduced HOBO into VQE to solve TSP of the same scale using fewer qubits and compared the experimental results between QUBO and HOBO encodings.