論文の概要: Algebraic Geometry Codes and Decoded Quantum Interferometry

• arxiv url: http://arxiv.org/abs/2510.06603v1
• Date: Wed, 08 Oct 2025 03:25:30 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-10-09 16:41:20.275593
• Title: Algebraic Geometry Codes and Decoded Quantum Interferometry
• Title（参考訳）: 代数幾何学符号と復号量子干渉法
• Authors: Andi Gu, Stephen P. Jordan,
• Abstract要約: Decoded Quantum Interferometry (DQI) は、デコード問題と最適化問題をペア化する双対性を定義する。 HOPIはHermitian曲線上の回帰問題であり、Hermitian符号の双対はHermitian符号であるので、HOPI問題はHermitian符号の近似リスト復元と見なすこともできる。
• 参考スコア（独自算出の注目度）: 0.0
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Decoded Quantum Interferometry (DQI) defines a duality that pairs decoding problems with optimization problems. The original work on DQI considered Reed-Solomon decoding, whose dual optimization problem, called Optimal Polynomial Intersection (OPI), is a polynomial regression problem over a finite field. Here, we consider a class of algebraic geometry codes called Hermitian codes, which achieve block length $q^3$ using alphabet $\mathbb{F}_{q^2}$ compared to Reed-Solomon's limitation to block length $q$ over $\mathbb{F}_q$, requiring approximately one-third fewer qubits per field element for quantum implementations. We show that the dual optimization problem, which we call Hermitian Optimal Polynomial Intersection (HOPI), is a polynomial regression problem over a Hermitian curve, and because the dual to a Hermitian code is another Hermitian code, the HOPI problem can also be viewed as approximate list recovery for Hermitian codes. By comparing to Prange's algorithm, simulated annealing, and algebraic list recovery algorithms, we find a large parameter regime in which DQI efficiently achieves a better approximation than these classical algorithms, suggesting that the apparent quantum speedup offered by DQI extends beyond Reed-Solomon codes to a broader class of polynomial regression problems on algebraic varieties.
• Abstract（参考訳）: Decoded Quantum Interferometry (DQI) は最適化問題とデコード問題をペア化する双対性を定義する。 DQIの元々の研究はリード・ソロモン復号(英語版)(Reed-Solomon decoding)であり、その双対最適化問題(Optimal Polynomial Intersection (OPI))は有限体上の多項式回帰問題である。 ここでは、ブロック長$q^3$をアルファベット$\mathbb{F}_{q^2}$と、Reed-Solomonのブロック長$q$ over $\mathbb{F}_q$と比較して、ブロック長$q^3$を達成するエルミート符号と呼ばれる代数的幾何学的符号のクラスを考える。 我々は、Hermitian Optimal Polynomial Intersection (HOPI) と呼ぶ双対最適化問題は、Hermitian曲線上の多項式回帰問題であり、Hermitian符号の双対は別のHermitian符号であるため、HOPI問題はHermitian符号の近似リスト復元として見ることもできることを示した。 Prangeのアルゴリズム、シミュレートされたアニーリング、代数的リスト回復アルゴリズムと比較することにより、DQIがこれらの古典的アルゴリズムよりも効率的に近似を達成できる大きなパラメータ構造を見つけ、DQIが提供する見かけの量子スピードアップがリード・ソロモン符号を超えて代数多様体上のより広範な多項式回帰問題のクラスに広がることを示唆する。

関連論文リスト

• Quantum advantage from soft decoders [0.7728149002473877]
  最適多項式補間法(OPI)問題におけるいくつかのインスタンス化の改善について述べる。 我々の結果は自然で説得力のある復号問題をもたらし、量子的優位性を持っていると信じている。 本稿では,Regevのリダクションの設定にデコーダを利用できるように,シンドロームからコセットサンプリング問題への新たなリダクションを提案する。
  論文  参考訳（メタデータ） (2024-11-19T15:12:03Z)
• Optimization by Decoded Quantum Interferometry [42.169154389732036]
  Decoded Quantum Interferometry (DQI) という量子アルゴリズムを導入する。 有限体上のデータに近似するために、DQIは我々の知るどの時間よりも良い近似比を達成する。
  論文  参考訳（メタデータ） (2024-08-15T17:47:42Z)
• 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)
• Complexity-Theoretic Limitations on Quantum Algorithms for Topological Data Analysis [59.545114016224254]
  トポロジカルデータ解析のための量子アルゴリズムは、古典的手法よりも指数関数的に有利である。 我々は、量子コンピュータにおいても、TDA(ベッチ数の推定)の中心的なタスクが難解であることを示します。 我々は、入力データが単純さの仕様として与えられると、指数的量子優位性を取り戻すことができると論じる。
  論文  参考訳（メタデータ） (2022-09-28T17:53:25Z)
• 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)
• Quantum message-passing algorithm for optimal and efficient decoding [2.3020018305241328]
  我々はBPQMアルゴリズムの理解、形式、適用性を拡張する。 BPQMアルゴリズムの完全かつ曖昧さのない最初の公式記述を提供する。 BPQM がサイクルを持つ因子グラフ上で最も優れた古典デコーダを著しく上回ることを示す有望な数値結果を示す。
  論文  参考訳（メタデータ） (2021-09-16T18:01:12Z)
• Optimal Gradient-based Algorithms for Non-concave Bandit Optimization [76.57464214864756]
  この研究は、未知の報酬関数が非可逆であるようなバンドイット問題の大群を考察する。 我々のアルゴリズムは、非常に一般化されたゼロ階最適化のパラダイムに基づいている。 標準的な楽観的アルゴリズムは次元因子によって準最適であることを示す。
  論文  参考訳（メタデータ） (2021-07-09T16:04:24Z)
• Adiabatic Quantum Graph Matching with Permutation Matrix Constraints [75.88678895180189]
  3次元形状と画像のマッチング問題は、NPハードな置換行列制約を持つ二次代入問題(QAP)としてしばしば定式化される。 本稿では,量子ハードウェア上での効率的な実行に適した制約のない問題として,いくつかのQAPの再構成を提案する。 提案アルゴリズムは、将来の量子コンピューティングアーキテクチャにおいて、より高次元にスケールする可能性がある。
  論文  参考訳（メタデータ） (2021-07-08T17:59:55Z)

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

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