著者

内藤 壮俊 長谷川 禎彦 松田 佳希 田中 宗

雑誌

量子ソフトウェア(QS) (ISSN:24356492)

巻号頁・発行日

vol.2022-QS-5, no.23, pp.1-9, 2022-03-17

---

量子コンパイラは,論理回路として表現された量子プログラムを受け取り,デバイス上で実行可能かつ論理的に等価な回路を合成するソフトウェアである.近年主流となっている NISQ デバイスは,物理的に接続された量子ビット間でしか量子ゲートを作用させられない,操作によって生じたエラーが蓄積するといった特性を有している.そのため NISQ デバイスを対象とする量子コンパイラは,接続関係の制約を満たしながら,回路のコストすなわちゲート操作回数が少なくなるように回路を出力しなければならない.このコンパイル操作において最も重要なタスクは,論理回路中の量子ビットをデバイス上の量子ビットに割り当てるタスクである.これは NP 困難であり,出力回路のコストに大きく影響する問題となっている.私たちの提案する量子コンパイラ「ISAAQ (ISing mAchine Assisted Quantum compiler)」は,出力回路のコストを QUBO モデルとして表現し,イジングマシンを用いた解の探索,およびその解に基づいた回路合成を実行する.ISAAQ は,実行結果に基づいた QUBO モデルの更新,複数イジングマシンによる並列実行,デバイス上の経路を考慮したコスト削減といった,他にはない特徴を多く持っている.IBM QX5 および IBM QX20 を対象とした実験では,ISAAQ は既存の QUBO 手法やその他のアルゴリズムよりも低コストな回路を出力できていることが確認され,本提案手法の有効性が示された.

著者

長谷川 禎彦 伊庭 斉志

出版者

The Japanese Society for Artificial Intelligence

雑誌

人工知能学会論文誌 = Transactions of the Japanese Society for Artificial Intelligence : AI (ISSN:13460714)

巻号頁・発行日

vol.22, pp.37-47, 2007-11-01

参考文献数

34

被引用文献数

1 4

---

Genetic Programming (GP) is a powerful optimization algorithm, which employs the crossover for genetic operation. Because the crossover operator in GP randomly selects sub-trees, the building blocks may be destroyed by the crossover. Recently, algorithms called PMBGPs (Probabilistic Model Building GP) based on probabilistic techniques have been proposed in order to improve the problem mentioned above. We propose a new PMBGP employing Bayesian network for generating new individuals with a special chromosome called <I>expanded parse tree</I>, which much reduces a number of possible symbols at each node. Although the large number of symbols gives rise to the large conditional probability table and requires a lot of samples to estimate the interactions among nodes, a use of the expanded parse tree overcomes these problems. Computational experiments on two subjects demonstrate that our new PMBGP is much superior to prior probabilistic models.