Combinatorial optimization by simulating adiabatic bifurcations in nonlinear Hamiltonian systems

See allHide authors and affiliations

Science Advances  19 Apr 2019:
Vol. 5, no. 4, eaav2372
DOI: 10.1126/sciadv.aav2372

eLetters is an online forum for ongoing peer review. Submission of eLetters are open to all . Please read our guidelines before submitting your own eLetter.

Compose eLetter

Plain text

  • Plain text
    No HTML tags allowed.
  • Web page addresses and e-mail addresses turn into links automatically.
  • Lines and paragraphs break automatically.
Author Information
First or given name, e.g. 'Peter'.
Your last, or family, name, e.g. 'MacMoody'.
Your email address, e.g.
Your role and/or occupation, e.g. 'Orthopedic Surgeon'.
Your organization or institution (if applicable), e.g. 'Royal Free Hospital'.
Statement of Competing Interests

This question is for testing whether or not you are a human visitor and to prevent automated spam submissions.

Vertical Tabs

  • RE: Authors’ response to Prof. Stefan Boettcher’s comment
    • Hayato Goto, Senior Research Scientist, Toshiba Corporation
    • Other Contributors:
      • Kosuke Tatsumura, Senior Research Scientist, Toshiba Corporation
      • Alexander R. Dixon, Research Scientist, Toshiba Corporation

    Prof. Boettcher points out that our best result for the 2000-node MAX-CUT problem will miss 600 cuts (about 1.8% of its maximum cut value), where the maximum cut value is estimated to be 33,600 using a method based on statistical mechanics and our best result is estimated to be 33,000 by analysis of Fig. 2B. For completeness we provide the exact best cut value presented in Fig. 2B: 33,155, which means that it will miss about 445 cuts (about 1.3% of the estimated maximum cut value). This is an important and interesting point, because this estimation indicates that the approximate solutions obtained by the SB machine are actually very close to the optimal solution. In other words, we believe that this result supports our conclusion that our SB machine can obtain fairly good approximate solutions in a short time, 0.5 ms in this case, and that many applications would benefit from the substantial speedup. In our opinion, this performance is surprising and of interest as the first result obtained by the newly proposed heuristic algorithm based on a completely new mechanism, that is, classical adiabatic evolution. (To the best of our knowledge, this is the first example of “classical adiabatic optimization.” By contrast, quantum adiabatic optimization based on the quantum adiabatic theorem has been well known and been studied in the past two decades since its proposal in Refs. 10 and 11.) In response to the question regarding the achievable solution accuracy and its scaling with...

    Show More
    Competing Interests: H.G. and K.T. are inventors on two U.S. patent applications related to this work filed by the Toshiba Corporation (no. 16/123146, filed 6 September 2018; no. 16/118646, filed 31 August 2018). The authors declare that they have no other competing interests.
  • RE: Systematic testing of heuristics for hard combinatorial problems
    • Stefan Boettcher, Professor of Physics, Emory University, Department of Physics

    Not to take away from the beauty and power of the presented algorithm and its implementation, I still feel compelled to note that this presentation is missing out on a far more powerful method of assessing its capabilities. (Incidentally, this is true for previous studies, like for the “digital annealer” cited here, and many similar comparisons.) As long as test instances can be defined over an ensemble (and the all-to-all Ising instance used here is obtained from a particularly well known ensemble!), then finite-size scaling from statistical mechanics allows for quite a stringent assessment: Plotting ensemble averages of optima for instances drawn first from rather small sizes N (which are likely exact optima) and ranging to increasingly larger N, one will quickly learn how those optima likely scale with large N. (In the Ising case here, to leading order it is exactly known to be N^(3/2) when J's are drawn from a symmetric distribution with sigma=1, but such knowledge is generally not essential.) Thus, defining intensive Ising energies e(N)=E/N^(3/2), these should converge smoothly to a finite limit. As heuristics for NP-hard problems are inherently limited, this will inevitably manifest itself in quantifiable deviations from that scaling for larger N. In fact, it is often possible to also extract first-order scaling corrections from small-N (likely exact) data to find asymptotically: e(N)~e(infinity)+A/N^omega, with e(infinity), A, and omega numerically extracted fr...

    Show More
    Competing Interests: None declared.

Stay Connected to Science Advances

Navigate This Article