{"id":"c5a2e1c5-cea4-4a2b-860b-d915b19c6ec7","arxiv_id":"2607.15343","paper_version":1,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":7.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":5,"one_line_summary":"A history-decoupled Hamiltonian mapping makes non-Hermitian adiabatic quantum optimization pseudospectrally stable, achieving polynomial-time (per configuration) evolution on the CK maximum-independent-set benchmarks.","lead":"This paper shows that non-Hermitian quantum adiabatic algorithms can fail even with real, gapped spectra if their pseudospectrum is unstable, and introduces a 'history-decoupled' Hamiltonian construction that avoids this instability. The method is demonstrated on a hard benchmark family of maximum independent set problems, with a proposed optical waveguide implementation.","discovery_kind":"new_method","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Robustness claim depends on unproven self-focusing under intra-degenerate-subspace mixing; the finite gap Ω does not protect this, and current noisy numerics stop at n=5.","rationale":"The paper's central claim is that HD QAA provides polynomial-wall-clock-time non-Hermitian adiabatic computation that remains robust against perturbations. The analytic pseudospectrum derivation (Eqs. 37–42) is internally consistent, and the noiseless numerics in Fig. 5 support the polynomial-depth construction. The weakest point is the robustness claim under noise inside the degenerate ground manifold, which the authors themselves flag in Sec. V. The gap Ω protects only against excitations out of the kernel, not against mixing within it; the self-focusing argument is plausible but unquantified and unsupported by large-n noisy simulations. The missing appendix on the CK non-unitary QC scaling is also a reproducibility gap, but the numerical PMIS≈1 in Fig. 5 partially supports that part of the claim, so I regard the degeneracy issue as more load-bearing. A targeted larger-n intra-kernel noise simulation would settle whether the concern actually lands. Since this is the same concern the reader identified, the conditional verdict stands unchanged.","tokens_in":28025,"tokens_out":14612,"duration_ms":138310,"concrete_test":"Simulate the noisy HD QAA on CK graphs G_3 and G_4 (n=9,13) with noise restricted to the instantaneous kernel: δH(t)=ε P(s) R(t) P(s), where P(s) is the projector in Eq. (31) and R(t) is a random Hermitian matrix with ∥R∥_2=1. Keep T=10L, p=2, q=4, Ω=1, and average over 100 noise instances. If PMIS for the MIS drops below ~0.9 at ε=10^{-4}, or systematically decreases with n, the self-focusing claim fails; if PMIS remains ~1 across these sizes, the degeneracy concern is substantially resolved.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The HD construction's instantaneous ground manifold is d_w-dimensional: H_l(s)=Ω(I-P_l(s)) has an exactly degenerate kernel. The pseudospectral analysis in Sec. III bounds the effect of perturbations on the gapped 0–Ω spectral separation, but it says nothing about matrix elements of noise inside the kernel, where there is no energy penalty. The paper explicitly acknowledges this in Sec. V: 'noise may induce state mixing or even quantum walk within the degenerate subspace — this is not protected by the finite gap Ω.' The response is a heuristic self-focusing argument ('amplifies relevant solutions and suppresses competing branches'), not a quantitative bound. The only noisy numerical evidence, Fig. 7, is for G_2 with n=5, where the kernel dimension is only 32; the CK hardness regime is at larger m. Because the advertised claim 'remains robust against perturbations' is exactly what the intra-degenerate mixing argument must secure, this is load-bearing: if noise injects suboptimal configurations faster than the non-unitary weight factor p^{2rF(x)} suppresses them, PMIS could decay with n even though the pseudospectrum is perfectly stable.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","summary":"The manuscript argues that non-Hermitian quantum adiabatic algorithms require three conditions: a real spectrum, a finite spectral gap, and a stable pseudospectrum. It examines two Hamiltonian constructions from non-unitary circuits: a direct Feynman-Kitaev (FK) mapping, which has a real, gapped spectrum but an exponentially unstable pseudospectrum, and a history-decoupled (HD) construction H_l(s)=Ω(I-P_l(s)), whose pseudospectrum is controlled by local gate singular values and whose gap is constant. For maximum independent set on CK graphs, the authors construct O(n^3)-depth diagonal non-unitary circuits, and numerical evolution shows that the HD QAA maintains success probability near 1 while the FK QAA degrades and a Hermitian Grover QAA fails exponentially. Noise simulations show HD robustness for the small G_2 instance. An optical coupled-waveguide implementation is proposed, and the paper explicitly disclaims exponential speedup, describing polynomial wall-clock time accompanied by exponential parallel or post-selection overhead.","tokens_in":28313,"tokens_out":15668,"duration_ms":138629,"significance":"If the robustness claim holds, the paper establishes pseudospectral stability as a design principle for non-Hermitian adiabatic computation and provides a constructive, local Hamiltonian framework. The analytical pseudospectrum formula via singular-value decomposition (Eqs. 35-40), the local condition-number bound (Eqs. 41-42), and the explicit numerical comparison across HM/FK/HD constructions are valuable and internally consistent. The paper is also unusually honest about complexity: Sec. V clearly separates wall-clock time from total computational complexity. The main unresolved point is whether robustness against perturbations survives in the degenerate ground-state manifold, and several supporting derivations are deferred to absent appendices; these issues presently block full acceptance.","major_comments":[{"comment":"The robustness claim is not protected by the spectral gap. H_l(s)=Ω(I-P_l(s)) has a d_w-dimensional zero-energy subspace; norm-ε perturbations have matrix elements inside this subspace that cost no energy. The manuscript explicitly acknowledges this in Sec. V ('noise may induce state mixing or even quantum walk within the degenerate subspace — this is not protected by the finite gap Ω') and answers with a self-focusing argument, but no quantitative bound or scaling analysis is given. The numerical evidence in Fig. 7 is only for G_2 (n=5, zero-space dimension 32), far from the CK hardness regime. Since the abstract promises 'remains robust against perturbations' and this is the central advantage over FK, the authors should provide either (i) a bound on intra-degenerate transition rates induced by norm-bounded perturbations over total time T=Θ(n^3), using the local amplification factors p^","section":"Sec. V, Eq. (30), Fig. 7"},{"comment":"Ideal adiabatic following inside the degenerate ground subspace needs an explicit justification. The non-Hermitian adiabatic theorem cited (Ref. [162]) is invoked without stating whether it covers a degenerate eigenvalue manifold. The construction relies on the specific parallel-transported vector |r^(l,a)(s)⟩; the claim in Sec. V that 'there is no holonomy or off-diagonal matrix element within the degenerate subspace in the ideal case' is asserted rather than proved. Please provide a short derivation that the biorthogonal left vectors satisfy ⟨ℓ^(l,a)|∂_s r^(l,b)⟩=0 and therefore the initial |ψ_{l-1}⟩ is mapped to V_l|ψ_{l-1}⟩, or cite a degenerate non-Hermitian adiabatic theorem with matching hypotheses.","section":"Sec. III, Eq. (30); Sec. V"},{"comment":"The submitted text repeatedly defers load-bearing details to appendices that are not present: the pseudospectrum derivation after Eq. (40); the CK-circuit analysis and r=Θ(m) bound in Sec. IV A; the ε_c estimates in Fig. 6; and the 'measure-theoretic analysis of the degeneracy' in Sec. V. These omissions make the manuscript non-self-contained and prevent verification of central claims. A revised version should include the appendices or move the necessary derivations into the main text.","section":"Appendices referenced throughout"}],"minor_comments":[{"comment":"'Polynomial-evolution-time' should be qualified as wall-clock time for a single successful branch. Sec. V correctly explains that the total complexity is exponential, but the abstract and Table I may be read as complexity claims.","section":"Abstract and Table I"},{"comment":"Panels (b) and (c) use asinh-scaled axes, which makes the pseudospectral contours and their exponential growth hard to interpret. A normal-scale inset or labeled contour levels would improve readability.","section":"Fig. 6"},{"comment":"The caption should state the number of rounds and the problem size explicitly; currently one must infer 'G_2' means n=5 and 'settings identical to Fig. 5' includes r=n.","section":"Fig. 7 caption"},{"comment":"The threshold ε_c is presented as an estimate; state explicitly that Eq. (52) is an approximation and justify why evaluating at x=x_MIS gives the most prominent pseudospectral problem rather than a generic configuration.","section":"Eq. (52)"},{"comment":"The sentence 'we adopt r=n' is abrupt. The relationship between this choice and the theoretical r=Θ(m) from Sec. IV A, and its effect on L and T, should be clarified.","section":"Sec. IV B"}],"recommendation":"major_revision","confidential_remarks":"The core construction is elegant and the pseudospectral analysis is largely sound. The key obstacle is not the instantaneous pseudospectrum but the unquantified behavior inside the degenerate ground manifold under noise; the paper's own Sec. V acknowledges this gap. The missing appendices may be an artifact of the submitted version, but as provided they cannot be checked. I would be willing to accept after a revision that supplies a quantitative argument or convincing scaling evidence for degenerate-subspace robustness and includes the referenced appendix material."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Colleague,\n\nWorth reading, and worth sending to referees. The paper makes a clean conceptual claim that non-Hermitian adiabatic algorithms need a stable pseudospectrum, not just a real gapped spectrum, and the history-decoupled (HD) construction is a genuinely new way to get that. The pseudospectral analysis—local singular values controlling the pseudospectrum, constant gap from the projector structure—is internally consistent, and the numerical evidence is credible because the diagonal gates make each configuration evolve independently. The FK construction's exponential pseudospectral instability is demonstrated convincingly.\n\nNow the soft spots. The biggest is the one the authors themselves flag in Sec. V: the instantaneous ground manifold is d_w-fold degenerate, and the finite gap Ω does nothing to prevent noise from mixing states inside it. The paper's answer is a heuristic self-focusing argument ('amplifies relevant solutions and suppresses competing branches'), not a bound. The noisy numerics stop at n=5, where the kernel is only 32-dimensional; the CK hardness regime is larger. So the advertised robustness claim is not actually established. That said, this is a soft spot in an otherwise sound paper, not a fatal one: the pseudospectral stability of the HD Hamiltonian itself is proven, and the self-focusing mechanism is plausible. I would want a quantitative argument or numerical evidence at larger m before accepting the robustness claim as stated.\n\nTwo smaller issues: the polynomial-time scaling relies on a non-unitary QC result whose proof sits in an appendix not included in the provided text, and there is no code or data for the numerics. Both are fixable. The optical implementation section is speculative but clearly framed as such—fine.\n\nWho this is for: people working on non-Hermitian quantum computation, adiabatic optimization, and open-system dynamics. The central design principle is worth taking seriously even if the robustness proof is incomplete. Send it to review, and ask the authors to tighten the degeneracy argument and provide the missing appendix material.","headline":"Useful new design principle, but the robustness claim is the load-bearing part that isn't proven.","tokens_in":28764,"tokens_out":1991,"would_cite":true,"duration_ms":19563,"reading_group":"yes","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":[],"pacs":[],"model":"deepseek-v4-flash","headline":"For a non-Hermitian quantum adiabatic algorithm to be practical, the spectrum must be stable under perturbation—not merely real and gapped.","keywords":["non-Hermitian quantum adiabatic algorithm","pseudospectrum","history-decoupled construction","maximum independent set","non-unitary quantum circuit","Feynman-Kitaev construction","adiabatic quantum computation","coupled optical waveguides"],"falsifier":"Run the proposed coupled-waveguide realization with deliberately time-dependent coupling or loss fluctuations at segment boundaries (where the degeneracy is largest) and measure the output intensity distribution across configurations. If, for realistic noise amplitudes, the distribution spreads over the degenerate subspace or peaks at a wrong configuration as n grows, the claimed robustness of HD QAA is refuted even though the pseudospectral-gap analysis itself remains correct.","tokens_in":27923,"feed_emoji":"⚛️","tokens_out":9497,"duration_ms":71783,"temperature":0.7,"pith_summary":"For a non-Hermitian quantum adiabatic algorithm to be practical, the paper argues, a real spectrum and a nonzero energy gap are not enough: a non-Hermitian Hamiltonian can be so sensitive that tiny perturbations destroy the gap and the adiabatic protection. The paper's central requirement is a stable pseudospectrum—a guarantee that eigenvalues do not move far under small perturbation—and it shows that the standard history-state mapping from quantum circuits to Hamiltonians fails this test, because non-Hermitian effects accumulate along the whole circuit. The authors replace it with a history-decoupled construction: the Hamiltonian at each segment involves only the current non-unitary gate, while the accumulated computation lives in the quantum state itself. For a hard family of maximum independent set problems, the resulting path has a constant gap, polynomial evolution time, and high success probability that survives random perturbations, unlike both a Hermitian search-based path (exponentially slow) and the direct non-Hermitian history-state path (exponentially fragile). This matters because non-unitary circuits are easy to design for optimization but were previously hampered by post-selection and noise; the paper shows an adiabatic route that avoids the accumulation.","feed_headline":"Stable pseudospectra make non-Hermitian adiabatic algorithms work","feed_subtitle":"History-decoupled evolution keeps the gap stable and solves MIS benchmarks in polynomial time.","key_machinery":"The history-decoupled (HD) Hamiltonian path: at segment l it is H_l(s)=Ω(I−P_l(s)), where P_l(s)=Σ_a |r^{(l,a)}(s)⟩⟨ℓ^{(l,a)}(s)|, with |r^{(l,a)}(s)⟩ = cosθ |a⟩⊗|l−1⟩ + sinθ V_l |a⟩⊗|l⟩ and ⟨ℓ^{(l,a)}(s)| the corresponding left vector built from V_l^{-1}. This rank-d_w projection Hamiltonian has spectrum {0,Ω} and adiabatically transfers a state from clock site |l−1⟩ to |l⟩ while applying V_l once. Its key property is that the pseudospectrum decomposes into independent 2×2 blocks, one per singular value σ_j of V_l, so the relevant condition number is κ(S_l)=max{1,‖V_l‖}max{1,‖V_l^{-1}‖}, local to a single gate rather than growing with circuit depth. That locality is what prevents the expone","core_discovery":"Central claim: a real, gapped spectrum is not enough for non-Hermitian adiabatic computation; the pseudospectrum must also be stable, meaning eigenvalues stay put under small perturbations. The direct non-Hermitian Feynman-Kitaev mapping has a real, polynomially gapped spectrum but is exponentially unstable, because non-Hermitian effects accumulate along the whole circuit. The history-decoupled construction uses H_l(s)=Ω(I−P_l(s)) in each segment, with a projection built only from the current gate V_l; this Hamiltonian has eigenvalues 0 and Ω and its pseudospectrum is governed by V_l's local singular values, not by the circuit's accumulated history. On a hard MIS benchmark family, this gives","pith_inferences":["If pseudospectral stability becomes an accepted design criterion, many non-Hermitian optimization proposals that check only real spectra may need re-evaluation; the FK example shows that a perfectly gapped ideal path can be useless under realistic noise.","The HD principle generalizes: any non-unitary circuit subroutine can be embedded as a locally applied projection Hamiltonian, so the same 'state carries history, Hamiltonian carries only the current operation' strategy could be applied to other gate families or hybrid algorithms.","The paper's robustness for degenerate ground-state mixing is argued heuristically via self-focusing; a clean experimental test in the waveguide platform (adding noise at segment boundaries) could either support or challenge this assumption.","Read honestly, the result is a wall-clock-time advantage with exponential overhead in physical resources, so the path to an actual quantum speedup passes through many-body platforms where dissipation is built in and the exponential channel replication is avoided."],"forward_implications":["The HD path's constant gap Ω replaces the Θ(L^{-2}) gap of the history-state mapping, so adiabatic evolution time scales polynomially while preserving the non-unitary circuit's optimization advantage.","On the hard MIS benchmark family, the HD construction achieves success probability near 1 at fixed total time T=10L for n=9,…,45, whereas a Hermitian search-based path decays exponentially over the same time.","Under random perturbations of strength up to ε=10^{-1}, HD QAA success probability remains close to the clean case; the direct FK mapping's success degrades substantially, and its perturbation threshold for gap closure shrinks exponentially with rounds and system size.","The construction maps onto coupled optical waveguides with an auxiliary lossy channel: for each configuration x the non-Hermitian 2×2 dynamics is realized with propagation length Θ(n^3), producing output intensities whose maximum identifies the MIS.","The post-selection overhead is exponential in total complexity, but the scheme converts an exponentially long coherent evolution into exponentially many short, parallelizable, resettable runs with failure flags."],"fun_headline_variants":["Non-Hermitian adiabatic computing needs stable pseudospectra","History-decoupled Hamiltonians tame non-Hermitian instability","Real gap isn't enough: pseudospectral stability is key","Pseudospectral stability unlocks non-Hermitian adiabatic speedup"],"cache_read_input_tokens":2304,"weakest_assumption_plain":"The load-bearing assumption is that noise-induced mixing inside the highly degenerate instantaneous ground-state subspace—where the finite gap Ω provides no protection—is harmless because the non-Hermitian dynamics self-focuses onto the target solution; the paper supports this heuristically and numerically but proves no bound.","fun_headline_variants_meta":{"raw":{"variants":["Non-Hermitian adiabatic computing needs stable pseudospectra","History-decoupled Hamiltonians tame non-Hermitian instability","Real gap isn't enough: pseudospectral stability is key","Pseudospectral stability unlocks non-Hermitian adiabatic speedup"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000372,"raw_usage":{"total_tokens":1804,"prompt_tokens":701,"completion_tokens":1103,"prompt_tokens_details":{"cached_tokens":256},"prompt_cache_hit_tokens":256,"prompt_cache_miss_tokens":445,"completion_tokens_details":{"reasoning_tokens":1031}},"tokens_in":445,"tokens_out":1103,"duration_ms":7109,"temperature":1.0,"reasoning_tokens":1031,"cache_read_input_tokens":256,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-01T23:39:06.189443+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Run the proposed coupled-waveguide realization with deliberately time-dependent coupling or loss fluctuations at segment boundaries (where the degeneracy is largest) and measure the output intensity distribution across configurations. If, for realistic noise amplitudes, the distribution spreads over the degenerate subspace or peaks at a wrong configuration as n grows, the claimed robustness of HD QAA is refuted even though the pseudospectral-gap analysis itself remains correct.","supporting_citations":[],"review_version":1}