論文の概要: Quantum Algorithms for OPI Variants Beyond Locality and Classical Decodability

• arxiv url: http://arxiv.org/abs/2610.00502v2
• Date: Fri, 02 Oct 2026 15:23:05 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-10-06 00:14:29.9802
• Title: Quantum Algorithms for OPI Variants Beyond Locality and Classical Decodability
• Title（参考訳）: OPI変数の局所性と古典的復位性を超えた量子アルゴリズム
• Abstract要約: Regevの還元は、二重符号を復号することで非線形制約を満たす符号語を量子的に見つける。 古典的デコーダと座標的制約を別々に克服する。 ランダムな点で句読されたリード・ミュラー符号に対して、我々のアルゴリズムは、それらの点で正確にサポートされた未定の双対符号の単語を見つける。
• 参考スコア（独自算出の注目度）: 2.8216694128509903
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Regev's reduction quantumly finds codewords satisfying nonlinear constraints by decoding the dual code. To date, applications that have not been dequantized have relied on efficient classical decoders and coordinate-wise constraints. We overcome these restrictions separately. Our first contribution uses a quantum decoder to find solutions $\mathbf{y}\in(\mathbb{F}_q\setminus\{0\})^m$ to $\mathbf{B}\mathbf{y}=0$, where $\mathbf{B}\in\mathbb{F}_q^{n\times m}$. For fixed prime $q>2$, Chen, Liu, and Zhandry solve this problem for random matrices with $m=Ω(n^2)$, a regime now covered by classical algorithms. We adapt their template to codes (spanned by the rows of $\mathbf{B}$) that satisfy a "two-fold multiplication property": the coordinate-wise products of pairs of codewords span a space of dimension smaller than $m$. Under suitable distance conditions, this allows us to solve instances with $m\leq n^{2-Ω(1)}$, beyond the established guarantees of classical algorithms. We also give an efficient classical algorithm under a stronger three-fold multiplication property, leaving intermediate regimes as candidates for quantum advantage. For Reed-Muller codes punctured at random points, our algorithm finds a word in the unpunctured dual code supported exactly on those points. This works beyond known efficient classical decoding regimes. Our second contribution retains classical decoding but allows global constraints on symbol frequencies. We study "histogram-local" constraints, which specify the allowed numbers of occurrences of each symbol. For broad families, stability under resampling one coordinate yields efficient quantum algorithms for variants of optimal polynomial intersection (OPI) combining coordinate-wise and histogram-local constraints. Adapting Yamakawa-Zhandry, we prove a quantum-classical separation for these problems relative to a classical random oracle.
• Abstract（参考訳）: Regevの還元は、二重符号を復号することで非線形制約を満たす符号語を量子的に見つける。 これまでは、デクタント化されていないアプリケーションは、効率的な古典的デコーダと座標的制約に依存してきた。 我々はこれらの制限を別々に克服する。 私たちの最初のコントリビューションは量子デコーダを使って解を見つけます $\mathbf{y}\in(\mathbb{F}_q\setminus\{0\})^m$ to $\mathbf{B}\mathbf{y}=0$, ここで $\mathbf{B}\in\mathbb{F}_q^{n\times m}$。 固定素数$q>2$の場合、Chen, Liu, Zhandry はこの問題を $m=Ω(n^2)$ のランダム行列に対して解く。 それらのテンプレートをコード($\mathbf{B}$の行で表される)に適応させ、「2倍の乗算特性」を満たす: ペアのコードワードの座標積は、$m$より小さい次元の空間にまたがる。 適切な距離条件の下では、古典的アルゴリズムの確立された保証を超えた$m\leq n^{2-Ω(1)}$のインスタンスを解くことができる。 また、より強い3倍の乗法特性の下で効率の良い古典的アルゴリズムも提供し、中間状態は量子的優位性の候補として残す。 ランダムな点で句読されたリード・ミュラー符号に対して、我々のアルゴリズムは、それらの点で正確にサポートされた未定の双対符号の単語を見つける。 これは、既知の古典的復号法を超えて機能する。 第2のコントリビューションは古典的復号を保ちながら、シンボル周波数に対する大域的制約を許容する。 本研究では,各シンボルの許容回数を規定する「ヒストグラム局所」制約について検討する。 広い族に対して、1つの座標を再サンプリングする安定性は、座標ワイドとヒストグラム局所的制約を組み合わせた最適多項式交叉(OPI)の変種に対する効率的な量子アルゴリズムをもたらす。 山川-Zhandry に適応し、古典的ランダムオラクルと比較してこれらの問題に対して量子古典的分離を証明した。

関連論文リスト

• Solving Sparse SDPs in Sublinear Time: A Classical Algorithm Inspired by the Quantum OR Lemma [70.99943094379263]
  有界ラディウス系におけるスパース半定値プログラムに対する最初の準時間古典的解法を与える。 我々の主な技術的貢献は、ハミルトンのギブス状態を同時に表す古典的な手続きである。
  論文  参考訳（メタデータ） (2026-09-30T17:51:21Z)
• Hardness of approximation for minimum-weight decoding of two-dimensional topological quantum codes [0.0]
  位相量子符号の最小重復号法の計算複雑性について検討する。 独立な$X$-および$Z$-errorモデルの下でのカラーコードについては、分離最小ウェイトデコードを考える。
  論文  参考訳（メタデータ） (2026-08-17T20:37:08Z)
• Two-Tower Quantum Matrix Chain Multiplication: Trading Qubits for Depth [73.08853228981701]
  行列連鎖乗法は、科学計算、機械学習、グラフ解析における問題である。 我々は、$K$行列の$mathcalW$を回路深さの量子状態にエンコードする量子サブルーチンであるemphTwo-Tower Matrixを提案する。
  論文  参考訳（メタデータ） (2026-07-14T18:42:40Z)
• Permutation-symmetric quantum trajectories [42.05677589454327]
  我々は、共通のシステムに結合した$N$エミッタのモデルに対して、弱い置換対称性を尊重する解法をいかに実行できるかを示す。 2レベルエミッターに関わる問題に対して、そのような暴言は計算コストを$mathcalO(N5)$から$mathcalO(N2)$に下げる。
  論文  参考訳（メタデータ） (2026-05-11T18:08:08Z)
• Spectral Gaps with Quantum Counting Queries and Oblivious State Preparation [47.600794349481966]
  本研究では、量子ビットの対数数を用いて、加算誤差$epsilonDelta_k$まで値を近似する量子アルゴリズムを提案する。 この分析における重要な技術的ステップは、適切なランダム初期状態の準備であり、最終的には閾値よりも小さい固有値の数を効率的に数えることができる。
  論文  参考訳（メタデータ） (2025-08-28T17:04:18Z)
• Quantum Goemans-Williamson Algorithm with the Hadamard Test and Approximate Amplitude Constraints [62.72309460291971]
  本稿では,n+1$ qubitsしか使用しないGoemans-Williamsonアルゴリズムの変分量子アルゴリズムを提案する。 補助量子ビット上で適切にパラメータ化されたユニタリ条件として目的行列を符号化することにより、効率的な最適化を実現する。 各種NPハード問題に対して,Goemans-Williamsonアルゴリズムの量子的効率的な実装を考案し,提案プロトコルの有効性を実証する。
  論文  参考訳（メタデータ） (2022-06-30T03:15:23Z)
• Linear-Time Gromov Wasserstein Distances using Low Rank Couplings and Costs [45.87981728307819]
  異種空間に居住する関連するデータセットを比較して整列する能力は、機械学習においてますます重要な役割を担っている。 グロモフ・ワッサーシュタイン (Gromov-Wasserstein, GW) 形式主義はこの問題に対処するのに役立つ。
  論文  参考訳（メタデータ） (2021-06-02T12:50:56Z)
• Quantum learning algorithms imply circuit lower bounds [7.970954821067043]
  量子アルゴリズムの設計と回路下界の一般接続を確立する。 我々の証明は、学習理論、擬似ランダム性、計算複雑性に関するいくつかの研究に基づいている。
  論文  参考訳（メタデータ） (2020-12-03T14:03:20Z)

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

指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。