{"id":"a449ac0a-3bb2-44cd-b69f-10121e3cbfe8","arxiv_id":"2608.10147","paper_version":1,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":7.0,"correctness_risk":"high","formal_verification":"none","parameter_count":3,"one_line_summary":"Under perfect completeness, a global-correlation-rounding analysis improves best-separable-state algorithms to n^{O(sqrt(n/epsilon))} and n^{O(sqrt(q))}.","lead":"This paper gives faster algorithms for finding the best unentangled (product) state accepted by a quantum measurement, in the perfect-completeness case where a product state is accepted with probability 1. It improves the runtime to n^{O(sqrt(n/epsilon))} for value 1-epsilon and to n^{O(sqrt(q))} for value q/n, and proves a new pinning lemma of independent interest.","discovery_kind":"new_method","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Lemma 5.4 is internally inconsistent: its lower bounds exceed the unit-norm maximum for q=2, so the 1 vs q/n regime is unsupported.","rationale":"The paper has a coherent first regime: Lemma 4.4 (mean rounding), Lemma 4.5 (pinning), and Theorem 4.1 are internally consistent, and the runtime n^{O(sqrt(n/epsilon))} follows from the stated potential-growth analysis. The fine-grained pinning lemma in Section 6 is plausible and appears to have an independent proof. However, the 1 versus q/n regime is a second headline result, and Lemma 5.4 is its pivot. The concern is not that the lemma is unproven but that it is impossible as stated: for q=2 and sufficiently large K, its lower bounds contradict the unit-norm upper bounds that hold for every feasible pseudoexpectation. The balancing choice Q ≍ theta sqrt n in the proof is dimensionally inconsistent, and the correct balance Q = theta/sqrt n would yield auxiliary bounds that are too weak for the subsequent singular-vector rounding. Since Theorem 5.1 explicitly invokes Lemma 5.4 for both the win condition and the auxiliary lower bounds, the q/n guarantee and the n^{O(sqrt q)} runtime are unsupported. This is a localized, fixable failure rather than evidence that the whole approach is wrong, so CONDITIONAL is the appropriate verdict. I agree with the reader that Lemma 5.4 is the load-bearing weak spot, but I do not share the secondary claim that ||R||_F >= sqrt(q)/n fails to follow from the stated lemma; it would follow from Lemma 5.4(b) if that condition were valid. The essential issue is that condition (b) is impossible, and the proof gives no corrected version.","tokens_in":36070,"tokens_out":5672,"duration_ms":55067,"concrete_test":"Analytically verify Lemma 5.4 by substituting theta = K sqrt(q/n) with q=2 and K larger than both 1/c and 1/sqrt(2) into the three displayed conclusions. Since any pseudodistribution satisfying (9) obeys the universal bounds ||E x||, ||E y|| <= 1 + n^{-beta} and ||E xy^T||_F <= 1 + n^{-beta}, the lemma's conditions (a) and (b) would require cK sqrt(2) <= 1 and K sqrt(2) ≲ 1, which fail for this K. If the contradiction is confirmed, Lemma 5.4 cannot be true as stated. Independently, solve the balancing equation Qn = theta^2/Q for Q; if the solution is not theta sqrt n, the balancing step in Lemma 5.4's proof is dimensionally wrong. A further useful check is to repeat the derivation with Q = theta/sqrt n and see whether the resulting lower bounds on means and on ||R||_F are strong enough to prove Theorem 5.1; if not, the q/n regime requires a genuinely different lemma.","verdict_should_be":"CONDITIONAL","load_bearing_attack":"The second headline guarantee of Theorem 1.2 (1 versus q/n) rests on Lemma 5.4, which is false as stated. Lemma 5.4 asserts that with theta = K sqrt(q/n), after O(theta sqrt n) operations the resulting pseudodistribution satisfies ||E'x||, ||E'y|| >= c theta sqrt n and ||E'xy^T||_F ≳ theta sqrt n. But for any x, y of unit norm (up to the 1/poly(n) slack in A'), every such pseudoexpectation satisfies ||E'x||^2 = sum_i (E' x_i)^2 <= E'||x||^2 <= 1 + n^{-beta}, similarly for y, and ||E'xy^T||_F <= E'||xy^T||_F = E'||x||||y|| <= 1 + n^{-beta}. Taking q=2 and K > max(1/c, 1/sqrt(2)) gives theta sqrt n = K sqrt(2), so the asserted lower bounds exceed 1, contradicting these universal upper bounds. The proof of Lemma 5.4 does not repair the issue: it balances O(Qn) first-phase pinnings against O(theta^2/Q) second-phase steps and concludes Q ≍ theta sqrt n, but the stationary point of Qn = theta^2/Q is Q = theta/sqrt n, not theta sqrt n; with Q = theta sqrt n the total round count becomes O(theta n^{3/2}), not O(theta sqrt n), and the resulting lower bound on the mean is sqrt(Q) = theta^{1/2} n^{-1/4}, not theta sqrt n. A corrected Lemma 5.4 would need to restate its auxiliary bounds at the scale sqrt(Q), which is too weak to feed the singular-vector argument in Theorem 5.1. The reader's secondary point that ||R||_F >= sqrt(q)/n in Theorem 5.1 is not a consequence of Lemma 5.4 is not quite right: if Lemma 5.4(b) held, then ||R||_F ≳ K sqrt(q) would indeed imply ||R||_F >= sqrt(q)/n. The fatal problem is that Lemma 5.4(b) itself cannot hold. Consequently the q/n regime of Theorem 1.2 and the n^{O(sqrt q)} running-time improvement are unsupported as written.","agreement_with_reader":"partial"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper studies the Best Separable State (BSS) problem in the perfect-completeness regime, where a measurement operator M with BSS(M)=1 is given and the goal is to find product vectors x,y achieving value close to 1, or at least q/n for a parameter q. The main claimed contribution, Theorem 1.2, is an algorithm with running time n^{O(sqrt(n/epsilon))} for the 1 versus 1-epsilon regime and n^{O(sqrt(q))} for the 1 versus q/n regime, improving on the prior works [BKS17] and [BGGLT17]. The algorithm is a global-correlation-rounding scheme for the sum-of-squares relaxation, with a new potential-function analysis, and the paper also states a fine-grained pinning lemma of independent interest. The 1 versus 1-epsilon section develops a pinning lemma and a mean-rounding success condition; the 1 versus q/n section introduces affine reweighting, multiple final rounding steps, and a Lemma 5.4 that is supposed to guarantee certain lower bounds on the conditional means and on the Frobenius norm of the second-moment matrix. The fine-grained pinning lemma in Section 6 is proved via a potential-function recurrence.","tokens_in":36427,"tokens_out":15744,"duration_ms":153098,"significance":"If the claimed guarantees were correct, the paper would represent a substantial algorithmic improvement over the state of the art for BSS, and the fine-grained pinning lemma would be a useful measure-decomposition tool. The high-level approach of combining global correlation rounding with carefully chosen potential functions is appealing, and the warmup presentation in Section 2 is pedagogically valuable. The paper also gives credit to prior work and includes an unusually detailed AI-usage disclosure. However, the main second guarantee rests on a lemma that is internally inconsistent, and the first guarantee's pinning lemma also contains a scale error in its statement. These issues are not merely presentation problems: the proof of Theorem 5.1 and hence the advertised n^{O(sqrt(q))} bound are unsupported as written. The fine-grained pinning lemma in Section 6 appears plausible and is presented with a coherent recurrence analysis, but it cannot rescue the BSS claims.","major_comments":[{"comment":"Lemma 5.4 cannot hold as stated. For any pseudodistribution satisfying (9), the universal bounds ||E'x|| <= (1+n^{-beta})^{1/2}, ||E'y|| <= (1+n^{-beta})^{1/2}, and ||E'xy^T||_F <= (E'||x||^2)^{1/2}(E'||y||^2)^{1/2} <= 1+n^{-beta} follow from Jensen/Cauchy-Schwarz for pseudo-expectations. In the application in Theorem 5.1, theta = K sqrt(q/n), so theta sqrt(n) = K sqrt(q). Taking q=2 and n large enough that theta < c, part (b) of Lemma 5.4 asserts ||E'xy^T||_F is at least a constant times K sqrt(2), which exceeds the universal upper bound whenever the constant is positive and K is chosen large. Part (a) similarly asserts cK sqrt(q) >= 1 for K >= 1/(c sqrt(q)). The proof's instruction to choose K 'sufficiently large' therefore makes the contradiction unavoidable.","section":"Section 5.2, proof of Lemma 5.4"},{"comment":"The balancing in the proof of Lemma 5.4 is dimensionally inconsistent. The first phase costs O(Qn) pinnings by Lemma 4.7, and the second phase is bounded by O(theta^2/Q) increments. The sum Qn + theta^2/Q is minimized at Q = theta/sqrt(n), not at Q ~ theta sqrt(n) as claimed. With the claimed choice Q ~ theta sqrt(n), the total operation count becomes O(theta n^{3/2}), not O(theta sqrt(n)). With the correct balancing Q = theta/sqrt(n), the mean-anchoring step only yields ||m_x||, ||m_y|| >= theta^{1/2} n^{-1/4}, not the c theta sqrt(n) lower bounds asserted in parts (a) and (b). Thus neither the operation count nor the auxiliary bounds of Lemma 5.4 follow from the proof as written.","section":"Section 5.6, proof of Theorem 5.1"},{"comment":"The final rounding argument for the 1 versus q/n regime depends essentially on the false auxiliary bounds in Lemma 5.4. In the singular-value case, the proof needs ||R||_F >= sqrt(q)/n to control the additive n^{-2} error in Lemma 5.3; Lemma 5.4(b) would supply this only if it were true, and it is not. In the mean case, the proof uses Lemma 5.4(a) to ensure that the best-response candidates exceed q/n. Since Lemma 5.4 is false, Theorem 5.1 and hence the second guarantee of Theorem 1.2 are unsupported. The reader's secondary point that sqrt(q)/n is not a consequence of Lemma 5.4 is not the core issue: if part (b) held at the stated theta sqrt(n) scale, the implication would be immediate. The core issue is that part (b) is impossible under the unit-norm constraints.","section":"Section 4.2, Lemma 4.5(b)"},{"comment":"The same type of scale error appears in the 1 versus 1-epsilon section. Lemma 4.5(b) asserts that the conditioned means satisfy ||E'x||, ||E'y|| >= gamma sqrt(n) for every 0 < gamma <= 1. For gamma sqrt(n) > 1, which occurs for any fixed positive epsilon when n is large, this violates the universal upper bound ||E'x|| <= (1+n^{-beta})^{1/2}. The proof of Theorem 4.1 uses part (b) only to control the term n^{-beta}/(||m|| ||q||), and a much weaker lower bound of order gamma/sqrt(n), or the gamma^{-1/2} n^{-1/4} actually delivered by the mean-anchoring step with Q ~ 1/(gamma sqrt(n)), would suffice for that purpose. This is a local fix, unlike the Section 5 issue, but as stated Lemma 4.5 is false and the proof of Theorem 4.1 cites the false statement.","section":"Section 4.4, proof of Theorem 4.1"}],"minor_comments":[{"comment":"The exposition of the first phase mixes squared and unsquared norm notation: 'both ||E x||_2 and ||E y||_2 will be at least sqrt(log n/(epsilon n))' should refer to the square of the norm or to the contribution to the squared norm, and the subsequent display 'epsilon * ||E x||_2^2 ||E y||_2^2 >= 1/2 * sqrt(epsilon log n/n) * Phi' should be written with consistent quantities.","section":"Algorithm 4.3"},{"comment":"The notation in Algorithm 4.3 is confusing: the variable eE is reused for both the input pseudodistribution and the conditioned pseudodistribution, and the symbol eEr appears without definition. Please introduce distinct names for the input, the conditioned object, and the pseudo-expectation operator.","section":"Section 6, Lemma 6.1"},{"comment":"The relationship between the parameter gamma in Lemma 6.1 and the parameter epsilon in the stated Theorem 2.7 is not made explicit. A reader cannot directly verify that the two statements are equivalent, especially because Theorem 2.7 is phrased as an upper bound on E||Cov||_F in terms of the mean, while Lemma 6.1 is phrased as a lower bound on the mean drift in terms of E||Cov||_F. Please state the parameter translation and show that the displayed min{} expression is the correct formal version of the informal statement.","section":"Section 5.4"},{"comment":"In the proof of Lemma 5.14, the line 'E[XY] = sigma_x^2(-1/2 + O(delta) + O(sqrt(delta Q)/sigma_x))' should specify whether the final error term is negligible compared to the main term under the stated assumptions. The current presentation makes the subsequent substitution 'sqrt(Q)/sigma_x <= ||m_x||/sigma_x' appear only after the fact.","section":"Section 2.4, Figure 1"},{"comment":"The caption of Figure 1 says 'noticeable fraction of conditional distributions' but the theorem statement is an in-expectation statement over the measure decomposition. Please clarify whether the intended claim is an expectation bound or a positive-measure bound.","section":"Section 1, AI usage statement"}],"recommendation":"reject","confidential_remarks":"The scale inconsistency in Section 5 is severe and load-bearing: Lemma 5.4 is false under the very constraints of the problem, and the balancing in its proof is algebraically wrong. This is not a routine typo; the entire 1 versus q/n analysis is built on the impossible lower bounds. The 1 versus 1-epsilon section has a similar but locally fixable issue in Lemma 4.5(b), and the fine-grained pinning lemma of Section 6 may well be correct. I recommend rejection of the current manuscript, but I would look favorably on a future submission that contains only the 1 versus 1-epsilon result with a corrected pinning lemma and the fine-grained pinning lemma, should those be properly established. The paper's extensive AI-usage disclosure is noted; it does not by itself affect my assessment, but it reinforces the need for the authors to re-derive Section 5 from first principles before resubmission."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Here's my take on arXiv:2608.10147. The paper has two headline results, and they are in very different shape.\n\nWhat is genuinely new and good: the 1 versus 1–ε regime. The authors give a much simpler global-correlation-rounding analysis of the BSS SoS relaxation and improve the BKS17 exponent from exp(√n (log n)^{O(1)}/ε²) to n^{O(√(n/ε))}. The proof in Section 4 looks coherent: the mean-rounding lemma, the new potential function Φ = 2(‖u‖²+‖v‖²+‖u‖‖v‖), and the pinning argument all hang together as far as I can tell. The fine-grained pinning lemma (Theorem 2.7 / Lemma 6.1) also seems plausible and is a genuinely useful contribution to the pinning-lemma toolbox. The paper is honest about AI assistance and about the simultaneous independent work; neither is a problem. The citation pattern is fine.\n\nNow the soft spot, which is not minor. Lemma 5.4, the engine of the 1 versus q/n regime, is false as stated. It claims that after O(θ√n) operations the conditional means satisfy ‖E'x‖, ‖E'y‖ ≥ c θ√n and ‖E'xy^T‖_F ≳ θ√n, where θ = K√(q/n). But θ√n = K√q, so for any q ≥ 1 and K > 1/c these lower bounds exceed 1, while the norm constraints in A'(β) force all these quantities to be at most 1 + n^{–β}. That is a hard contradiction, not a technical gap. The proof attempt also contains a balancing error: equating the O(Qn) first-phase pinnings with O(θ²/Q) second-phase steps gives Q = θ/√n, not Q ≍ θ√n as written. With Q = θ√n the total becomes O(θ n^{3/2}), not O(θ√n). So the n^{O(√q)} running time for the q/n guarantee is unsupported. The subsequent claim in Theorem 5.1 that ‖R‖_F ≥ √q/n would indeed follow from a correct version of Lemma 5.4(b), but that is cold comfort when (b) is impossible.\n\nIs this fixable? Possibly, but it is not a typo. The proof would need a different scaling for the auxiliary bounds, and it is not obvious that the weaker bounds can still feed the singular-vector rounding argument. Until Section 5 is rewritten, Theorem 1.2's second clause should be treated as unproven.\n\nWho is this for? People working on SoS rounding, BSS, QMA[2], and pinning lemmas. The first regime and the pinning lemma deserve a serious referee; the paper as a whole does too, but only with the expectation that Section 5 gets fixed or the q/n claim is withdrawn. I would not cite the q/n result in its current form.\n\nMy recommendation: send it to peer review, but flag Lemma 5.4 clearly and do not accept until the 1 versus q/n regime is repaired.","headline":"The 1 vs 1–ε result is a real, likely-correct advance; the 1 vs q/n result rests on a false lemma and is currently unsupported.","tokens_in":37125,"tokens_out":3687,"would_cite":false,"duration_ms":37618,"reading_group":"maybe","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["68Q17","68W20","81P68","90C22"],"pacs":[],"model":"deepseek-v4-flash","headline":"For measurements that accept some product state with probability 1, a pinning-based rounding finds near-optimal product states in time $n^{O(\\sqrt{n/\\varepsilon})}$ and product states with value $q/n$ in time $n^{O(\\sqrt{q})}$.","keywords":["best separable state","sum-of-squares relaxation","global correlation rounding","pinning lemma","quantum Merlin-Arthur games","rank-one matrix approximation","polynomial optimization","conditioning"],"falsifier":"For $q=2$ and large $K$, check whether Lemma 5.4's bounds can hold: with $\\theta=K\\sqrt{2/n}$, the asserted lower bounds $\\|\\mathbb{E}'x\\|, \\|\\mathbb{E}'y\\| \\ge c\\theta\\sqrt{n}$ individually exceed $1$ for unit vectors, so a direct counterexample to the lemma exists if the claim is taken literally; constructing one would settle whether the $n^{O(\\sqrt{q})}$ theorem is correct.","tokens_in":35761,"feed_emoji":"⚛️","tokens_out":10819,"duration_ms":98587,"temperature":0.7,"pith_summary":"The paper studies the best separable state problem: given a Hermitian matrix $M$ with $0 \\preceq M \\preceq I$, find the maximum of $\\langle x \\otimes y, M(x \\otimes y)\\rangle$ over unit vectors $x,y$, i.e. the largest acceptance probability of a measurement over unentangled states. In the perfect completeness case, where some product state is accepted with probability $1$, the paper claims a simple rounding algorithm for the sum-of-squares relaxation that finds a product state with value at least $1-\\varepsilon$ in time $n^{O(\\sqrt{n/\\varepsilon})}$, and a product state with value at least $q/n$ in time $n^{O(\\sqrt{q})}$. These running times improve the previous best exponents, and the search versions are solved in the same time. The argument is carried by iterated coordinate conditioning, with a potential function on conditional means, plus a new fine-grained pinning lemma stated as a measure decomposition of independent interest.","feed_headline":"Quantum product-state search in n^{O(√(n/ε))} time","feed_subtitle":"Also finds q/n-acceptance states in n^{O(√q)} time, improving on the earlier n^{O(q)} exponent.","key_machinery":"The load-bearing mechanism is a pinning lemma built on global correlation rounding. Starting from a degree-$t$ SoS pseudo-distribution over a discretized sphere, the algorithm conditions on coordinate values one at a time; the potential $\\Phi(u,v)=2(\\|u\\|^2+\\|v\\|^2+\\|u\\|\\|v\\|)$ on the conditional means increases by a fixed multiplicative factor whenever the desired small-covariance or low-soundness condition fails, so the number of conditioning steps is bounded by the budget $O(\\sqrt{n/\\varepsilon})$ or $O(\\sqrt{q})$. The success condition for the $1-\\varepsilon$ regime is $\\|\\mathrm{Cov}(x,y)\\|_F \\le \\gamma \\|\\mathbb{E}x\\|\\,\\|\\mathbb{E}y\\|$; when it holds, the mean pair is close to the accepting subspace because the relaxation forces $\\mathbb{E}[x\\otimes y]$ to lie in it. For the $q/n$ regime, affine-square reweighting is added and the final output is chosen among two best-response candidates and the top singular vectors of $R=\\mathbb{E}[xy^\\top]$.","core_discovery":"The central claim, Theorem 1.2, is that under $\\mathrm{BSS}(M)=1$ the SoS relaxation can be rounded by pinning only $O(\\sqrt{n/\\varepsilon})$ coordinates (for the $1-\\varepsilon$ guarantee) or $O(\\sqrt{q})$ coordinates and affine-square reweightings (for the $q/n$ guarantee). After that many steps, either the conditional cross-covariance is small compared with the product of the conditional means, or one of three low-soundness win conditions holds; the corresponding mean pair, best response, or top singular-vector pair then has the claimed value. The analysis shows the relaxation is infeasible in the NO cases, and in the YES case every witness can be discretized to a feasible point. The paper separately proves a fine-grained pinning lemma: a distribution on the sphere can be decomposed by conditioning on $O(\\sqrt{n}/\\gamma)$ coordinates, sampled so the decomposition is exact, and the expected Frobenius norm of the conditional covariance is at most $O(\\gamma)$ times the expected squared drift of the conditional mean.","pith_inferences":["The paper does not explore whether the exhaustive enumeration over all conditioning branches can be replaced by randomized or adaptive branch selection; if it can, the same pinning analysis would likely give a Las Vegas-style rounding with the same guarantees.","The potential-growth argument is not obviously specific to product states: any degree-4 relaxation whose pseudo-moment is constrained to lie in a subspace may admit the same low-soundness reweighting template, so the $n^{O(\\sqrt{q})}$ tradeoff may transfer to other rank-one-in-subspace problems.","The tightness example for the fine-grained pinning lemma suggests the $\\sqrt{n}$ in the exponent may be inherent for pinning-based rounding; reducing it to $O(\\log n)$ would require a different primitive, not just a sharper potential analysis.","One testable extension is to benchmark the conditioning budget empirically on planted instances: if the number of pinnings actually needed scales like $\\sqrt{n/\\varepsilon}$ rather than $\\log n$, that would support the analysis being tight rather than loose."],"forward_implications":["For $\\mathrm{BSS}(M)=1$ versus $\\mathrm{BSS}(M)\\le 1-\\varepsilon$, the $n^{O(\\sqrt{n/\\varepsilon})}$ runtime is subexponential for every $\\varepsilon = n^{-1+\\Omega(1)}$, which was not achieved by the previous $\\exp(\\sqrt{n}(\\log n)^{O(1)}/\\varepsilon^2)$ algorithm.","For $\\mathrm{BSS}(M)=1$ versus $\\mathrm{BSS}(M)\\le q/n$, the $n^{O(\\sqrt{q})}$ runtime improves on the earlier $n^{O(q)}$ algorithm whenever $q\\gg \\log^2 n$.","Both algorithms solve the search versions in the same running time, producing explicit unit vectors $x,y$ with the claimed acceptance probability.","The fine-grained pinning lemma gives an exact measure decomposition of a spherical distribution into conditionals with controlled covariance-to-mean-drift ratio, using $O(\\sqrt{n}/\\gamma)$ coordinates, and it applies to pseudo-distributions of corresponding degree.","Since BSS generalizes finding the closest rank-one matrix to a subspace guaranteed to contain one and upper-bounds two-prover quantum Merlin-Arthur games, the new exponents carry over as algorithmic upper bounds in those settings."],"supporting_citations":[{"why":"Sets the previous best algorithm for perfect-completeness BSS and introduces the SoS relaxation that this paper rounds.","marker":"[BKS17]"},{"why":"Gives the prior $n^{O(q)}$ algorithm that the $q/n$ regime improves on.","marker":"[BGGLT17]"},{"why":"Introduces global correlation rounding and the variance-drop inequality used in the potential growth argument.","marker":"[BRS11]"},{"why":"Establishes the QMA[2]/product-state testing connection and the ETH-based lower bound that motivates the runtime target.","marker":"[HM13]"},{"why":"Applies global correlation conditioning and pinning in SoS hierarchy rounding, the primitive this paper generalizes.","marker":"[RT12]"}],"fun_headline_variants":["Pinning lemma yields faster best separable state search","Simpler rounding for best separable state in n^{O(√(n/ε))} time","Best separable state: n^{O(√q)} runtime via global correlation","New pinning lemma speeds up quantum product-state search","Faster algorithm for best separable state with pinning"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The $q/n$ part of the main theorem depends on Lemma 5.4, which asserts that after $O(\\sqrt{q})$ pinning/reweighting operations one of three win conditions always holds together with specific quantitative lower bounds; if that lemma fails, the $n^{O(\\sqrt{q})}$ guarantee is not established.","fun_headline_variants_meta":{"raw":{"variants":["Pinning lemma yields faster best separable state search","Simpler rounding for best separable state in n^{O(√(n/ε))} time","Best separable state: n^{O(√q)} runtime via global correlation","New pinning lemma speeds up quantum product-state search","Faster algorithm for best separable state with pinning"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000247,"raw_usage":{"total_tokens":1652,"prompt_tokens":1163,"completion_tokens":489,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":779,"completion_tokens_details":{"reasoning_tokens":399}},"tokens_in":779,"tokens_out":489,"duration_ms":4919,"temperature":1.0,"reasoning_tokens":399,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-14T04:12:35.555074+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"For $q=2$ and large $K$, check whether Lemma 5.4's bounds can hold: with $\\theta=K\\sqrt{2/n}$, the asserted lower bounds $\\|\\mathbb{E}'x\\|, \\|\\mathbb{E}'y\\| \\ge c\\theta\\sqrt{n}$ individually exceed $1$ for unit vectors, so a direct counterexample to the lemma exists if the claim is taken literally; constructing one would settle whether the $n^{O(\\sqrt{q})}$ theorem is correct.","supporting_citations":[],"review_version":1}