論文の概要: From Leaves to Clusters: Depth-Efficient SAT-Oracle Synthesis Based on the HRSE Model
- arxiv url: http://arxiv.org/abs/2607.11401v1
- Date: Mon, 13 Jul 2026 11:08:54 GMT
- ステータス: 翻訳完了
- システム内更新日: 2026-07-14 17:47:21.445512
- Title: From Leaves to Clusters: Depth-Efficient SAT-Oracle Synthesis Based on the HRSE Model
- Title（参考訳）: 葉からクラスターへ:HRSEモデルに基づく深部効率的なSAT-Oracle合成
- Abstract要約: クラスタ化合成木(CST)はSATオーラクルのための深層合成フレームワークである。
CST は階層的な合成木の個々の節をクラスタに分類し、インスタンス依存の節レベルの並列性を公開する。
CSTは、標準的なSATLIBベンチマークにおいて、最先端(SOTA)ベースライン上のオラクルの回路深さを68%$--94%$で削減する。
- 参考スコア（独自算出の注目度）: 11.402462649149918
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: Quantum oracles are a common building block of many quantum algorithms, where circuit depth is a primary cost that directly affects overall performance. Synthesizing oracles for SAT (CNF) formulas under a limited ancilla budget, however, tends to yield deep circuits, as existing methods underexploit clause-level parallelism. In this work, we present the Clustered Synthesis Tree (CST), a depth-oriented framework whose core idea is to group the individual clause leaves of a hierarchical synthesis tree into clusters, exposing instance-dependent clause-level parallelism under ancilla constraints. CST comprises three parts: the clause-grouping problem it induces, which we formulate as an ancilla-constrained scheduling problem and prove NP-complete in general, is addressed by SeedGrow, a polynomial-time $O(m^2 k)$ heuristic; ClausePack, a reversible oracle that evaluates a cluster's clauses in parallel at only a logarithmic-depth overhead; and CST-Map, which compiles the clustered tree into an executable SAT-oracle. On random $4$-CNF under the same ancilla budgets, CST reduces the oracle's circuit depth over the state-of-the-art (SOTA) baseline by $68\%$--$94\%$. On the standard SATLIB benchmarks, CST achieves about a $2.6\times$--$43.2\times$ reduction over the SOTA baseline, with the largest gains under dense variable sharing, and matches the baseline's maximum-budget depth using only $3.7\%$--$20\%$ of its ancilla qubits. A Grover-search resource estimate shows the advantage carries over to the full algorithm, reducing total circuit depth by $70\%$--$89\%$.
- Abstract（参考訳）: 量子オラクルは多くの量子アルゴリズムの共通構築ブロックであり、回路深さは全体的な性能に直接影響を与える主要なコストである。
しかし、SAT (CNF) の公式を限られたアンシラ予算で合成すると、既存の方法では節レベルの並列性が不足しているため、深い回路が得られる傾向にある。
本稿では,階層型合成木の個々の節の葉をクラスタに分類し,インスタンス依存の節レベルの並列性をアシラ制約下で露呈する,深層指向のフレームワークであるClustered Synthesis Tree(CST)を提案する。
CST は 3 つの部分から構成される: 制約付きスケジューリング問題として定式化され、一般にNP完全であることが証明される節群問題。SeedGrow は多項式時間 $O(m^2 k)$ ヒューリスティック、ClausPack は対数-深さのオーバーヘッドでクラスタの節を並列に評価する可逆的なオラクル、CST-Map はクラスタツリーを実行可能なSAT-oracle にコンパイルする。
標準的なSATLIBベンチマークでは、CSTは2.6\times$--43.2\times$-43.2\times$でSOTAベースラインを下げ、密度変数共有で最大の利得を達成し、ベースラインの最大予算深度をわずか3.7\%$-20\%で一致させる。
Grover-search のリソース推定では、その利点が全アルゴリズムに受け継がれ、総回路深さが $70\%$--89\%$ になる。
関連論文リスト
- ECHO: Early-layer Collaborative Hierarchical Orchestration with Bonus Logits in Speculative Decoding [60.34475274870224]
ECHOは、LLM層間の機能的非対称性を利用する階層的なデュアルループフレームワークである。
インナーループ内では、アーリーレイヤのボーナスロジットは、最小限のコストで、高速で多段階のドラフトツリー探索を駆動する。
ECHOは平均的なトークンを著しく増加させ、2.4$times$2.9$times$スピードアップを達成する。
論文 参考訳（メタデータ） (2026-09-15T14:21:33Z) - Chain-of-Thought Shows the Path to a Tree: Realizing Branching Complexity [22.2188018390594]
思考の連鎖(CoT)は、有界深度変換器の表現的天井を持ち上げる。
深度優先探索(DFS)とDijkstraアルゴリズムのCoT実現について述べる。
経路表現の両測度について独立的に構成する。
論文 参考訳（メタデータ） (2026-08-12T06:57:08Z) - SILAGE: Memory-Efficient, Full-Gradient-Free Nonconvex Optimization for Nested Finite Sums [51.49970814177172]
データセットに対する経験的リスクは、自然に$N=nm$全サンプルに類似性を示す。
我々は悲観的な収束分析を避ける分析を提供する。
我々の成果は、既存の最先端の体制を改善した。
論文 参考訳（メタデータ） (2026-06-14T14:11:07Z) - Scalable Deep Subspace Clustering Network [6.321283533425182]
我々はランドマークベースの近似により$mathcalO(n)$複雑性を実現するディープサブスペースクラスタリングフレームワークであるSDSNetを提案する。
本研究では,SDSNetのクラスタリング品質を最先端手法と同等に向上し,計算効率が大幅に向上したことを示す。
論文 参考訳（メタデータ） (2025-12-24T21:46:38Z) - Learning-Augmented Hierarchical Clustering [29.438861266606573]
自然のオラクルから補助情報を得た階層的クラスタリングの問題を考察する。
分割オラクルは、アルゴリズムが標準のHCアプローチより優れていることを示す。
我々のアプローチはサブ線形設定にまで拡張され、保証を改善した新しいストリーミングとPRAMアルゴリズムが示されます。
論文 参考訳（メタデータ） (2025-06-05T18:22:40Z) - Revisiting Instance-Optimal Cluster Recovery in the Labeled Stochastic Block Model [85.51611950757643]
IAC (Instance-Adaptive Clustering, インスタンス適応クラスタリング) を提案する。
IACは$ MathcalO(n, textpolylog(n) $の計算複雑性を維持しており、大規模問題に対してスケーラブルで実用的なものである。
論文 参考訳（メタデータ） (2023-06-18T08:46:06Z) - Matching Pursuit Based Scheduling for Over-the-Air Federated Learning [67.59503935237676]
本稿では,フェデレートラーニング手法を用いて,オーバー・ザ・エアラーニングのための低複雑さデバイススケジューリングアルゴリズムのクラスを開発する。
最先端の提案方式と比較すると,提案方式は極めて低効率なシステムである。
提案手法の有効性は,CIFARデータセットを用いた実験により確認した。
論文 参考訳（メタデータ） (2022-06-14T08:14:14Z) - An Information-theoretic Perspective of Hierarchical Clustering [30.896561720088954]
階層クラスタリングのコスト関数はDasgupta citedasgupta 2016 Costによって導入された。
本稿では,階層的クラスタリングをインセンフィス理論の観点から検討し,新たな目的関数を定式化する。
論文 参考訳（メタデータ） (2021-08-13T03:03:56Z) - Exact and Approximate Hierarchical Clustering Using A* [51.187990314731344]
クラスタリングのA*探索に基づく新しいアプローチを紹介します。
A*と新しいエンフォレリスデータ構造を組み合わせることで、禁止的に大きな検索空間を克服します。
実験により,本手法は粒子物理利用事例や他のクラスタリングベンチマークにおいて,ベースラインよりもかなり高品質な結果が得られることを示した。
論文 参考訳（メタデータ） (2021-04-14T18:15:27Z) - Computationally efficient sparse clustering [67.95910835079825]
我々はPCAに基づく新しいクラスタリングアルゴリズムの有限サンプル解析を行う。
ここでは,ミニマックス最適誤クラスタ化率を,体制$|theta infty$で達成することを示す。
論文 参考訳（メタデータ） (2020-05-21T17:51:30Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。