pith. sign in

arxiv: 2606.20017 · v1 · pith:7N3LFZ7Mnew · submitted 2026-06-18 · 🪐 quant-ph

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

Juncheng Wang , Takumi Kanezashi , Daisuke Tsukayama , Koki Awaya , Reo Saito , Jun-ichi Shirakashi , Tetsuo Shibuya , Hiroshi Imai This is my paper

Pith reviewed 2026-06-26 17:19 UTC · model grok-4.3

classification 🪐 quant-ph
keywords VQEHOBOTSPNISQquantum optimizationconstrained combinatorial optimizationcyclic mappingpenalty terms
0
0 comments X

The pith

AVS-HOBO encoding eliminates one penalty term in TSP Hamiltonians by cyclic mapping of all binary states to valid tours.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The paper introduces an all-valid-state higher-order binary optimization encoding for solving the traveling salesperson problem with variational quantum eigensolvers. It applies cyclic mapping so that every binary string represents a valid tour, removing the need for one penalty term that standard HOBO encodings require. Noiseless simulations of up to 20 cities and runs on real quantum hardware demonstrate better energy convergence, higher feasibility ratios, and improved scalability versus the original HOBO approach. The method targets practical use of VQE on NISQ devices for constrained combinatorial optimization problems.

Core claim

The central claim is that cyclic mapping in the HOBO formulation converts all 2^n binary states into representations of valid tours for TSP, eliminating one penalty term from the Hamiltonian while preserving the relative energies of valid solutions and avoiding new local minima that would impair VQE.

What carries the argument

The AVS-HOBO scheme based on cyclic mapping, which reuses states that would otherwise be invalid to remove a penalty term from the cost Hamiltonian.

If this is right

  • Higher approximation and tour-length ratios emerge in VQE runs for TSP instances up to 20 cities.
  • Feasibility ratios increase because invalid states no longer need explicit penalization.
  • Scalability improves for larger constrained optimization instances on NISQ hardware.
  • The encoding extends to other problems that impose permutation or ordering constraints in quantum optimization.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

  • The same cyclic-mapping trick could reduce qubit overhead in other ordering-constrained problems such as job-shop scheduling.
  • Device-specific error profiles observed in the hardware comparisons suggest the method's advantage may be largest on chips with particular two-qubit gate fidelities.
  • Combining AVS-HOBO with existing error-mitigation stacks could compound the observed feasibility gains without changing the encoding itself.

Load-bearing premise

Cyclic mapping reuses states without distorting the relative energies of valid tours or creating new local minima that degrade VQE performance.

What would settle it

An experiment on the same NISQ device that finds AVS-HOBO yields equal or lower feasibility ratios and slower energy convergence than standard HOBO for identical TSP instances would falsify the performance claim.

Figures

Figures reproduced from arXiv: 2606.20017 by Daisuke Tsukayama, Hiroshi Imai, Juncheng Wang, Jun-ichi Shirakashi, Koki Awaya, Reo Saito, Takumi Kanezashi, Tetsuo Shibuya.

Figure 1
Figure 1. Figure 1: FIG. 1. Hamiltonian construction method. (a) One possible [PITH_FULL_IMAGE:figures/full_fig_p002_1.png] view at source ↗
Figure 2
Figure 2. Figure 2: FIG. 2. Cyclic mapping used in AVS-HOBO to replace the [PITH_FULL_IMAGE:figures/full_fig_p004_2.png] view at source ↗
Figure 3
Figure 3. Figure 3: FIG. 3. Ratio of feasible states in the Hilbert space for different encoding methods, where feasible states are those that satisfy [PITH_FULL_IMAGE:figures/full_fig_p005_3.png] view at source ↗
Figure 4
Figure 4. Figure 4: FIG. 4. Solution energy landscape. (a) Results obtained using the original HOBO method. The horizontal axis shows the [PITH_FULL_IMAGE:figures/full_fig_p005_4.png] view at source ↗
Figure 5
Figure 5. Figure 5: FIG. 5. Relationship between the residual energy and the iteration number for the TSP. The figure shows the residual energies [PITH_FULL_IMAGE:figures/full_fig_p007_5.png] view at source ↗
Figure 6
Figure 6. Figure 6: FIG. 6. Average approximation ratio over 20 instances for [PITH_FULL_IMAGE:figures/full_fig_p008_6.png] view at source ↗
Figure 7
Figure 7. Figure 7: FIG. 7. Length ratio for the TSP using AVS-HOBO and HOBO. (a) Average LR over 20 instances for each city size in [PITH_FULL_IMAGE:figures/full_fig_p009_7.png] view at source ↗
Figure 8
Figure 8. Figure 8: FIG. 8. Feasibility ratio for the TSP using AVS-HOBO and HOBO. (a) Average FR over 20 instances for each city size in [PITH_FULL_IMAGE:figures/full_fig_p009_8.png] view at source ↗
Figure 9
Figure 9. Figure 9: FIG. 9. Average AR values for different city sizes obtained on [PITH_FULL_IMAGE:figures/full_fig_p010_9.png] view at source ↗
Figure 10
Figure 10. Figure 10: FIG. 10. Average LR and FR values for different city sizes. (a) and (c) show the results obtained on the real quantum hardware [PITH_FULL_IMAGE:figures/full_fig_p011_10.png] view at source ↗
Figure 11
Figure 11. Figure 11: FIG. 11. Effects of error mitigation strategies on real quantum hardware. (a) and (c) show the approximation ratio (AR), [PITH_FULL_IMAGE:figures/full_fig_p012_11.png] view at source ↗
read the original abstract

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.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Referee Report

3 major / 2 minor

Summary. The manuscript introduces an all-valid-state HOBO (AVS-HOBO) encoding for the traveling salesperson problem (TSP) that employs a cyclic mapping to reuse states that would otherwise be invalid under standard binary encoding. This construction eliminates one penalty term from the Hamiltonian. The authors compare AVS-HOBO against the original HOBO encoding in VQE simulations (noiseless, up to 20 cities) and on real NISQ hardware, reporting improvements in energy convergence, approximation ratio, tour length, and feasibility ratio, and claim broader applicability to constrained quantum optimization.

Significance. If the cyclic mapping preserves the relative energies among valid tours and does not introduce new local minima, the reduction in penalty terms could improve the practical performance and scalability of VQE for constrained combinatorial problems on NISQ devices. The hardware experiments and direct comparison of encodings provide concrete evidence that would be valuable if the underlying spectral assumption holds.

major comments (3)
  1. [§3] §3 (Encoding construction): The central claim that the cyclic mapping reuses invalid states without distorting the energy differences among valid tours or creating spurious minima is load-bearing for all reported performance gains. No explicit comparison of the restricted spectrum on valid configurations (before vs. after mapping) or degeneracy analysis is provided; without this, the reported improvements in feasibility ratio and tour length for n=20 instances could be artifacts of the specific penalty coefficients rather than a general property of AVS-HOBO.
  2. [Results] Results section (simulation and hardware metrics): The abstract and reported comparisons give energy, tour length, and feasibility ratios but supply no error bars, number of independent VQE runs, or statistical tests. This prevents assessment of whether the observed gains are significant or reproducible, directly undermining the claim of enhanced reliability on NISQ devices.
  3. [Hardware experiments] Hardware experiments: The manuscript states that different error-mitigation methods were tested on real chips, yet provides no quantitative breakdown of how mitigation interacts with the AVS-HOBO Hamiltonian (e.g., whether the eliminated penalty term changes the noise sensitivity). This detail is required to support the claim that AVS-HOBO improves practical reliability.
minor comments (2)
  1. [Abstract] The phrase 'noiseless simulations representative of NISQ devices' is imprecise; clarify whether any noise model was actually applied or whether the simulations are purely ideal.
  2. [§3] Notation for the cyclic mapping and the resulting HOBO terms should be introduced with an explicit example for a small TSP instance (e.g., n=4) to make the state reuse concrete.

Simulated Author's Rebuttal

3 responses · 0 unresolved

We thank the referee for the constructive comments, which help improve the clarity and rigor of our work. We address each major point below and will revise the manuscript accordingly.

read point-by-point responses

  1. Referee: [§3] §3 (Encoding construction): The central claim that the cyclic mapping reuses invalid states without distorting the energy differences among valid tours or creating spurious minima is load-bearing for all reported performance gains. No explicit comparison of the restricted spectrum on valid configurations (before vs. after mapping) or degeneracy analysis is provided; without this, the reported improvements in feasibility ratio and tour length for n=20 instances could be artifacts of the specific penalty coefficients rather than a general property of AVS-HOBO.

    Authors: We agree that an explicit spectral comparison strengthens the central claim. The cyclic mapping is constructed to induce a bijection on valid tour configurations while leaving the relative energies among them unchanged (the eliminated penalty applies exclusively to invalid states). In the revised manuscript we will add to §3 a direct side-by-side evaluation of the restricted Hamiltonian on all valid configurations before and after mapping, together with a degeneracy count, to confirm that no new local minima are introduced among valid tours. revision: yes

  2. Referee: [Results] Results section (simulation and hardware metrics): The abstract and reported comparisons give energy, tour length, and feasibility ratios but supply no error bars, number of independent VQE runs, or statistical tests. This prevents assessment of whether the observed gains are significant or reproducible, directly undermining the claim of enhanced reliability on NISQ devices.

    Authors: We accept that statistical reporting is necessary for reproducibility claims. The revised Results section will state the number of independent VQE runs executed per instance, include error bars (standard deviation across runs) on all plotted metrics, and add paired statistical tests to quantify the significance of observed differences between the two encodings. revision: yes

  3. Referee: [Hardware experiments] Hardware experiments: The manuscript states that different error-mitigation methods were tested on real chips, yet provides no quantitative breakdown of how mitigation interacts with the AVS-HOBO Hamiltonian (e.g., whether the eliminated penalty term changes the noise sensitivity). This detail is required to support the claim that AVS-HOBO improves practical reliability.

    Authors: We will expand the hardware section with a quantitative comparison. The revision will include tables reporting mitigated versus unmitigated metrics for both encodings on each device, together with an analysis of how the reduced penalty term in AVS-HOBO alters observed noise sensitivity under the tested mitigation strategies. revision: yes

Circularity Check

0 steps flagged

No significant circularity; AVS-HOBO is a direct construction with independent empirical validation

full rationale

The paper proposes the AVS-HOBO encoding as an explicit construction using cyclic mapping to eliminate one penalty term and reuse otherwise-invalid states in the TSP Hamiltonian. Performance gains are shown via direct comparison of energy convergence, approximation ratios, tour lengths, and feasibility ratios in simulations up to n=20 and on real hardware, without any reduction of results to fitted parameters, self-definitional equivalences, or load-bearing self-citations. The derivation chain consists of a new ansatz plus external benchmarking, making the central claims self-contained rather than circular by construction.

Axiom & Free-Parameter Ledger

0 free parameters · 1 axioms · 0 invented entities

The central claim rests on standard domain assumptions about VQE convergence on the constructed Hamiltonian and the correctness of the cyclic mapping; no free parameters or invented entities are visible in the abstract.

axioms (1)
  • domain assumption VQE can locate low-energy states of the HOBO Hamiltonian that correspond to good TSP tours under the chosen encoding.
    Invoked by the use of VQE to solve the encoded problem and by the comparison of energy convergence and feasibility ratios.

pith-pipeline@v0.9.1-grok · 5790 in / 1312 out tokens · 20003 ms · 2026-06-26T17:19:00.478213+00:00 · methodology

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Reference graph

Works this paper leans on

40 extracted references · 4 linked inside Pith

  1. [1]

    Cerezo, A

    M. Cerezo, A. Arrasmith, R. Babbush, S. C. Benjamin, S. Endo, K. Fujii, J. R. McClean, K. Mitarai, X. Yuan, L. Cincio,et al., Nature Reviews Physics3, 625 (2021)

    2021

  2. [2]

    Preskill, Quantum2, 79 (2018)

    J. Preskill, Quantum2, 79 (2018)

    2018

  3. [3]

    Bharti, A

    K. Bharti, A. Cervera-Lierta, T. H. Kyaw, T. Haug, S. Alperin-Lea, A. Anand, M. Degroote, H. Heimonen, J. S. Kottmann, T. Menke,et al., Reviews of Modern Physics94, 015004 (2022)

    2022

  4. [4]

    N. Moll, P. Barkoutsos, L. S. Bishop, J. M. Chow, A. Cross, D. J. Egger, S. Filipp, A. Fuhrer, J. M. Gam- betta, M. Ganzhorn,et al., Quantum Science and Tech- nology3, 030503 (2018)

    2018

  5. [5]

    D. F. Perez-Ramirez, arXiv preprint arXiv , :2407.06421 (2024)

    arXiv 2024

  6. [6]

    Nannicini, Physical Review E99, 013304 (2019)

    G. Nannicini, Physical Review E99, 013304 (2019)

    2019

  7. [7]

    Glover, G

    F. Glover, G. Kochenberger, R. Hennig, and Y. Du, An- nals of Operations Research314, 141 (2022)

    2022

  8. [8]

    Lucas, Frontiers in physics2, 74887 (2014)

    A. Lucas, Frontiers in physics2, 74887 (2014)

    2014

  9. [9]

    Salehi, A

    Ö. Salehi, A. Glos, and J. A. Miszczak, Quantum Infor- mation Processing21, 67 (2022)

    2022

  10. [10]

    Palackal, B

    L. Palackal, B. Poggel, M. Wulff, H. Ehm, J. M. Lorenz, and C. B. Mendl, Proceedings of the 2023 IEEE Inter- national Conference on Quantum Computing and Engi- neering (QCE) , 648 (2023)

    2023

  11. [11]

    Domino, A

    K. Domino, A. Kundu, Ö. Salehi, and K. Krawiec, Quan- tum Information Processing21, 337 (2022)

    2022

  12. [12]

    Y. Chai, L. Funcke, T. Hartung, K. Jansen, S. Kühn, P. Stornati, and T. Stollenwerk, Physical review applied 20, 064025 (2023)

    2023

  13. [13]

    A. Glos, A. Krawiec, and Z. Zimborás, npj Quantum In- formation8, 39 (2022)

    2022

  14. [14]

    Schnaus, L

    M. Schnaus, L. Palackal, B. Poggel, X. Runge, H. Ehm, J. M. Lorenz, and C. B. Mendl, Proceedings of the 2024 IEEE International Conference on Quantum Software (QSW) , 81 (2024)

    2024

  15. [15]

    Farhi, J

    E. Farhi, J. Goldstone, and S. Gutmann, arXiv preprint arXiv , :1411.4028 (2014)

    Pith/arXiv arXiv 2014

  16. [16]

    Farhi, J

    E. Farhi, J. Goldstone, S. Gutmann, and H. Neven, arXiv preprint arXiv , :1703.06199 (2017)

    Pith/arXiv arXiv 2017

  17. [17]

    W. Qian, R. A. Basili, M. M. Eshaghian-Wilner, A. Khokhar, G. Luecke, and J. P. Vary, Entropy25, 1238 (2023)

    2023

  18. [18]

    Peruzzo, J

    A. Peruzzo, J. McClean, P. Shadbolt, M.-H. Yung, X.-Q. Zhou, P. J. Love, A. Aspuru-Guzik, and J. L. O’brien, Nature communications5, 4213 (2014)

    2014

  19. [19]

    Tilly, H

    J. Tilly, H. Chen, S. Cao, D. Picozzi, K. Setia, Y. Li, E. Grant, L. Wossnig, I. Rungger, G. H. Booth,et al., Physics Reports986, 1 (2022)

    2022

  20. [20]

    J. R. McClean, J. Romero, R. Babbush, and A. Aspuru- Guzik, New Journal of Physics18, 023023 (2016)

    2016

  21. [21]

    Tsukayama, J.-i

    D. Tsukayama, J.-i. Shirakashi, T. Shibuya, and H. Imai, AIP Advances15(2025)

    2025

  22. [22]

    Zaborniak and U

    T. Zaborniak and U. Stege, arXiv preprint arXiv , :2305.00568 (2023)

    arXiv 2023

  23. [23]

    K. M. Nakanishi, K. Fujii, and S. Todo, Physical Review Research2, 043158 (2020)

    2020

  24. [24]

    D. P. Kingma and J. Ba, arXiv preprint arXiv , :1412.6980 (2014)

    Pith/arXiv arXiv 2014

  25. [25]

    Tsukayama, J.-i

    D. Tsukayama, J.-i. Shirakashi, and H. Imai, Japanese Journal of Applied Physics62, 088003 (2023)

    2023

  26. [26]

    Javadi-Abhari, M

    A. Javadi-Abhari, M. Treinish, K. Krsulich, C. J. Wood, J. Lishman, J. Gacon, S. Martiel, P. D. Nation, L. S. Bishop, A. W. Cross,et al., arXiv preprint arXiv , :2405.08810 (2024)

    Pith/arXiv arXiv 2024

  27. [27]

    IBM, Ibm quantum platform (2026),https: //quantum-computing.ibm.com/

    2026

  28. [28]

    Matsuo, Y

    A. Matsuo, Y. Suzuki, I. Hamamura, and S. Yamashita, IEICE TRANSACTIONS on Information and Systems 106, 1772 (2023)

    2023

  29. [29]

    IBM Corporation, Ibm ilog cplex optimiza- tion studio user’s manual for cplex (2026), https://www.ibm.com/docs/en/icos/22.1.1?topic= optimizers-users-manual-cplex

    2026

  30. [30]

    S. V. Barron, D. J. Egger, E. Pelofske, A. Bärtschi, S. Ei- denbenz, M. Lehmkuehler, and S. Woerner, Nature Com- putational Science4, 865 (2024)

    2024

  31. [31]

    T. A. Chowdhury, K. Yu, M. A. Shamim, M. Kabir, and R. S. Sufian, Physical Review Research6, 033107 (2024)

    2024

  32. [32]

    Lubinski, J

    T. Lubinski, J. J. Goings, K. Mayer, S. Johri, N. Reddy, A. Mehta, N. Bhatia, S. Rappaport, D. Mills, C. H. Bald- win,et al., arXiv preprint arXiv , :2402.08985 (2024)

    arXiv 2024

  33. [33]

    Ezzell, B

    N. Ezzell, B. Pokharel, L. Tewala, G. Quiroz, and D. A. Lidar, Physical Review Applied20, 064027 (2023)

    2023

  34. [34]

    B. Yang, R. Raymond, and S. Uno, Physical Review A 106, 012423 (2022)

    2022

  35. [35]

    Kanezashi, D

    T. Kanezashi, D. Tsukayama, J.-i. Shirakashi, T. Shibuya, and H. Imai, Applied Physics Express 18, 047001 (2025)

    2025

  36. [36]

    P. K. Barkoutsos, G. Nannicini, A. Robert, I. Tavernelli, and S. Woerner, Quantum4, 256 (2020)

    2020

  37. [37]

    R. Sato, C. Gordon, K. Saito, H. Kawashima, T. Nikuni, and S. Watabe, IEEE Transactions on Quantum Engi- neering (2025)

    2025

  38. [38]

    L. Liu, L. Qian, X.-Y. Wu, C.-R. Fan, L.-F. Zhang, D.-B. Cai, H.-J. Lu, T.-J. Wang, and C. Wang, IEEE Transac- tions on Intelligent Transportation Systems (2025)

    2025

  39. [39]

    Y. Sano, K. Mitarai, N. Yamamoto, and N. Ishikawa, IEEE Transactions on Quantum Engineering5, 1 (2024)

    2024

  40. [40]

    Gilliam, S

    A. Gilliam, S. Woerner, and C. Gonciulea, Quantum5, 428 (2021)

    2021