Fugu-MT 論文翻訳(概要): No exponential quantum speedup for $\mathrm{SIS}^\infty$ anymore

論文の概要: No exponential quantum speedup for $\mathrm{SIS}^\infty$ anymore

arxiv url: http://arxiv.org/abs/2510.07515v1
Date: Wed, 08 Oct 2025 20:28:47 GMT
ステータス: 翻訳完了
システム内更新日: 2025-10-10 17:54:14.71696
Title: No exponential quantum speedup for $\mathrm{SIS}^\infty$ anymore
Title（参考訳）: $\mathrm{SIS}^\infty$ に対する指数的量子スピードアップはもはや存在しない
Authors: Robin Kothari, Ryan O'Donnell, Kewen Wu,
Abstract要約: 平均ケース$ell_infty暗号$-Short Solution(mathrmSISinfty$)問題に対する効率的な量子アルゴリズムを提案する。
参考スコア（独自算出の注目度）: 2.8004615208539523
License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
Abstract: In 2021, Chen, Liu, and Zhandry presented an efficient quantum algorithm for the average-case $\ell_\infty$-Short Integer Solution ($\mathrm{SIS}^\infty$) problem, in a parameter range outside the normal range of cryptographic interest, but still with no known efficient classical algorithm. This was particularly exciting since $\mathrm{SIS}^\infty$ is a simple problem without structure, and their algorithmic techniques were different from those used in prior exponential quantum speedups. We present efficient classical algorithms for all of the $\mathrm{SIS}^\infty$ and (more general) Constrained Integer Solution problems studied in their paper, showing there is no exponential quantum speedup anymore.
Abstract（参考訳）: 2021年、Chen, Liu, Zhandry は平均ケース $\ell_\infty$-Short Integer Solution (\mathrm{SIS}^\infty$) 問題に対して、通常の暗号的関心の範囲外のパラメータ範囲で効率的な量子アルゴリズムを提示した。なぜなら、$\mathrm{SIS}^\infty$は構造を持たない単純な問題であり、それらのアルゴリズム技術は以前の指数量子スピードアップで使われたものとは異なるからである。我々は、これらの論文で研究された制約付き整数解問題に対して、より効率的な古典的アルゴリズムを提示し、指数的量子スピードアップはもはや存在しないことを示した。

関連論文リスト

Qudit-based scalable quantum algorithm for solving the integer programming problem [0.0]
プログラミング (IP) はNPのハードな最適化問題であり、現実世界の様々な問題を表現するために広く使われている。 IPを解くためのほとんどの量子アルゴリズムは、整数を量子ビットにエンコードするため、非常に非効率である。本研究では,回路ベースでスケーラブルな量子アルゴリズムを複数の相互作用量子ビットを用いて提案し,量子スピードアップを示す。
論文参考訳（メタデータ） (2025-08-19T15:06:49Z)
Quantum oracles for the finite element method [45.200826131319815]
本研究では,N倍の剛性および質量行列のブロックエンコーディングに使用されるオラクルの実装に必要な量子ルーチンについて検討した。本稿では, 要素幾何学, 平方根の計算, 条件演算の実装など, 必要なオラクルを構築する方法を示す。
論文参考訳（メタデータ） (2025-04-28T14:28:31Z)
On the practicality of quantum sieving algorithms for the shortest vector problem [42.70026220176376]
格子ベースの暗号は、量子後暗号の主要な候補の1つである。量子攻撃に対する暗号セキュリティは、最短ベクトル問題(SVP)のような格子問題に基づいている SVPを解くための漸近的な量子スピードアップはGroverの探索に依存している。
論文参考訳（メタデータ） (2024-10-17T16:54:41Z)
Sum-of-Squares inspired Quantum Metaheuristic for Polynomial Optimization with the Hadamard Test and Approximate Amplitude Constraints [76.53316706600717]
最近提案された量子アルゴリズムarXiv:2206.14999は半定値プログラミング(SDP)に基づいている SDPにインスパイアされた量子アルゴリズムを2乗和に一般化する。この結果から,本アルゴリズムは大きな問題に適応し,最もよく知られた古典学に近似することが示唆された。
論文参考訳（メタデータ） (2024-08-14T19:04:13Z)
Quantum spectral method for gradient and Hessian estimation [4.193480001271463]
勾配降下は連続最適化問題を解くための最も基本的なアルゴリズムの1つである。本稿では、クエリの複雑さを$widetildeO (1/varepsilon)$とすることで、その勾配の$varepsilon$-approximationを返す量子アルゴリズムを提案する。また、ニュートン法の量子アナログを改善することを目的としたヘッセン推定のための2つの量子アルゴリズムを提案する。
論文参考訳（メタデータ） (2024-07-04T11:03:48Z)
Quantum algorithms for Hopcroft's problem [45.45456673484445]
計算幾何学の基本的な問題であるホップクロフト問題に対する量子アルゴリズムについて検討する。この問題の古典的な複雑さはよく研究されており、最もよく知られているアルゴリズムは$O(n4/3)の時間で動作する。我々の結果は、時間複雑性が$widetilde O(n5/6)$の2つの異なる量子アルゴリズムである。
論文参考訳（メタデータ） (2024-05-02T10:29:06Z)
Do you know what q-means? [42.96240569413475]
古典的な$varepsilon$-$k$-meansアルゴリズムは、ロイドのアルゴリズムの1つの反復の近似バージョンを時間的複雑さで実行する。また,時間的複雑さを考慮した$q$-means量子アルゴリズムも提案する。
論文参考訳（メタデータ） (2023-08-18T17:52:12Z)
Quantum Speedups for Bayesian Network Structure Learning [12.02309220445177]
ノードが$n$のネットワークの場合、最も高速な既知のアルゴリズムは、最悪の場合は$O(2nn2)$で実行され、20年で改善はない。量子コンピューティングの最近の進歩に触発されて、ある定数$c$が2ドル以下であれば、時間$O(cn)$で量子アルゴリズムによって解けるかどうかを問う。
論文参考訳（メタデータ） (2023-05-31T09:15:28Z)
Solving the semidefinite relaxation of QUBOs in matrix multiplication time, and faster with a quantum computer [0.157286095422595]
いくつかの量子SDOソルバは、低精度な状態において高速化を提供する。この事実を利用してアルゴリズムの精度への依存を指数関数的に改善する。我々のアルゴリズムの量子実装は、$mathcalO left(ns + n1.5 cdot textpolylog left(n, | C |_F, frac1epsilon right)$の最悪の実行時間を示す。
論文参考訳（メタデータ） (2023-01-10T23:12:05Z)
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)

関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。