Cited by 43Quantum Computing Algorithms and ArchitectureMetaheuristic Optimization Algorithms ResearchAdvanced Optimization Algorithms Research

Benchmark Test of Black-box Optimization Using D-Wave Quantum Annealer

Open access
Koshikawa, Ami S., Ohzeki, Masayuki, Kadowaki, Tadashi, Tanaka, Kazuyuki·2021·Journal of the Physical Society of Japan

Abstract

In solving optimization problems, objective functions generally need to be minimized or maximized. However, objective functions cannot always be formulated explicitly in a mathematical form for complicated problem settings. Although several regression techniques infer the approximate forms of objective functions, they are at times expensive to evaluate. Optimal points of "black-box" objective functions are computed in such scenarios, while effectively using a small number of clues. Recently, an efficient method by use of inference by sparse prior for a black-box objective function with binary variables has been proposed. In this method, a surrogate model was proposed in the form of a quadratic unconstrained binary optimization (QUBO) problem, and was iteratively solved to obtain the optimal solution of the black-box objective function. In the present study, we employ the D-Wave 2000Q quantum annealer, which can solve QUBO by driving the binary variables by quantum fluctuations. The D-Wave 2000Q quantum annealer does not necessarily output the ground state at the end of the protocol due to freezing effect during the process. We investigate effects from the output of the D-Wave quantum annealer in performing black-box optimization. We demonstrate a benchmark test by employing the sparse Sherrington-Kirkpatrick (SK) model as the black-box objective function, by introducing a parameter controlling the sparseness of the interaction coefficients. Comparing the results of the D-Wave quantum annealer to those of the simulated annealing (SA) and semidefinite programming (SDP), our results by the D-Wave quantum annealer and SA exhibit superiority in black-box optimization with SDP. On the other hand, we did not find any advantage of the D-Wave quantum annealer over the simulated annealing. As far as in our case, any effects by quantum fluctuation are not found.

The claims and statistics of this paper haven’t been checked yet.

Run the check — free, no account needed. It reads the open-access text and checks the sources it cites.

A few free checks a day · papers already verified open instantly · results are public

Integrity signals

Registry

Crossref · 10.7566/jpsj.90.064001

Cites

44 of 44 references verified0 citation errors · 0 not checkable

Statistics

Claims the paper makes

The claims and statistics of this paper haven’t been checked yet.

Run the check — free, no account needed. It reads the open-access text and checks the sources it cites.

A few free checks a day · papers already verified open instantly · results are public

Claims other papers make about this one

Each is checked against this paper’s own text: does it say what the citing paper says it does?

Self-check

Percentages, sums and reported differences re-computed from the paper’s own numbers.

The self-check needs the paper’s full text.

Cites

Flagged first, then by citations

Research works printed but not linked: 24

  1. [1]A. R.Oganov and C. W.Glass: The Journal of Chemical Physics 124 (2006) 244704.
  2. [2]J. Snoek, H. Larochelle, and R. P. Adams: Proceedings of the 25th International Conference on Neural Information Processing Systems - Volume 2, NIPS'12, 2012, pp. 2951-2959.
  3. [4]D. R. Jones, M. Schonlau, and W. J. Welch: Journal of Global Optimization 13 (1998) 455.
  4. [5]R. Baptista and M. Poloczek: In J. Dy and A. Krause (eds), Proceedings of the 35th International Conference on Machine Learning , Vol. 80 of Proceedings of Machine Learning Research , July 2018, pp. 462-471.
  5. [11]M. H.Amin, E. Andriyash, J. Rolfe, B. Kulchytskyy, and R. Melko: Physical Review X 8 (2018).
  6. [12]S. Suzuki and M. Okada: Journal of the Physical Society of Japan 74 (2005) 1649.
  7. [13]S. Morita and H. Nishimori: Journal of Mathematical Physics 49 (2008).
  8. [14]M. Ohzeki and H. Nishimori: Journal of Computational and Theoretical Nanoscience 8 (2011-06-01T00:00:00) 963.
  9. [19]C. Baldassi and R. Zecchina: Proceedings of the National Academy of Sciences 115 (2018) 1457.
  10. [20]S. Arai, M. Ohzeki, and K. Tanaka: arXiv:2102.08609 [cond-mat,dis-nn] (2021). · arXiv
  11. [21]K. Kitai, J. Guo, S. Ju, S. Tanaka, K. Tsuda, J. Shiomi, and R. Tamura: Physical Review Research 2 (2020).
  12. [22]J. Cai, W. G. Macready, and A. Roy: arXiv:1406.2741 [quant-ph] (2014). · arXiv
  13. [24]S. Okada, M. Ohzeki, and K. Tanaka: Journal of the Physical Society of Japan 89 (2020) 094801.
  14. [27]M. Kuramata, R. Katsuki, and K. Nakata: arXiv:2012.10135 [quant-ph] (2020). · arXiv
  15. [32]M. Ohzeki and H. Nishimori: Journal of Physics: Conference Series 302 (2011) 012047.
  16. [34]T. Kadowaki and M. Ohzeki: Journal of the Physical Society of Japan 88 (2019) 061008.
  17. [35]C. Takahashi, M. Ohzeki, S. Okada, M. Terabe, S. Taguchi, and K. Tanaka: Journal of the Physical Society of Japan 87 (2018) 074001.
  18. [38]E. Makalic and D. F. Schmidt: IEEE Signal Processing Letters 23 (2016) 179.
  19. [42]Y. Seki and H. Nishimori: Journal of Physics A: Mathematical and Theoretical 48 (2015) 335301.
  20. [45]S. Okada, M. Ohzeki, and K. Tanaka: Journal of the Physical Society of Japan 88 (2019) 024802.
  21. [46]M. Ohzeki: Journal of the Physical Society of Japan 88 (2019) 061005.
  22. [47]M. Yamaoka, C. Yoshimura, M. Hayashi, T. Okuyama, H. Aoki, and H. Mizuno: IEEE Journal of Solid-State Circuits 51 (2016) 303.
  23. [48]S. Tsukamoto, M. Takatsu, S. Matsubara, and H. Tamura: FUJITSU Sci. Tech. J., Vol. 53, 2017, p. 8.
  24. [50]H. M. Waidyasooriya, M. Hariyama, M. J. Miyama, and M. Ohzeki: The Journal of Supercomputing 75 (2019) 5019.

Cited by

Sorted by citations

Authors
Koshikawa, A. S., Ohzeki, M., Kadowaki, T., & Tanaka, K.
Affiliations
  • Tohoku University (JP)
  • Tokyo Institute of Technology (JP)
  • Denso (Japan) (JP)
Venue
Journal of the Physical Society of Japan
Published
2021-06-15
Volume
90
Issue
6
Pages
064001
ISSN
  • 0031-9015 (ISSN-L)
  • 1347-4073
OpenAlex
W3139206159
Cited by
43
References
44
Citations by year
2026: 4 · 2025: 11 · 2024: 4 · 2023: 13 · 2022: 8 · 2021: 3
FWCI
2.45
Type
journal article
Language
en
Open access
Licence
cc-by
Locations
  • Journal of the Physical Society of Japan (publishedVersion, cc-by)
  • arXiv (Cornell University) (submittedVersion)
  • arXiv (Cornell University)
Funders
  • Japan Society for the Promotion of Science (18H03303, 18J20396, 19H01095, 20H02168)
  • Japan Science and Technology Agency (JPMJCR1402)
  • Ministry of Education, Culture, Sports, Science and Technology (MXS0120352009)
Topics
  • Physical Sciences › Computer Science › Artificial Intelligence › Quantum Computing Algorithms and Architecture
  • Physical Sciences › Computer Science › Artificial Intelligence › Metaheuristic Optimization Algorithms Research
  • Physical Sciences › Mathematics › Numerical Analysis › Advanced Optimization Algorithms Research
Keywords
black-box optimization, D-Wave quantum annealer, quantum annealing, QUBO, Sherrington-Kirkpatrick model, simulated annealing, semidefinite programming, benchmark tests, binary optimization

About these checks

Registry, retraction, Cites and statistics results are computed, not judged, with one exception: a printed reference that no index lists is read once by a model before it counts as a citation error. Claims are extracted by a model and kept only when their quote appears verbatim in the text; each cited source is then checked, with a model’s help, for whether it says what the claim relies on. Those verdicts can be wrong — read the claim’s quote and the cited source before relying on one.

Statistics and arithmetic are recomputed, not judged.

Confidence bands are shown only for fields calibrated on our annotated test set. None is calibrated yet, so no band is shown.

What counts as a claim ›How we measure confidence ›How we check this ›

Are you an author, or do you see a problem with this page? Request a review