Dual-Matrix Domain Wall: A Novel Technique for Generating Permutations by QUBO and Ising Models with Quadratic Sizes

DOI DOI Web Site 28 References
  • Koji Nakano
    Graduate School of Advanced Science and Engineering, Hiroshima University, Kagamiyama 1-4-1, Higashihiroshima 739-8527, Hiroshima, Japan
  • Shunsuke Tsukiyama
    Graduate School of Advanced Science and Engineering, Hiroshima University, Kagamiyama 1-4-1, Higashihiroshima 739-8527, Hiroshima, Japan
  • Yasuaki Ito
    Graduate School of Advanced Science and Engineering, Hiroshima University, Kagamiyama 1-4-1, Higashihiroshima 739-8527, Hiroshima, Japan
  • Takashi Yazane
    Research and Development Headquarters, NTT DATA Group Corporation, Toyosu Center Bldg, Annex, 3-9, Toyosu 3-chome, Koto-ku 135-8671, Tokyo, Japan
  • Junko Yano
    Research and Development Headquarters, NTT DATA Group Corporation, Toyosu Center Bldg, Annex, 3-9, Toyosu 3-chome, Koto-ku 135-8671, Tokyo, Japan
  • Takumi Kato
    Research and Development Headquarters, NTT DATA Group Corporation, Toyosu Center Bldg, Annex, 3-9, Toyosu 3-chome, Koto-ku 135-8671, Tokyo, Japan
  • Shiro Ozaki
    Research and Development Headquarters, NTT DATA Group Corporation, Toyosu Center Bldg, Annex, 3-9, Toyosu 3-chome, Koto-ku 135-8671, Tokyo, Japan
  • Rie Mori
    Research and Development Headquarters, NTT DATA Group Corporation, Toyosu Center Bldg, Annex, 3-9, Toyosu 3-chome, Koto-ku 135-8671, Tokyo, Japan
  • Ryota Katsuki
    Research and Development Headquarters, NTT DATA Group Corporation, Toyosu Center Bldg, Annex, 3-9, Toyosu 3-chome, Koto-ku 135-8671, Tokyo, Japan

Description

<jats:p>The Ising model is defined by an objective function using a quadratic formula of qubit variables. The problem of an Ising model aims to determine the qubit values of the variables that minimize the objective function, and many optimization problems can be reduced to this problem. In this paper, we focus on optimization problems related to permutations, where the goal is to find the optimal permutation out of the n! possible permutations of n elements. To represent these problems as Ising models, a commonly employed approach is to use a kernel that applies one-hot encoding to find any one of the n! permutations as the optimal solution. However, this kernel contains a large number of quadratic terms and high absolute coefficient values. The main contribution of this paper is the introduction of a novel permutation encoding technique called the dual-matrix domain wall, which significantly reduces the number of quadratic terms and the maximum absolute coefficient values in the kernel. Surprisingly, our dual-matrix domain-wall encoding reduces the quadratic term count and maximum absolute coefficient values from n3−n2 and 2n−4 to 6n2−12n+4 and 2, respectively. We also demonstrate the applicability of our encoding technique to partial permutations and Quadratic Unconstrained Binary Optimization (QUBO) models. Furthermore, we discuss a family of permutation problems that can be efficiently implemented using Ising/QUBO models with our dual-matrix domain-wall encoding.</jats:p>

Journal

  • Technologies

    Technologies 11 (5), 143-, 2023-10-17

    MDPI AG

References(28)*help

See more

Related Projects

See more

Keywords

Details 詳細情報について

Report a problem

Back to top