{"id":"6ebc9fcc-c576-4fdf-ba1d-7a1cfeb6d0a4","arxiv_id":"2411.14224","paper_version":1,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":6.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":5,"one_line_summary":"A hybrid digital-thermodynamic interior-point algorithm for quadratic programming is proposed, with simulated support-vector-machine speedups of 10-30x at about 1000 dimensions.","lead":"The authors propose a hybrid computer that uses a physical thermal system to solve the linear equations inside an interior-point optimizer for quadratic programs, and they predict 10 to 30 times faster training for support vector machines around a thousand variables. If the hardware assumptions hold, the approach would give a polynomial speedup over exact digital solvers and a practical speedup for common optimization workloads.","discovery_kind":"new_method","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Speedup claim assumes inexact TLS Newton solves preserve O(sqrt(n+m) log(1/eps)) IPM iterations; neither the zero-mean thermal error nor the fixed lambda=0.1 regularization is shown to satisfy the residual conditions of the cited inexact-IPM theorems.","rationale":"The reader's weakest assumption identifies exactly the gap I see: the paper assumes without proof that the inexact Newton solves produced by the thermodynamic subroutine preserve the polynomial iteration bound of the interior-point method. My stress-test sharpens this in two ways. First, the TLS error is not simply 'small noise': the paper's own simulation uses a fixed regularization lambda = 0.1, which changes the Newton system and introduces a residual that does not vanish as mu_k goes to zero; this alone invalidates the O(log(1/eps)) convergence unless lambda is also shrunk with eps, which is neither stated nor reflected in the complexity table. Second, even for the unbiased thermal-averaging error, the residual condition in inexact-IPM theory is on J_k^T J_k times the solution error, so the tolerance must depend on the conditioning of the symmetrized KKT matrix; the paper does not make this dependence explicit or verify it numerically. These are correctness risks, not disagreements with consensus, and they are addressable by a numerical iteration-count experiment. Because the reader already conditioned acceptance on this point, I leave the verdict as UNCHANGED: the paper is promising but does not yet establish its headline asymptotic claim.","tokens_in":15402,"tokens_out":6001,"duration_ms":64123,"concrete_test":"Run a numerical version of Algorithm 2 on random feasible QPs with n = 50, 100, 200, 400 (and m ~ n/2), replacing the exact Newton solve by (i) adding zero-mean Gaussian noise with variance matched to the TLS finite-time averaging model and (ii) using the regularized matrix J_k^T J_k + 0.1 I. Count IPM iterations to reach primal-dual gap <= eps for eps = 1e-4, 1e-6, 1e-8, and compare to O(sqrt(n+m) log(1/eps)) and to an exact LU-based IPM baseline. If the iteration count grows faster than the predicted bound, or if the gap stalls at a lambda-dependent floor, then Table 1 does not describe convergence to the original QP solution.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The central complexity claim in Section 3.2.3 inherits the exact-IPM iteration count N = O(sqrt(n+m) log(1/eps)) from Eq. (6). For the hybrid algorithm this is only valid if every inexact Newton solve keeps the iterates in the N2-neighborhood of the central path. Section 3.2.2 asserts that Refs [33,34] provide update schemes for mu_k and alpha that preserve Eq. (6), but it does not identify which theorem applies, what residual or relative-error condition is required, or how the TLS error satisfies it. The error from finite-time thermal averaging is only asymptotically Gaussian; the paper does not derive a per-iteration integration time tau_k that guarantees the needed residual bound with the required probability. More importantly, the implementation in Figure 2 solves the regularized system (J_k^T J_k + 0.1 I) Delta r = J_k^T v_k, not Eq. (16). This introduces a deterministic bias whose residual is approximately 0.1 * ||Delta r||, independent of the barrier parameter mu_k. A fixed lambda therefore prevents the iterates from approaching the central path to arbitrary accuracy, so the O(log(1/eps)) convergence to the true QP solution is not established. Even ignoring the bias, the residual from a solution error delta_k is (J_k^T J_k) delta_k, so the tolerance on delta_k must be scaled by the norm or conditioning of J_k^T J_k; the complexity table does not track this coupling. Until these conditions are verified, the polynomial speedup over LU and CG is an assumption rather than a demonstrated result.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","summary":"The manuscript presents a hybrid thermodynamic-digital algorithm for convex quadratic programming. It embeds a thermodynamic linear solver (TLS) from Ref. [20] into an interior-point method, solving the symmetrized normal equations J_k^T J_k Δr = J_k^T v_k. The paper claims a polynomial asymptotic speedup over conventional digital approaches, gives a complexity analysis in Table 1, and reports SVM simulations with predicted 10–30x speedups. It also sketches applications to portfolio optimization and nonlinear resistive networks.","tokens_in":139,"tokens_out":9578,"duration_ms":105385,"significance":"If the central complexity and convergence claims were rigorously established, the paper would be a useful contribution to thermodynamic computing: it identifies a practical subroutine (IPM linear solves) that could be offloaded to analog hardware, and it provides a concrete hardware timing model and an open-source simulation package. The observation that only diagonal blocks of the symmetrized KKT matrix change between IPM iterations is a nice algorithmic insight. However, the missing error analysis for the inexact IPM and the use of fixed regularization mean that the asymptotic claims are not yet supported as stated.","major_comments":[{"comment":"The claimed asymptotic speedup over conjugate gradients is not present at the dominant order. Both the CG and thermodynamic rows contain O(n^3+m^3) for initialization and O(sqrt(n+m) log(1/eps)(n^2+m^2)) for the per-iteration work. The terms kappa^2(n+m)delta^{-2} and sqrt(kappa)(n+m)^2 are lower order than n^2+m^2 when n and m are of the same size and kappa and delta are treated as constants, so the two algorithms have identical leading-order complexity. The abstract's 'polynomial asymptotic speedup compared to conventional digital approaches' is therefore only valid relative to LU decomposition, not to CG; the paper should either restrict the speedup claim to LU or provide a complexity model that accounts for the different constant factors and hardware parallelism.","section":"3.2.3, Table 1"},{"comment":"The paper does not establish that the inexact-IPM iteration bound of Eq. (6) applies to the thermodynamic solver. Section 3.2.2 asserts that Refs. [33,34] provide update schemes, but it does not state the residual or relative-error condition required by those theorems, nor does it show that the zero-mean Gaussian error from Algorithm 1 satisfies it. Moreover, the implementation in Figure 2 solves (J_k^T J_k + 0.1 I) Delta r = J_k^T v_k rather than Eq. (16). The constant 0.1 regularization introduces a bias that is independent of the barrier parameter mu_k, so the iterates cannot approach the central path beyond a fixed tolerance; consequently, the O(sqrt(n+m) log(1/eps)) convergence to the QP solution is not established.","section":"3.2.2, Eq. (16), Figure 2"},{"comment":"The complexity table leaves delta, the accuracy of each thermodynamic linear solve, unspecified in relation to the QP accuracy epsilon. If the inexact IPM requires the Newton residual to decrease proportionally to mu_k (as is typical for path-following methods), then delta must decrease with epsilon (and possibly with conditioning), and the delta^{-2} factor would contribute an additional log(1/epsilon) or larger factor to the overall complexity. The paper should derive the required per-solve accuracy and include it in the complexity expression, rather than treating delta as an independent parameter.","section":"3.2.3, Table 1"},{"comment":"The numerical SVM experiments report training accuracy but not the KKT residual or optimality gap. Given the fixed regularization lambda=0.1, the results may reflect a regularized proxy rather than the original quadratic program. To support the practical speedup claim for QP solving, the authors should report the achieved optimality gap or constraint violation for the thermodynamic algorithm and compare it with the digital baselines on the same metric.","section":"4.1"}],"minor_comments":[{"comment":"Equation (11) appears to have sign errors: from Eq. (10) the Lagrangian should read 1/2 x^T Q x + (A^T mu + c)^T x - mu^T b, and the subsequent stationarity condition in Eq. (12) should be Qx + A^T mu = -c (or the sign convention should be fixed consistently).","section":"3.1, Eqs. (10)-(12)"},{"comment":"In the line 'rk+1 <- rk + (alpha_p Delta x, alpha_d Delta y, alpha_d Delta x)', the last component should presumably be alpha_d Delta z, not alpha_d Delta x.","section":"Algorithm 2"},{"comment":"The portfolio optimization problem in Eq. (22) includes an inequality constraint x^T r >= R, which is not in the standard form of Eq. (1); the conversion to an equality constraint via a slack variable should be stated.","section":"4.2"},{"comment":"The phrase 'identity vector' is nonstandard; it should be 'all-ones vector'.","section":"2.3"},{"comment":"Ref. [44] appears to duplicate Ref. [13] (both cite Kalinin et al. on the analog iterative machine); the two should be consolidated or distinguished.","section":"References"}],"recommendation":"major_revision","confidential_remarks":"The paper relies heavily on the authors' own Ref. [20] for the TLS complexity bound and on a hardware timing model from the same group (Appendix 2). This is not inherently problematic, but the refereeing should verify that the cited TLS complexity is indeed as stated and that the convergence theorems in Refs. [33,34] are applicable to the specific error model used here. The duplicate reference and sign errors suggest the manuscript would benefit from a careful revision before publication."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"First, what's actually new: the paper embeds a thermodynamic linear solver inside an interior-point method for QP, and it makes the hybrid approach viable by showing that the symmetrized normal equations J^T J can be updated in O(n+m) per iteration because only the diagonal blocks involving X_k and Z_k change. That update trick is the real contribution. It's not in the earlier thermodynamic-linear-algebra papers, and it's what makes the acceleration idea specific and potentially practical. The SVM simulation is a genuine attempt to estimate real-world performance, and the authors are transparent about the timing model.\n\nWhere the paper falls short: the abstract's \"polynomial asymptotic speedup\" is only true against LU. Against CG, both algorithms have the same leading-order complexity: O(n^3+m^3 + sqrt(n+m) log(1/eps)(n^2+m^2)). The thermodynamic linear-solve term is smaller in the subdominant bracket, but for large n the n^2 term dominates. So the claim as stated is misleading.\n\nThe bigger gap is the inexact IPM. Section 3.2.2 cites Refs [33,34] but doesn't verify that the TLS error satisfies the residual conditions those theorems need. The thermal time-average error is only asymptotically Gaussian; no per-iteration tau_k is derived. And the numerical experiments replace the Newton system with (J^T J + 0.1 I), which introduces a fixed bias. That bias is fine if you're willing to accept ~1-2% training accuracy loss, but it means the O(log(1/eps)) convergence to the true QP solution is not established. The complexity table silently assumes exact convergence.\n\nThe timing model is plausible but has hand-set parameters (RC=1us, 16-bit, 100Mb/s). The predicted 10-30x speedup at n~1000 is a model prediction, not a measurement.\n\nNone of this makes the paper worthless. The core idea is good, the writing is clear, and the authors are honest about the regularization's effect on accuracy. But the theoretical claims need to be scaled back to what is actually proven: a speedup over LU, not over CG, and a heuristic practical speedup subject to hardware validation. The inexact-IPM convergence should either be worked out or presented as a conjecture. I'd send this to a serious referee — it deserves careful review, and the fix is doable — but I'd want major revision before acceptance.","headline":"A genuine algorithmic contribution — embedding a thermodynamic linear solver in an interior-point method with an O(n+m) diagonal-block update — but the asymptotic speedup claim is overstated and the inexact-IPM convergence is asserted rather than demonstrated.","tokens_in":16322,"tokens_out":5037,"would_cite":false,"duration_ms":45878,"reading_group":"maybe","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":[],"pacs":[],"model":"deepseek-v4-flash","headline":"Quadratic programs can be solved faster by letting a thermal physical system do the linear algebra inside an interior-point method; the paper claims a polynomial asymptotic speedup and predicts 10–30× speedups on support vector machines.","keywords":["thermodynamic computing","quadratic programming","interior-point methods","linear system solving","analog computing","support vector machines","portfolio optimization","resistive networks"],"falsifier":"One concrete test: run Algorithm 2 on a family of random QPs of increasing size $n$ with a fixed condition number $\\kappa$ (e.g., by scaling $Q$), and count the number of interior-point iterations until the barrier parameter $\\mu$ drops below a fixed threshold. If the iteration count grows faster than $O(\\sqrt{n+m}\\log(1/\\epsilon))$, or if the algorithm fails to converge for moderately ill-conditioned problems with regularization $\\lambda=0.1$, then the claimed polynomial speedup does not hold. A second check is to measure the actual residual $\\|\\tilde{J}_k\\Delta r_k-\\tilde{v}_k\\|$ produced by the thermal time-average and compare it with the per-iteration error bounds in the inexact-IPM theorems the paper cites.","tokens_in":15246,"feed_emoji":"⚡","tokens_out":6689,"duration_ms":55765,"temperature":0.7,"pith_summary":"Quadratic programming is a convex optimization framework with applications in machine learning, finance, and circuit design, and its standard interior-point solvers repeatedly solve large linear systems. This paper claims that those linear-system solves can be offloaded to a thermodynamic computer—a physical system that relaxes to thermal equilibrium and whose time-averaged position solves a linear system—producing a hybrid digital-analog interior-point method. The claimed result is a polynomial asymptotic speedup over conventional digital solvers such as LU decomposition, with complexity $O(n^3+m^3+\\sqrt{n+m}\\log(1/\\epsilon)[n^2+m^2+\\kappa^2(n+m)\\delta^{-2}])$ versus $O((n+m)^{7/2}\\log(1/\\epsilon))$. Simulations on a support vector machine task predict a 10–30× speedup at around a thousand dimensions with a small loss in training accuracy. If this holds, thermodynamic hardware becomes a practical accelerator for a broad class of optimization problems, not just a theoretical curiosity.","feed_headline":"Thermodynamic hardware accelerates quadratic programming","feed_subtitle":"Moving interior-point linear solves to a thermal analog chip beats LU scaling, with 10–30× speedups predicted for SVMs.","key_machinery":"The central object is the thermodynamic linear solver (TLS), which maps a linear system $Qx=c$ to a quadratic potential $V(x)=\\frac12 x^\\top Qx-c^\\top x$ and reads off the solution as the time-averaged position $\\langle x\\rangle=\\frac1\\tau\\int_{t_0}^{t_0+\\tau}x(t)\\,dt$ after the system thermalizes. The paper inserts this solver into the interior-point method by symmetrizing each KKT Jacobian $J_k$ into $\\tilde{J}_k=J_k^\\top J_k$, a positive-semidefinite matrix that the TLS requires; the crucial efficiency comes from the fact that only the diagonal blocks $X_k^2,Z_k^2,X_kZ_k$ change between iterations, so the GPU computes those $O(n+m)$ updates and transfers them to the analog chip while the expensive matrix-matrix products are done once at initialization.","core_discovery":"The paper's central claim is that quadratic programs can be solved faster by replacing the linear-system solve inside an interior-point method with a thermodynamic linear solver. The key structural observation is that the symmetrized Newton system $\\tilde{J}_k\\Delta r_k=\\tilde{v}_k$ with $\\tilde{J}_k=J_k^\\top J_k$ can be updated between iterations by changing only the diagonal blocks $X_k^2$, $Z_k^2$, and $X_kZ_k$, so the per-iteration cost of maintaining the matrix on analog hardware is $O(n+m)$ rather than $O(n^3+m^3)$. The paper states that this reduces the total runtime to $O(n^3+m^3+\\sqrt{n+m}\\log(1/\\epsilon)[n^2+m^2+\\kappa^2(n+m)\\delta^{-2}])$, which is polynomially faster than the LU-based IPM's $O((n+m)^{7/2}\\log(1/\\epsilon))$, and it reports SVM simulations predicting 10–30× speedups at ~1000 dimensions with minimal accuracy loss.","pith_inferences":["The diagonal-only update structure may also appear in KKT symmetrizations for other convex programs, such as certain second-order cone or semidefinite programs, which would let the same thermodynamic speedup extend beyond QPs; the paper raises this possibility but does not analyze it in detail.","The zero-mean Gaussian error of the thermal average suggests a clean accuracy-versus-time trade-off: longer integration $\\tau$ reduces $\\delta$ and hence the $\\delta^{-2}$ factor, so an optimal $\\tau$ could be chosen per iteration to balance total runtime; the paper does not derive such a schedule.","The predicted 10–30× speedup assumes 16-bit digital-analog conversion at 100 Mb/s; if real applications require higher precision, the DAC/ADC transfer time will grow and could erode the advantage, making the speedup precision-dependent rather than absolute.","If the inexact-IPM convergence theorems are satisfied by the thermal error model, the same hybrid construction would also accelerate the sequential quadratic programming extension the paper sketches, effectively carrying the speedup over to general nonlinear optimization."],"forward_implications":["Quadratic programs of dimension roughly a thousand can be solved 10–30 times faster on hybrid GPU/thermodynamic hardware than with LU or conjugate-gradient solvers, at the cost of a small accuracy loss in SVM experiments.","The same diagonal-block update trick makes the interior-point linear solve a cheap $O(n+m)$ operation per iteration on the analog side, which is what turns the asymptotic gain into a practical one.","The method extends directly to equality-constrained QPs and to three showcased applications: support vector machines, portfolio optimization, and simulation of nonlinear resistive networks.","Because the complexity scales as $\\kappa^2\\,\\delta^{-2}$ in the condition number and solver error, the speedup is largest when the symmetrized KKT matrix is well-conditioned and moderate accuracy suffices.","The paper states that the approach can in principle be carried by any hardware accelerator for linear algebra, not only resistive networks, so the speedup may transfer to other analog platforms."],"supporting_citations":[{"why":"Supplies the thermodynamic linear solver (TLS) that solves each Newton system via thermal time-averaging; the paper's speedup rests on this subroutine.","marker":"[20]"},{"why":"Supplies the $O(\\sqrt{n+m}\\log(1/\\epsilon))$ interior-point iteration bound and the central-path neighbourhood that the approximate updates must preserve.","marker":"[29]"},{"why":"Supplies the convergence analysis of an inexact feasible interior-point method for convex QPs, cited to justify that approximate Newton solves keep the iteration bound.","marker":"[33]"},{"why":"Supplies the global polynomial-time convergence result for infeasible interior-point methods using inexact computation, cited alongside [33] for the same purpose.","marker":"[34]"},{"why":"Supplies the cross-point resistive array hardware concept that motivates the assumed analog matrix-encoding and time-averaging capabilities.","marker":"[26]"},{"why":"Supplies the hybrid GPU/stochastic-processing-unit strategy of offloading linear algebra to analog hardware, the architectural template for Algorithm 2.","marker":"[19]"}],"fun_headline_variants":["Thermodynamic linear solves give polynomial speedup for QPs","Thermal chip beats LU for interior-point quadratic programming","Thermodynamic IPM predicts 10–30× SVM speedups","Interior-point method gets polynomial speedup from thermal hardware","Quadratic programming accelerated by a thermodynamic linear solver"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The load-bearing premise is that the interior-point iteration count $O(\\sqrt{n+m}\\log(1/\\epsilon))$ remains valid when each Newton system is solved only approximately by the thermodynamic solver, whose output error is a zero-mean Gaussian whose magnitude depends on integration time and on an added $\\lambda=0.1$ regularization; the paper cites two earlier convergence analyses for inexact interior-point methods but does not prove that this particular error model satisfies their residual or relative-error conditions.","fun_headline_variants_meta":{"raw":{"variants":["Thermodynamic linear solves give polynomial speedup for QPs","Thermal chip beats LU for interior-point quadratic programming","Thermodynamic IPM predicts 10–30× SVM speedups","Interior-point method gets polynomial speedup from thermal hardware","Quadratic programming accelerated by a thermodynamic linear solver"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000346,"raw_usage":{"total_tokens":1859,"prompt_tokens":869,"completion_tokens":990,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":485,"completion_tokens_details":{"reasoning_tokens":908}},"tokens_in":485,"tokens_out":990,"duration_ms":8379,"temperature":1.0,"reasoning_tokens":908,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-12T15:25:47.365093+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"One concrete test: run Algorithm 2 on a family of random QPs of increasing size $n$ with a fixed condition number $\\kappa$ (e.g., by scaling $Q$), and count the number of interior-point iterations until the barrier parameter $\\mu$ drops below a fixed threshold. If the iteration count grows faster than $O(\\sqrt{n+m}\\log(1/\\epsilon))$, or if the algorithm fails to converge for moderately ill-conditioned problems with regularization $\\lambda=0.1$, then the claimed polynomial speedup does not hold. A second check is to measure the actual residual $\\|\\tilde{J}_k\\Delta r_k-\\tilde{v}_k\\|$ produced by the thermal time-average and compare it with the per-iteration error bounds in the inexact-IPM theorems the paper cites.","supporting_citations":[{"cited_title":"Foundations of operations research: From linear programming to data envelopment analysis,","cited_arxiv_id":null,"evidence_quote":"Supplies the $O(\\sqrt{n+m}\\log(1/\\epsilon))$ interior-point iteration bound and the central-path neighbourhood that the approximate updates must preserve."},{"cited_title":"Convergence analysis of an inexact feasible interior point method for convex quadratic programming,","cited_arxiv_id":null,"evidence_quote":"Supplies the convergence analysis of an inexact feasible interior-point method for convex QPs, cited to justify that approximate Newton solves keep the iteration bound."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Supplies the global polynomial-time convergence result for infeasible interior-point methods using inexact computation, cited alongside [33] for the same purpose."},{"cited_title":"Thermodynamic state machine network,","cited_arxiv_id":null,"evidence_quote":"Supplies the hybrid GPU/stochastic-processing-unit strategy of offloading linear algebra to analog hardware, the architectural template for Algorithm 2."}],"review_version":1}