From Leaves to Clusters: Depth-Efficient SAT-Oracle Synthesis Based on the HRSE Model

• URL: http://arxiv.org/abs/2607.11401v1
• Date: Mon, 13 Jul 2026 11:08:54 GMT
• Title: From Leaves to Clusters: Depth-Efficient SAT-Oracle Synthesis Based on the HRSE Model
• Abstract summary: Clustered Synthesis Tree (CST) is a deep synthesis framework for SAT oracles.<n>CST group the individual clause leaves of a hierarchical synthesis tree into clusters, exposing instance-dependent clause-level parallelism.<n>CST reduces the oracle's circuit depth over the state-of-the-art (SOTA) baseline by $68%$--$94%$ on the standard SATLIB benchmarks.
• Score: 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\%$.

Related papers

• ECHO: Early-layer Collaborative Hierarchical Orchestration with Bonus Logits in Speculative Decoding [60.34475274870224]
  ECHO is a hierarchical dual-loop framework that exploits the functional asymmetry between LLM layers.<n>Within the inner loop, early-layer bonus logits drive rapid, multi-step draft-tree exploration at a minimal cost.<n>ECHO significantly boosts mean accepted tokens and achieves a 2.4$times$ to 2.9$times$ speedup.
  arXiv  Detail & Related papers  (2026-09-15T14:21:33Z)
• Chain-of-Thought Shows the Path to a Tree: Realizing Branching Complexity [22.2188018390594]
  Chain of Thought (CoT) lifts the expressive ceiling of bounded-depth Transformers.<n>We give CoT realizations of depth-first search (DFS) and of Dijkstra algorithm.<n>We give independent constructions for both measures on the path representation.
  arXiv  Detail & Related papers  (2026-08-12T06:57:08Z)
• SILAGE: Memory-Efficient, Full-Gradient-Free Nonconvex Optimization for Nested Finite Sums [51.49970814177172]
  Empirical risk on datasets naturally exhibits similarities in $N=nm$ total samples.<n>We provide an analysis that avoids pessimistic convergence analysis.<n>Our results improve existing state-of-the-art regimes.
  arXiv  Detail & Related papers  (2026-06-14T14:11:07Z)
• Scalable Deep Subspace Clustering Network [6.321283533425182]
  We propose SDSNet, a deep subspace clustering framework that achieves $mathcalO(n)$ complexity through landmark-based approximation.<n>We show that SDSNet achieves comparable clustering quality to state-of-the-art methods with significantly improved computational efficiency.
  arXiv  Detail & Related papers  (2025-12-24T21:46:38Z)
• Learning-Augmented Hierarchical Clustering [29.438861266606573]
  We consider the problem of hierarchical clustering given auxiliary information from natural oracles.<n>We show that a splitting oracle enables algorithms to outperform standard HC approaches.<n>Our approaches extend to sublinear settings, in which we show new streaming and PRAM algorithms with improved guarantees.
  arXiv  Detail & Related papers  (2025-06-05T18:22:40Z)
• Revisiting Instance-Optimal Cluster Recovery in the Labeled Stochastic Block Model [85.51611950757643]
  We propose IAC (Instance-Adaptive Clustering), the first algorithm whose performance matches the instance-specific lower bounds both in expectation and with high probability.<n>IAC maintains an overall computational complexity of $ mathcalO(n, textpolylog(n) $, making it scalable and practical for large-scale problems.
  arXiv  Detail & Related papers  (2023-06-18T08:46:06Z)
• Matching Pursuit Based Scheduling for Over-the-Air Federated Learning [67.59503935237676]
  This paper develops a class of low-complexity device scheduling algorithms for over-the-air learning via the method of federated learning. Compared to the state-of-the-art proposed scheme, the proposed scheme poses a drastically lower efficiency system. The efficiency of the proposed scheme is confirmed via experiments on the CIFAR dataset.
  arXiv  Detail & Related papers  (2022-06-14T08:14:14Z)
• An Information-theoretic Perspective of Hierarchical Clustering [30.896561720088954]
  A cost function for hierarchical clustering was introduced by Dasgupta citedasgupta2016cost. In this paper, we investigate hierarchical clustering from the emphinformation-theoretic perspective and formulate a new objective function.
  arXiv  Detail & Related papers  (2021-08-13T03:03:56Z)
• Exact and Approximate Hierarchical Clustering Using A* [51.187990314731344]
  We introduce a new approach based on A* search for clustering. We overcome the prohibitively large search space by combining A* with a novel emphtrellis data structure. We empirically demonstrate that our method achieves substantially higher quality results than baselines for a particle physics use case and other clustering benchmarks.
  arXiv  Detail & Related papers  (2021-04-14T18:15:27Z)
• Computationally efficient sparse clustering [67.95910835079825]
  We provide a finite sample analysis of a new clustering algorithm based on PCA. We show that it achieves the minimax optimal misclustering rate in the regime $|theta infty$.
  arXiv  Detail & Related papers  (2020-05-21T17:51:30Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.