[17a-A22-1~12] KS.2 Quantum Information Engineering Group

11:15 AM - 11:30 AM JST(2:15 AM - 2:30 AM UTC)English Presentation

[17a-A22-9] Higher Order Binary Optimization: Advanced Encoding for Larger Scale Traveling Salesperson Problems through Variational Quantum Eigensolver

〇Juncheng Wang¹, Daisuke Tsukayama¹, Takumi Kanezashi¹, Jun-ichi Shirakashi¹, Tetsuo Shibuya², 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 salesperson problem (TSP) over N cities, QUBO requires N² qubits. 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. Unlike our previous presentation, this time we have improved the penalty function related to HOBO and conducted experiments on larger-scale problems, comparing the experimental results between QUBO and HOBO encodings.