[23p-A302-1~13] FS.1 Focused Session "AI Electronics"

2:00 PM - 2:15 PM JST(5:00 AM - 5:15 AM UTC)English Presentation

[23p-A302-4] Binary Encoding for Solving Traveling Salesman Problem Using Variational Quantum Eigensolver

〇Juncheng Wang¹, Daisuke Tsukayama¹, Shanchuan Li¹, Jun-ichi Shirakashi¹, Hiroshi Imai² (1.Tokyo Univ. Agr. & Tech., 2.Univ. Tokyo)

Keywords:

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 N² 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(N²) to O(N log N), however, the number of gates needed is O(N³).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.