論文の概要: Memory Compression with Quantum Random-Access Gates
- arxiv url: http://arxiv.org/abs/2203.05599v1
- Date: Thu, 10 Mar 2022 19:27:53 GMT
- ステータス: 処理完了
- システム内更新日: 2023-02-22 11:51:18.913049
- Title: Memory Compression with Quantum Random-Access Gates
- Title（参考訳）: 量子ランダムアクセルゲートによるメモリ圧縮
- Authors: Harry Buhrman, Bruno Loff, Subhasree Patro, Florian Speelman
- Abstract要約: 量子ランダムアクセスゲートを備えた量子アルゴリズムに対して、類似した結果を示す。
空間非効率であるがスパースな量子データ構造を構築することはしばしば可能である。
- 参考スコア（独自算出の注目度）: 0.0
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: In the classical RAM, we have the following useful property. If we have an
algorithm that uses $M$ memory cells throughout its execution, and in addition
is sparse, in the sense that, at any point in time, only $m$ out of $M$ cells
will be non-zero, then we may "compress" it into another algorithm which uses
only $m \log M$ memory and runs in almost the same time. We may do so by
simulating the memory using either a hash table, or a self-balancing tree.
We show an analogous result for quantum algorithms equipped with quantum
random-access gates. If we have a quantum algorithm that runs in time $T$ and
uses $M$ qubits, such that the state of the memory, at any time step, is
supported on computational-basis vectors of Hamming weight at most $m$, then it
can be simulated by another algorithm which uses only $O(m \log M)$ memory, and
runs in time $\tilde O(T)$.
We show how this theorem can be used, in a black-box way, to simplify the
presentation in several papers. Broadly speaking, when there exists a need for
a space-efficient history-independent quantum data-structure, it is often
possible to construct a space-inefficient, yet sparse, quantum data structure,
and then appeal to our main theorem. This results in simpler and shorter
arguments.
- Abstract（参考訳）: 古典的なRAMでは、以下の有用な特性がある。
実行を通じて$M$のメモリセルを使用するアルゴリズムがあり、また、どんな時点でも$M$のメモリセルのうち$m$しかゼロではないという意味で、スパースであるなら、$m \log M$メモリのみを使用し、ほぼ同じ時間に実行される別のアルゴリズムにそれを「圧縮」することができる。
ハッシュテーブルまたは自己バランスツリーを使用してメモリをシミュレートすることで、そうすることができる。
量子ランダムアクセスゲートを備えた量子アルゴリズムの類似の結果を示す。
もし時間$T$で実行し、任意のステップでメモリの状態が最大$m$のハミング重みの計算基底ベクトルでサポートされているような$M$ qubitsを使用する量子アルゴリズムがあるなら、それは、$O(m \log M)$メモリのみを使用し、時間$\tilde O(T)$で実行する別のアルゴリズムでシミュレートできる。
我々は,この定理をブラックボックス方式で利用し,プレゼンテーションを単純化する方法をいくつかの論文で示す。
広義的には、空間非効率な歴史非依存の量子データ構造が存在する場合、空間非効率でスパースな量子データ構造を構築し、その上で主定理に訴えることがしばしば可能である。
これにより、より単純で短い議論が生まれる。
関連論文リスト
- Dimension Independent and Computationally Efficient Shadow Tomography [0.0]
シャドウトモグラフィーアルゴリズムは$n=Theta(sqrtmlog m/epsilon2)$サンプルを使用し、$m$の測定と追加エラー$epsilon$について説明する。
これは、ナイーブなアプローチを改善する、これまで知られていたすべてのアルゴリズムとは対照的である。
論文 参考訳（メタデータ） (2024-11-03T03:07:35Z) - A quantum random access memory (QRAM) using a polynomial encoding of binary strings [0.0]
量子ランダムアクセスメモリ(QRAM)は量子オラクルを実現するための有望なアーキテクチャである。
我々はQRAMの新しい設計を開発し、Clifford+T回路で実装する。
我々は、Tカウントを減らし、クォービット数を同じにしながら、T深度を指数的に改善する。
論文 参考訳（メタデータ） (2024-08-28T18:39:56Z) - Quantum algorithms for Hopcroft's problem [45.45456673484445]
計算幾何学の基本的な問題であるホップクロフト問題に対する量子アルゴリズムについて検討する。
この問題の古典的な複雑さはよく研究されており、最もよく知られているアルゴリズムは$O(n4/3)の時間で動作する。
我々の結果は、時間複雑性が$widetilde O(n5/6)$の2つの異なる量子アルゴリズムである。
論文 参考訳（メタデータ） (2024-05-02T10:29:06Z) - Spacetime-Efficient Low-Depth Quantum State Preparation with
Applications [93.56766264306764]
任意の量子状態を作成するための新しい決定論的手法は、以前の方法よりも少ない量子資源を必要とすることを示す。
我々は、量子機械学習、ハミルトンシミュレーション、方程式の線形系を解くことなど、この能力が役立ついくつかのアプリケーションを強調した。
論文 参考訳（メタデータ） (2023-03-03T18:23:20Z) - Cumulative Memory Lower Bounds for Randomized and Quantum Computation [1.52292571922932]
累積記憶は時間空間の複雑さの尺度である。
逐次古典計算と量子回路の両方において、累積メモリの複雑さに関する最初の下位境界を証明した。
論文 参考訳（メタデータ） (2023-01-13T17:57:02Z) - Quantum Resources Required to Block-Encode a Matrix of Classical Data [56.508135743727934]
回路レベルの実装とリソース推定を行い、古典データの高密度な$Ntimes N$行列をブロックエンコードして$epsilon$を精度良くすることができる。
異なるアプローチ間のリソーストレードオフを調査し、量子ランダムアクセスメモリ(QRAM)の2つの異なるモデルの実装を検討する。
我々の結果は、単純なクエリの複雑さを超えて、大量の古典的データが量子アルゴリズムにアクセスできると仮定された場合のリソースコストの明確な図を提供する。
論文 参考訳（メタデータ） (2022-06-07T18:00:01Z) - A lower bound on the space overhead of fault-tolerant quantum computation [51.723084600243716]
しきい値定理は、フォールトトレラント量子計算の理論における基本的な結果である。
振幅雑音を伴う耐故障性量子計算の最大長に対する指数的上限を証明した。
論文 参考訳（メタデータ） (2022-01-31T22:19:49Z) - Low-depth Quantum State Preparation [3.540171881768714]
量子コンピューティングにおける重要なサブルーチンは、$N$複素数の古典的なデータを重ね合わせの$n=lceil logNrceil$-qubit状態の振幅にロードすることである。
ここでは、古典的データを用いた量子状態準備におけるこの時空トレードオフについて検討する。
我々は、$mathcal O(n2)$の回路深さを持つ量子アルゴリズムを提案し、任意の$N$複素数を符号化する。
論文 参考訳（メタデータ） (2021-02-15T13:11:43Z) - Quantum Logspace Algorithm for Powering Matrices with Bounded Norm [7.510385608531827]
コンダクタンス行列,すなわちスペクトルノルムを最大1とする量子対数空間アルゴリズムを提案する。
このアルゴリズムは中間測度を使わずにユニタリ演算子のみを適用する。
このことは、量子コンピューティングの基本原理である遅延測定原理が量子対数アルゴリズムにも適用されていることを示している。
論文 参考訳（メタデータ） (2020-06-08T19:01:04Z) - Quantum Gram-Schmidt Processes and Their Application to Efficient State
Read-out for Quantum Algorithms [87.04438831673063]
本稿では、生成した状態の古典的ベクトル形式を生成する効率的な読み出しプロトコルを提案する。
我々のプロトコルは、出力状態が入力行列の行空間にある場合に適合する。
我々の技術ツールの1つは、Gram-Schmidt正則手順を実行するための効率的な量子アルゴリズムである。
論文 参考訳（メタデータ） (2020-04-14T11:05:26Z) - Quantum Coupon Collector [62.58209964224025]
我々は、$k$-要素集合$Ssubseteq[n]$が、その要素の一様重ね合わせ$|Srangleからいかに効率的に学習できるかを研究する。
我々は、$k$と$n$ごとに必要となる量子サンプルの数に厳密な制限を与え、効率的な量子学習アルゴリズムを与える。
論文 参考訳（メタデータ） (2020-02-18T16:14:55Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。