論文の概要: Trading Memory for Depth: Tight Bounds for LCU Block-Encodings
- arxiv url: http://arxiv.org/abs/2611.15229v1
- Date: Wed, 11 Nov 2026 09:22:38 GMT
- ステータス: 翻訳完了
- システム内更新日: 2026-11-14 01:36:33.091062
- Title: Trading Memory for Depth: Tight Bounds for LCU Block-Encodings
- Title(参考訳): 深さのトレーディングメモリ:LCUブロックエンコーディングのためのタイト境界
- Abstract要約: LCUブロックエンコーディングの$A=sum_j_j U_j$は1レジスタで$U_j$を連続して実行するので、その選択深度は$sum_j d_j$である。
for a $g$-branched realisation において、選択深さは$(C+log(g,maxn,m))$ for $gge2$, with $C$ the binning makespan and $m$ the largest bin, in the $k$-local atomic-oracle model
- 参考スコア(独自算出の注目度): 0.0
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: An LCU block-encoding of $A=\sum_jα_j U_j$ runs the $U_j$ in series on one register, so its select depth is the total work $\sum_j d_j$. Depth was the one block-encoding constraint with no knob: grouping the $T$ terms into $g$ registers that run in parallel gives it one, and the binning is the knob. For a $g$-branched realisation (up to $g$ oracles in parallel) the select depth is tight at $Θ(C+\log(g\,\max\{n,m\}))$ for $g\ge2$, with $C$ the binning makespan and $m$ the largest bin, in the $k$-local atomic-oracle model. The work floor is a two-way reduction to classical multiprocessor scheduling: every realisation \emph{induces} a $g$-machine schedule, and the construction realises any binning, so an optimal binning attains it. The additive logarithmic routing term is a light-cone cost, independent of the selector encoding and robust to register reuse, measurement, reset, and teleportation; width is at least $gn$. The standard $1/α$ subnormalisation and success probability are unchanged; the endpoints are sequential LCU ($g{=}1$) and the fully parallel realisation ($g{=}T$). Allowing the oracles to be split (McNaughton's rule) reaches the work floor $\sum_j d_j/g$. Two selector realisations trade space for depth: a dense (Möttönen) one is memory-tight at the standard LCU footprint but its multiplexed controls cost a $\log\log(m{+}1)$ factor on the makespan; a one-hot one is depth-tight at $T$ selector qubits. Neither reaches both at once.
- Abstract(参考訳): LCUブロックエンコーディングの$A=\sum_jα_j U_j$は1つのレジスタで$U_j$を連続して実行するので、その選択深度は合計$\sum_j d_j$である。
Depthは、knobのないブロックエンコード制約のひとつで、$T$項を並列に実行する$g$レジスタにグループ化することで、knobとなる。
a $g$-branched realization (並列で$g$ oraclesまで) に対して、選択深度は$(C+\log(g\,\max\{n,m\}))$ for $g\ge2$, with $C$ the binning makespan and $m$ the largest bin, in the $k$-local atomic-oracle model。
すべての実化 \emph{induces} は$g$-machine スケジュールであり、構造は任意の双行を実現するので、最適双行はそれを達成する。
加算対数ルーティング項は光コーンコストであり、セレクタエンコーディングとは独立して再利用、測定、リセット、テレポーテーションを登録する。
標準の1/α$部分正規化と成功確率は変化せず、エンドポイントは連続LCU(g{=}1$)、完全並列化(g{=}T$)である。
オーラクルを分割すること(McNaughtonのルール)は、作業フロアに$\sum_j d_j/g$に達する。
密度 (Möttönen) は標準LCUフットプリントにおけるメモリタイトであるが、その多重制御はメイスパン上の$\log\log(m{+}1)$ factor を犠牲にしている。
どちらもすぐには到達しない。
関連論文リスト
- Fast Approximate $\ell_p$ Chamfer Distance via Lopsided Embeddings and Structured JL [63.08320557041278]
本稿では,Chamfer 距離を $ell_p ノルムで 1 p le 2$ で近似する効率的なアルゴリズムを提案する。
チャムファー距離を保存するのに十分であることを示す。
また, ストリーミング環境における角距離および上下境界について, 追加的な結果を与える。
論文 参考訳(メタデータ) (2026-11-08T05:46:25Z) - Optimal Temporal Hiding in Correlated Quantum Reference-Frame Processes [0.0]
$[n,k]_q$コードの一様コセット法則は、$d(Cperp)$スロット以下のすべての集合で同一である。
ネストされたコードに対して$Csubset D$、ペイロード$R=dim D-dim C$、見えない深さ$t=d_mathrmrel(Cperp,Dperp)-1$、セクター距離$d_mathrmrel(D,C)-1leq n$。
論文 参考訳(メタデータ) (2026-08-06T06:27:12Z) - Near-Optimal Dimension Lower Bounds for Single-Vector Embeddings of Maximum Inner Product Similarity [75.14269295861845]
シングルトンクエリでは、Chamferは最大内部積類似度(MAX-IP)になる。
すべての固定$in(0,1)$に対して、定数は$A_,c_>0$である。
単位球MAX-IPマトリクスは、DNFパターンマトリクスの正確な2値アフィンイメージであり、少なくとも8ドルのギャップがある。
論文 参考訳(メタデータ) (2026-07-22T17:27:20Z) - Actively Learning Halfspaces without Synthetic Data [34.777547976926456]
我々は、点合成なしでハーフスペースを学習するための効率的なアルゴリズムを設計する。
コーナリーとして、軸整合半空間に対して最適な$O(d + log n)$クエリ決定論的学習器を得る。
我々のアルゴリズムはブール関数を$f$ over $n$要素で学習するより一般的な問題を解く。
論文 参考訳(メタデータ) (2025-09-25T07:39:25Z) - $\mathrm{TIME}[t]\subseteq \mathrm{SPACE}[O(\sqrt{t})]$ via Tree Height Compression [0.0]
Algebraic Replay Engineは、ポインターレスDSSとインデックスなしストリーミングとともに、一定の大きさのフィールド上の一定度マップを持つ。
S(b)=O(b+t/b)$は、残余乗法的ポリログ因子を持たない$O(sqrtt)$空間を与える。
論文 参考訳(メタデータ) (2025-08-20T16:27:53Z) - Depth-Efficient Quantum Circuit Synthesis for Deterministic Dicke State Preparation [5.755460769073285]
ディック状態は量子コンピューティングに広く応用された、絡み合った量子状態の重要なクラスを表す。
一般に見られる2つの量子ビット接続制約の下でDicke状態生成のための決定論的量子回路を提案する。
論文 参考訳(メタデータ) (2025-05-21T11:55:17Z) - Near-Optimal Regret Bounds for Multi-batch Reinforcement Learning [54.806166861456035]
本研究では,有限水平マルコフ決定過程(MDP)によってモデル化されたエピソディック強化学習(RL)問題をバッチ数に制約を加えて検討する。
我々は,$tildeO(sqrtSAH3Kln (1/delta))$tildeO(cdot)をほぼ最適に後悔するアルゴリズムを設計し,$(S,A,H,K)$の対数項を$K$で隠蔽する。
技術的貢献は2つある: 1) 探索のためのほぼ最適設計スキーム
論文 参考訳(メタデータ) (2022-10-15T09:22:22Z) - An Optimal Separation of Randomized and Quantum Query Complexity [67.19751155411075]
すべての決定木に対して、与えられた順序 $ellsqrtbinomdell (1+log n)ell-1,$ sum to at least $cellsqrtbinomdell (1+log n)ell-1,$ where $n$ is the number of variables, $d$ is the tree depth, $c>0$ is a absolute constant。
論文 参考訳(メタデータ) (2020-08-24T06:50:57Z) - Streaming Complexity of SVMs [110.63976030971106]
本稿では,ストリーミングモデルにおけるバイアス正規化SVM問題を解く際の空間複雑性について検討する。
両方の問題に対して、$frac1lambdaepsilon$の次元に対して、$frac1lambdaepsilon$よりも空間的に小さいストリーミングアルゴリズムを得ることができることを示す。
論文 参考訳(メタデータ) (2020-07-07T17:10:00Z) - $Q$-learning with Logarithmic Regret [60.24952657636464]
楽観的な$Q$は$mathcalOleft(fracSAcdot mathrmpolyleft(Hright)Delta_minlogleft(SATright)right)$ cumulative regret bound, where $S$ is the number of state, $A$ is the number of action, $H$ is the planning horizon, $T$ is the total number of steps, $Delta_min$ is the least sub-Optitimality gap。
論文 参考訳(メタデータ) (2020-06-16T13:01:33Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。