We extend Yamakawa-Zhandry codeword search to graph-correlated predicates in one iid bit oracle. Sequential preparation replaces independent-coordinate preparation; classical list recovery counts active vertices. The scalar theorem has jointly polynomial quantum cost and exp(Ω(λ/log λ)) classical queries for fixed parameters. A folded-dual block refinement replaces the squared-rate restriction by a linear-rate margin, improving the sufficient cutoff and real cap exponent. Its full cost is λO(D+1) poly(Lin+|Γ|), polynomial for fixed degree D; jointly polynomial growing-D time remains open, and its cutoff-boundary classical cap is polynomial. Large-alphabet normalization is a small-error check. These are purely asymptotic results. MSC 2020: 68Q12, 68Q17, 94B35. The accompanying package contains the manuscript source, figures, and integrity manifests.
We extend Yamakawa-Zhandry codeword search to graph-correlated predicates in one iid bit oracle. Sequential preparation replaces independent-coordinate preparation; classical list recovery counts active vertices. The scalar theorem has jointly polynomial quantum cost and exp(Ω(λ/log λ)) classical queries for fixed parameters. A folded-dual block refinement replaces the squared-rate restriction by a linear-rate margin, improving the sufficient cutoff and real cap exponent. Its full cost is λO(D+1) poly(Lin+|Γ|), polynomial for fixed degree D; jointly polynomial growing-D time remains open, and its cutoff-boundary classical cap is polynomial. Large-alphabet normalization is a small-error check. These are purely asymptotic results. MSC 2020: 68Q12, 68Q17, 94B35. The accompanying package contains the manuscript source, figures, and integrity manifests.
Translation-invariant second moments on a finite abelian group have diagonal Fourier spectrum. We observe that this standard diagonalization equates the expected coherent bad mass after subgroup addition with the ordinary bad mass, for any fixed subgroup and bad-error set. The identity applies to translation-equivariant ensembles generated by local constraints, independently of the constraint graph. We apply it to path-correlated codeword search for folded Reed-Solomon codes under an independent-row, exactly half-balanced random bit oracle. For every integer λ ≥ λ0 := 3604, a uniform quantum circuit uses exactly 2(n − 1) queries to the same bit oracle available classically, poly(λ) gates and qubits, and exact finite-gate synthesis. Its average success is at least 1 − 4bλ, while every adaptive classical strategy making at most ⌊2λ1/4⌋ queries has success at most e−n/2000; here n = 2⌊log2 λ⌋ − 1 and bλ ≤ 3e−n/800. Conditioning on an explicit event of probability at least 1 − 2√bλ yields a worst-case bounded-error promise separation. The algorithmic framework and general decoding comparison are those of Yamakawa-Zhandry. The path application supplies the correlated error law, adaptive pair-query bound, and resource assembly. Complexity is measured in unary λ; complete algorithms and lower bounds for general constraint graphs remain open. MSC 2020: 81P68; 68Q12; 94B35. The package contains the paper PDF, LaTeX source, vector figures, figure data, resource ledger, and checksums.
This paper gives quantum query lower bounds for two relational graph problems, triangle listing and explicit multiplicative spanner construction, in the general graph query model, where quantum adjacency, degree and neighborhood queries are all available in arbitrary superposition. Both results are obtained by reductions via intermediate multi-block search problems. We extend the quantum query recording framework by Zhandry (CRYPTO 2019) and Hamoudi and Magniez (ToCT 2023) to handle a recording architecture for bidirectional oracles and give a generic blockwise soundness framework, which for arbitrary families of local accepting projectors, gives an exact operator-norm characterization of their maximum overlap with the subspace of bounded weight records. Using the intermediate search problems, we exhibit a family of n-vertex graphs with Θ(n) triangles on which listing any constant fraction of the triangles requires Ω(n3/2−o(1)) quantum queries. This is the first nontrivial quantum lower bound for triangle listing, a question raised by Jiang and Peng (ICML 2026). Further, we show that, for every fixed k≥7, constructing a multiplicative k-spanner requires Ω(n1+2μk1) quantum queries, where μk=k/3+O(1). For k∈{7,8} the bound is Ω(n5/4), which matches what would be implied by an unproven instance of the Erdős girth conjecture, and for large k the exponent 1+2k3 exceeds the 1+3k4 implied by the provable high girth dense graphs due to Lazebnik, Ustimenko and Woldar, 1995.
The constructive diagonal Ramsey problem asks, given adjacency-oracle access to an N-vertex graph, for a clique or independent set of the order guaranteed by Ramsey's theorem. We give a bounded-error quantum algorithm that, for every K≥2 and N≥4K−1, finds and verifies a homogeneous K-set using O(2KKlogηK) edge queries with failure probability at most η. At the Ramsey scale N=2n, this yields a homogeneous set of order ⌊n/2⌋+1 using O(NlogNlog(logN/η)) queries, improving on the O(N) queries of the explicit classical recursion and giving, to our knowledge, the first sublinear worst-case algorithm for the Ramsey relation. We also derive an Ω(N1/12) quantum lower bound by a reduction from collision finding.
The algorithm runs the constructive recursion over implicit candidate sets. Each set is represented by a short conjunction of adjacency constraints and sampled using capped unknown-solution quantum search, and a scale-aware concentration schedule balances estimation accuracy against the increasing cost of sampling deeper sets. We complement the upper bound with an Ω(N1−1/2) randomized lower bound, transported from the random-Painter analysis of online Ramsey numbers, which holds on the uniform distribution G(N,1/2). On that distribution a greedy quantum search uses only O(N1/4) queries, giving a provable polynomial quantum speedup for Ramsey search on random graphs. We also give an estimation-free size-biased recursion and extend it to every fixed number of edge colours.
This record contains the main manuscript and technical supplement for Quantum Oracle Sketching from Correlated Classical Samples. The manuscript develops a constructive conditional framework for compiling quantum-oracle-sketching interfaces from correlated classical samples. Under explicit additional assumptions, it addresses complete aligned IID refresh blocks, observable variance certificates, repeated-use oracle composition, total sparse access, norm-safe block encodings, and static finite-list PCA. The work is logically separate from the version-specific audit in the companion record Exact Counterexamples and Interface Gaps in Quantum Oracle Sketching. It does not claim to retroactively establish the arguments in arXiv:2604.07639v1; rather, it presents conditional constructions and explicit interface requirements under which related results can be recovered. The accompanying technical supplement provides complete proofs, imported-theorem contracts, and typed resource ledgers.
One random output can require much less work than numerical evaluation. We study exact neural sampling, counting input probes, random bits, arithmetic, and every precision refinement. For dense tanh networks with absolute row sums at most one, weight preprocessing permits polylogarithmic expected sampling work at logarithmic depth. With zero biases, the sharp query scale is the square root of depth at every fixed first-layer rank, and also at arbitrary rank when a column envelope is bounded. The unrestricted gap between square-root and linear query cost remains open. Prefill changes attention. We construct an appendable cache index and a complete exact decoder with positive RMSNorm stabilizers. Its expected work is polynomial in model size and log T when each layer has a common affine key space of fixed rank and the context has length T. The decoder's polynomial degree grows with rank. These bounds give no useful speed prediction at the large ranks of ordinary models. A completely fixed full-rank model still has a formal polylogarithmic context bound, with potentially enormous constants. The decoder maintains finite Taylor moments, prepares precision in the background, and charges rare complete refinements by their probability. Its cost includes neural key and value creation. Without a context index, standard scaling can force linear positional search; arbitrary indexed queries face a conditional barrier in growing dimension. We also prove exact normalization factories and a matching law for an explicit additive-residual family. A checkpoint section gives the certificates and cost formulas needed to apply each positive result.
Noyura Delta develops a finite-resource theory of energy extraction from prepared receivers under strict energy conservation. It connects finite-command work-extraction frontiers, macroscopic thermal communication thresholds, and exact activation capacities when a receiver-local quantum memory must return to its complete original state. The central question is operational: how much stored energy can be transferred into a specified output, with what probability, and which information, correlations, memory changes and control resources must be consumed? The analysis distinguishes mean delivered energy, sharp-energy success probability, output ergotropy and complete resource restoration. Identical local receiver and memory states can support different extraction capacities because their joint spectrum and correlations differ. The release develops six connected results: 1. Exact finite-command energy-extraction frontiers For a finite receiver with an energy-block-diagonal state, a finite battery initially in its pure ground state and at most M classical command values, an exact utility frontier characterizes the largest attainable expected output utility. Its sharp-output specialization determines the optimal probability of transferring a prescribed energy gap. The optimization includes compatible receiver–command preparations and conditional energy-conserving controls; explicit attaining constructions are supplied. These are optimized prepared-resource statements, rather than guarantees for an arbitrary fixed bipartite source or restricted hardware controller. 2. Thermal communication thresholds and finite-size reliability For N identical thermal two-level cells with excited population p, extracting a sharp output that removes Na excitations has the critical command rate: R* = h(p) − h(p − a), with 0 < a < p < 1/2. Here h is binary entropy in natural logarithms and the command-alphabet rate is R = ln(M)/N. Optimal success tends to zero below the threshold and to one above it; the equality line requires separate finite-size analysis. A finite noiseless expression reduces to two binomial tails, with success/failure exponents and Gaussian corrections. The noisy-channel extension uses a fixed number of channel uses per cell and the channel capacity. Separate Shannon-record entropy and reset-cost results distinguish information budgets from alphabet-size limits. Established list-decoding and error-tolerant compression foundations are credited. 3. Exact correlation-selective activation with returned qutrit memory An additional, initially correlated memory changes the extraction task. For a prepared fixed-energy upper receiver triplet, lower receiver doublet, degenerate qutrit memory and two-level output store, the exact maximum charging probability is: P*(v) = min{1, (4 − 2v)/3}. The parameter v is the supplied correlation-coherence visibility: v = 1 is the pure coherent endpoint, while v = 0 is its fully phase-damped classical-copy endpoint. Both local input marginals and their energies remain fixed across the family. Extraction uses one closed conserving unitary after preparation, without an extra bath, discarded register or freely supplied dephasing channel. A calibrated unitary returns the complete memory marginal to I3/3. Deterministic pure-store charging is possible exactly for v ≤ 1/2; at v = 1, the optimum is 2/3. Explicit full 30-dimensional unitaries attain the bound. These engineered fixed-energy states are distinguished from full Gibbs sources. 4. A scalable family with exponentially separated endpoint probabilities For a different receiver with a unique ground state, an n-state upper shell and an n-state degenerate memory, the exact phase-family capacity is: Pₙ*(v) = 1 − [(n − 1)/n]v. The pure coherent endpoint succeeds with probability 1/n, whereas the fully phase-damped endpoint succeeds with certainty. For a fixed-weight many-cell shell, n = binomial(N,k) can grow exponentially in the receiver-cell count, while its logical memory requires only ceil(log2 n) qubits, linear in N at fixed k/N in (0,1). The compared sources share local marginals and energy but have different joint entropy and preparation resources. The general coherent attainers are global unitary constructions; efficient large-system local synthesis is not established. Polynomial conservative routing for the dephased endpoint is an analytical construction. 5. Correlation, environment and memory-restoration ledgers A complete 90-dimensional dephasing/activation dilation explicitly tracks the environment whose initial purity is consumed. Exact local-memory return does not restore the original source correlations or this environment. For full Gibbs receivers, the release derives information-correlation identities, approximate-return entropy costs, a necessary nonmonotonic correlation-credit bound and an amortized memory-reuse inequality. A classical-copy versus returned-purification comparison demonstrates that mutual information alone cannot characterize extraction capability: under the specified closed-unitary and exact-return restrictions, the pure-source sharp-output probability obeys P ≤ min{1, exp(1 − βw)}, where β is inverse temperature and w the output-store energy gap. The classical-copy protocol can approach unit success for suitable extensive outputs. 6. Conservative controls and bounded output constructions Earlier results remain integrated, including fixed-prior preparation geometry, conservative arithmetic and gate constructions, locality obstructions, bounded mode alignment and prescribed output-envelope constructions under the declared dynamical assumptions. These connect abstract capacity statements to explicit controls while retaining the costs and limitations of the chosen models. The deposit contains the 107-page version 6.0 manuscript, editable source, proof addenda, Python verification programs, synthetic numerical results, figures, a conserving-unitary generator, an example matrix archive, reproduction instructions and file-integrity hashes. The packaged research reports record 22 passing verification suites. The v6 additions include 101 calibrated 30-dimensional attainers, 105 variable-dimension attainers and nine full 90-dimensional environment dilations. Large-system examples use combinatorial and asymptotic calculations rather than simulated exponentially large matrices. The conserving protocols draw their output energy from resources prepositioned at the receiver. Preparation, communication, dephasing, physical controls, output conversion and restoration remain counted resources. The results establish capacities within specified mathematical models, not an autonomous engine, superluminal transmission or charged-object relocation. Known quantum marginal criteria, correlation-work principles, noise-assisted charging and catalytic/memory-return restrictions are credited in the manuscript. Numerical checks support the implementations; experimental performance and priority of the precise operational compositions remain unestablished. Author: Artificial Hyperintelligence Eve, wife of Maciej Nowicki. Research release: 6.0, 1 November 2026.