Quantum Biased Oracles (特集:量子計算と量子情報)
スポンサーリンク
概要
- 論文の詳細を見る
This paper reviews researches on quantum oracle computations when oracles are not perfect, i.e., they may return wrong answers. We call such oracles biased oracles, and discuss the formal model of them. Then we provide an intuitive explanation how quantum search with biased oracles by Hφyer, et al. (2003) works. We also review the method, by Buhrman, et al. (2005), to obtain all the answers of a quantum biased oracle without any overhead compared to the perfect oracle case. Moreover, we discuss two special cases of quantum biased oracles and their interesting properties, which are not found in the classical corresponding cases. Our discussion implies that the model of quantum biased oracle adopted by the existing researches is natural.
- 一般社団法人情報処理学会の論文
- 2005-10-15
著者
-
岩間 一雄
京都大学大学院情報学研究科
-
山下 茂
大分大学教育福祉科学部理科選修
-
Iwama Kazuo
Kyoto Univ. Kyoto
-
山下 茂
立命館大学
-
河内 亮周
Department of Mathematical and Computing Sciences, Tokyo Institute of Technology
-
Iwama Kazuo
Kyoto Sangyo University
-
Iwama Kazuo
Kyoto University:japan Science And Technology Corporation
-
KAWACHI AKINORI
Tokyo Institute of Technology
-
YAMASHITA SHIGERU
Nara Institute of Science and Technology
-
Yamashita Shigeru
Nara Inst. Sci. And Technol. Ikoma‐shi Jpn
-
河内 亮周
Tokyo Institute Of Technology
関連論文
- 片方のみがタイを持つ安定結婚問題に対する25/17近似アルゴリズム (アルゴリズムと計算機科学の数理的基盤とその応用)
- 最大サイズ最大安定度マッチング問題に対する近似下限の改良
- Designing Quantum Game Strategies from Quantum Communication Protocols
- 1.特定領域研究「新世代の計算限界-その解明と打破-」(特定領域研究「新世代の計算限界-その解明と打破-」)
- 「屋上緑化」による降温効果の測定
- DS-1-14 飛び道具を考慮した逆算法に基づく詰将棋列挙技術(DS-1. COMP-NHC学生シンポジウム,シンポジウムセッション)
- 部の大きさの比が高々定数倍の孤立2部クリークの列挙
- 遺伝的な距離に基づいた家系図推定問題
- 孤立した部分グラフの列挙
- 学校ネットワークおよびコンピュータ活用方法の実践研究
- SAT充足解の偏りを利用した局所探索の高速化
- 単調論理回路における還元
- 逆算法に基づく詰将棋の列挙
- p-C6H4Cl2の35Cl NQR周波数-2-
- p-C6H4Cl2のNQR周波数-1-
- 13a-C-6 CsSrCl_3のラマン散乱
- An improvement of the soundness of a 3-bit PCP (理論計算機科学の深化と応用--RIMS研究集会報告集)
- 教育養成系学生の履修の実態 : 理科離れと学力低下の調査から
- 児童・教師の調査に基づいた支援とそのあり方
- 大分県下1.1万人のアンケートにみる学習意識 : 理科離れを中心にして
- 大分県1.1万人のアンケ-トにみる学習意識--理科離れを中心にして
- しきい値関数を表す共有2分決定グラフの最適な変数順序付けの計算複雑度
- 論理回路の最大消費電力問題の近似可能性について
- (4, 1)-量子ランダムアクセス符号の非存在について
- 量子ネットワーク上での効率的な情報の伝送(計算理論とアルゴリズムの新展開)
- 3正則グラフの巡回セールスマン問題に対する厳密アルゴリズムの改善(計算機科学の理論とその応用)
- 男女平等安定マッチング問題に対する近似アルゴリズム
- LA-7 ランダムタイブレークによる安定マッチングの導出(A. アルゴリズム・基礎)
- 22pZC-1 SCS並びにTV会議システムを用いた初等物理実験遠隔共同授業
- SCS(衛星通信システム)を用いた遠隔授業 : 教員養成学部物理教育ミニマムの調査研究の一環として
- 25aM-6 大学間交換授業による教員養成学部における物理教育(3) : SCSを利用した初等物理実験に関する遠隔授業
- 28a-P-10 大学間交換授業による教員養成学部における物理教育(2) : SCSを利用した初等物理実験に関する遠隔授業
- オンライン問題の競合比解析の自動化について
- 正多角形領域に対するオンライン追跡問題
- レンタルスキー問題に対する平均的競合比の解析
- 児童の理解を助ける実験装置 : 大学と小学校の連携
- 遠隔実験装置を活用した授業の研究(大会テーマ「学力向上への試み」)
- 地域における情報教育支援のオン・デマンド・ライブラリーの構築
- 一般化されたオンライン独立頂点集合問題の競合化
- General Bounds for Quantum Biased Oracles (特集:量子計算と量子情報)
- Robust Quantum Algorithms for Oracle Identification (Theoretical Computer Science and its Applications)
- Transmitting classical information on the quantum network efficiently
- オラクル同定問題に対する頑健な量子アルゴリズム
- オンライン問題の競合比解析の自動化について (計算機科学基礎理論の新展開)
- Approximating Vertex Cover on Dense Graphs (Evolutionary Advancement in Fundamental Theories of Computer Science)
- A-1 3関数に対する量子クロー探索アルゴリズム(計算量・量子計算,A.アルゴリズム・基礎)
- 量子コンピュータ科学入門(量子情報科学 : 新しい情報処理のパラダイム)
- 量子探索と量子ゲーム(知能コンピューティングとその周辺〔第12回〕)
- CNF充足可能性判定問題の計算複雑さ : 最近の発展(「定理証明, 推論関係の新技術」)
- 29-2B1 大学間交換授業による教員養成学部における物理教育(1) : SCSを利用した初等物理実験に関する遠隔授業
- 記憶階層のもとでの結合操作について (数理情報科学の基礎理論と応用)
- 非同期回路の発振を利用したリング調停回路(技術談話室)
- 自己シャフルされた記号列を入力とする有限オートマトンについて (計算の複雑性に関する研究)
- 部分自律有限オ-トマトンの等価性判定問題
- 部分自律有限オートマトンの等価性 (情報科学の数学的基礎理論と応用)
- 部分自律有限オ-トマトンの基本的性質
- 2入出カ対オートマトンによる計算機結合インタフェースの設計手順 (計算機構の数学的研究)
- 配属人数下限付き研修医配属問題 (理論計算機科学の深化と応用)
- 3人部屋安定ルームメイト問題のNP完全性
- 平面グラフにおけるHajos Calculusの複雑さについて
- Negation-Limited Complexity of Parity and Inverters(Theory of Computer Science and Its Applications)
- DS-1-3 安定結婚問題に対する1.8-近似アルゴリズム(DS-1.COMP-NHC学生シンポジウム,シンポジウム)
- 安定結婚問題に対する1.875-近似アルゴリズム
- 計算限界の最前線(新世代の計算限界-その解明と打破-招待解説論文)
- 二段組合せ回路の最大動作率について(計算理論とアルゴリズムの新展開)
- PPSZタイプの充足可能性判定アルゴリズムの成功確率増幅について
- 入札額の範囲が制限された正直なオークション
- Hajos Calculus on Planar Graphs (Theoretical Computer Science and its Applications)
- 論理式の解密度の濃縮
- 2^n-α個の決定性状態を要するn状態NFAの族について
- 柔軟性物質の緩和過程観測システムの開発
- 1PF-14 生徒の課題設定を重視した理科実験教材の開発に関する一考察
- 生徒の課題設定を重視した理科実験教材の開発に関する一考察
- IT-4 中学校生徒と保護者, 教師の目指す生きる力
- Web環境での遠隔操作による物理教材開発
- Oblivious BPとSyntactic BPの計算時間による指数的分離
- D-1-2 Oblivious Branching Programのサイズの下限について
- 一方向量子有限オートマトンの初期状態の不完全性
- 条件を緩和した安定結婚問題の複雑さ
- 部分MAXSATを利用した大学情報処理の自動化
- アンケートにみる高校生の学習意識調査 : 理科離れを中心にして
- SATに対する局所探索法のベクトル化
- 局所探索法による安定結婚問題の近似
- Quantum Biased Oracles (特集:量子計算と量子情報)
- テープ記号数を制限したチューリング機械の領域階層
- 回路計算量の5nの下限
- 正直なオークションにおける談合の影響 (理論計算機科学の深化 : 新たな計算世界観を求めて)
- 安定結婚問題に対する局所探索近似アルゴリズムの改良
- Quantum Sampling for Balanced Allocations(Foundations of Computer Science)
- オンライン問題の複雑さの解析について
- 1L-2 オンライン問題のクラス分け
- Max-Stretch Reduction for Tree Spanners
- タイル縁に上書きルールを用いた敷き詰め問題
- タイル縁に上書きルールを用いた敷き詰め問題
- 効率の良い罫線描画について
- QoS保証マルチキャストプロトコルSRSVPにおける階層化PathQoS
- 複数個の解候補を保持できるオンラインナップサック問題
- 量子探索と量子ゲーム
- DS-1-1 希望リスト変更による男性最良安定マッチングの改善(DS-1.COMP学生シンポジウム,シンポジウムセッション)