Can I read Minor-embedding Heuristics for Large-scale Annealing Processors with Sparse Hardware Graphs of Up to 102,400 Nodes on EtoBox?

Minor-embedding Heuristics for Large-scale Annealing Processors with Sparse Hardware Graphs of Up to 102,400 Nodes by Yuya Sugie; Yuki Yoshida; Normann Mertig; Takashi Takemoto; Hiroshi Teramoto; Atsuyoshi Nakamura; Ichigaku Takigawa; Shin-ichi Minato; Masanao Yamaoka; Tamiki Komatsuzaki is a Computer Science article available to read on EtoBox.

What is Minor-embedding Heuristics for Large-scale Annealing Processors with Sparse Hardware Graphs of Up to 102,400 Nodes about?

Minor-embedding heuristics have become an indispensable tool for compiling problems in quadratically unconstrained binary optimization (QUBO) into the hardware graphs of quantum and CMOS annealing processors. While recent embedding heuristics have been developed for annealers of moderate size (about 2000 nodes), the size of the latest CMOS annealing processor (with 102,400 nodes) poses entirely new demands on the embedding heuristic. This raises the question, if recent embedding heuristics can maintain meaningful embedding performance on hardware graphs of increasing size. Here, we develop an improved version of the probabilistic-swap-shift-annealing (PSSA) embedding heuristic [which has recently been demonstrated to outperform the standard embedding heuristic by D-Wave Systems (Cai et al. in http://arxiv.org/abs/1406.2741, 2014)] and evaluate its embedding performance on hardware graphs of increasing size. For random cubic and Barábasi-Albert graphs we find the embedding performance of improved PSSA to consistently exceed the threshold of the best known complete graph embedding by a factor of 3.2 and 2.8, respectively, up to hardware graphs with 102,400 nodes. On the other hand, f

Who reads Minor-embedding Heuristics for Large-scale Annealing Processors with Sparse Hardware Graphs of Up to 102,400 Nodes?

Author

Yuya Sugie; Yuki Yoshida; Normann Mertig; Takashi Takemoto; Hiroshi Teramoto; Atsuyoshi Nakamura; Ichigaku Takigawa; Shin-ichi Minato; Masanao Yamaoka; Tamiki Komatsuzaki

Publisher

Springer Science and Business Media LLC

Published

2021

Language

EN

Field

Computer Science (Physical Sciences)