- 著者
-
佐多 恵悟
松山 開
坂口 裕一
中山 茂
小野 智司
- 出版者
- 一般社団法人情報処理学会
- 雑誌
- 情報処理学会論文誌数理モデル化と応用(TOM) (ISSN:18827780)
- 巻号頁・発行日
- vol.7, no.1, pp.84-93, 2014-03-28
近年,Span Programに基づく論理式評価の量子アルゴリズム(Span-Program-based Quantum Algorithm: SPQA)が注目されている.SPQAに適した量子クエリ計算量が少ない最適なSpan Programの導出は,一般的な手法が見つかっておらず,対象となる論理式ごとに専門家が試行錯誤的に導出している.特に,入力ビットが多い論理式では行列の要素数が指数関数的に増加するため,導出が困難である.本研究では,量子クエリ計算量が少ない最適なSpan Programの導出を最適化問題として定式化し,進化計算を用いて近似解を導出する手法を提案する.In recent years, Span-Program-based Quantum Algorithm (SPQA) for evaluating Boolean formulas has been paid attention. However there has been no general method to derive optimal span program, which make the quantum query complexity of SPQA the least, and only professionals can derive for each formula through trial and error. Especially, it is difficult to derive span program for a formula with many input bits because number of elements of its matrix will increase exponentially. This paper proposes a method for optimal span program derivation, which formulates the problem as an optimization problem and solves it by evolutionary computation.