論文の概要: Optimal T Counts under Sparsity: from QROM to State Preparation and Block Encoding
- arxiv url: http://arxiv.org/abs/2607.28260v1
- Date: Thu, 30 Jul 2026 14:18:29 GMT
- ステータス: 翻訳完了
- システム内更新日: 2026-07-31 21:37:00.603818
- Title: Optimal T Counts under Sparsity: from QROM to State Preparation and Block Encoding
- Title（参考訳）: QROMから状態準備、ブロックエンコーディングまで
- Authors: Tongyang Li, Fengning Ou, Xinzhao Wang, Penghui Yao, Pei Yuan, Shengyu Zhang,
- Abstract要約: 多くの量子アルゴリズムは古典的なデータへのコヒーレントなアクセスを必要とし、しばしば量子読み取り専用メモリ(QROM)によってモデル化される。
スパースQROMの$T$数を調べ、$2n$アドレスの$s$だけが非ゼロデータを格納している。
我々の上界はマルチレベルハッシュ方式を使用し、下界はスパースQROMを減らし、適応的なClifford+$T$回路のカウント引数を使用する。
- 参考スコア（独自算出の注目度）: 26.296743455346604
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: Many quantum algorithms require coherent access to classical data, often modeled by quantum read-only memory (QROM). We initiate the study of the $T$ count of sparse QROM, in which only $s$ of the $2^n$ addresses store nonzero data. We prove asymptotically optimal $T$-count bounds $Θ(\sqrt{sm} + \sqrt{sn})$ with square-root dependence on the support size $s$ and message length $m$. Our upper bounds use a multilevel hashing scheme, while our lower bounds reduce sparse QROM to state preparation and use counting arguments for adaptive Clifford+$T$ circuits. The lower bounds thus hold even when mid-circuit measurements and classically controlled operations are allowed. As applications, we obtain matching $T$-count bounds $Θ(\sqrt{sn} + \sqrt{s\log(1/\varepsilon)} + \log(1/\varepsilon))$ for $s$-sparse state preparation and $Θ( \sqrt{2^n sn} + \sqrt{2^n s\log(s/\varepsilon_{\mathrm{BE}})} + \log(s/\varepsilon_{\mathrm{BE}}))$ for block encoding of $s$-sparse matrices, where $\varepsilon$ and $\varepsilon_{\mathrm{BE}}$ are the precision of state preparation and block encoding, respectively.
- Abstract（参考訳）: 多くの量子アルゴリズムは古典的なデータへのコヒーレントなアクセスを必要とし、しばしば量子読み取り専用メモリ(QROM)によってモデル化される。
スパースQROMの$T$カウントの研究を開始し、$2^n$アドレスの$s$だけが非ゼロデータを格納する。
我々は、サポートサイズ$s$とメッセージ長$m$に二乗根依存した漸近的に最適な$T$-count bounds $\(\sqrt{sm} + \sqrt{sn})$を証明する。
我々の上界はマルチレベルハッシュ方式を使用し、下界はスパースQROMを減らし、適応的なClifford+$T$回路のカウント引数を使用する。
これにより、中間回路の測定や古典的に制御された操作が許可された場合でも、下限は保持される。
アプリケーションとして、$T$-count bounds $ (\sqrt{sn} + \sqrt{s\log(1/\varepsilon)} + \log(1/\varepsilon))$ for $s$-sparse state prepared and $ ( \sqrt{2^n sn} + \sqrt{2^n s\log(s/\varepsilon_{\mathrm{BE}}) + \log(s/\varepsilon_{\mathrm{BE}})$ for block encoding of $s$-sparse matrices, where $\varepsilon$ and $\varepsilon_{\mathrm{BE}})は、それぞれブロックとエンコーディングの精度である。
関連論文リスト
- Faster quantum linear system solver beyond the condition number [50.84794327094274]
線形系の正規化解 $|xrangle$ を生成する2つの量子アルゴリズムを、条件数$=lVert A-1rVert$ に依存しない複雑性を持つ精度 $Ax=| b rangle$ に提示する。
フィルタベースのソルバは非常にシンプルで、実行時プレファクタが適しています。
論文 参考訳（メタデータ） (2026-07-08T17:49:40Z) - Quantum Search With Generalized Wildcards [0.4310167974376404]
我々は、コスト$O(sqrtn log n)$の量子アルゴリズムと、ほぼ一致する$Omega(sqrtn)$の低い境界を示す。
以下に示すように、$calQ$が有界サイズセット、連続ブロック、プレフィックス、フルセットのみである場合に、ほぼタイトなバウンダリを表示する。
論文 参考訳（メタデータ） (2025-11-06T18:55:05Z) - Spectral Gaps with Quantum Counting Queries and Oblivious State Preparation [47.600794349481966]
本研究では、量子ビットの対数数を用いて、加算誤差$epsilonDelta_k$まで値を近似する量子アルゴリズムを提案する。
この分析における重要な技術的ステップは、適切なランダム初期状態の準備であり、最終的には閾値よりも小さい固有値の数を効率的に数えることができる。
論文 参考訳（メタデータ） (2025-08-28T17:04:18Z) - Sandwich test for Quantum Phase Estimation [0.0]
量子位相推定(QPE)は多くの実用的な応用を通じて科学的革命の可能性を秘めている。
多くのQPEアルゴリズムは、大きな整数$k$に対して$langle psi|Uk|psirangle$を推定するためにHadamardテストを使用する。
本稿では,このボトルネックに対処する新しいアルゴリズムであるSANDWICHを提案する。
論文 参考訳（メタデータ） (2025-07-31T16:45:07Z) - Quantum state preparation with optimal T-count [1.9402062012850008]
任意の$n$-qubit量子状態を誤差$varepsilon$に近似するために、Tゲートがいくつ必要かを示す。
また、これは任意の対角線$n$-qubitユニタリをエラー$varepsilon$に実装するための最適なTカウントであることを示す。
論文 参考訳（メタデータ） (2024-11-07T15:29:33Z) - A shortcut to an optimal quantum linear system solver [55.2480439325792]
複雑で解析困難な手法を用いない、概念的にシンプルな量子線形システム解法(QLSS)を提案する。
ソリューションノルム$lVertboldsymbolxrVert$が正確に知られているなら、私たちのQLSSはカーネルの1つのアプリケーションだけを必要とします。
あるいは、断熱経路追従法から概念を再導入することにより、標準推定に$O(kappa)$複雑さを実現できることを示す。
論文 参考訳（メタデータ） (2024-06-17T20:54:11Z) - Low-degree learning and the metric entropy of polynomials [44.99833362998488]
少なくとも$Omega(sqrtvarepsilon)2dlog n leq log mathsfM(mathscrF_n,d,|cdot|_L,varepsilon)は2辺の推定値$c(1-varepsilon)2dlogを満たす。
論文 参考訳（メタデータ） (2022-03-17T23:52:08Z) - 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)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。