Curator's Take
This article shows that a clever reformulation of the traveling‑salesperson problem—an all‑valid‑state HOBO (AVS‑HOBO) encoding—can cut out an entire penalty term and recycle otherwise discarded basis states, directly addressing one of the biggest bottlenecks in NISQ‑scale constrained optimization. By demonstrating faster energy convergence and higher feasibility ratios on both noiseless simulations up to 20 cities and real hardware across several chip families, it builds on recent advances in VQE constraint handling and error‑mitigation to push practical problem sizes a step farther. The work suggests that smarter encodings may be as crucial as hardware improvements for achieving useful quantum advantage on combinatorial tasks, though the results still hinge on current noise levels and limited circuit depth.
— Mark Eatherly
Summary
Continued advancements in quantum computing have stimulated growing interest in translating quantum technologies into real-world applications. Consequently, the investigation of practically motivated NP-hard problems is of significant value. This study investigates the performance of a variational quantum eigensolver (VQE) in addressing the traveling salesperson problem (TSP) through noiseless simulations representative of noisy intermediate-scale quantum (NISQ) devices using higher-order binary optimization (HOBO) encodings. We construct a HOBO Hamiltonian with an efficient binary representation and propose an all-valid-state HOBO (AVS-HOBO) scheme based on cyclic mapping that eliminates one penalty term and reuses states that would otherwise be invalid. Using TSP instances of up to 20 cities, we compare the original HOBO and AVS-HOBO encodings from multiple perspectives, including the energy convergence behavior and the approximation, tour-length, and feasibility ratios. In addition to simulations, we perform computations on real quantum hardware with different device architectures, where we not only compare the performances of different chips but also investigate the effects of different error-mitigation methods on actual quantum machines. The results indicate that AVS-HOBO encoding enhances the practical reliability of VQE on NISQ devices and improves scalability for larger TSP instances, with broader applicability to constrained quantum optimization problems.