論文の概要: SAT, MaxSAT, and SMT for QLDPC Distance Computation: A Large-Scale Empirical Study
- arxiv url: http://arxiv.org/abs/2606.12445v1
- Date: Fri, 29 May 2026 15:34:33 GMT
- ステータス: 翻訳完了
- システム内更新日: 2026-06-15 07:09:36.913351
- Title: SAT, MaxSAT, and SMT for QLDPC Distance Computation: A Large-Scale Empirical Study
- Title（参考訳）: QLDPC距離計算のためのSAT, MaxSAT, SMT:大規模実証研究
- Abstract要約: 代表符号間の正確なQLDPC距離計算のためのSATおよびMaxSATに基づく定式化の体系的研究を行う。
正確なQLDPC距離計算に関するいくつかの一般的な直観を洗練する。
ブランチ・アンド・バウンドのMaxSATは、挑戦的なベンチマークで非サットコアのMaxSATを著しく上回っている。
- 参考スコア（独自算出の注目度）: 6.170087143925186
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: Exact distance computation for quantum LDPC (QLDPC) codes plays a central role in validating candidate fault-tolerant quantum-code constructions, yet the computational structure of this problem remains poorly understood. Despite substantial recent progress in QLDPC design, it remains unclear which algorithmic principles govern the practical scalability of exact distance computation and which classes of exact solvers are best suited to this task. To address these questions, we conduct a systematic study of SAT- and MaxSAT-based formulations for exact QLDPC distance computation across representative codes. We further compare these formulations against several established exact-distance approaches in order to better understand the algorithmic landscape of exact QLDPC distance computation. Our study challenges and refines several prevailing intuitions about exact QLDPC distance computation. First, despite the XOR-rich structure of QLDPC parity checks, practical scalability appears to be governed more by the handling of cardinality constraints and optimization bounds than by parity reasoning alone. Accordingly, XOR-aware reasoning does not provide a systematic advantage across our benchmark suite. Second, Brouwer-Zimmermann-style search, long regarded as the benchmark paradigm for exact distance computation in sparse classical codes, no longer maintains its traditional scalability advantage in the QLDPC setting. This finding challenges the expectation that techniques successful for sparse classical codes remain dominant for QLDPC codes. Third, substantial qualitative differences arise even among MaxSAT solvers themselves. Branch-and-bound MaxSAT significantly outperforms unsat-core-based MaxSAT on challenging benchmarks, demonstrating that solver architecture and optimization strategy play a decisive role in practical scalability.
- Abstract（参考訳）: 量子LDPC (QLDPC) 符号の厳密な距離計算は、予測フォールトトレラントな量子コード構成の検証において中心的な役割を果たすが、この問題の計算構造はよく分かっていない。
近年のQLDPC設計の進歩にもかかわらず、どのアルゴリズムの原理が正確な距離計算の実用的スケーラビリティを支配しているか、どの正確な解法がこの課題に最も適しているかは定かではない。
これらの問題に対処するために、代表符号間の正確なQLDPC距離計算のためのSATおよびMaxSATに基づく定式化の体系的研究を行う。
さらに、これらの定式化を、QLDPC距離計算のアルゴリズム的景観をよりよく理解するために、いくつかの確立された完全距離アプローチと比較する。
本研究は,正確なQLDPC距離計算に関するいくつかの一般的な直観に挑戦し,洗練するものである。
第一に、QLDPCパリティチェックのXORに富んだ構造にもかかわらず、実用的なスケーラビリティは、パリティ推論のみによるよりも、濃度制約と最適化境界の扱いによってより支配されているように思われる。
したがって、XORを意識した推論は、ベンチマークスイートに対して体系的な優位性を提供していません。
第二に、Brouwer-Zimmermannスタイルの検索は、昔からスパース古典符号の正確な距離計算のベンチマークパラダイムと考えられてきたが、QLDPC設定における従来のスケーラビリティの優位性は維持されていない。
この発見は、希少な古典符号で成功した技術がQLDPC符号で支配的であることへの期待に疑問を呈する。
第3に、MaxSAT解決者自身の間でも実質的な質的な違いが生じる。
ブランチ・アンド・バウンドのMaxSATは、挑戦的なベンチマークで非サットコアのMaxSATよりも大幅に優れており、ソルバアーキテクチャと最適化戦略が実用的なスケーラビリティにおいて決定的な役割を担っていることを実証している。
関連論文リスト
- Towards Tensor-Network SAT-Solvers for Quantum-Classical Workflows [1.1916225387199697]
HPC/QC統合システムは、古典的な高性能コンピューティングと量子プロセッサを組み合わせることを目的としている。
統合アーキテクチャは、QPUだけでは実装できない可観測性のような側面をサポートしなければならない。
論文 参考訳（メタデータ） (2026-08-03T10:36:30Z) - Evaluating the Formal Reasoning Capabilities of Large Language Models through Chomsky Hierarchy [62.32144504442516]
SOTA LLMが形式言語の構造的・階層的複雑性を把握できるかどうかは不明である。
ChomskyBench はchomsky Hierarchy のレンズを通して LLM を体系的に評価するためのベンチマークである。
ChomskyBenchは、各レベルで機能をテストするように設計された、言語認識と生成タスクの包括的なスイートで構成されている。
論文 参考訳（メタデータ） (2026-04-03T04:06:39Z) - ECCentric: An Empirical Analysis of Quantum Error Correction Codes [40.10865338207471]
本稿では,量子誤り訂正符号を評価するためのエンドツーエンドベンチマークフレームワークであるECCentricを紹介する。
我々は、QECの主要コードファミリーの、現実的で中期的な量子デバイスパラメータに対する最初の体系的なベンチマークを行う。
以上の結果から,Qubitシャットリングを用いたイオン閉じ込め型アーキテクチャが最も有望な短期プラットフォームであることが示唆された。
論文 参考訳（メタデータ） (2025-11-02T20:01:43Z) - Unlocking Symbol-Level Precoding Efficiency Through Tensor Equivariant Neural Network [84.22115118596741]
シンボルレベルのプリコーディングにおいて,推論の複雑さの低いエンドツーエンドディープラーニング(DL)フレームワークを提案する。
提案手法は,従来の手法よりも約80倍の高速化を実現しつつ,SLPの大幅な性能向上を達成できることを示す。
論文 参考訳（メタデータ） (2025-10-02T15:15:50Z) - Decoded Quantum Interferometry Requires Structure [1.121518046252855]
MAX-$k$-XOR-SATの典型例における復号量子干渉法(DQI)の性能について検討した。
DQI は、多くの標準的な符号のアンサンブルに対して、量子ワッサーシュタイン計量の下ではおよそリプシッツであることが証明されている。
論文 参考訳（メタデータ） (2025-09-18T00:51:36Z) - Extractors: QLDPC Architectures for Efficient Pauli-Based Computation [39.98920557126034]
本稿では,任意のQLDPCメモリをPauliベースの計算に適した計算ブロックに拡張できる新しいプリミティブを提案する。
特に、メモリ上でサポートされている任意の論理パウリ演算子は、1つの論理サイクルでフォールトトレラントに測定できる。
我々のアーキテクチャは並列論理的測定により普遍的な量子回路を実装できる。
論文 参考訳（メタデータ） (2025-03-13T14:07:40Z) - Performance of Parity QAOA for the Signed Max-Cut Problem [0.0]
パリティアーキテクチャにおける量子近似アルゴリズムの最適化性能(パリティQAOA)について検討する。
固定回路深さでのアルゴリズムの比較により、Parity QAOAはSWAPネットワークに基づく従来のQAOA実装よりも優れていることを示す。
論文 参考訳（メタデータ） (2024-09-23T08:00:03Z) - Provably Efficient UCB-type Algorithms For Learning Predictive State
Representations [55.00359893021461]
逐次決定問題は、予測状態表現(PSR)によってモデル化された低ランク構造が認められる場合、統計的に学習可能である
本稿では,推定モデルと実モデル間の全変動距離を上限とする新しいボーナス項を特徴とする,PSRに対する最初のUCB型アプローチを提案する。
PSRに対する既存のアプローチとは対照的に、UCB型アルゴリズムは計算的トラクタビリティ、最優先の準最適ポリシー、モデルの精度が保証される。
論文 参考訳（メタデータ） (2023-07-01T18:35:21Z) - Qubit efficient quantum algorithms for the vehicle routing problem on
NISQ processors [48.68474702382697]
時間窓付き車両ルーティング問題(VRPTW)は、ロジスティクス業界で直面する一般的な最適化問題である。
そこで本研究では,以前に導入した量子ビット符号化方式を用いて,バイナリ変数の数を削減した。
論文 参考訳（メタデータ） (2023-06-14T13:44:35Z) - End-to-end resource analysis for quantum interior point methods and portfolio optimization [63.4863637315163]
問題入力から問題出力までの完全な量子回路レベルのアルゴリズム記述を提供する。
アルゴリズムの実行に必要な論理量子ビットの数と非クリフォードTゲートの量/深さを報告する。
論文 参考訳（メタデータ） (2022-11-22T18:54:48Z) - Logical blocks for fault-tolerant topological quantum computation [55.41644538483948]
本稿では,プラットフォームに依存しない論理ゲート定義の必要性から,普遍的なフォールトトレラント論理の枠組みを提案する。
資源オーバーヘッドを改善するユニバーサル論理の新しいスキームについて検討する。
境界のない計算に好適な論理誤差率を動機として,新しい計算手法を提案する。
論文 参考訳（メタデータ） (2021-12-22T19:00:03Z) - Approximation Algorithms for Sparse Principal Component Analysis [57.5357874512594]
主成分分析(PCA)は、機械学習と統計学において広く使われている次元削減手法である。
スパース主成分分析(Sparse principal Component Analysis)と呼ばれる,スパース主成分負荷を求める様々な手法が提案されている。
本研究では,SPCA問題に対するしきい値の精度,時間,近似アルゴリズムを提案する。
論文 参考訳（メタデータ） (2020-06-23T04:25:36Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。