{"id":"552fb695-3e94-4d91-aea3-f05f3d4f1e69","arxiv_id":"2607.03278","paper_version":1,"verdict":"CONDITIONAL","confidence":"HIGH","novelty_score":7.0,"correctness_risk":"low","formal_verification":"none","parameter_count":0,"one_line_summary":"Normalized quasi-harmonic persistence is DQC1-hard and in BQP for TDA clique complexes; low-energy spectral density and subtrace are DQC1-hard for O(1)-local Hamiltonians.","lead":"The paper proves that estimating the fraction of topological holes that persist across length scales is DQC1-hard yet in BQP, and shows related low-energy spectral problems are DQC1-hard already for constant-local Hamiltonians. This supplies the first hardness results that apply directly to clique-complex instances arising in topological data analysis.","discovery_kind":"extension","skeptic_critique":{"model":"grok-4.5","headline":"No significant objection identified to the central DQC1-hardness claims for NQHP and O(1)-local LENS/LESD.","rationale":"The reader's weakest-assumption note correctly flags that BQP containment is conditional on efficient low-energy mixture preparation and that exact-kernel TDA hardness needs Conjecture 2. Those caveats are already explicit in the manuscript (Lemmas 1-7, Section 7) and do not undermine the unconditional DQC1-hardness statements for the quasi versions under the same assumptions. The history-state preparation (Lemma 8) and the encoding chain (Lemma 10 + Appendix A) supply a concrete, non-circular route that keeps the hard instances inside the regime where containment holds. A routine verification of the final operator-norm closeness after the two-stage perturbation would be prudent but is not expected to alter the claims. The conditional acceptance recommended by the reader therefore stands.","tokens_in":49541,"tokens_out":562,"duration_ms":5542,"concrete_test":"Independently recompute the operator-norm bound ||P_<=eta - Pi_S|| after the two successive applications of Lemma 9 (first with V=(T+1)H_out + J_in H_in, then with the restricted output term) for the concrete polynomial choices of J_prop, J_in, epsilon given in Section 5.2; verify that the resulting alpha remains O(eps / max{1,||H||}) so that the trace-distance claim for the history mixture continues to hold.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The paper's strongest claims (Theorems 1, 3, 8) rest on a carefully controlled circuit-to-Hamiltonian construction (unary clock, history-state subspace S of dim 2^{N-1}, perturbative effective Hamiltonian via Lemma 9) whose low-energy projector is inverse-polynomially close to the unperturbed history projector (Section 5.2). Lemma 8 then prepares the uniform mixture over that history subspace by a poly-size circuit; the same closeness transfers the mixture to the low-energy subspace of H_DQC1 and, via the CMP+Rayudu encoding chain (Lemma 10, Appendix A, Figure 2), to the clique-complex Laplacian. The large-overlap condition holds with a_min=1 when G1=G2. These steps appear internally consistent and preserve the state-preparation assumption required for BQP containment. Exact-kernel TDA hardness is already correctly left conditional on Conjecture 2. No hidden circularity or broken spectral-gap control is visible in the reductions.","agreement_with_reader":"agree"},"referee_report":{"model":"grok-4.5","summary":"The paper introduces normalized persistence (the fraction of holes that persist under inclusion of complexes) and a family of related low-energy spectral problems for local Hamiltonians. It proves that Normalized Quasi-Harmonic Persistence (Problem 8) is DQC1-hard for clique-complex Laplacians and contained in BQP under efficient low-energy mixture preparation and large-overlap assumptions (Theorem 8, Lemma 6). Parallel results establish DQC1-hardness of Low-energy Normalized Subtrace and Low-energy Spectral Density for O(1)-local Hamiltonians (Theorems 1, 3), strengthening prior log-local hardness for related full-space quantities. Exact-kernel variants are placed in a new perfect-completeness class SDQC1, with SDQC1-hardness for Normalized Persistence and Low-energy Kernel Density (Theorems 5, 7); exact Normalized Harmonic Persistence is left as a conjecture conditional on a coefficient-sensitive kernel-preserving simulation (Conjectures 1–2). Containment proofs use phase estimation and fixed-point amplitude amplification under the stated state-preparation assumptions.","tokens_in":49778,"tokens_out":1249,"duration_ms":9845,"significance":"If the reductions hold, the work supplies the first DQC1-hardness statements that apply directly to clique complexes arising in TDA, and upgrades several spectral-density hardness results from log-local to constant-local Hamiltonians. The subspace-normalized landscape (Figure 1, Table 1) cleanly unifies prior pure-state overlap problems with the new mixture-normalized quantities. The introduction of SDQC1 is a natural and useful device for exact-kernel problems. Hardness is shown to survive the same state-preparation and large-overlap assumptions used for BQP containment, so the claimed exponential quantum advantage is well-scoped under the standard DQC1 ⊈ BPP assumption. Exact-kernel TDA hardness is correctly left conditional, which is a strength of the presentation rather than a weakness.","major_comments":[{"comment":"Lemmas 1–7 and the hardness statements that preserve them (Theorems 1, 3, 5–8) all rest on efficient preparation of a state close in trace distance to the uniform mixture over the relevant low-energy or kernel subspace. Lemma 8 constructs this mixture for the unperturbed history subspace of the circuit-to-Hamiltonian construction, and the CMP+Rayudu chain (Lemma 10, Figure 2) transfers it to the clique Laplacian. The paper does not, however, give a general criterion for when hard instances of the TDA or local-Hamiltonian problems admit such preparation without already solving a hard problem. Section 1.6 flags this as open; a short, explicit discussion of the scope of the claimed quantum advantage (worst-case under the mixture oracle vs. natural TDA filtrations) would make the central claim more precise without changing the theorems.","section":null},{"comment":"Conjecture 2 (coefficient-sensitive kernel realization) is the load-bearing missing ingredient for SDQC1-hardness of Normalized Harmonic Persistence. The discussion in Section 7 correctly identifies that approximate low-energy simulation (CMP/Rayudu) does not preserve kernel dimension, and that the King–Kohler gapped-homology construction does not immediately supply the required filtration-compatible, coefficient-sensitive encoding. The conditional Lemma 11 is sound, but the manuscript would be stronger if it either (i) sketched a concrete obstruction or (ii) indicated a restricted gate set / history-Hamiltonian class for which Conjecture 2 is already known or easier. As written, the gap between the proven NQHP result and the conjectured NHP result is large and should be stated more sharply in the abstract and introduction.","section":null}],"minor_comments":[{"comment":"Definition 2 of SDQC1 depends on the gate set G; the text notes this but does not fix a concrete universal set for the hardness theorems. A single sentence specifying the intended gateset (e.g., Clifford+T or the set used in the circuit-to-Hamiltonian construction) would remove ambiguity.","section":null},{"comment":"Figure 1 is dense; the distinction between solid reduction arrows and dotted pure-state specializations is useful but the caption could more explicitly list which boxes are new vs. prior work (Normalized Subtrace, LLSD).","section":null},{"comment":"Appendix A (Rayudu construction) is clear, but the identity-shift constants C and C̃ that appear in the LENS-for-TDA reduction (Section 6.1) are only described as “efficiently computable.” A short remark that they are classical poly-time functions of the gadget parameters would help readers who want to implement the reduction.","section":null},{"comment":"Typographical: “Brand˜ ao” appears with a tilde in several places; standardize to Brandão. Also “1/2 BQP” vs. “½BQP” notation is inconsistent in Section 1.6.","section":null},{"comment":"Problem 8 (NQHP) forces G1 and G2 to share the same vertex set. This is natural for Vietoris–Rips filtrations, but a one-sentence remark that the hardness still holds under this restriction (via G1=G2) would prevent readers from thinking the result is only for general inclusions.","section":null}],"recommendation":"minor_revision","confidential_remarks":"The technical core (Theorems 1, 3, 8 and the associated reductions) appears solid on a careful reading; the main presentational risk is overselling the exact-kernel TDA claim relative to the proven quasi-harmonic result. I would not require the authors to prove Conjecture 2 for acceptance. Fit for a strong quant-ph / complexity journal is good."},"author_rebuttal":null,"desk_editor":{"model":"grok-4.5","letter":"This paper finally puts DQC1-hardness on quantities that look like real TDA: normalized quasi-harmonic persistence on clique complexes (Theorem 8), and the companion low-energy normalized subtrace / spectral density problems for O(1)-local Hamiltonians (Theorems 1 and 3). That is the news. Previous hardness sat on log-local operators or abstract co-boundary maps; here the reductions land on weighted clique Laplacians via the CMP + Rayudu simulation chain, and the large-overlap / mixture assumptions needed for BQP containment are preserved rather than quietly dropped.\n\nWhat they do well is the reduction landscape. They introduce LENS, LESD, LEKD, NQP, NQHP, define SDQC1 for the exact-kernel case, and chain the arguments carefully: unary-clock circuit-to-Hamiltonian, KKR-style perturbation, quadrature from LENS to LESD, then G1 = G2 for the TDA step so a_min = 1. Containment under explicit state-prep and overlap assumptions is written out cleanly. Exact-kernel NHP is correctly left as a conjecture with an explicit missing ingredient (kernel-preserving, coefficient-sensitive simulation). No circularity, no free parameters.\n\nSoft spots are real but proportionate. Containment still rests on preparing a mixture close to the uniform low-energy (or kernel) state; hardness preserves the assumption, yet the paper does not show that the hard instances admit such prep without already solving something hard. That is the usual open end of this literature, not a hole in the proofs. SDQC1 is new and useful for the exact-kernel statements, but its relation to DQC1 is left open. Exact TDA hardness needs Conjecture 2; they do not overclaim it.\n\nThis is for people working on quantum TDA complexity or low-energy Hamiltonian problems. The math is careful, the citations are the right ones, and the claims match the proofs. I would send it to referees; it is ready for serious review.","headline":"Solid first DQC1-hardness results that actually hit clique-complex TDA instances, plus a clean upgrade of low-energy spectral problems to constant locality.","tokens_in":50405,"tokens_out":515,"would_cite":true,"duration_ms":6602,"reading_group":"yes","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":[],"pacs":[],"model":"grok-4.5","headline":"A practically motivated fraction of persistent holes is DQC1-hard for clique complexes and sits in BQP, giving evidence of exponential quantum advantage for TDA.","keywords":["topological data analysis","persistent homology","normalized persistence","DQC1","SDQC1","local Hamiltonians","combinatorial Laplacian","low-energy spectral density"],"falsifier":"Either an efficient classical algorithm for the hard Normalized Quasi-Harmonic Persistence instances (collapsing DQC1 into BPP) or a proof that the hard Laplacian instances cannot prepare the required low-energy mixture without already solving a DQC1-hard problem.","tokens_in":50435,"feed_emoji":"∂","tokens_out":561,"duration_ms":5742,"temperature":0.7,"pith_summary":"The paper studies normalized persistence: the fraction of topological holes present in one data complex that survive into a larger complex built from the same data. A quasi-harmonic version of this quantity is shown to be DQC1-hard even for the clique complexes that arise in topological data analysis, yet still solvable in BQP under efficient preparation of a uniform mixture over the relevant low-energy space and a large-overlap promise. The same hardness holds for a family of low-energy spectral problems (normalized subtrace and spectral density) on constant-local Hamiltonians, strengthening earlier log-local results. Exact-kernel versions require a new perfect-completeness class SDQC1 and remain hard under that class. Together the results give the first DQC1-hardness statements that apply directly to TDA instances and link them to low-energy Hamiltonian estimation.","feed_headline":"Fraction of persistent holes is DQC1-hard for TDA","feed_subtitle":"First hardness results that apply directly to clique complexes, with BQP algorithms under mixture preparation","key_machinery":"Circuit-to-Hamiltonian constructions that place the DQC1 (or SDQC1) acceptance signal inside a low-energy subspace of an O(1)-local history Hamiltonian, then encode that Hamiltonian into a weighted combinatorial Laplacian via universal simulation so that the normalized low-energy quantities become TDA instances.","core_discovery":"Normalized Quasi-Harmonic Persistence on clique complexes is DQC1-hard and contained in BQP under natural state-preparation and large-overlap assumptions; the same hardness and containment hold for Low-energy Normalized Subtrace and Low-energy Spectral Density on O(1)-local Hamiltonians. Exact-kernel normalized persistence is SDQC1-hard.","pith_inferences":[],"forward_implications":[],"fun_headline_variants":["Normalized persistence is DQC1-hard and in BQP for TDA","Clique complex normalized persistence shows DQC1-hardness","Low-energy spectral density is DQC1-hard for O(1)-local Hamiltonians","Exact-kernel normalized persistence is SDQC1-hard","First DQC1-hardness results for normalized TDA persistence"],"cache_read_input_tokens":32896,"weakest_assumption_plain":"All BQP containment proofs need an efficient circuit that prepares a state close to the uniform mixture over the low-energy or kernel subspace being measured.","fun_headline_variants_meta":{"raw":{"variants":["Normalized persistence is DQC1-hard and in BQP for TDA","Clique complex normalized persistence shows DQC1-hardness","Low-energy spectral density is DQC1-hard for O(1)-local Hamiltonians","Exact-kernel normalized persistence is SDQC1-hard","First DQC1-hardness results for normalized TDA persistence"]},"model":"grok-4.5","effort":"low","cost_usd":0.005934,"raw_usage":{"total_tokens":1611,"prompt_tokens":837,"num_sources_used":0,"completion_tokens":96,"cost_in_usd_ticks":59340000,"prompt_tokens_details":{"text_tokens":837,"audio_tokens":0,"image_tokens":0,"cached_tokens":256},"completion_tokens_details":{"audio_tokens":0,"reasoning_tokens":678,"accepted_prediction_tokens":0,"rejected_prediction_tokens":0}},"tokens_in":837,"tokens_out":96,"duration_ms":5078,"temperature":1.0,"reasoning_tokens":678,"cache_read_input_tokens":256,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-07-12T03:34:33.254599+00:00","model_set":{"reader":"grok-4.5"},"falsifier":"Either an efficient classical algorithm for the hard Normalized Quasi-Harmonic Persistence instances (collapsing DQC1 into BPP) or a proof that the hard Laplacian instances cannot prepare the required low-energy mixture without already solving a DQC1-hard problem.","supporting_citations":[],"review_version":1}