研究業績リスト
ジャーナル論文 - rm_published_papers: Scientific Journal
Approximate Block Diagonalization of Symmetric Matrices Using the D‐Wave Advantage Quantum Annealer
公開済 02/10/2025
Concurrency and Computation: Practice and Experience, 37, 25-26
ABSTRACT
Approximate block diagonalization is a problem of transforming a given symmetric matrix as close to block diagonal as possible by symmetric permutations of its rows and columns. This problem arises as a preprocessing stage of various scientific calculations and has been shown to be NP‐complete. In this paper, we consider solving this problem approximately using the D‐Wave Advantage quantum annealer. For this purpose, several steps are needed. First, we have to reformulate the problem as a quadratic unconstrained binary optimization (QUBO) problem. Second, the QUBO has to be embedded into the physical qubit network of the quantum annealer. Third, and optionally, reverse annealing for improving the solution can be applied. We propose two QUBO formulations and four embedding strategies for the problem and discuss their advantages and disadvantages. Through numerical experiments, it is shown that the combination of domain‐wall encoding and D‐Wave's automatic embedding is the most efficient in terms of usage of physical qubits, while the combination of one‐hot encoding and automatic embedding is superior in terms of the probability of obtaining a feasible solution. It is also shown that reverse annealing is effective in improving the solution for medium‐sized problems.
ジャーナル論文 - rm_published_papers: Scientific Journal
Solvability of Peg Solitaire on Graphs is NP-Complete
公開済 01/06/2023
IEICE Transactions on Information and Systems, E106.D, 6, 1111 - 1116
ジャーナル論文 - rm_published_papers: Scientific Journal
On the Power of Lookahead in Single-Player PuyoPuyo
公開済 2021
ICGA Journal, 43, 2, 102 - 113
ジャーナル論文 - rm_published_papers: Scientific Journal
公開済 10/2020
Information Processing Letters, 162, 105995
ジャーナル論文 - rm_published_papers: Scientific Journal
公開済 03/2020
Graphs and Combinatorics, 36, 2, 347 - 357
ジャーナル論文 - rm_published_papers: International Conference Proceedings
Anti-Slide Placements of Pentominoes
公開済 07/09/2019
The Japan Conference on Discrete and Computational Geometry, Graphs, and Games (JCDCG^3) 2019, 121 - 122
ジャーナル論文 - rm_published_papers: International Conference Proceedings
公開済 08/2017
Proc. the 20th Japan Conference on Discrete and Computational Geometry, Graphs, and Games, 137 - 138
ジャーナル論文 - rm_published_papers: Scientific Journal
Strategies for Single-Player PuyoPuyo
公開済 2017
ICGA JOURNAL, 39, 2, 87 - 101
ジャーナル論文 - rm_published_papers: Scientific Journal
Number of Three-Point Tilings with Triangle Tiles
公開済 2015
Journal of Information Processing, 23, 3, 305 - 309
ジャーナル論文 - rm_published_papers: International Conference Proceedings
Satogaeri, Hebi and Suraromu are NP-Complete
公開済 2015
3RD INTERNATIONAL CONFERENCE ON APPLIED COMPUTING AND INFORMATION TECHNOLOGY (ACIT 2015) 2ND INTERNATIONAL CONFERENCE ON COMPUTATIONAL SCIENCE AND INTELLIGENCE (CSI 2015), 46 - 51