論文の概要: Efficient Exact Quantum Sampling from the Sun-Wootters Distribution for Optimal Polynomial Intersection
- arxiv url: http://arxiv.org/abs/2607.16541v2
- Date: Wed, 22 Jul 2026 04:55:03 GMT
- ステータス: 翻訳完了
- システム内更新日: 2026-07-23 16:42:31.531544
- Title: Efficient Exact Quantum Sampling from the Sun-Wootters Distribution for Optimal Polynomial Intersection
- Title（参考訳）: 最適ポリノミアル断面積分布から抽出した高効率量子サンプリング
- Authors: Sunghyeon Jo,
- Abstract要約: ポリノミアル・インターセクション (OPI) は、半円法則によって支配される満足度を保証するデコード量子干渉法 (DQI) を実現するための構造化された最適化問題である。
P_u$ は素体上の平衡 OPI に対して効率的にサンプリング可能であることを示す。
- 参考スコア（独自算出の注目度）: 0.0
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: Optimal Polynomial Intersection (OPI) is a structured optimization problem for which Decoded Quantum Interferometry (DQI) attains a satisfaction guarantee governed by the semicircle law. Sun and Wootters recently showed that, for balanced OPI over prime fields, a Fourier-defined distribution $P_u$ gives a strict worst-case improvement from limiting rate $0.6225$ onward and asymptotically perfect solutions from rate $0.7496$ onward, and asked whether $P_u$ can be sampled efficiently. We answer this question for Reed--Solomon OPI parameters satisfying their exponent condition strictly below the dual Johnson radius. Under coherent membership-oracle access, we give a bounded-error polynomial-time quantum sampler for $P_u$. The ideal circuit samples $P_u$ exactly conditioned on success, while a finite-precision implementation achieves any prescribed inverse-polynomial total-variation error. Consequently, every fixed limiting rate $0.6225\le r<1$ admits a strict worst-case improvement over the DQI semicircle value, and every limiting rate $r\ge 3/4$ admits solutions of satisfaction $1-o(1)$ with high probability. The algorithm coherently sums the amplitudes of all low-weight errors in each syndrome class using deterministic complete list decoding. Complete Reed--Solomon list decoding and the Sun--Wootters denominator estimate make the list size and postselection overhead polynomial. In concurrent and independent work, Horinaga and Yamakawa obtain worst-case OPI algorithms over prime-power fields and exact satisfaction at every fixed rate strictly above $3/4$.
- Abstract（参考訳）: OPI(Optimal Polynomial Intersection)は、デコード量子干渉法(Decoded Quantum Interferometry, DQI)が半円法則によって支配される満足度を保証する構造最適化問題である。
Sun と Wootters は最近、素体上のバランスの取れた OPI に対して、Fourier の定義した$P_u$ は、0.6225$ 以降の制限率と 0.7496$ 以降の漸近的に完璧な解から厳密な最悪の場合の改善をもたらし、$P_u$ を効率的にサンプリングできるかどうかを問うた。
Reed-Solomon OPIパラメータはジョンソン半径の双対以下で指数条件を満たす。
コヒーレントなメンバーシップ・オークルアクセスの下では、有界誤差多項式時間量子サンプリング器を$P_u$で提供する。
理想回路は成功時に正確に条件付き$P_u$をサンプリングし、有限精度実装は所定の逆多項式全変分誤差を達成する。
その結果、固定制限率$0.6225\le r<1$は、DQI半円値よりも厳しい最悪のケース改善を許容し、全ての制限レート$r\ge 3/4$は、高い確率で満足度1-o(1)$の解を認める。
アルゴリズムは、決定論的完全リストデコーディングを用いて、各シンドロームクラスにおける全ての低ウェイトエラーの振幅をコヒーレントに和算する。
Complete Reed--Solomon list decoding and the Sun--Wootters denominator estimated the list size and postelection overhead polynomial。
同時に、ホリナガと山川は、原動力場上の最悪のOPIアルゴリズムと、厳密な3/4ドルの固定レート毎の正確な満足度を得る。
関連論文リスト
- Worst-Case Quantum Algorithm for Optimal Polynomial Intersection Beyond Decoded Quantum Interferometry [6.7936678022428225]
最適多項式補間問題(OPI)は、できるだけ多くの与えられた入力に対して所定の部分集合に値を持つ有限体上の低次を求める。
副生成物として、特定のパラメータ状態における太陽とウーターの存在境界も改善する。
我々の結果は、任意の距離分離可能符号(MDS)に関してMax-LINSAT問題に拡張される。
論文 参考訳（メタデータ） (2026-07-16T07:18:57Z) - Optimal algorithmic complexity of inference in quantum kernel methods [0.815557531820863]
量子カーネル法は、教師あり学習において量子優位性を達成するための主要な候補の一つである。
標準アプローチでは、各項をサンプリングによって独立に見積もっており、クエリの複雑さは$O(NlVertrVert2/varepsilon2)$である。
単一可観測体の期待値として全推論和を符号化したクエリ-最適組合せを提案する。
この結果から,クエリ最適化アルゴリズムと,ハードウェア能力による戦略選択の両立が期待できる。
論文 参考訳（メタデータ） (2026-04-16T16:45:02Z) - On Worst-Case Optimal Polynomial Intersection [10.37026246853005]
復号量子干渉法(Decoded Quantum Interferometry, DQI)は、最悪の場合であっても問題に対する優れた解を効率的に返す量子アルゴリズムである。
素体に対する最悪の事例に対するより良い解が存在することを示す。
論文 参考訳（メタデータ） (2026-04-10T17:50:46Z) - Provably Adaptive Linear Approximation for the Shapley Value and Beyond [73.0940890296463]
基本的で長期にわたる課題は、その効率的な近似である。
一般に用いられるすべての半値に対して$P(|hatboldsymbol-boldsymbol|_2geq)leq$を必要とする線形空間アルゴリズムを開発する。
本アルゴリズムは,各ユーティリティ関数の平均二乗誤差の明示的最小化を可能にする。
論文 参考訳（メタデータ） (2026-04-09T16:38:14Z) - Quantum Approximate Optimization of Integer Graph Problems and Surpassing Semidefinite Programming for Max-k-Cut [0.8084252698425037]
グラフ上の整数問題に適用された量子近似最適化アルゴリズム(QAOA)について検討する。
任意の大きさの高次$d$正則グラフ上で、深さ-p$QAOA予想に対する一般的な反復公式を導出する。
その結果、二進法から整数最適化問題への移動は、量子的優位性のために新しい道を開くことができることを示した。
論文 参考訳（メタデータ） (2026-02-05T18:11:18Z) - Towards large-scale quantum optimization solvers with few qubits [59.63282173947468]
我々は、$m=mathcalO(nk)$バイナリ変数を$n$ qubitsだけを使って最適化するために、$k>1$で可変量子ソルバを導入する。
我々は,特定の量子ビット効率の符号化が,バレン高原の超ポリノミウム緩和を内蔵特徴としてもたらすことを解析的に証明した。
論文 参考訳（メタデータ） (2024-01-17T18:59:38Z) - Mind the gap: Achieving a super-Grover quantum speedup by jumping to the
end [114.3957763744719]
本稿では,数種類のバイナリ最適化問題に対して,厳密な実行保証を有する量子アルゴリズムを提案する。
このアルゴリズムは、$n$非依存定数$c$に対して、時間で$O*(2(0.5-c)n)$の最適解を求める。
また、$k$-spinモデルからのランダムなインスタンスの多数と、完全に満足あるいはわずかにフラストレーションされた$k$-CSP式に対して、文 (a) がそうであることを示す。
論文 参考訳（メタデータ） (2022-12-03T02:45:23Z) - 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)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。