- Physical Review Journals
All JournalsPhysics Magazine
Access Provided by Xinjiang University

Physical Review E

Export citation

Export citation

Choose format for download:

Download Citation
  • Access by Xinjiang University

Quadratic unconstrained binary optimization formulation for rectified-linear-unit-type functions

Go Sato1, Makiko Konoshima2, Takuya Ohwa2, Hirotaka Tamura2, and Jun Ohkubo1,3,*

  • 1Graduate School of Science and Enginnering, Saitama University, 255 Shimo-Okubo, Sakura-ku, Saitama-shi 338-8570, Japan
  • 2Fujitsu Laboratories Ltd., 4-1-1 Kawasaki, Kanagawa 211-8558, Japan
  • 3JST, PREST, 4-1-8 Honcho, Kawaguchi, Saitama 332-0012, Japan

  • *johkubo@mail.saitama-u.ac.jp
PDF

Phys. Rev. E 99, 042106 – Published 4 April, 2019

DOI: https://doi.org/10.1103/PhysRevE.99.042106

Abstract

We propose a quadratic unconstrained binary optimization (QUBO) formulation of rectified-linear-unit (ReLU) type functions. Different from the q-loss function proposed by Denchev et al. [in Proceedings of the 29th International Conference on Machine Learning, Edinburgh, edited by J. Langford and J. Pineau (Omnipress, Madison, USA, 2012)], a simple discussion based on the Legendre duality is not sufficient to obtain the QUBO formulation of ReLU-type functions. In addition to the Legendre duality, we employ the Wolfe duality, and the QUBO formulation of ReLU type is derived. The QUBO formulation is available in Ising-type annealing methods, including quantum annealing machines.

View figure in article

Physics Subject Headings (PhySH)

Article Text

References (19)

  1. S. Kirkpatrick, C. D. Gelatt Jr., and M. P. Vecchi, Science 220, 671 (1983).
  2. P. Ray, B. K. Chakrabarti, and A. Chakrabarti, Phys. Rev. B 39, 11828 (1989).
  3. T. Kadowaki and H. Nishimori, Phys. Rev. E 58, 5355 (1998).
  4. E. Farhi, J. Goldstone, S. Gutmann, J. Lapan, A. Lundgren, and D. Preda, Science 292, 472 (2001).
  5. E. Boros and P. L. Hammer, Discrete Appl. Math. 123, 155 (2002).
  6. E. Boros, P. L. Hammer, and G. Tavares, J. Heuristics 13, 99 (2007).
  7. D-Wave, D-Wave Systems Inc., https://www.dwavesys.com/home/ (accessed 2017-11-16).
  8. M. Aramon, G. Rosenberg, E. Valiante, T. Miyazawa, H. Tamura, and H. G. Katzgraber, arXiv:1806.08815 [Frontier in Physics (to be published)].
  9. J. Biamonte, P. Wittek, N. Pancotti, P. Rebentrost, N. Wiebe, and S. Lloyd, Nature (London) 549, 195 (2017).
  10. J. D. Whitfield, M. Faccin, and J. D. Biamonte, Europhys. Lett. 99, 57004 (2012).
  11. D. P. Nazareth and J. D. Spaans, Phys. Med. Biol. 60, 4137 (2015).
  12. V. Denchev, N. Ding, S. V. N. Vishwanathan, and H. Neven, in Proceedings of the 29th International Conference on Machine Learning, Edinburgh, edited by J. Langford and J. Pineau (Omnipress, Madison, USA, 2012), p. 863.
  13. X. Glorot, A. Bordes, and Y. Bengio, Proc. Machine Learning Res. 15, 315 (2011).
  14. P. Wolfe, Quart. Appl. Math. 19, 239 (1961).
  15. R. Tibshirani, J. R. Stat. Soc., Ser. B 58, 267 (1994).
  16. D. Donoho, IEEE Trans. Inf. Theory 52, 1289 (2006).
  17. M. Lustig, D. Donoho, and J. Pauly, Magn. Reson. Med. 58, 1182 (2007).
  18. J. Haupt, W. Bajwa, M. Rabbat, and R. Nowak, IEEE Signal Process. Mag. 25, 92 (2008).
  19. V. S. Denchev, N. Ding, S. Matsushima, S. V. N. Vishwanathan, and H. Neven, arXiv:1504.01446.

Outline

Information

Phys. Rev. E 99, 042106– Published 4 April, 2019
  • Received 6 November 2018
Crossmark - Check for updates button

©2019 American Physical Society

Sign In to Your Journals Account

Filter

Filter

Article Lookup

Enter a citation