{"id":"04d33fe8-c3ca-4ec6-b59b-7537e3febb8e","arxiv_id":"2505.01528","paper_version":1,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":7.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":3,"one_line_summary":"SOSSA writes a shifted Hamiltonian as a sum of squares, block-encodes its square root, and proves O(sqrt(Delta*lambda)/epsilon) query algorithms for low-energy expectation and phase estimation, with a sqrt(N) speedup on the SYK model.","lead":"The paper introduces sum-of-squares spectral amplification (SOSSA), a framework that combines semidefinite programming over Hamiltonian representations with spectral amplification to simulate low-energy quantum states faster. It proves query complexity improvements from linear in the Hamiltonian norm to the square root of a low-energy window times the norm, and demonstrates a square-root-in-system-size speedup for the SYK model.","discovery_kind":"new_method","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Theorem 5's final sign-discrimination step invokes Corollary 1/Lemma 6 in a parameter regime (theta0=pi/2, epsilon>0) that violates the lemma's own condition epsilon+theta0<=pi/2, leaving the no-prior energy-estimation scaling unproven as written.","rationale":"Reading the manuscript in good faith, the SOSSA construction is coherent: Lemma 3 gives the block-encoding of the spectral-amplified operator, Theorems 4 and 6 give the non-adaptive bounds, Theorem 8 provides a genuine lower bound, and the double-factorization compilation of the degree-2 Majorana SOS is a plausible route to the SYK gate count. Lemma 8's use of random matrix theory is also plausible; even though the hidden constants are not reported, the claimed asymptotic O(N^{-1}) norm for the flattened coupling tensor is standard for this scaling, so the SYK speedup is not the weakest point. The actual internal contradiction is in Theorem 5's proof: the final separation of E<0 versus E>0 uses Corollary 1 with theta0=pi/2, which Lemma 6 forbids for positive epsilon. Since Theorem 5 is the only theorem supporting the headline no-prior energy-estimation complexity, this is load-bearing. The fix may be straightforward, for example via a valid phase-shifted gapped-phase-estimation construction, and Theorem 7 provides an alternative route to the SYK speedup, so I would not reject the paper. The reader's rationale already flags this Theorem 5 issue, although their formal weakest_assumption was the Lemma 8 constants; my stress-test prioritizes the theorem gap, so the agreement is partial. The verdict remains CONDITIONAL: the framework and phase-estimation results are substantial, but the energy-estimation theorem needs a corrected proof before the full abstract claim is supported.","tokens_in":33214,"tokens_out":20756,"duration_ms":226764,"concrete_test":"Independently re-derive the final sign-discrimination step of Theorem 5 using only parameter regimes allowed by Lemma 6. In particular, try applying Lemma 6 with theta0 = pi/2 - delta to both the walk operator W and the phase-shifted operator e^{i*pi/2}W, and check whether the query count remains O(lambda/max(epsilon',|E|)). If such a two-call construction works, Theorem 5 is repairable and the CONDITIONAL verdict stands; if the only valid applications cost O(lambda/epsilon' * log(...)) or cannot decide the sign at all, the no-prior energy-estimation claim is unsupported and the abstract's energy-estimation speedup must be weakened.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The load-bearing flaw is in Appendix B 1, in the proof of Theorem 5. That theorem is the sole support for the advertised no-prior expectation-estimation query complexity O(sqrt(max{epsilon, lambda-|E|})*lambda/epsilon); Theorem 4 requires a known upper bound Delta, so it cannot replace it. In the final sign-discrimination step, the proof invokes Corollary 1 with parameters epsilon = pi/2 - I_{imax,r} and theta0 = pi/2. But Lemma 6, whose hypotheses Corollary 1 repeats verbatim, requires 0 < epsilon <= theta0 <= epsilon+theta0 <= pi/2. With theta0 = pi/2, the last inequality forces epsilon <= 0, contradicting the use of a positive interval. The proof therefore lacks a valid subroutine to decide whether E<0 or E>0 once |E| has been bounded. This is an internal consistency failure in a central theorem, not merely a missing constant in Lemma 8. The SYK speedup can still be obtained through Theorem 7, so the framework is not destroyed, but the energy-estimation claim needs a corrected phase-shifted gapped-phase-estimation argument.","agreement_with_reader":"partial"},"referee_report":{"model":"deepseek-v4-flash","summary":"The manuscript introduces SOSSA, a framework that combines sum-of-squares (SOS) decompositions of shifted Hamiltonians with spectral amplification (SA) to improve quantum algorithms for low-energy simulation problems. It claims gate- and query-complexity improvements for expectation estimation and ground-state phase estimation, replacing the standard O(lambda/epsilon) scaling by O(sqrt(Delta lambda)/epsilon) when a low-energy bound Delta is known, and by an adaptive no-prior bound of the form stated in Theorem 5 and Table II. The framework is applied to the Sachdev-Ye-Kitaev model, where a degree-2 Majorana SOS is shown via a random-matrix dual argument (Lemma 8) to give beta = O(N), implying Delta_SOS = O(N) and lambda_SOS = O(N^2), and hence a query complexity O(N^{3/2}) compared with O(N^2) for LCU. The paper also proves a matching lower bound Omega(sqrt(lambda Delta)/epsilon) for phase estimation in the block-encoding access model and gives a low-depth, standard-quantum-limit expectation estimator using Hadamard tests.","tokens_in":33388,"tokens_out":26841,"duration_ms":269651,"significance":"If the main theorems are correct, SOSSA is a significant contribution to quantum simulation: it generalizes prior spectral-amplification results [5, 16], removes the need for a priori energy upper bounds in expectation estimation, and exhibits a polynomial speedup for a strongly correlated model. The SYK analysis is a genuine strength: Lemma 8 is internally consistent, the random-matrix bound ||J|| = O(N^{-1}) and the trace inequality give beta = O(N), and the double-factorization bound lambda_SOS = O(N^2) is derived explicitly. The lower-bound reduction from PARITY of OR (Theorem 8) is an interesting and appropriate optimality result. The paper is carefully written and the appendices contain detailed proofs. However, the proof of the no-prior expectation-estimation theorem has a gap in its final sign-discrimination step, and the theorem statements of Theorems 5 and 7 contain a dimensional inconsistency with the bounds derived in their own proofs. These issues are local and repairable, but they are load-bearing for the advertised complexity claims, so the paper needs a major revision.","major_comments":[{"comment":"The proof invokes Corollary 1 with parameters (epsilon, theta0) = (pi/2 - I_{imax,r}, pi/2). Corollary 1 and Lemma 6 require 0 < epsilon <= theta0 <= epsilon + theta0 <= pi/2. With theta0 = pi/2, the condition forces epsilon <= 0, while the actual value epsilon = pi/2 - I_{imax,r} is positive whenever I_{imax,r} < pi/2. The invoked subroutine is therefore outside the stated hypotheses, and the proof does not provide a valid way to distinguish the cases E < 0 and E > 0. Since Theorem 5 claims to estimate E for arbitrary sign and this final step is the only mechanism for that distinction, the no-prior expectation-estimation result is unproven as written. The text after Lemma 6 already notes the correct remedy (another round of phase estimation on, say, e^{i pi/2} U), so the gap is likely repairable, but it must be fixed explicitly.","section":"Appendix B 1, proof of Theorem 5, final sign-discrimination step (after Eq. (B45))"},{"comment":"The stated query complexity in Theorem 5 is O(sqrt(max{epsilon, lambda-|E|}) * lambda / epsilon * log(1/q)), and Theorem 7 has an analogous expression with lambda/(sqrt(p) epsilon). However, the proof's final bound in Eq. (B48) is Q = O(sqrt(lambda) * (sqrt(epsilon) + sqrt(lambda-|E|)) / epsilon * log(1/q)) = O(sqrt(lambda * max{epsilon, lambda-|E|}) / epsilon * log(1/q)), and the corresponding bound in Eq. (B69) is sqrt(lambda * max{epsilon, lambda+E}) / (sqrt(p) epsilon). The printed theorem statements and Table II carry an extra factor sqrt(lambda) and are not invariant under the physical rescaling (lambda, epsilon) -> (s lambda, s epsilon). The proof's version is dimensionally consistent and is the bound needed for the advertised speedup over lambda/epsilon. The theorem statements and Table II should be corrected to match the proof, and the comparison with prior work should be restated accordingly.","section":"Theorems 5 and 7 statements and Table II"},{"comment":"The proof defines the non-Hermitian operator O = (|0><0| ⊗ I) Gpe and claims that, because Be[O/1] can be constructed with one query to Gpe, one may apply Theorem 4 or Theorem 5 to estimate kappa = <psi|O†O|psi> to additive error p/2. Theorem 4 and Theorem 5 estimate expectations of Hermitian operators from their block-encodings; the operator whose expectation equals kappa is O†O = Gpe† (|0><0| ⊗ I) Gpe, not O, and the text does not show how Be[O†O] is obtained. The quoted costs Q_{P,i} = O((1/sqrt(p)) log(1/q_i)) and Q_{H,i} = O(1/(sqrt(p) r^i) log(1/p) log(1/q_i)) are those of amplitude estimation, suggesting that the intended subroutine is standard amplitude estimation on Gpe followed by the projector. The proof needs a precise reduction to such a subroutine; as written, the justification for this step is incomplete.","section":"Appendix B 2, proof of Theorem 7, decision step around Eqs. (B60)-(B61)"}],"minor_comments":[{"comment":"The trace step Tr(J rho) >= -||J|| Tr(rho) uses the identity Tr(rho) = C(N,2); this depends on the normalization E[1] = 1 and on the choice of basis elements i gamma_a gamma_b (whose squares are +1). Please state these conventions explicitly, since the same calculation with gamma_a gamma_b would give diagonal entries -1 and change the sign of the bound.","section":"Lemma 8, proof"},{"comment":"The error-propagation inequality epsilon <= sqrt(2 Delta lambda) * epsilon_PEA is stated without derivation; a one-line argument using the derivative of arccos at E/lambda would make the constant transparent to the reader.","section":"Theorem 4, inequality (B14)"},{"comment":"The symbols Delta (energy gap) and Delta_1, Delta_2, Delta_3 (failure probabilities in Theorem 5) are overloaded; please rename the failure probabilities, e.g. q_1, q_2, q_3, to avoid confusion.","section":"Throughout, and Theorem 5 proof"},{"comment":"There are small textual issues: \"of ofH\" appears in the Introduction, and Lemma 5's phrasing \"with probability p_j we estimate\" should be rephrased to indicate that each eigencomponent with weight p_j is estimated with confidence 1-q.","section":"Introduction and Lemma 5"},{"comment":"The statement that the number of terms in HSYK scales like ~N^4 could be made precise (e.g., Theta(N^4) with the combinatorial constant absorbed), since it is used to argue the optimality of the O(N^4) gate count for the LCU block-encoding.","section":"Section IV"}],"recommendation":"major_revision","confidential_remarks":"The SOSSA framework is likely of significant interest to the quantum algorithms community, and the SYK application is compelling. The major issues I identified are a genuine but locally repairable gap in the proof of Theorem 5, a dimensionality/consistency error in the statements of Theorems 5 and 7 and Table II, and a terse reduction in the proof of Theorem 7. I do not see circularity: the new proofs are based on cited prior results, and the SOS/dual analysis for SYK is self-contained. I recommend major revision rather than rejection; the authors should also carefully re-derive the final query-complexity expressions to ensure the theorem statements match the proofs."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Dear X,\n\nQuick take: this is a genuinely new algorithmic framework with a real, localized bug in one central theorem. If you only read one thing, read the proof of Theorem 5; the sign-discrimination step at the end calls Corollary 1 with theta0 = pi/2 and positive epsilon, but Lemma 6 (whose hypotheses Corollary 1 copies) requires epsilon + theta0 <= pi/2, which forces epsilon <= 0. The proof needs a phase-shifted gapped phase estimation argument that is not there. That is not a missing constant; it is an internal inconsistency in a load-bearing claim.\n\nWhat is good. The SOSSA concept — using SOS lower bounds to shift a Hamiltonian and then applying spectral amplification to the square root — is presented clearly and the generalization beyond chemistry is real. Theorem 7 (phase estimation with overlap p, no prior energy upper bound) and Theorem 8 (query lower bound matching the sqrt(Delta*lambda/epsilon) scaling) are solid and new. Theorem 9's low-depth standard-quantum-limit estimator is a nice bonus. The SYK analysis in Appendix D is internally consistent: Lemma 8's Cauchy-Schwarz/Holder argument checks out, and the lambda_SOS bound via double factorization gives O(N^2). The proofs are unusually complete for a preprint of this type. I did not find a second issue of comparable magnitude.\n\nWhere it is softer. Theorem 5 is the main advertised improvement for no-prior energy estimation, and as written it is unproven. Theorem 4 requires a known upper bound Delta, so it does not substitute. The SYK speedup survives through Theorem 7, so the framework is not destroyed, but the abstract's 'energy estimation' claim needs fixing. Also: the constants in Lemma 8 and the RMT bound are not reported, so the sqrt(N) speedup is strictly asymptotic; and there is no code or numerical data, which is fine for a theory paper but limits checking. Self-citation of the companion chemistry paper [16] is prominent but legitimate, since the companion result is independent and published.\n\nWho should read it: quantum algorithms people working on low-energy simulation and phase estimation. It deserves serious refereeing; a careful referee could verify the rest of the proofs and pin down whether Theorem 5 is repairable. I would conditionally accept after that fix.\n\nRecommendation: send to peer review, don't desk reject.","headline":"Real framework, one real proof bug: Theorem 5's sign-discrimination step violates the phase-estimation lemma it invokes; the rest is coherent and worth serious refereeing.","tokens_in":34075,"tokens_out":2181,"would_cite":true,"duration_ms":22066,"reading_group":"yes","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["81P68","68Q12"],"pacs":[],"model":"deepseek-v4-flash","headline":"Rewriting a Hamiltonian as a sum of squares and simulating its square root turns $O(\\lambda/\\epsilon)$ energy estimation into $O(\\sqrt{\\Delta\\lambda}/\\epsilon)$ with a matching lower bound.","keywords":["quantum simulation","sum-of-squares spectral amplification","energy estimation","ground-state phase estimation","SYK model","block-encoding","query complexity","spectral amplification"],"falsifier":"Solve the degree-2 Majorana SOS relaxation for random SYK instances at increasing $N$ (for example $N=16,32,48,64$) by evaluating the dual pseudoexpectation or the primal SDP, and check whether $\\beta/N$ stays bounded by a constant independent of $N$; if $\\beta$ grows faster than linearly, or if the empirical low-energy gap $\\Delta_{SOS}$ exceeds $O(N)$, the claimed $O(N^{3/2})$ scaling for SYK fails.","tokens_in":32900,"feed_emoji":"⚛️","tokens_out":13690,"duration_ms":130481,"temperature":0.7,"pith_summary":"This paper argues that low-energy quantum simulation can be accelerated by rewriting the shifted Hamiltonian $H+\\beta\\mathbb{1}$ as an explicit sum of squares $\\sum_j B_j^\\dagger B_j$, then block-encoding the square root $H_{\\mathrm{SOSSA}}=\\sum_j |j\\rangle\\otimes B_j$ instead of $H$ itself. Because the square root is steep near zero, a coarse phase estimate of a small eigenvalue of the square root yields a fine estimate of the corresponding eigenvalue of $H$, reducing the query complexity of energy estimation and ground-state phase estimation from $O(\\lambda/\\epsilon)$ to $O(\\sqrt{\\Delta\\lambda}/\\epsilon)$. The paper provides adaptive algorithms that achieve this scaling without prior knowledge of the low-energy scale $\\Delta$, and a matching $\\Omega(\\sqrt{\\Delta\\lambda}/\\epsilon)$ lower bound showing the scaling is optimal in the square-root access model. For the SYK model, a degree-2 Majorana sum of squares gives $\\beta=O(N)$ and a double-factorized block-encoding with $\\lambda_{SOS}=O(N^2)$, making the total query cost $O(N^{3/2})$ instead of $O(N^2)$ with comparable gate costs per query. If the key random-matrix bound for the SOS relaxation holds, low-energy simulation of SYK and similar strongly correlated systems is polynomially faster and query-optimal.","feed_headline":"Square-root trick speeds low-energy quantum simulation","feed_subtitle":"Sum-of-squares rewriting makes energy estimation run in O(√(Δλ)/ε) queries — and that is optimal.","key_machinery":"The load-bearing object is the SOSSA square-root operator $H_{\\mathrm{SOSSA}}=\\sum_j |j\\rangle\\otimes B_j$ built from the sum-of-squares identity $H+\\beta\\mathbb{1}=\\sum_j B_j^\\dagger B_j$; it satisfies $H_{\\mathrm{SOSSA}}^\\dagger H_{\\mathrm{SOSSA}}=H+\\beta\\mathbb{1}$ and is block-encoded with normalization $\\lambda_{SOS}$. Two supporting mechanisms carry the argument: the qubitization quantum walk, whose eigenphases are $\\arccos((E+\\beta)/\\lambda_{SOS})$ and whose derivative near the low-energy edge produces the $\\sqrt{\\Delta\\lambda}$ amplification, and adaptive gapped phase estimation, which locates the low-energy edge without an a priori bound on $\\Delta$ and removes the logarithmic overhead a naive binary search would pay. For the SYK application, the generators $B_j$ are degree-2 Majorana polynomials, and double factorization compiles their block-encoding with $O(N^4)$ gates while keeping $\\lambda_{SOS}=O(N^2)$, the same asymptotic gate cost as the LCU encodings it replaces.","core_discovery":"The paper's central claim is that any Hamiltonian admitting an SOS identity $H+\\beta\\mathbb{1}=\\sum_j B_j^\\dagger B_j$ with efficiently block-encodable generators $B_j$ can be simulated in the low-energy sector through the spectral-amplified operator $H_{\\mathrm{SOSSA}}=\\sum_j |j\\rangle\\otimes B_j$, whose composition with itself is $H+\\beta\\mathbb{1}$. Qubitization of the block-encoding $H_{\\mathrm{SOSSA}}/\\sqrt{\\lambda_{SOS}}$ gives a quantum walk whose eigenphases are $\\arccos((E+\\beta)/\\lambda_{SOS})$, and the nonlinearity of arccos at the low-energy edge lets a phase measurement of accuracy $\\epsilon/\\sqrt{\\Delta\\lambda}$ supply an energy estimate of accuracy $\\epsilon$ when the state lies at most $\\Delta$ above the lower bound $-\\beta$. The resulting expectation estimator has query complexity $O(\\sqrt{\\max\\{\\epsilon,\\lambda-|E|\\}}\\,\\lambda/\\epsilon)$, and the ground-state phase estimator with overlap $p$ has query complexity $O(\\sqrt{\\max\\{\\epsilon,\\lambda+E\\}}\\,\\lambda/(\\sqrt{p}\\,\\epsilon)\\log(1/p)\\log(1/q))$, both with adaptive versions that need no prior bound on $\\Delta$. For the SYK model the paper proves, using the dual pseudoexpectation formulation plus the random-matrix bound $\\|J\\|=O(N^{-1})$, that the degree-2 Majorana SOS achieves $\\beta=O(N)$ with high probability, and with double factorization gives $\\lambda_{SOS}=O(N^2)$ and $\\Delta_{SOS}=O(N)$, hence $\\sqrt{\\Delta_{SOS}\\lambda_{SOS}}=O(N^{3/2})$ versus $\\lambda_{LCU}\\sim N^2$. Theorem 8 establishes an $\\Omega(\\sqrt{\\Delta\\lambda}/\\epsilon)$ lower bound for phase estimation in this access model, so the quadratic reduction is not an artifact of a weak upper bound.","pith_inferences":["The same $\\sqrt{\\Delta\\lambda}$ reduction should transfer to any strongly correlated model that admits a low-degree SOS with a tight lower bound and a cheaply block-encoded normalization; the paper demonstrates this only for SYK, so extending it to lattice fermion or spin models with local generators is an untested extrapolation.","The degree-3 SOS example from the paper's reference [31] gives a tighter $\\beta=O(\\sqrt{N})$ but a larger $\\lambda_{SOS}=O(N^{7/2})$, washing out the gain; this tradeoff suggests future SOS design should co-optimize the spectral gap with the encoding normalization rather than minimize $\\beta$ alone, a program the paper notes but does not pursue.","The lower bound is proven when the algorithm receives the square-root block-encoding $H_{SOSSA}/\\sqrt{\\lambda_{SOS}}$; whether the same $\\Omega(\\sqrt{\\Delta\\lambda}/\\epsilon)$ holds for algorithms given only the standard LCU block-encoding of $H$ directly is left open, since the advantage may partly be a re-encoding choice.","A practical test of the adaptive estimators would be to run the coarse first pass on small SYK instances to see how often the state is correctly classified as low-energy before committing to the full $\\sqrt{\\Delta\\lambda}$ precision; the paper's complexity bounds assume this classification succeeds, and its empirical probability on finite systems is unmeasured."],"forward_implications":["Energy expectation values in the low-energy sector can be estimated with $O(\\sqrt{\\max\\{\\epsilon,\\lambda-|E|\\}}\\,\\lambda/\\epsilon)$ queries, improving the generic $O(\\lambda/\\epsilon)$ cost; the dependence on $\\lambda-|E|$ rather than a known bound $\\Delta$ means no prior knowledge of the low-energy scale is needed.","Ground-state phase estimation inherits the same quadratic reduction, costing $O(\\sqrt{\\max\\{\\epsilon,\\lambda+E\\}}\\,\\lambda/(\\sqrt{p}\\,\\epsilon)\\log(1/p)\\log(1/q))$ queries with only two ancillary qubits.","For the SYK model, the total query complexity drops from $O(N^2)$ for LCU and termwise spectral amplification to $O(N^{3/2})$, a factor $\\sqrt{N}$ speedup at equal $O(N^4)$ block-encoding gate costs.","The matching lower bound $\\Omega(\\sqrt{\\Delta\\lambda}/\\epsilon)$ for phase estimation in the square-root access model shows these algorithms saturate the information-theoretic limit, not just beat the previous best known upper bound.","A low-depth variant estimates expectations of sum-of-squares observables at the standard quantum limit, with sample complexity $O\\big((\\sum_j \\sqrt{\\Delta_j a_j}/\\sigma)^2\\big)$ and only single-query Hadamard tests per term."],"supporting_citations":[{"why":"The companion SOSSA paper demonstrating improved gate costs for quantum-chemistry phase estimation; the present work generalizes its SOS machinery beyond chemistry.","marker":"[16]"},{"why":"Supplies the known SYK spectrum support $[-c\\sqrt{N},c\\sqrt{N}]$ and the degree-3 SOS bound that defines the baseline the degree-2 SOS must beat.","marker":"[31]"},{"why":"Random-matrix concentration theorem used in Lemma 8 to bound the spectral norm $\\|J\\|=O(N^{-1})$ for the SYK coupling matrix.","marker":"[47]"},{"why":"Double-factorization technique used to compile the degree-2 Majorana SOS generators with $\\lambda_{SOS}=O(N^2)$ and comparable gate cost.","marker":"[30]"},{"why":"Qubitization quantum walk construction whose arccos eigenphase map is the amplification mechanism behind spectral amplification.","marker":"[4]"},{"why":"Quantum singular value transformations used to turn the square-root block-encoding into the shifted operator needed by the phase-estimation algorithms.","marker":"[23]"},{"why":"Prior spectral-amplification time-evolution work and the $\\mathrm{PARITY}\\circ\\mathrm{OR}$ query lower bound that Theorem 8 adapts to energy and phase estimation.","marker":"[5]"},{"why":"Amplified amplitude estimation baseline that needs a known upper bound $\\Delta$; Theorem 5 improves on it by removing that a priori bound and generalizing beyond projections.","marker":"[17]"}],"fun_headline_variants":["Sum-of-squares trick gives optimal speedup for low-energy sims","Quadratic speedup for phase estimation via sum-of-squares","SOSSA: optimal low-energy simulation with square-root queries","Sum-of-squares amplification cuts energy estimation cost","Optimal square-root query bound for low-energy phase estimation"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The load-bearing premise is Lemma 8's high-probability bound $\\beta=O(N)$ for the degree-2 Majorana SOS on the SYK model; if the constants in the spectral-norm estimate $\\|J\\|=O(N^{-1})$ or in the known spectrum support $[-c\\sqrt{N},c\\sqrt{N}]$ grow with $N$ or are unusually large, then $\\Delta_{SOS}$ could exceed $O(N)$ and the claimed $\\sqrt{N}$ speedup would degrade.","fun_headline_variants_meta":{"raw":{"variants":["Sum-of-squares trick gives optimal speedup for low-energy sims","Quadratic speedup for phase estimation via sum-of-squares","SOSSA: optimal low-energy simulation with square-root queries","Sum-of-squares amplification cuts energy estimation cost","Optimal square-root query bound for low-energy phase estimation"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000595,"raw_usage":{"total_tokens":2860,"prompt_tokens":1092,"completion_tokens":1768,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":708,"completion_tokens_details":{"reasoning_tokens":1684}},"tokens_in":708,"tokens_out":1768,"duration_ms":12397,"temperature":1.0,"reasoning_tokens":1684,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-16T04:19:38.752551+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Solve the degree-2 Majorana SOS relaxation for random SYK instances at increasing $N$ (for example $N=16,32,48,64$) by evaluating the dual pseudoexpectation or the primal SDP, and check whether $\\beta/N$ stays bounded by a constant independent of $N$; if $\\beta$ grows faster than linearly, or if the empirical low-energy gap $\\Delta_{SOS}$ exceeds $O(N)$, the claimed $O(N^{3/2})$ scaling for SYK fails.","supporting_citations":[{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Supplies the known SYK spectrum support $[-c\\sqrt{N},c\\sqrt{N}]$ and the degree-3 SOS bound that defines the baseline the degree-2 SOS must beat."},{"cited_title":"Vershynin, High-dimensional probability: An introduc- tion with applications in data science , Vol","cited_arxiv_id":null,"evidence_quote":"Random-matrix concentration theorem used in Lemma 8 to bound the spectral norm $\\|J\\|=O(N^{-1})$ for the SYK coupling matrix."},{"cited_title":"von Burg, G","cited_arxiv_id":null,"evidence_quote":"Double-factorization technique used to compile the degree-2 Majorana SOS generators with $\\lambda_{SOS}=O(N^2)$ and comparable gate cost."},{"cited_title":"Gily´ en, Y","cited_arxiv_id":null,"evidence_quote":"Quantum singular value transformations used to turn the square-root block-encoding into the shifted operator needed by the phase-estimation algorithms."},{"cited_title":"Zlokapa and R","cited_arxiv_id":null,"evidence_quote":"Prior spectral-amplification time-evolution work and the $\\mathrm{PARITY}\\circ\\mathrm{OR}$ query lower bound that Theorem 8 adapts to energy and phase estimation."}],"review_version":1}