講演名 | 2001/7/17 量子計算によるプトリネットの解析について 平石 邦彦, |
---|---|
PDFダウンロードページ | PDFダウンロードページへ |
抄録(和) | 本研究の目的は, 量子計算アルゴリズムをペトリネットにより表現されるコンカレントシステムのモデルチェッキングに利用することである.論文では, 与えられた容量付きペトリネットにおける到達可能性の判定問題に対する量子計算アルゴリズムを示す.アルゴリズムは, まずκステップ以内で到達可能なマーキングをすべて含むマーキングの集合をヒルベルト空間上の重ね合わせとして計算し, 量子探索アルゴリズムにより目的マーキングがその重ね合わせに含まれているかどうかを判定する.アルゴリズムはネットのサイズおよびステップ数κに比例した量子ビットしか必要としない. |
抄録(英) | The aim of this research is to utilize quantum algorithms for model checking of concurrent systems represented by Petri nets. We propose a quantum algorithm for checking reachability in a given Petri net with capacity. The algorithm first computes a set of markings that contains all markings reachable within κ steps as a superposition of them in a Hilbert space. Then the quantum search algorithm is applied to check of a given goal marking is in the superposition or not. The algorithm requires only a number of quantum bits proportional to the size of the net and the number of steps κ. |
キーワード(和) | ペトリネット / 量子計算 / モデルチェッキング |
キーワード(英) | Petri nets / quantum computation / model checking |
資料番号 | CST2001-11 |
発行日 |
研究会情報 | |
研究会 | CST |
---|---|
開催期間 | 2001/7/17(から1日開催) |
開催地(和) | |
開催地(英) | |
テーマ(和) | |
テーマ(英) | |
委員長氏名(和) | |
委員長氏名(英) | |
副委員長氏名(和) | |
副委員長氏名(英) | |
幹事氏名(和) | |
幹事氏名(英) | |
幹事補佐氏名(和) | |
幹事補佐氏名(英) |
講演論文情報詳細 | |
申込み研究会 | Concurrent System Technology (CST) |
---|---|
本文の言語 | ENG |
タイトル(和) | 量子計算によるプトリネットの解析について |
サブタイトル(和) | |
タイトル(英) | Analysis of Petri Nets by Quantum Computation |
サブタイトル(和) | |
キーワード(1)(和/英) | ペトリネット / Petri nets |
キーワード(2)(和/英) | 量子計算 / quantum computation |
キーワード(3)(和/英) | モデルチェッキング / model checking |
第 1 著者 氏名(和/英) | 平石 邦彦 / Kunihiko Hiraishi |
第 1 著者 所属(和/英) | 北陸先端科学技術大学院大学 情報科学研究科 School of Information Science, Japan Advanced Institute of Science and Technology |
発表年月日 | 2001/7/17 |
資料番号 | CST2001-11 |
巻番号(vol) | vol.101 |
号番号(no) | 212 |
ページ範囲 | pp.- |
ページ数 | 8 |
発行日 |