Individual subject evaluated difficulty of adjustable mazes generated using quantum annealing
In this study, the maze generation using quantum annealing is proposed. We reformulate a standard algorithm to generate a maze into a specific form of a quadratic unconstrained binary optimization problem suitable for the input of the quantum annealer. To generate more difficulty mazes, we introduce...
| Main Authors: | , , , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
Frontiers Media S.A.
2023-12-01
|
| Series: | Frontiers in Computer Science |
| Subjects: | |
| Online Access: | https://www.frontiersin.org/articles/10.3389/fcomp.2023.1285962/full |
| _version_ | 1797401580531613696 |
|---|---|
| author | Yuto Ishikawa Takuma Yoshihara Keita Okamura Masayuki Ohzeki Masayuki Ohzeki Masayuki Ohzeki |
| author_facet | Yuto Ishikawa Takuma Yoshihara Keita Okamura Masayuki Ohzeki Masayuki Ohzeki Masayuki Ohzeki |
| author_sort | Yuto Ishikawa |
| collection | DOAJ |
| description | In this study, the maze generation using quantum annealing is proposed. We reformulate a standard algorithm to generate a maze into a specific form of a quadratic unconstrained binary optimization problem suitable for the input of the quantum annealer. To generate more difficulty mazes, we introduce an additional cost function Qupdate to increase the difficulty. The difficulty of the mazes was evaluated by the time to solve the maze of 12 human subjects. To check the efficiency of our scheme to create the maze, we investigated the time-to-solution of a quantum processing unit, classical computer, and hybrid solver. The results show that Qupdate generates difficult mazes tailored to the individual. Furthermore, it show that the quantum processing unit is more efficient at generating mazes than other solvers. Finally, we also present applications how our results could be used in the future. |
| first_indexed | 2024-03-09T02:12:10Z |
| format | Article |
| id | doaj.art-dc17b34a4daa4559938534feb80c940e |
| institution | Directory Open Access Journal |
| issn | 2624-9898 |
| language | English |
| last_indexed | 2024-03-09T02:12:10Z |
| publishDate | 2023-12-01 |
| publisher | Frontiers Media S.A. |
| record_format | Article |
| series | Frontiers in Computer Science |
| spelling | doaj.art-dc17b34a4daa4559938534feb80c940e2023-12-07T09:07:34ZengFrontiers Media S.A.Frontiers in Computer Science2624-98982023-12-01510.3389/fcomp.2023.12859621285962Individual subject evaluated difficulty of adjustable mazes generated using quantum annealingYuto Ishikawa0Takuma Yoshihara1Keita Okamura2Masayuki Ohzeki3Masayuki Ohzeki4Masayuki Ohzeki5Department of Computer Science, Nagoya University, Nagoya, JapanDepartment of Engineering, Tokyo Denki University, Adachi, JapanDepartment of Physics and Astronomy, Tokyo University of Science, Noda, JapanGraduate School of Information Sciences, Tohoku University, Sendai, JapanDepartment of Physics, Tokyo Institute of Technology, Meguro, JapanSigma-i Co., Ltd., Shinagawa, JapanIn this study, the maze generation using quantum annealing is proposed. We reformulate a standard algorithm to generate a maze into a specific form of a quadratic unconstrained binary optimization problem suitable for the input of the quantum annealer. To generate more difficulty mazes, we introduce an additional cost function Qupdate to increase the difficulty. The difficulty of the mazes was evaluated by the time to solve the maze of 12 human subjects. To check the efficiency of our scheme to create the maze, we investigated the time-to-solution of a quantum processing unit, classical computer, and hybrid solver. The results show that Qupdate generates difficult mazes tailored to the individual. Furthermore, it show that the quantum processing unit is more efficient at generating mazes than other solvers. Finally, we also present applications how our results could be used in the future.https://www.frontiersin.org/articles/10.3389/fcomp.2023.1285962/fullquantum annealingcombinatorial optimizationmaze generationbar-tipping algorithmtime-to-solution |
| spellingShingle | Yuto Ishikawa Takuma Yoshihara Keita Okamura Masayuki Ohzeki Masayuki Ohzeki Masayuki Ohzeki Individual subject evaluated difficulty of adjustable mazes generated using quantum annealing Frontiers in Computer Science quantum annealing combinatorial optimization maze generation bar-tipping algorithm time-to-solution |
| title | Individual subject evaluated difficulty of adjustable mazes generated using quantum annealing |
| title_full | Individual subject evaluated difficulty of adjustable mazes generated using quantum annealing |
| title_fullStr | Individual subject evaluated difficulty of adjustable mazes generated using quantum annealing |
| title_full_unstemmed | Individual subject evaluated difficulty of adjustable mazes generated using quantum annealing |
| title_short | Individual subject evaluated difficulty of adjustable mazes generated using quantum annealing |
| title_sort | individual subject evaluated difficulty of adjustable mazes generated using quantum annealing |
| topic | quantum annealing combinatorial optimization maze generation bar-tipping algorithm time-to-solution |
| url | https://www.frontiersin.org/articles/10.3389/fcomp.2023.1285962/full |
| work_keys_str_mv | AT yutoishikawa individualsubjectevaluateddifficultyofadjustablemazesgeneratedusingquantumannealing AT takumayoshihara individualsubjectevaluateddifficultyofadjustablemazesgeneratedusingquantumannealing AT keitaokamura individualsubjectevaluateddifficultyofadjustablemazesgeneratedusingquantumannealing AT masayukiohzeki individualsubjectevaluateddifficultyofadjustablemazesgeneratedusingquantumannealing AT masayukiohzeki individualsubjectevaluateddifficultyofadjustablemazesgeneratedusingquantumannealing AT masayukiohzeki individualsubjectevaluateddifficultyofadjustablemazesgeneratedusingquantumannealing |