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

• arxiv url: http://arxiv.org/abs/2610.00502v1
• Date: Wed, 30 Sep 2026 18:02:44 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-10-03 01:19:23.681617
• Title: Quantum Algorithms for OPI Variants Beyond Locality and Classical Decodability
• Title（参考訳）: OPI変数の局所性と古典的復位性を超えた量子アルゴリズム
• Abstract要約: Regevの還元は、二重符号を復号することで非線形制約を満たすコードワードを見つけるための量子アルゴリズムのフレームワークである。 本研究では,各シンボルの出現回数を規定するヒストグラム局所的制約について検討する。 これにより、重み付け可能な十分質量、最適交叉(OPI)の変種に対する効率的な量子アルゴリズムが提供される。
• 参考スコア（独自算出の注目度）: 2.8216694128509903
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Regev's reduction is a quantum algorithmic framework for finding 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 specifying a set of allowed values for each coordinate. We push past these two restrictions separately via two separate contributions. 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 (Eurocrypt 2022) 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}$) with a ``two-fold multiplication property'': the coordinate-wise products of pairs of codewords span a space of dimension much smaller than $m$. 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 of these constraints, we show that a uniformly random satisfying vector remains satisfying with constant probability after resampling a uniformly random coordinate. This stability provides sufficient Fourier mass at decodable Hamming weights, yielding efficient quantum algorithms for variants of optimal polynomial intersection (OPI).
• Abstract（参考訳）: Regevの還元は、二重符号を復号することで非線形制約を満たすコードワードを見つけるための量子アルゴリズムのフレームワークである。 これまでは、復号化されていないアプリケーションは、効率的な古典的デコーダと、各座標に対して許容される値のセットを指定する座標的制約に依存してきた。 私たちは2つの異なるコントリビューションを通じて、これらの2つの制限を別々に通過させます。 私たちの最初のコントリビューションは量子デコーダを使って解を見つけます $\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 (Eurocrypt 2022) はこの問題を$m=Ω(n^2)$で解く。 我々は、それらのテンプレートをコード($\mathbf{B}$の行で表される)に ``two-fold multiplication property'' で適応する: 符号語対の座標右積は、$m$よりもはるかに小さい次元の空間にまたがる。 第2のコントリビューションは古典的復号を保ちながら、シンボル周波数に対する大域的制約を許容する。 本研究では,各シンボルの出現回数を規定する'histogram-local''制約について検討する。 これらの制約の広い族に対しては、一様ランダムな座標を再サンプリングした後、一様ランダムを満たすベクトルが一定の確率で満たされることが示される。 この安定性は、可除ハミング重みにおける十分なフーリエ質量を提供し、最適多項式交叉(OPI)の変種に対する効率的な量子アルゴリズムをもたらす。

関連論文リスト

• 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)

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

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