1回読み定数幅制約下での量子ブランチングプログラムと確率ブランチングプログラムの計算能力の比較
スポンサーリンク
概要
- 論文の詳細を見る
従来の計算モデルと量子計算モデルの能力の比較として, これまでに量子有限オートマトンが従来の有限オートマトンより能力が高いという結果が報告されている[1, 3].また, 従来の計算モデルとして, 種々のブランチングプログラムが研究されてきている[4].本稿では, 新しい量子計算モデルとして, 量子ブランチングプログラムを導入し, 従来の計算モデルである確率ブランチングプログラムとその能力の比較を行なう.結果として, 順序付定数幅量子ブランチングプログラムで計算可能であるが, 順序付定数幅ブランチングプログラムでは計算不可能な関数が存在することを示す.
- 社団法人電子情報通信学会の論文
- 2000-03-22
著者
-
浜口 清治
大阪大学大学院情報科学研究科
-
柏原 敏伸
大阪大学大学院情報科学研究科
-
中西 正樹
山形大学地域教育文化学部
-
中西 正樹
大阪大学大学院基礎工学研究科
-
柏原 敏伸
大阪大学大学院
-
浜口 清治
大阪大学大学院基礎工学研究科
関連論文
- 第一階述語論理のサブクラスに対する近似的モデル検査アルゴリズム (ディペンダブルコンピューティング)
- 第一階述語論理のサブクラスに対する近似的モデル検査アルゴリズム (VLSI設計技術)
- メッセージ・シークエンス・チャートに対するSATソルバーを用いたディスコード計算手法 (ディペンダブルコンピューティング)
- メッセージ・シークエンス・チャートに対するSATソルバーを用いたディスコード計算手法 (コンピュータシステム)
- stグラフの道独立頂点集合の性質
- 第一階述語論理のサブクラスに対する近似的モデル検査アルゴリズム
- メッセージ・シークエンス・チャートに対するSATソルバーを用いたディスコード計算手法
- メッセージ・シークエンス・チャートに対するSATソルバーを用いたディスコード計算手法
- メッセージ・シークエンス・チャートに対するSATソルバーを用いたディスコード計算手法
- メッセージ・シークエンス・チャートに対するSATソルバーを用いたディスコード計算手法
- メッセージ・シークエンス・チャートに対するSATソルバーを用いたディスコード計算手法
- メッセージ・シークエンス・チャートに対するSATソルバーを用いたディスコード計算手法
- メッセージ・シークエンス・チャートに対するSATソルバーを用いたディスコード計算手法
- マークグラフにおけるトランジションの潜在的同時発火可能性判定アルゴリズム
- 1-有界無競合ペトリネットにおける二つのトランジションの同時発火可能性を判定するYenのアルゴリズムの改良
- マークグラフにおけるトランジションの潜在的同時発火可能性判定アルゴリズム
- ペトリネットの部分クラスにおける同時発火可能性
- しきい値関数を表す共有2分決定グラフの最適な変数順序付けの計算複雑度
- 局所変数を含むアサーションに対するモデルチェッキングのためのチェッカ生成(アサーションベース検証,システム設計及び一般)
- 局所変数を含むアサーションに対するモデルチェッキングのためのチェッカ生成(システム設計及び一般)
- 動的局所変数を含むアサーションに対する限定モデルチェッキング(デザインガアイ2006-VLSI設計の新しい大地を考える研究会)
- 動的局所変数を含むアサーションに対する限定モデルチェッキング(検証,デザインガイア2006-VLSI設計の新しい大地を考える研究会)
- 動的局所変数を含むアサーションに対する限定モデルチェッキング(検証,デザインガイア2006-VLSI設計の新しい大地を考える研究会)
- アサーションベース検証の基礎とそのねらい(設計・検証, FRGAとその応用及び一般)
- アサーションベース検証の基礎とそのねらい(設計・検証, FRGAとその応用及び一般)
- アサーションベース検証の基礎とそのねらい(設計・検証, FRGAとその応用及び一般)
- 大規模回路設計に対するフォーマル仕様記述・検証技術の現状と動向
- 第一階述語論理のサブクラスに対する項の高さ縮減を用いた不変条件の近似的検証アルゴリズム(テストと検証,デザインガイア2007-VLSI設計の新しい大地を考える研究会-)
- 第一階述語論理のサブクラスに対する項の高さ縮減を用いた不変条件の近似的検証アルゴリズム(テストと検証,デザインガイア2007-VLSI設計の新しい大地を考える研究会-)
- 第一階述語論理のサブクラスに対する項の高さ縮減を用いた不変条件の近似的検証アルゴリズム(テストと検証,デザインガイア2007-VLSI設計の新しい大地を考える研究会-)
- 同値制約を考慮した第一階述語論理の決定可能なサブクラスによる等価性判定(デザインガアイ2006-VLSI設計の新しい大地を考える研究会)
- 同値制約を考慮した第一階述語論理の決定可能なサブクラスによる等価性判定(検証,デザインガイア2006-VLSI設計の新しい大地を考える研究会)
- 同値制約を考慮した第一階述語論理の決定可能なサブクラスによる等価性判定(検証,デザインガイア2006-VLSI設計の新しい大地を考える研究会)
- 定数幅量子ブランチングプログラムの計算能力 (計算理論とアルゴリズムの新展開)
- 1回読み定数幅制約下での量子ブランチングプログラムと確率ブランチングプログラムの計算能力の比較
- クロネッカー式関数決定グラフの最適展開規則選択問題の計算複雑度(情報基礎理論ワークショップ(LAシンポジウム)論文小特集)
- 二分モーメントグラフによる除算表現の大きさの指数下界 (アルゴリズムと計算の理論)
- 二分モーメントグラフによる除算表現の大きさの指数下界
- 妨害者のいる場合の最短経路問題
- 妨害の下での最短経路問題の複雑さ : 通過後の妨害を許さない場合
- 円筒上長方形交グラフの最大クリークを求めるアルゴリズム
- 妨害の下での最短経路問題
- パスグラフから区間グラフへの最小辺付加による変換の NP 完全性
- 交互シャフルについて
- 木上二重コンベックスグラフと二部サークルグラフの等価性
- 端子間に配線を通過させない順列配線のビア数最小化アルゴリズム
- 円筒上長方形交グラフの最大クリークを求めるアルゴリズム
- パスグラフから区間グラフへの最小辺付加による変換のNP完全性
- ある種のグラフにおける最大クリーク重みの折点数について
- モニタベース形式検証のための入力制約を考慮したモニタ回路生成手法(ハードウェア,フォーマルアプローチ論文)
- モニタベース形式検証のための入力制約を考慮したモニタ回路生成手法(プロセッサ, DSP, 画像処理技術及び一般)
- モニタベース形式検証のための入力制約を考慮したモニタ回路生成手法(プロセッサ, DSP, 画像処理技術及び一般)
- モニタベース形式検証のための入力制約を考慮したモニタ回路生成手法(プロセッサ, DSP, 画像処理技術及び一般)
- モニタベース形式検証のための入力制約を考慮したモニタ回路生成手法(プロセッサ, DSP, 画像処理技術及び一般)
- 平面グラフの最大重み窓問題
- 外窓上の頂点および辺の重みの和を最大にするような,2連結平面グラフの描写アルゴリズム
- 第一階述語論理のサブクラスを利用したブール関数レベルの等価性判定手法(FPGAとその応用及び一般)
- 第一階述語論理のサブクラスを利用したブール関数レベルの等価性判定手法(FPGAとその応用及び一般)
- 第一階述語論理のサブクラスを利用したブール関数レベルの等価性判定手法(FPGAとその応用及び一般)
- 第一階述語論理のサブクラスを利用したブール関数レベルの等価性判定手法(FPGAとその応用及び一般)
- コンパラビリティグラフから得られるst有向グラフのセパレータ
- An Algorithm for Generating Maximum Weight Independent Sets in a Circle Graph
- パラメトリックグラフにおける最大クリ-ク重みの折れ点数
- 2層配線における3端子ネットの分割
- 部品の端子間に配線を通過させない一層配線問題について
- 部品の反転を許さない一層平面配線問題について
- トランザクション識別子を伴うバスプロトコル間の変換器自動生成手法 (ディペンダブルコンピューティング)
- トランザクション識別子を伴うバスプロトコル間の変換器自動生成手法 (コンピュータシステム)
- トランザクション識別子を伴うバスプロトコル間の変換器自動生成手法
- トランザクション識別子を伴うバスプロトコル間の変換器自動生成手法
- 第一階述語論理の決定可能なサブクラスに対する同値制約を考慮した充足可能性判定(検証・理論, 組込技術とネットワークに関するワークショップ)
- 第一階述語論理の決定可能なサブクラスに対する同値制約を考慮した充足可能性判定
- 第一階述語論理の決定可能なサブクラスに対する同値制約を考慮した充足可能性判定(検証・理論, 組込技術とネットワークに関するワークショップ)
- VLIWプロセッサにおける演算命令発行スロット数の最適化
- VLIWプロセッサにおける演算命令発行スロット数の最適化
- VLIWプロセッサ自動生成における演算器構成最適化の一手法
- VLIWプロセッサ自動生成における演算器構成最適化の一手法
- A-3-8 メモリを用いた算術演算回路のFPGA実現とその電力評価(A-3.VLSI設計技術,一般セッション)