論文の概要: On the Quantum Equivalence between $S|LWE\rangle$ and $ISIS$
- arxiv url: http://arxiv.org/abs/2510.06097v1
- Date: Tue, 07 Oct 2025 16:25:47 GMT
- ステータス: 翻訳完了
- システム内更新日: 2025-10-08 17:57:08.353547
- Title: On the Quantum Equivalence between $S|LWE\rangle$ and $ISIS$
- Title（参考訳）: S|LWE\rangle$と$ISIS$の量子同値性について
- Authors: André Chailloux, Paul Hermouet,
- Abstract要約: ISIS$ から $S|LWErangle$ への最初の完全に汎用的な還元を示し、基礎となるアルゴリズムにエラーがある場合でも有効である。
また、ある回復可能性条件下では、$ISIS$ のアルゴリズムを $S|LWErangle$ のアルゴリズムに変換することも示している。
- 参考スコア（独自算出の注目度）: 2.5782420501870296
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: Chen, Liu, and Zhandry [CLZ22] introduced the problems $S|LWE\rangle$ and $C|LWE\rangle$ as quantum analogues of the Learning with Errors problem, designed to construct quantum algorithms for the Inhomogeneous Short Integer Solution ($ISIS$) problem. Several later works have used this framework for constructing new quantum algorithms in specific cases. However, the general relation between all these problems is still unknown. In this paper, we investigate the equivalence between $S|LWE\rangle$ and $ISIS$. We present the first fully generic reduction from $ISIS$ to $S|LWE\rangle$, valid even in the presence of errors in the underlying algorithms. We then explore the reverse direction, introducing an inhomogeneous variant of $C|LWE\rangle$, denoted $IC|LWE\rangle$, and show that $IC|LWE\rangle$ reduces to $S|LWE\rangle$. Finally, we prove that, under certain recoverability conditions, an algorithm for $ISIS$ can be transformed into one for $S|LWE\rangle$. We instantiate this reverse reduction by tweaking a known algorithm for $(I)SIS_\infty$ in order to construct quantum algorithm for $S|LWE\rangle$ when the alphabet size q is a small power of 2, recovering some results of Bai et al. [BJK+ 25]. Our results thus clarify the landscape of reductions between $S|LWE\rangle$ and $ISIS$, and we show both their strong connection as well as the remaining barriers for showing full equivalence.
- Abstract（参考訳）: Chen, Liu, and Zhandry [CLZ22] は、Learning with Errors 問題の量子アナログとして、S|LWE\rangle$ と $C|LWE\rangle$ を導入した。
その後のいくつかの研究では、特定のケースで新しい量子アルゴリズムを構築するためにこのフレームワークを使用している。
しかし、これらの問題の一般的な関係はいまだ不明である。
本稿では,$S|LWE\rangle$と$ISIS$の等価性を考察する。
ISIS$ から $S|LWE\rangle$ への最初の完全に汎用的な還元を示し、基礎となるアルゴリズムにエラーがある場合でも有効である。
次に逆方向を探索し、$C|LWE\rangle$の不均一な変種を$IC|LWE\rangle$として導入し、$IC|LWE\rangle$が$S|LWE\rangle$に還元されることを示す。
最後に、ある回復可能性条件下では、$ISIS$ のアルゴリズムを $S|LWE\rangle$ のアルゴリズムに変換することができることを示す。
我々は、この逆還元を、既知のアルゴリズムを$(I)SIS_\infty$で調整して、アルファベットサイズ q が 2 の小さなパワーであるとき、$S|LWE\rangle$ の量子アルゴリズムを構築するために、Bai et al [BJK+ 25] のいくつかの結果を復元する。
以上の結果から,S|LWE\rangle$ と $ISIS$ の縮小の背景を明らかにするとともに,両者の強い関係と,完全同値性を示すための障壁を示す。
関連論文リスト
- p-Mean Regret for Stochastic Bandits [52.828710025519996]
単純で統一された UCB ベースのアルゴリズムを導入し、新しい$p$-mean の後悔境界を実現する。
我々の枠組みは、特別な場合として、平均的な累積的後悔とナッシュ後悔の両方を包含する。
論文 参考訳（メタデータ） (2024-12-14T08:38:26Z) - Learning low-degree quantum objects [5.2373060530454625]
低次量子オブジェクトを、$ell$-distanceで$varepsilon$-errorまで学習する方法を示す。
我々の主な技術的貢献は、量子チャネルと完全有界ポリリノミアルに対する新しいボネンブラスト・ヒル不等式である。
論文 参考訳（メタデータ） (2024-05-17T17:36:44Z) - Basic quantum subroutines: finding multiple marked elements and summing
numbers [1.1265248232450553]
量子クエリーの最適数$O(sqrtN k)$を用いて、サイズ$N$のリスト内のすべての$k$マーク要素を見つける方法を示す。
論文 参考訳（メタデータ） (2023-02-20T19:11:44Z) - Layered State Discovery for Incremental Autonomous Exploration [106.37656068276901]
Layered Autonomous Exploration (LAE) は、$tildemathcalO(LSrightarrow_LAln12(Srightarrow_LAln12(Srightarrow_LAln12(Srightarrow_LAln12(Srightar row_LAln12)Srightarrow_LAln12(Srightarrow_LAln12)Srightarrow_LAln12(Srightarrow_LAln12)のサンプル複雑性を達成するAXの新しいアルゴリズムである。
論文 参考訳（メタデータ） (2023-02-07T22:58:12Z) - Finding many Collisions via Reusable Quantum Walks [1.376408511310322]
衝突発見は暗号解析におけるユビキタスな問題である。
本稿では,この問題に対するアルゴリズムを改良し,特に許容可能なパラメータの範囲を広げる。
応用として、最短ベクトル問題に対する量子シービングアルゴリズムを改善する。
論文 参考訳（メタデータ） (2022-05-27T14:50:45Z) - Corralling a Larger Band of Bandits: A Case Study on Switching Regret
for Linear Bandits [99.86860277006318]
本稿では,一組の逆アルゴリズムを組み合わせ,学習することの問題点について考察する。
Agarwal et al. の CORRAL はこの目標を、$widetildeO(sqrtd S T)$ の残酷なオーバーヘッドで達成している。
この問題に触発されて、後悔のオーバーヘッドが百万ドルにしか依存しない大規模バンディットアルゴリズムのバンドを囲む新しいレシピを提案する。
論文 参考訳（メタデータ） (2022-02-12T21:55:44Z) - 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) - Fast digital methods for adiabatic state preparation [0.0]
ゲート型量子コンピュータにおいて,逆誤差の複雑多元対数を伴う断熱状態生成のための量子アルゴリズムを提案する。
論文 参考訳（メタデータ） (2020-04-08T18:00:01Z) - Tight Quantum Lower Bound for Approximate Counting with Quantum States [49.6558487240078]
Aaronson, Kothari, Kretschmer, Thaler (2020) が考える数え上げ問題の次の変種に対する厳密な下界を証明する。
このタスクは、入力セット$xsubseteq [n]$が$k$か$k'=(1+varepsilon)k$であるかどうかを識別する。
論文 参考訳（メタデータ） (2020-02-17T10:53:50Z) - Quantum algorithms for the Goldreich-Levin learning problem [3.8849433921565284]
Goldreich-Levinアルゴリズムは元々暗号目的のために提案され、その後学習に適用された。
ウォルシュ係数を持つベクトルを$w$で出力するには$poly(n,frac1epsilonlogfrac1delta)$時間を要する。
本稿では,この問題に対する量子アルゴリズムをクエリ複雑性$O(fraclogfrac1deltaepsilon4)$で与えられる。
論文 参考訳（メタデータ） (2019-12-31T14:52:36Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。