文献

J-GLOBAL ID：201502247114651839   整理番号：15A0170610

量子アルゴリズムで用いられるSpan Programの進化計算による導出

Derivation of Span Program for Span-Program-Based Quantum Algorithm by Evolutionary Computation

著者 (5件)： 佐多恵悟 (鹿児島大) ,  松山開 (鹿児島大) ,  坂口裕一 (鹿児島大) ,  中山茂 (鹿児島大) ,  小野智司 (鹿児島大)
資料名： 情報処理学会研究報告(Web)  (IPSJ Technical Report (Web))
巻： 2013  号： MPS-95  ページ： WEB ONLY VOL.2013-MPS-95,NO.11  発行年： 2013年09月19日 
JST資料番号： U0451A  資料種別： 会議録 (C)
記事区分： 原著論文  発行国： 日本 (JPN)  言語： 日本語 (JA)

抄録/ポイント： 近年,Span Programに基づく論理式評価の量子アルゴリズム(Span-Program-based Quantum Algorithm:SPQA)が注目されている。SPQAの量子クエリ計算量が少ない最適なSpan Programの導出は,一般的な手法が見つかっておらず,対象となる論理式毎に専門家が試行錯誤的に導出している。特に,入力ビットが多い論理式では行列の要素数が指数関数的に増加するため,導出が困難である。本研究では,量子クエリ計算量が少ない最適なSpan Programの導出を最適化問題として定式化し,進化計算を用いて導出する手法を提案する。(著者抄録)

シソーラス用語： 計算機アルゴリズム ,  *量子計算 ,  *進化的計算 ,  計算量 ,  質問処理 ,  論理演算 ,  導出原理 ,  式 ,  *最適化問題 ,  量子情報 ,  評価試験 ,  *量子コンピュータ
準シソーラス用語： *量子アルゴリズム ,  量子ビット ,  論理式

分類 (4件)： 計算理論  (JB02000A) ,  人工知能  (JE08000Z) ,  その他のオペレーションズリサーチの手法  (KA03070E) ,  その他の計算機  (JC06020B)

引用文献 (20件)：

• Farhi, E., Goldstone, J. and Gutmann, S.: A quantum algorithm for the Hamiltonian NAND tree, arXiv preprint quant-ph/07021447 pp. 1-16 (2007).
• Snir, M.: Lower bounds on probabilistic linear decision trees, Theoretical Computer Science, Vol. 38, pp. 69-82 (1985).
• Saks, M. and Wigderson, A.: Probabilistic Boolean decision trees and the complexity of evaluating game trees, Foundations of Computer Science, 1986., 27th Annual Symposium on, IEEE, pp. 29-38 (1986).
• Santha, M.: On the Monte carlo boolean decision tree complexity of read-once formulae, Random Structures & Algorithms, Vol. 6, No. 1, pp. 75-87 (1995).
• Childs, A. M., Reichardt, B. W., Špalek cur, R. and Zhang, S.: Every NAND formula on N variables can be evaluated in time O (N 1/2+ o(1)), arXiv preprint quant-ph/0703015, pp. 1-14 (2007).

タイトルに関連する用語 (3件)： 量子アルゴリズム ,  進化計算 ,  導出