論文の概要: Quantum Random Access Stored-Program Machines
- arxiv url: http://arxiv.org/abs/2003.03514v2
- Date: Sat, 10 Sep 2022 05:39:19 GMT
- ステータス: 処理完了
- システム内更新日: 2023-05-30 06:59:22.185077
- Title: Quantum Random Access Stored-Program Machines
- Title(参考訳): 量子ランダムアクセスストアドプログラムマシン
- Authors: Qisheng Wang and Mingsheng Ying
- Abstract要約: 我々は、量子ランダムアクセスマシン(QRAM)と量子ランダムアクセスストアドプログラムマシン(QRASP)のモデルを正式に定義する。
我々は、$textbfEQRAMP$と$textbfBQRAMP$が、それぞれ確実性とバウンドエラーで解決できる問題の集合を表しています。
我々の証明の核心は、独立した関心を持つ拡張停止スキームによるQTMの標準化である。
- 参考スコア(独自算出の注目度): 3.015392924074054
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: Random access machines (RAMs) and random access stored-program machines
(RASPs) are models of computing that are closer to the architecture of
real-world computers than Turing machines (TMs). They are also convenient in
complexity analysis of algorithms. The relationships between RAMs, RASPs and
TMs are well-studied. However, clear relationships between their quantum
counterparts are still missing in the literature. We fill in this gap by
formally defining the models of quantum random access machines (QRAMs) and
quantum random access stored-program machines (QRASPs) and clarifying the
relationships between QRAMs, QRASPs and quantum Turing machines (QTMs). In
particular, we show that $\textbf{P} \subseteq \textbf{EQRAMP} \subseteq
\textbf{EQP} \subseteq \textbf{BQP} = \textbf{BQRAMP}$, where $\textbf{EQRAMP}$
and $\textbf{BQRAMP}$ stand for the sets of problems that can be solved by
polynomial-time QRAMs with certainty and bounded-error, respectively. At the
heart of our proof, is a standardisation of QTM with an extended halting
scheme, which is of independent interest.
- Abstract(参考訳): ランダム・アクセス・マシン (RAM) とランダム・アクセス・ストアド・プログラム・マシン (RASP) は、チューリング・マシン (TM) よりも現実のコンピュータのアーキテクチャに近い計算モデルである。
アルゴリズムの複雑性分析にも便利である。
RAM、RASP、TMの関係はよく研究されている。
しかし、量子的な関係性はいまだに文献に残っていない。
量子ランダムアクセスマシン(QRAM)と量子ランダムアクセスストアプログラムマシン(QRASP)のモデルを定義し,QRAM,QRASP,量子チューリングマシン(QTM)の関係を明らかにすることで,このギャップを埋める。
特に、$\textbf{P} \subseteq \textbf{EQRAMP} \subseteq \textbf{EQP} \subseteq \textbf{BQP} = \textbf{BQRAMP}$, where $\textbf{EQRAMP}$ と $\textbf{BQRAMP}$ は多項式時間 QRAM と有界エラーでそれぞれ解ける問題の集合を表す。
我々の証明の核心は、独立した関心を持つ拡張停止スキームによるQTMの標準化である。
関連論文リスト
- The Power of Unentangled Quantum Proofs with Non-negative Amplitudes [55.90795112399611]
非負の振幅を持つ非絡み合った量子証明のパワー、つまり $textQMA+(2)$ を表すクラスについて研究する。
特に,小集合拡張,ユニークなゲーム,PCP検証のためのグローバルプロトコルを設計する。
QMA(2) が $textQMA+(2)$ に等しいことを示す。
論文 参考訳(メタデータ) (2024-02-29T01:35:46Z) - Systems Architecture for Quantum Random Access Memory [0.6386668251980657]
量子ランダムアクセスメモリ(QRAM)は、量子クエリを実現するための有望なアーキテクチャである。
提案するQRAMの固有バイアスノイズレジリエンスを、NISQ(Noisy Intermediate-Scale Quantum)またはFTQC(Fault-Tolerant Quantum Computing)ハードウェア上で実装する方法を示す。
論文 参考訳(メタデータ) (2023-06-05T20:52:28Z) - QRAM: A Survey and Critique [1.52292571922932]
量子ランダムアクセスメモリ(QRAM)は、それ自体が量子状態であるアドレスに基づいてデータにアクセスするメカニズムである。
文献から得られた2つの主要なQRAMカテゴリ(アクティブとパッシブ)を使用します。
結論として、既存の提案では、安価でスケーラブルに受動的なQRAMはありえないと結論付けている。
論文 参考訳(メタデータ) (2023-05-17T15:48:48Z) - InQuIR: Intermediate Representation for Interconnected Quantum Computers [0.0]
InQuIRは、分散量子システム上での通信と計算を表現できる表現である。
デッドロックなどの分散プログラムで発生する問題を説明するために,InQuIRで記述した例を挙げる。
また、InQuIR用のソフトウェアツールを提供し、量子回路の計算コストを評価する。
論文 参考訳(メタデータ) (2023-02-01T06:19:23Z) - TeD-Q: a tensor network enhanced distributed hybrid quantum machine
learning framework [59.07246314484875]
TeD-Qは、量子機械学習のためのオープンソースのソフトウェアフレームワークである。
古典的な機械学習ライブラリと量子シミュレータをシームレスに統合する。
量子回路とトレーニングの進捗をリアルタイムで視覚化できるグラフィカルモードを提供する。
論文 参考訳(メタデータ) (2023-01-13T09:35:05Z) - Approximate Quantum Random Access Memory Architectures [7.509129971169722]
量子超越性(Quantum supremacy)は、よく知られた量子アルゴリズムを用いた多くのアプリケーションにおいて、量子形式におけるデータの可用性に依存している。
本稿では、アドレス行を入力として取り出し、これらのアドレス行の対応するデータを出力として出力する、近似パラメトリック量子回路(PQC)ベースのQRAMを提案する。
提案するPQCベースのQRAMの2つの応用として、バイナリデータのストレージと機械学習データセットのストレージを分類する。
論文 参考訳(メタデータ) (2022-10-24T19:53:28Z) - Quantum Depth in the Random Oracle Model [57.663890114335736]
浅量子回路の計算能力と古典計算の組合せを包括的に評価する。
いくつかの問題に対して、1つの浅い量子回路で適応的な測定を行う能力は、適応的な測定をせずに多くの浅い量子回路を実行する能力よりも有用である。
論文 参考訳(メタデータ) (2022-10-12T17:54:02Z) - Oracle separations of hybrid quantum-classical circuits [68.96380145211093]
量子計算の2つのモデル: CQ_dとQC_d。
CQ_dは、d-d-deepth量子コンピュータのシナリオを何度も捉え、QC_dは測定ベースの量子計算に類似している。
CQ_dとQC_dの類似性にもかかわらず、2つのモデルは本質的にはCQ_d $nsubseteq$QC_dとQC_d $nsubseteq$CQ_dである。
論文 参考訳(メタデータ) (2022-01-06T03:10:53Z) - Adiabatic Quantum Graph Matching with Permutation Matrix Constraints [75.88678895180189]
3次元形状と画像のマッチング問題は、NPハードな置換行列制約を持つ二次代入問題(QAP)としてしばしば定式化される。
本稿では,量子ハードウェア上での効率的な実行に適した制約のない問題として,いくつかのQAPの再構成を提案する。
提案アルゴリズムは、将来の量子コンピューティングアーキテクチャにおいて、より高次元にスケールする可能性がある。
論文 参考訳(メタデータ) (2021-07-08T17:59:55Z) - Cost-efficient QFA Algorithm for Quantum Computers [0.0]
修正されたムーア・クラッチフィールド量子有限オートマトン (MCQFA) アルゴリズムを言語 $mathttMOD_p$ に対して提案する。
文献で与えられた元のアルゴリズムの実装と比較して,基底ゲートが少なくて短い量子プログラムが得られる。
論文 参考訳(メタデータ) (2021-07-05T20:41:18Z) - Parallelising the Queries in Bucket Brigade Quantum RAM [69.43216268165402]
量子アルゴリズムは、しばしばデータベースのような方法で格納された情報にアクセスするために量子RAM(QRAM)を使用する。
本稿では,Clifford+Tゲートの並列性を利用して,効率的なクエリ時間を大幅に短縮する手法を提案する。
理論的には、フォールトトレラントバケットの量子RAMクエリは古典的なRAMの速度とほぼ一致する。
論文 参考訳(メタデータ) (2020-02-21T14:50:03Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。