論文の概要: Weak Schur sampling with logarithmic quantum memory
- arxiv url: http://arxiv.org/abs/2309.11947v1
- Date: Thu, 21 Sep 2023 10:02:46 GMT
- ステータス: 処理完了
- システム内更新日: 2023-09-22 15:49:59.101939
- Title: Weak Schur sampling with logarithmic quantum memory
- Title（参考訳）: 対数量子メモリを用いたWeak Schurサンプリング
- Authors: Enrique Cervero and Laura Man\v{c}inska
- Abstract要約: 弱いシュアサンプリングのための新しいアルゴリズムを提案する。
我々のアルゴリズムは、既約表現をインデックスするヤングラベルと対称群の多重度ラベルの両方を効率的に決定する。
- 参考スコア（独自算出の注目度）: 0.0
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: The quantum Schur transform maps the computational basis of a system of $n$
qudits onto a \textit{Schur basis}, which spans the minimal invariant subspaces
of the representations of the unitary and the symmetric groups acting on the
state space of $n$ $d$-level systems. We introduce a new algorithm for the task
of weak Schur sampling. Our algorithm efficiently determines both the Young
label which indexes the irreducible representations and the multiplicity label
of the symmetric group. There are two major advantages of our algorithm for
weak Schur sampling when compared to existing approaches which proceed via
quantum Schur transform algorithm or Generalized Phase Estimation algorithm.
First, our algorihtm is suitable for streaming applications and second it is
exponentially more efficient in its memory usage. We show that an instance of
our weak Schur sampling algorithm on $n$ qubits to accuracy $\epsilon$ requires
only $O(\log_2n)$ qubits of memory and $O(n^3\log_2(\frac{n}{\epsilon}))$ gates
from the Clifford+T set. Further, we show that our weak Schur sampling
algorithm on $n$ qudits decomposes into
$O\big(dn^{2d}\log_2^p\big(\frac{n^{2d}}{\epsilon}\big)\big)$ gates from an
arbitrary fault-tolerant qudit universal set, for $p\approx 4$, and requires a
memory of $O(\log_dn)$ qudits to implement.
- Abstract（参考訳）: 量子シュール変換は、$n$ qudits の系の計算基底を \textit{Schur basis} にマッピングする。これはユニタリ表現の最小不変部分空間と$n$$d$レベルの状態空間に作用する対称群にまたがる。
弱schurサンプリングタスクのための新しいアルゴリズムを提案する。
本アルゴリズムは、既約表現をインデックスするヤングラベルと対称群の多重性ラベルの両方を効率的に決定する。
量子シュア変換アルゴリズムや一般化位相推定アルゴリズムを通した既存手法と比較して,本アルゴリズムの弱いシュアサンプリングには2つの大きな利点がある。
第1に,当社のalgorihtmはストリーミングアプリケーションに適しており,第2に,メモリ使用量において指数関数的に効率的である。
精度を高めるために$n$ qubitsの弱いSchurサンプリングアルゴリズムの例は、$O(\log_2n)$ qubits of memoryと$O(n^3\log_2(\frac{n}{\epsilon})$ Gates from the Clifford+T set。
さらに、$n$ qudits上の弱いSchurサンプリングアルゴリズムは、$O\big(dn^{2d}\log_2^p\big(\frac{n^{2d}}{\epsilon}\big)\big)$ gates from a arbitrary fault-tolerant qudit universal set, for $p\approx 4$, and requires a memory of $O(\log_dn)$ qudits to implement。
関連論文リスト
- Towards Optimal Circuit Size for Sparse Quantum State Preparation [10.386753939552872]
我々は、$s$非ゼロ振幅を持つ$n$量子ビットスパース量子状態の準備を検討し、2つのアルゴリズムを提案する。
最初のアルゴリズムは$O(ns/log n + n)$ gatesを使用し、以前のメソッドを$O(log n)$で改善する。
2番目のアルゴリズムは、短いハミルトニアンパスを示す二進弦向けに調整されている。
論文 参考訳（メタデータ） (2024-04-08T02:13:40Z) - A Scalable Algorithm for Individually Fair K-means Clustering [77.93955971520549]
Jung et al. と Mahabadi et al が導入した個別フェア (p$, $k$) クラスタリング問題に対するスケーラブルなアルゴリズムを提案する。
クラスタリングは、各$xin P$に対して$delta(x)$ of $x$の範囲内で中心となる場合、個別にフェアと呼ばれる。
我々は,従来よりもアルゴリズムがはるかに高速であるだけでなく,低コストのソリューションを生み出すことを実証的に示す。
論文 参考訳（メタデータ） (2024-02-09T19:01:48Z) - Do you know what q-means? [50.045011844765185]
クラスタリングは、大規模なデータセットを分析する上で最も重要なツールの1つである。
クラスタリングのための"$q$-means"アルゴリズムの改良版を提案する。
また、$Obig(frack2varepsilon2(sqrtkd + log(Nd))big で実行される $varepsilon に対する "dequantized" アルゴリズムも提示する。
論文 参考訳（メタデータ） (2023-08-18T17:52:12Z) - Efficiently Learning One-Hidden-Layer ReLU Networks via Schur
Polynomials [50.90125395570797]
正方形損失に関して、標準的なガウス分布の下での$k$ReLU活性化の線形結合をPAC学習する問題をmathbbRd$で検討する。
本研究の主な成果は,この学習課題に対して,サンプルおよび計算複雑性が$(dk/epsilon)O(k)$で,epsilon>0$が目標精度である。
論文 参考訳（メタデータ） (2023-07-24T14:37:22Z) - Quantum Simulation of the First-Quantized Pauli-Fierz Hamiltonian [0.5097809301149342]
我々は、我々の分割と形式主義の征服を通じて、大きな$Lambda$の量子化よりも優れたスケーリングと量子化を得られることを示す。
また,マルチコントロールされたXゲート群を実装する新しい方法を含む,ゲート最適化のための新しいアルゴリズムおよび回路レベル技術も提供する。
論文 参考訳（メタデータ） (2023-06-19T23:20:30Z) - Mind the gap: Achieving a super-Grover quantum speedup by jumping to the
end [114.3957763744719]
本稿では,数種類のバイナリ最適化問題に対して,厳密な実行保証を有する量子アルゴリズムを提案する。
このアルゴリズムは、$n$非依存定数$c$に対して、時間で$O*(2(0.5-c)n)$の最適解を求める。
また、$k$-spinモデルからのランダムなインスタンスの多数と、完全に満足あるいはわずかにフラストレーションされた$k$-CSP式に対して、文 (a) がそうであることを示す。
論文 参考訳（メタデータ） (2022-12-03T02:45:23Z) - Best Policy Identification in Linear MDPs [70.57916977441262]
縮退した線形マルコフ+デルタ決定における最適同定問題について, 生成モデルに基づく固定信頼度設定における検討を行った。
複雑な非最適化プログラムの解としての下位境界は、そのようなアルゴリズムを考案する出発点として用いられる。
論文 参考訳（メタデータ） (2022-08-11T04:12:50Z) - How to simulate quantum measurement without computing marginals [3.222802562733787]
量子状態$psi$を標準で計算するためのアルゴリズムを,古典的に記述し,解析する。
我々のアルゴリズムはサンプリングタスクを$n$-qubit状態のポリ(n)$振幅の計算に還元する。
論文 参考訳（メタデータ） (2021-12-15T21:44:05Z) - Streaming Complexity of SVMs [110.63976030971106]
本稿では,ストリーミングモデルにおけるバイアス正規化SVM問題を解く際の空間複雑性について検討する。
両方の問題に対して、$frac1lambdaepsilon$の次元に対して、$frac1lambdaepsilon$よりも空間的に小さいストリーミングアルゴリズムを得ることができることを示す。
論文 参考訳（メタデータ） (2020-07-07T17:10:00Z) - A Practical Quantum Algorithm for the Schur Transform [0.09208007322096534]
量子シュア変換のための効率的な量子アルゴリズムについて述べる。
シュール変換は、標準計算基底を既約表現からなる基底にマッピングする量子コンピュータ上の演算である。
論文 参考訳（メタデータ） (2017-09-21T01:09:31Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。