論文の概要: Overflow-Safe Polylog-Time Parallel Minimum-Weight Perfect Matching Decoder: Toward Experimental Demonstration

• arxiv url: http://arxiv.org/abs/2603.03776v1
• Date: Wed, 04 Mar 2026 06:32:24 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-03-05 21:29:15.204527
• Title: Overflow-Safe Polylog-Time Parallel Minimum-Weight Perfect Matching Decoder: Toward Experimental Demonstration
• Title（参考訳）: オーバーフローセーフなポリログ時間並列最小値完全整合デコーダ
• Authors: Ryo Mikami, Hayata Yamasaki,
• Abstract要約: フォールトトレラント量子計算(FTQC)は、量子エラーの高速かつ正確な復号化を必要とする。 有限ビット表現におけるオーバーフローを検出するポリログ時間MWPMデコーダを提案する。 行列式に基づくアプローチの構造に合わせたアルゴリズム最適化により、中間値を表すために必要なビットを99.9%以上削減する。
• 参考スコア（独自算出の注目度）: 1.0742675209112622
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Fault-tolerant quantum computation (FTQC) requires fast and accurate decoding of quantum errors, which is often formulated as a minimum-weight perfect matching (MWPM) problem. A determinant-based approach has been proposed as a promising method to surpass the conventional polynomial runtime of MWPM decoding via the blossom algorithm, asymptotically achieving polylogarithmic parallel runtime. However, the existing approach requires an impractically large bit length to represent intermediate values during the computation of the matrix determinant; moreover, when implemented on a finite-bit machine, the algorithm cannot detect overflow, and therefore, the mathematical correctness of such algorithms cannot be guaranteed. In this work, we address these issues by presenting a polylog-time MWPM decoder that detects overflow in finite-bit representations by employing an algebraic framework over a truncated polynomial ring. Within this framework, all arithmetic operations are implemented using bitwise XOR and shift operations, enabling efficient and hardware-friendly implementation. Furthermore, with algorithmic optimizations tailored to the structure of the determinant-based approach, we reduce the arithmetic bit length required to represent intermediate values in the determinant computation by more than $99.9\%$, while preserving its polylogarithmic runtime scaling. These results open the possibility of a proof-of-principle demonstration of the polylog-time MPWM decoding in the early FTQC regime.
• Abstract（参考訳）: フォールトトレラント量子計算(FTQC)は、量子エラーの高速かつ正確な復号化を必要とし、しばしば最小ウェイト完全マッチング(MWPM)問題として定式化される。 MWPMデコーディングの従来の多項式ランタイムを越え, 漸近的に多対数並列実行を実現するために, 行列式に基づく手法が提案されている。 しかし、既存の手法では行列行列の計算中に中間値を表すために急激な大きなビット長が必要であり、さらに有限ビットマシンに実装された場合、アルゴリズムはオーバーフローを検出できないため、そのようなアルゴリズムの数学的正確性は保証できない。 本研究では,有限ビット表現におけるオーバーフローを検出するポリログ時間MWPMデコーダを,代数的フレームワークを用いてトランカットした多項式環上に配置することで,これらの問題に対処する。 このフレームワーク内では、全ての算術演算はビットワイズXORとシフト演算を使用して実装され、効率的でハードウェアフレンドリーな実装を可能にする。 さらに、行列式に基づく手法の構造に合わせたアルゴリズム最適化により、行列式計算の中間値を表すのに必要な演算ビット長を99.9\%$以上削減し、その多対数実行時スケーリングを保存する。 これらの結果は、FTQC初期のポリログ時間MPWMデコーディングの実証的実証の可能性を開く。

関連論文リスト

• Fast MLE and MAPE-Based Device Activity Detection for Grant-Free Access via PSCA and PSCA-Net [13.076905065264091]
  高速で正確なデバイスアクティビティは、大規模なマシンタイプの通信をサポートするための許可なしアクセスにおける重要な課題である。 本稿では,MLEに基づくデバイスアクティビティ検出手法を提案する。 本稿では,計算時間を削減するために,PSCA-Netと呼ばれるディープアンローリングニューラルネットワークの実装を提案する。
  論文  参考訳（メタデータ） (2025-03-19T14:31:09Z)
• Fast Expectation Value Calculation Speedup of Quantum Approximate Optimization Algorithm: HoLCUs QAOA [55.2480439325792]
  本稿では,LCU演算子の線形結合として表現できる演算子の期待値を計算するための新しい手法を提案する。 この方法は任意の量子アルゴリズムに対して一般的であり、変分量子アルゴリズムの加速に特に関心がある。
  論文  参考訳（メタデータ） (2025-03-03T17:15:23Z)
• A Sample Efficient Alternating Minimization-based Algorithm For Robust Phase Retrieval [56.67706781191521]
  そこで本研究では,未知の信号の復元を課題とする,ロバストな位相探索問題を提案する。 提案するオラクルは、単純な勾配ステップと外れ値を用いて、計算学的スペクトル降下を回避している。
  論文  参考訳（メタデータ） (2024-09-07T06:37:23Z)
• From Optimization to Control: Quasi Policy Iteration [2.0769172070951067]
  準政治反復(QPI)と呼ばれる新しい制御アルゴリズムを提案する。 QPIは、MDP特有の2つの線形構造制約を利用し、遷移確率カーネルの事前情報を組み込むことができる。
  論文  参考訳（メタデータ） (2023-11-18T21:00:14Z)
• Quantum-Based Feature Selection for Multi-classification Problem in Complex Systems with Edge Computing [15.894122816099133]
  マルチクラス化問題,すなわちQReliefFに対する量子ベースの特徴選択アルゴリズムを提案する。 我々のアルゴリズムは、O(M) から O(sqrt(M)) への複雑さを減らし、最も近い隣人を見つけるのに優れている。
  論文  参考訳（メタデータ） (2023-10-01T03:57:13Z)
• 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)
• Adaptive Sampling for Best Policy Identification in Markov Decision Processes [79.4957965474334]
  本稿では,学習者が生成モデルにアクセスできる場合の,割引マルコフ決定(MDP)における最良の政治的識別の問題について検討する。 最先端アルゴリズムの利点を論じ、解説する。
  論文  参考訳（メタデータ） (2020-09-28T15:22:24Z)
• Accelerated Message Passing for Entropy-Regularized MAP Inference [89.15658822319928]
  離散値のランダムフィールドにおけるMAP推論の最大化は、機械学習の基本的な問題である。 この問題の難しさから、特殊メッセージパッシングアルゴリズムの導出には線形プログラミング(LP)緩和が一般的である。 古典的加速勾配の根底にある手法を活用することにより,これらのアルゴリズムを高速化するランダム化手法を提案する。
  論文  参考訳（メタデータ） (2020-07-01T18:43:32Z)
• Approximation Algorithms for Sparse Principal Component Analysis [57.5357874512594]
  主成分分析(PCA)は、機械学習と統計学において広く使われている次元削減手法である。 スパース主成分分析(Sparse principal Component Analysis)と呼ばれる,スパース主成分負荷を求める様々な手法が提案されている。 本研究では,SPCA問題に対するしきい値の精度,時間,近似アルゴリズムを提案する。
  論文  参考訳（メタデータ） (2020-06-23T04:25:36Z)

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

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