Grover search, amplitude amplification, and quantum counting all rely on the same reusable subroutine, a phase oracle, whose construction the algorithms literature takes as given: the classical predicate is assumed to be already encoded as a correct, resource-bounded circuit. We turn this assumption into a measured capability. QEncodeBench tasks large language models (LLMs) with encoding classical constraint problems as phase oracles and scores the generated circuits with an adversarially self-validated verifier that decides full solution-set equivalence up to a global phase, with ancillas restored and resource budgets enforced. Sampled basis-state tests, we show, systematically overestimate this ability. Measured this way, models separate sharply: code models without a reasoning mode solve essentially nothing, and enabling native reasoning on identical weights improves accuracy by an order of magnitude. The failures are overwhelmingly semantic rather than syntactic. Two architectures, a unit-verified constraint agent and a neuro-symbolic compilation pipeline, close most of the remaining gap by delegating correctness-critical composition to deterministic procedures. Ablations quantify the contribution of each component, and resource gating exposes an architecture-dependent trade-off between circuit width and depth. Finally, controlled difficulty escalation reveals architecture-specific responses to difficulty structure: different difficulty axes degrade different methods, while the neuro-symbolic pipeline passes every evaluated instance. Code and data are available at https://github.com/chexujun/QEncodeBench.
Xu-Jun Che, Han-Han Wu, Yu-Chen Yuan et al.· 0 citations
Poisson subsampling is the default sampler in differentially private optimization because its independence makes privacy amplification tractable. Practical systems, however, are moving toward structured participation: random allocation (balls-in-bins), per-epoch allocation, random check-ins, schemes widely believed to be at least as private as Poisson subsampling at the matched rate. We isolate the probabilistic mechanism behind this belief and delimit it exactly, for Gaussian mechanisms up to correlated-noise matrix mechanisms. (1) If the participation indicator vector is negatively associated (NA), then at every integer R\'enyi order $\alpha\ge2$, exactly at all finite parameters, its remove-direction R\'enyi divergence is dominated by that of the marginal-matched independent scheme. For fixed gradient sequences, this extends to the mechanism level whenever the noise strategy's Gram matrix is sign-balanced, an $O(t^2)$-checkable condition. (2) The integer-order restriction is essential. For random allocation with $k=1$, we prove a linear law for the R\'enyi-difference criterion: at large $t$, dominance reverses for every $\alpha<3/2$, including KL divergence, while the crossing order tends to $3/2$ independently of $\sigma$. (3) We also localize the known failure of rate-matched Poisson domination exactly: below $(1-q)^t$, the hockey-stick ordering reverses, so substituting the Poisson pair into composition machinery is unsound. An upper-tail argument yields a finite crossover $\gamma_\star$, connecting this threshold picture to the R\'enyi boundary at $3/2$. Together, these results give a substitution map for privacy accounting: when Poisson-based computations remain sound for structured participation, where they fail, and what sound alternatives cost in deployment.
The results indicate that diffusion transformers carry more concept-level information than current attribution methods recover, and that much of it is lost on the way to the mask rather than absent from the model.
Rajatsubhra Chakraborty, Xu-Jun Che, Ritabrata Chakraborty et al.· 0 citations
The exact DP constant is pin down for the two that carry the practical weight, counterfactual memorization and adaptive extraction, and it is shown that they do not control each other.
On the NPLIB1 benchmark, MARLIN is the strongest method evaluated without a ground-truth formula across exact-match accuracy, structural distance, and fingerprint similarity, and it recovers the correct molecular formula as a byproduct about as often as a dedicated predictor without ever using one.
Xujun Che, Xiuxia Du, Depeng Xu· 0 citations
We use cookies to run the site and, with your consent, for analytics and to show ads.
See our Cookie Policy.
