All-valid-state HOBO encoding for constrained combinatorial optimization on NISQ devices

@misc{wang2026allvalidstate,
  title = {{All-valid-state HOBO encoding for constrained combinatorial optimization on NISQ devices}},
  author = {Juncheng Wang and Takumi Kanezashi and Daisuke Tsukayama and Koki Awaya and Reo Saito and Jun-ichi Shirakashi and Tetsuo Shibuya and Hiroshi Imai},
  howpublished = {arXiv},
  year = {2026},
  month = jun,
  doi = {10.48550/arxiv.2606.20017},
  eprint = {2606.20017},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2606.20017},
}

TY  - UNPB
TI  - All-valid-state HOBO encoding for constrained combinatorial optimization on NISQ devices
AU  - Juncheng Wang
AU  - Takumi Kanezashi
AU  - Daisuke Tsukayama
AU  - Koki Awaya
AU  - Reo Saito
AU  - Jun-ichi Shirakashi
AU  - Tetsuo Shibuya
AU  - Hiroshi Imai
PY  - 2026
DA  - 2026/06/18
PB  - arXiv
DO  - 10.48550/arxiv.2606.20017
UR  - https://arxiv.org/abs/2606.20017
AB  - 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.
ER  -