{"id":"5c10b0b3-b15c-4ac7-be00-3bb14e0dd5f7","arxiv_id":"1908.02210","paper_version":2,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":5.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":2,"one_line_summary":"A QAOA variant with a linear penalty for knapsack-style battery scheduling achieves roughly 95 percent of optimal revenue at shallow circuit depth in small simulated instances.","lead":"This paper tests two quantum optimization algorithms for scheduling battery charging in electricity markets, where the problem reduces to the knapsack problem. The relaxed approach reported about 95 percent of optimal revenue with shallow circuits, but only in small simulations and with no shared code.","discovery_kind":"new_application","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Reported 0.95 ratios are measured against the penalized objective, not the feasible knapsack optimum; with alpha=1 the two optima can differ substantially, so the central near-optimality claim is not established.","rationale":"The reader identified the fixed linear angles and alpha=1 as the weakest assumption. That concern is valid, but this stress-test finds a more fundamental issue: the performance metric itself may not measure what the abstract claims. Section 5.1 defines ratio over 'the optimal value for the chosen target function,' and for the with-penalty simulations the chosen target function includes a linear penalty with alpha=1. Because the penalty coefficient is finite and arbitrary, the maximizer of the penalized objective can violate the knapsack constraint. In that case, a ratio near 0.95 tells us nothing about approximation quality for the original battery revenue problem. This is not a question of parameter generalization; it is a mismatch between the stated problem and the measured quantity. The paper's conclusion that the linear penalty 'has appeared more successful' therefore needs to be re-evaluated against feasible schedules. The reader's suggested sensitivity analysis for alpha and angles should still be done, but it is secondary to establishing the correct baseline. A concrete re-scoring of the stored simulation data, or a fresh small simulation, would settle the concern. I keep the conditional verdict because the algorithmic construction is not disproven, but the central performance claim is not yet supported.","tokens_in":12665,"tokens_out":10144,"duration_ms":110423,"concrete_test":"Take the n=5, p=12 entry in Table 3 (reported ratio 0.971). Re-run the exact circuit simulation on the same random instances, but score each sampled bitstring by its true return if cost <= Cmax and by 0 otherwise; compare the best and average feasible return to the optimal feasible knapsack value computed by dynamic programming. Also compute the optimum of the penalized objective and check whether it is attained by an infeasible schedule. If the feasible ratio drops materially below 0.95, or if the penalized optimum is infeasible on any instance, the headline near-optimality claim fails.","verdict_should_be":"CONDITIONAL","load_bearing_attack":"The abstract's central claim ('approximations about 0.95 of the optimum') is only meaningful if the baseline is the original constrained revenue maximization. Section 5.1, however, defines the ratio as 'the value of the output of the algorithm over the optimal value for the chosen target function.' For the with-penalty simulations (Section 5.3.2), the target function is f(z) = return(z) + penalty(z), with penalty(z) = -alpha*(cost(z)-Cmax) for cost(z) >= Cmax and alpha set to 1. A finite linear penalty does not enforce the original constraint: whenever the marginal return of an infeasible schedule exceeds alpha times its excess cycle cost, the maximizer of f is infeasible for the original knapsack problem. For example, with Cmax=n, c_t^1=2, lambda_t^1=5, lambda_t^2=0, the all-M1 schedule has return 5n, cost 2n, and penalized value 4n, while the best feasible value is about 2.5n. Thus ratios near 0.95 against the penalized optimum do not imply 0.95 of the feasible optimum. The paper reports no constraint-violation rate and no comparison against the optimal feasible schedule. The fixed linear QAOA schedule (Section 2.2) and arbitrary alpha are untested hyperparameters, as the reader notes, but the baseline-objective mismatch is logically prior: even perfectly optimized angles would not fix an evaluation against the wrong optimum. Re-scoring the simulated outputs against feasible optima is required before the abstract's claim can be accepted.","agreement_with_reader":"partial"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper implements two QAOA variants for a battery revenue optimization problem modeled as a knapsack problem. The first variant enforces the capacity constraint through a quadratic penalty and an Ising reformulation, but simulations show non-convergent behavior for intermediate circuit depths. The second, 'relaxed' variant uses a non-Ising objective with a linear penalty, implemented with arithmetic and flag-qubit subroutines, and is claimed to run in O(p(log_2 n)^3) time with O(n log n) qubits. The main reported result is a roughly 0.95 approximation ratio of the optimal penalized objective at shallow depth (p <= 10), with an exponential improvement in the ratio as p increases. The paper concludes that the linear-penalty QAOA is a promising way to handle constrained problems with shallow circuits.","tokens_in":12971,"tokens_out":5243,"duration_ms":56643,"significance":"If the central claim is established after correcting the evaluation baseline, the paper would be a useful proof-of-concept for applying QAOA to constrained, non-Ising optimization problems. The proposed circuit construction for computing a linear penalty is novel and nontrivial, and the explicit complexity estimates (polylogarithmic depth in n, O(n log n) qubits) are valuable. The paper also provides concrete simulation tables over random instances and is honest about the arbitrary choice of alpha. However, the current evidence does not yet support the abstract's near-optimality claim because the reported ratios are measured against the penalized objective rather than the feasible knapsack optimum, and the statistical support for the exponential-improvement claim is thin.","major_comments":[{"comment":"The reported approximation ratios for the with-penalty experiments are measured against the penalized objective f(z) = return(z) + penalty(z), not against the original feasible knapsack optimum. Section 5.1 defines the ratio as 'the value of the output of the algorithm over the optimal value for the chosen target function,' and in Section 5.3.2 the target function includes the linear penalty with alpha = 1. A finite linear penalty does not enforce the capacity constraint: with Cmax = n, c_t^1 = 2, lambda_t^1 = 5, lambda_t^2 = 0, the all-M1 schedule has return 5n, cost 2n, and penalized value 4n, while the best feasible value is about 2.5n. Thus ratios near 0.95 against the penalized optimum do not imply 0.95 of the feasible optimum. The paper reports no constraint-violation rate and no comparison against the optimal feasible schedule. Re-scoring the simulated outputs against the feasible optimum is required before the abstract's claim can be accepted; the 'without penalty' experiments do not provide such a benchmark because they solve an unconstrained selection problem.","section":"Section 5.1 and 5.3.2, Eq. (12)"},{"comment":"The 'exponential improvement' claim is not statistically supported. The tables report only mean ratios over 1000 random instances, with no standard deviations, confidence intervals, or significance tests. The with-penalty results stop at n = 7 and contain missing entries for n = 6 at p >= 9 and for n = 7 at p >= 7, while the text refers to behavior for n = 8 without data. With one mean per condition, the reader cannot assess whether the apparent improvement with p is real or within sampling noise, nor can the functional form of the claimed exponential improvement be checked. The authors should report distributions or error bars and specify the fitted curve used to infer exponential scaling.","section":"Section 5.3.2, Table 3 and Figures 17-18"},{"comment":"The fixed linear annealing schedule beta_k = 1 - k/p, gamma_k = k/p and the penalty coefficient alpha = 1 are untested hyperparameters. The paper itself states that alpha = 1 is 'arbitrary.' Since the central near-optimality result depends on these choices, the claim should either be tested over a range of alpha values and at least one alternative angle schedule, or explicitly stated as conditional on these specific choices. Without such testing, the reported approximation ratios could be specific to this parameter setting rather than a property of the algorithm.","section":"Section 2.2 and Section 5.3.2"}],"minor_comments":[{"comment":"The text says 'We present below two implementations to compute e^{-i*gamma*return(z)}' but the surrounding discussion is about the penalty part; this appears to be a typo for the penalty Hamiltonian.","section":"Section 4.4"},{"comment":"In the introduction to Subroutine 1, 'As stated in Equation ??' has an unresolved equation reference; the bound d = max c_t^i should be stated explicitly at first use.","section":"Section 4.4.1"},{"comment":"The text says 'It seems to sink for n = 8' but Table 3 contains no n = 8 row; either add the data or remove the speculation.","section":"Section 5.3.2"},{"comment":"Several entries read 'NO DAT'; these should be replaced with actual values or the reasons for their absence should be explained in the caption.","section":"Table 3"},{"comment":"The complexity derivation is a sketch: the number of steps and the ancillary-qubit count are described in words, and the phrase 'The subroutine 2 takes therefore a shortest time' should read 'a shorter time.' A more formal accounting of circuit depth and qubit reuse would make the O(p(log n)^3) and O(n log n) claims easier to verify.","section":"Appendix B"},{"comment":"The figures plot 'ratio versus P' but do not state what quantity is used to infer an exponential improvement; the authors should define the plotted data and describe any fitted curve in the captions.","section":"Figures 16 and 18"}],"recommendation":"major_revision","confidential_remarks":"The baseline-objective issue is the key obstacle: the paper's main numerical claim is currently not about the quantity stated in the abstract. If the authors can re-score their simulations against feasible optima and report constraint-violation rates, the manuscript could become publishable as a proof-of-concept study. If re-scoring shows materially lower ratios, the abstract and conclusion would need substantial rewriting. The small-n and missing-data issues are secondary but should also be addressed."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Read 1908.02210. The useful kernel is real: they build a QAOA circuit for a non-Ising objective and handle a linear knapsack-type constraint with reversible arithmetic and a linear penalty. That is a genuine extension of the usual QAOA framework, and the O(p log^3 n) depth for the relaxed circuit is worth having in the literature. They also report that the constrained Ising variant fails, which is useful negative evidence, and they explicitly admit alpha=1 is arbitrary.\n\nThe problem is the headline number. Section 5.1 defines the ratio as the output over \"the optimal value for the chosen target function.\" With the penalty included and alpha=1, the penalized optimum is not the feasible optimum. When the marginal return of exceeding the cap is high enough, an infeasible schedule wins the penalized objective. So the 0.95 figures in the abstract do not mean 0.95 of the best feasible battery revenue, which is what a reader will naturally assume. The paper reports no constraint-violation rate and no comparison against the optimal feasible schedule. This is the load-bearing measurement issue, and it is logically prior to the hyperparameter concern: better angles would not fix an evaluation against the wrong baseline.\n\nOther soft spots are smaller but real. There are no error bars or statistical tests; the largest penalized simulations use only n=7, and Table 3 has missing entries. The \"exponential improvement\" claim comes from eyeballing small plots, not from a fitted curve or analysis. The fixed linear angle schedule is untested beyond these instances, and no code or data are released, so the results are not independently reproducible. Appendix B is a sketch; the idea is plausible, but it is not a tight complexity proof.\n\nThe method itself is not disproven. For tiny instances the ratios may hold up even against the feasible optimum, and the circuit construction is a legitimate contribution. But the paper has not shown that, and the abstract currently overstates what was actually evaluated.\n\nFor whom: people working on QAOA for constrained optimization and near-term industrial use cases. If this crossed my desk, I would not desk reject it; the non-Ising penalty construction deserves referee time. But I would send it back demanding a re-scoring against feasible optima, a constraint-violation rate, sensitivity analysis for alpha and the angle schedule, and code or at least the random instance data. Right now it is an interesting idea attached to a performance claim that has not been established.","headline":"The non-Ising QAOA with a reversible-arithmetic linear penalty is a real idea, but the paper's headline 0.95 claim is measured against the penalized objective, not the constrained knapsack optimum, so the performance claim needs re-scoring before it can be trusted.","tokens_in":13505,"tokens_out":2581,"would_cite":false,"duration_ms":29482,"reading_group":"maybe","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["68Q12","81P68","90C27"],"pacs":[],"model":"deepseek-v4-flash","headline":"This paper tries to establish that a relaxed, non-Ising QAOA encoding of the knapsack constraint reaches about 0.95 of the optimal battery revenue with shallow depth (p ≤ 10) and shows exponential improvement in depth, whereas the Ising…","keywords":["QAOA","knapsack problem","battery revenue optimisation","non-Ising objective function","linear penalty","constrained optimisation","near-term quantum computing","shallow circuits"],"falsifier":"Run the relaxed QAOA on the same random instance family with n = 10 and p = 12 while re-optimising the angles β, γ instead of using the fixed schedule; if the average approximation ratio falls below 0.9, the claim that shallow fixed-schedule depth suffices would be contradicted.","tokens_in":12455,"feed_emoji":"🔋","tokens_out":4183,"duration_ms":41647,"temperature":0.7,"pith_summary":"The paper studies two QAOA-based approaches to a battery revenue scheduling problem modelled as a knapsack problem. Its central claim is that a relaxed QAOA variant with a linear penalty, using a non-Ising objective function, reaches about 0.95 of the optimum with shallow depth (p ≤ 10) and exhibits exponential improvement as depth increases. The alternative constrained approach, which enforces the constraint through a quadratic Ising penalty, does not converge for intermediate depths up to p = 50. A careful reader would care because this is a concrete proposal for handling constrained industrial optimisation problems on near-term quantum hardware, with a circuit depth that grows only polylogarithmically in the problem size.","feed_headline":"Shallow QAOA hits 95 percent on knapsack battery schedules","feed_subtitle":"A relaxed QAOA with a linear penalty reaches ~0.95 of optimum at depth p≤10, while the Ising penalty stalls.","key_machinery":"The key object is the non-Ising target Hamiltonian whose phase operator U(C, γ) = $e^{{-iγ f(z)}}$ is built from four subroutines: cost calculation, constraint testing with a flag qubit, penalty dephasing, and reinitialisation by uncomputation. The linear penalty is enforced by rotating the flag-controlled phase by $e^{{iγα(cost(z)−Cmax)}}$, which makes the constraint violation enter the objective linearly rather than quadratically. This construction is what allows the relaxed approach to avoid the heavy quadratic penalty that stalls the Ising formulation.","core_discovery":"The central claim is that QAOA can approximate the optimal battery schedule by encoding the knapsack constraint as a linear penalty in the objective function rather than as a quadratic Ising penalty. The relaxed objective is f(z) = return(z) + penalty(z), where penalty(z) is zero when the cycle budget is respected and −α(cost(z) − Cmax) otherwise. The circuit uses O(n log n) qubits and has depth O(p(log n)^3), with the phase separation implemented through addition circuits, a constraint-testing flag, and controlled dephasing. Simulations on a qubit-level simulator report approximation ratios around 0.95 for p ≤ 10 and an exponential improvement in p, while the Ising constrained variant plateaus near 0.75 for p ≤ 50.","pith_inferences":["If the observed exponential improvement in depth persists at larger n, QAOA with a linear penalty could become a competitive heuristic for small knapsack instances, though this remains to be tested beyond n ≤ 7.","The fixed linear annealing schedule (β_k = 1 − k/p, γ_k = k/p) is likely not optimal; re-optimising the angles could push approximation ratios higher or reveal a different scaling with p.","The penalty coefficient α = 1 was chosen arbitrarily; varying α could trade off constraint satisfaction against revenue and might be necessary for problems with different return/cost scales.","The same relaxation strategy could apply to other weakly NP-hard problems with a single linear constraint, such as subset sum, where Ising penalties are known to create heavy objective weights."],"forward_implications":["Battery revenue schedules can be approximated with shallow QAOA circuits using the relaxed non-Ising encoding, provided the fixed angle schedule is kept.","The quadratic-penalty Ising route is not effective for this problem at shallow or intermediate depth, so further work on constrained QAOA should consider linear penalty encodings.","The circuit's depth O(p(log n)^3) and qubit count O(n log n) make the approach implementable for small problem sizes on near-term devices.","Linear constraints of the form sum w_t z_t ≤ Cmax can be handled in QAOA by the flag-controlled linear penalty technique, not only for knapsack but for a wider class of constrained binary optimisation problems."],"supporting_citations":[{"why":"Supplies the original QAOA framework and the convergence guarantee used to justify the algorithm.","marker":"[6]"},{"why":"Provides the knapsack Hamiltonian that the constrained approach adapts and the penalty structure it builds on.","marker":"[3]"},{"why":"Gives the adiabatic theorem that underlies the claim that QAOA works with any objective function.","marker":"[7]"},{"why":"Supports the choice of linear annealing angles by suggesting optimal angles may be close to linear for certain problems.","marker":"[5]"},{"why":"Further evidence that optimal QAOA angles can be close to a linear annealing schedule for some instances.","marker":"[17]"},{"why":"The simulator used for all reported experiments, providing the empirical basis for the approximation ratios.","marker":"[1]"}],"fun_headline_variants":["Relaxed QAOA hits 95% on knapsack battery revenue at shallow depth","Linear penalty yields 95% knapsack optimum for QAOA battery schedules","Shallow QAOA reaches 95% of optimum when penalty is linear","Exponential depth gain: relaxed QAOA hits 95% on knapsack","QAOA with linear penalty: 95% knapsack approximation at shallow depth"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The reported 0.95 approximation assumes that the fixed linear annealing schedule (β_k = 1 − k/p, γ_k = k/p) and the penalty coefficient α = 1 work on the small random instances tested; if these choices do not generalise, the exponential improvement and near-optimal ratios do not transfer.","fun_headline_variants_meta":{"raw":{"variants":["Relaxed QAOA hits 95% on knapsack battery revenue at shallow depth","Linear penalty yields 95% knapsack optimum for QAOA battery schedules","Shallow QAOA reaches 95% of optimum when penalty is linear","Exponential depth gain: relaxed QAOA hits 95% on knapsack","QAOA with linear penalty: 95% knapsack approximation at shallow depth"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.001158,"raw_usage":{"total_tokens":4757,"prompt_tokens":864,"completion_tokens":3893,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":480,"completion_tokens_details":{"reasoning_tokens":3788}},"tokens_in":480,"tokens_out":3893,"duration_ms":28401,"temperature":1.0,"reasoning_tokens":3788,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-14T14:49:59.166555+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Run the relaxed QAOA on the same random instance family with n = 10 and p = 12 while re-optimising the angles β, γ instead of using the fixed schedule; if the average approximation ratio falls below 0.9, the claim that shallow fixed-schedule depth suffices would be contradicted.","supporting_citations":[{"cited_title":"Adiabatic quantum computing solution of the knapsack problem","cited_arxiv_id":"1701.05584","evidence_quote":"Provides the knapsack Hamiltonian that the constrained approach adapts and the penalty structure it builds on."},{"cited_title":"A quantum adiabatic evolution algorithm applied to random instances of an NP-complete problem","cited_arxiv_id":null,"evidence_quote":"Gives the adiabatic theorem that underlies the claim that QAOA works with any objective function."},{"cited_title":"Performance of the Quantum Approximate Optimization Algorithm on the Maximum Cut Problem","cited_arxiv_id":null,"evidence_quote":"Supports the choice of linear annealing angles by suggesting optimal angles may be close to linear for certain problems."}],"review_version":1}