{"id":"941a46f1-1d0d-4b57-b3ef-7368161b7656","arxiv_id":"2412.12773","paper_version":1,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":4.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":3,"one_line_summary":"QAOA solves simplified, cost-weighted tail-assignment instances with up to 14 routes in simulation, but its time-to-solution grows faster than classical branch-and-price.","lead":"This paper applies QAOA, a hybrid quantum-classical algorithm, to small instances of the airline Tail Assignment Problem, where the goal is to assign aircraft to flights at minimum cost. Its main finding is that QAOA can find optimal solutions for tiny instances but scales much worse than classical branch-and-price, so no practical quantum advantage appears at current sizes.","discovery_kind":"extension","skeptic_critique":{"model":"deepseek-v4-flash","headline":"The QUBO-to-Ising mapping is internally inconsistent: Eq. 16's ZZ coupling is a factor of two too small, so the QAOA cost Hamiltonian does not represent the stated route-cost objective.","rationale":"I read the paper as claiming that the QAOA circuit built from Eqs. 14-17 optimizes Eqs. 11-12 and that the experiments evaluate that objective. The most load-bearing point is therefore the derivation of the Ising coefficients. Re-expanding Eq. 12 gives a factor of two in the pairwise term that Eq. 16 omits; this is not a modeling simplification but an internal inconsistency. It can be fixed, but as published the formula for the cost Hamiltonian is wrong, and absent code there is no way to tell whether the reported experiments used the corrected version. The reader's weakest assumption concerned the removed tail constraints; I agree that is an external-validity limitation, but it is explicitly scoped in Section III B. The internal coefficient discrepancy is more immediate because it affects even the simplified set-partitioning problem. Therefore I recommend rejecting the current manuscript, while noting that a corrected derivation and rerun would justify reconsideration.","tokens_in":9437,"tokens_out":26112,"duration_ms":246271,"concrete_test":"Using the smallest nontrivial instance from Section IV, or the two-route one-flight example above, enumerate all bitstrings and verify whether H built from Eqs. 14-17 satisfies H|x> = Q(x)|x> as required by Eq. 2. If the two energy lists are not equal up to a common positive scale plus a constant, correct J_rr' to (P/2) sum_f a_fr a_fr', fix the constant in Eq. 17, rerun the Section IV A experiments and Figure 9, and compare the success-probability and TTS curves. If the authors release their code, checking the implemented ZZ rotation coefficient settles the point directly.","verdict_should_be":"REJECT","load_bearing_attack":"Re-expanding Eq. 12 under Eq. 13 gives a cross term 2P sum_f a_fr a_fr' x_r x_r', hence the Ising coupling must be J_rr' = (P/2) sum_f a_fr a_fr'; Eq. 16 gives P/4. Eq. 15 is consistent with the full factor, so Eqs. 15 and 16 cannot both be correct, and Eq. 17's constant does not match the same expansion. For instance, with P=1 and route costs (1,2) on one flight covered by two routes, Eq. 12 has energies (1,1,2,4) for bitstrings (00,10,01,11), while Eqs. 15-17 give (0.25,0.75,1.75,3.25), a non-affine mismatch. The Hamiltonian actually minimized by QAOA therefore differs from the TAP objective in Eq. 11, so the success probabilities in Section IV A and the TTS comparison in Figure 9 are not anchored to the stated problem unless the implementation silently corrects the formulas.","agreement_with_reader":"partial"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper applies the Quantum Approximate Optimization Algorithm (QAOA) to a simplified version of the Tail Assignment Problem (TAP). The authors formulate the problem as a QUBO with a coverage penalty, map it to an Ising Hamiltonian, and solve small instances (4–15 routes) built from BTS flight data with ICAO-based route costs. They report that QAOA with INTERP parameter initialization finds high-probability optimal solutions when enough layers are used, that higher route-graph valency makes instances harder, and that QAOA's time-to-solution scales worse than branch-and-price and quantum annealing on these sizes.","tokens_in":9677,"tokens_out":17193,"duration_ms":139052,"significance":"If the formulation were correct, the paper would provide a useful empirical benchmark of QAOA on a realistic, cost-weighted airline scheduling problem, and its honest comparison with classical methods would be a valuable data point for quantum optimization research. The use of real flight data, ICAO cost figures, and the INTERP initialization are positive features. However, the central derivation of the Ising coefficients is flawed, which calls into question whether the experiments actually solve the problem stated. The paper's scope is also narrower than its title suggests, since the tail-assignment and unassigned-flight variables are removed.","major_comments":[{"comment":"The Ising coefficients in Eqs. (15)–(17) are algebraically inconsistent with the QUBO in Eq. (12) under the substitution x_r = (1 − σ^z_r)/2 of Eq. (13). Expanding the penalty term in Eq. (12) gives a quadratic cross-term 2P Σ_f a_{fr} a_{fr'} x_r x_{r'}, which after substitution yields a ZZ coupling J_{rr'} = (P/2) Σ_f a_{fr} a_{fr'}, not P/4 as written in Eq. (16). Correspondingly, the constant term in Eq. (17) is off by −(P/4) Σ_f (Σ_r a_{fr}) relative to the correct expansion. The h_r coefficient in Eq. (15) is correct. Because Eqs. (16) and (17) are wrong, the cost Hamiltonian actually minimized by QAOA is not an affine image of Q(x). In fact, for flights covered by more than two routes, the effective penalty contribution in the wrong Hamiltonian can become negative, so the ground state may be infeasible even for arbitrarily large P. This directly affects the success probabilities in Section IV A and the time-to-solution comparison in Figure 9. Please correct Eqs. (16) and (17), and state clearly whether the simulations used the printed coefficients or the correct expansion. If the printed (incorrect) coefficients were used, the experimental results need to be re-evaluated.","section":"Section III B 1, Eqs. (15)–(17)"},{"comment":"The reduction from Eq. (1) to Eq. (11) assumes that all flights can be assigned and that there are enough aircraft, each suitable for any route, thereby removing the variables u_f and v_t. This reduces the problem to a set-partitioning problem over routes, not the full Tail Assignment Problem as defined in Eq. (1). The abstract and conclusions state that 'the TAP is successfully solved using QAOA' without this caveat. The claims should be explicitly qualified to say that a simplified variant of TAP is being solved, since the tail-usage constraint and aircraft-route eligibility are not modeled.","section":"Section III B"},{"comment":"The penalty weight P in Eq. (12) is never specified for any instance or experiment. P controls the trade-off between route costs and flight-coverage constraints; without P values, the results are not reproducible, and the statement that violating configurations are 'discouraged' depends on P. Please report the P values used in Section IV and provide a sensitivity analysis showing that the reported success probabilities and TTS values are stable with respect to the choice of P.","section":"Section IV"},{"comment":"The time-to-solution comparison in Figure 9 is not clearly defined. The text says 'TTS for different instances using different methods,' which may mean that each method was run on different problem instances. In particular, the QA TTS values are attributed to reference [20], a review, suggesting they are not computed on the same instances generated for this paper. A meaningful scalability comparison requires that all methods solve identical instances. Please clarify the benchmarking protocol, state explicitly whether the same instances were used, and if not, explain how the comparison supports the scalability conclusions.","section":"Section IV B, Figure 9"}],"minor_comments":[{"comment":"The heading 'ectionResults applying QAOA' appears to be truncated or mis-formatted; the section structure should be fixed.","section":"Section IV A"},{"comment":"The word 'Formulation' is typeset as 'F ormulation' in the section heading.","section":"Section III B"},{"comment":"The cost data in Table I is attributed to a generic ICAO/DOT Form 41 source without specifying the actual data file or date. Please provide a precise citation for the operating costs.","section":"Table I"},{"comment":"The symbol 'log' in Eq. (18) should be specified as the natural logarithm, or the base should be stated explicitly.","section":"Eq. (18)"},{"comment":"The caption of Figure 8 does not explain how the gate counts and therefore the time per layer are computed from the problem size; please add the counting formula or a reference for the gate execution times.","section":"Figure 8"},{"comment":"The 'extra cost for routes with fewer flights' mentioned in the dataset description is not formalized in the model. Please state how this cost is computed and incorporated into the route cost c_r.","section":"Section IV A"}],"recommendation":"major_revision","confidential_remarks":"The Ising mapping error in Eqs. (16) and (17) is the most serious issue. If the authors confirm that the simulations used the correct Hamiltonian (i.e., a silent implementation fix), the paper could be revised with corrected formulas. If the printed formulas were used, all experimental results are suspect and the paper would likely require rejecting unless the experiments are redone. The benchmarking comparison with QA from the literature is also a concern for the journal's standards and should be addressed in the revision."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Quick take: this is a credible, small-scale application study with a genuine extension to route costs, but the Ising coefficient in Eq. (16) is off by a factor of two. That means the Hamiltonian used in the reported simulations is not the objective stated in Eq. (12). The main negative result about QAOA scaling is probably still right, but the quantitative claims are not anchored until the formulas are fixed.\n\nWhat is new: extending Vikstål et al.'s decision version to route costs in Eq. (11) is a real, modest contribution. Using real BTS flight data and ICAO cost indices is a plus. The comparison against brute force, branch-and-price, and quantum annealing is sensible and gives a believable picture: on instances up to 14 routes, QAOA scales worse than both branch-and-price and QA. The valency experiments support the expected qualitative story that connectivity makes the problem harder.\n\nWhere it is soft: the stress-test note is correct on the algebra. Re-expanding Eq. (12) with x_r=(1-σ_z^r)/2 gives a route-pair cross-term 2P Σ_f a_fr a_fr' x_r x_r', so the Ising coupling should be J_rr'=(P/2)Σ_f a_fr a_fr'. The published factor P/4 makes the cost Hamiltonian only half as strong in the ZZ terms and not affinely equivalent to Eq. (12). The illustrative energies in the stress-test note do not match my own expansion exactly, but the factor-of-two discrepancy is real and central. Because the penalty weight P is not stated, the reader cannot tell whether the wrong Hamiltonian still has the same optimum for the displayed instances. The tail-usage constraints are dropped by assuming enough suitable aircraft; the authors flag this, but it means the results do not carry over to full TAP instances. The extra-cost rule, P, and gate timings are missing, and no code or data are shipped. The literature work is fine; Vikstål is properly credited for the decision version.\n\nThe central problem is not the scope or the negative result; it is that the numerical claims currently rest on equations that contradict each other. I would not desk-reject the paper outright. It is the kind of application study a good referee can usefully check, and the fix is straightforward. Send it to review with instructions to correct Eq. (16), report P and instance-generation details, and ideally release the code and data before the numbers are taken seriously.","headline":"Honest small-scale application study with a real cost-weighted formulation, but the central Ising coupling is wrong by a factor of two and the numerical claims need that fixed before they can be trusted.","tokens_in":10201,"tokens_out":10859,"would_cite":false,"duration_ms":97142,"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":"The paper shows that QAOA can solve small, cost-weighted tail-assignment instances with enough circuit layers, and that its time-to-solution scaling is worse than classical branch-and-price and quantum annealing.","keywords":["Tail Assignment Problem","QAOA","QUBO","Ising Hamiltonian","route graph connectivity","time to solution","airline scheduling","quantum annealing"],"falsifier":"Re-solve one of the paper's 10-route instances after restoring the tail-usage constraint (each aircraft can fly at most one route and some aircraft cannot serve some flights); if QAOA's success probability falls well below 90% at the same layer counts, the simplified set-partitioning result does not transfer to the full problem.","tokens_in":9241,"feed_emoji":"✈️","tokens_out":8266,"duration_ms":66772,"temperature":0.7,"pith_summary":"The paper sets out to show that the Tail Assignment Problem, in a simplified form where every flight is assigned and any aircraft can fly any route, can be encoded as a QUBO with realistic route costs and solved by the Quantum Approximate Optimization Algorithm. On simulated instances of up to 15 qubits, QAOA with the INTERP parameter-initialization heuristic reaches high success probability once enough circuit layers are added, and it can separate the minimum-cost route set from suboptimal feasible sets. The paper then compares time-to-solution with brute force, branch-and-price, and quantum annealing, finding that QAOA scales worse than the two strong baselines. A careful reader would take the contribution to be a demonstration that QAOA works on very small simplified instances, not a claim of practical competitiveness at current sizes.","feed_headline":"QAOA solves small tail-assignment problems—then lags","feed_subtitle":"With enough layers it finds optimal route sets below 15 routes, but scaling trails classical solvers.","key_machinery":"The central object is the reduced set-partitioning QUBO of Eq. (12), in which route costs enter linearly and a penalty term squares the coverage constraint; the binary variables are mapped to an Ising cost Hamiltonian via $x_r \\to (1-\\hat{\\sigma}^z_r)/2$. QAOA alternates cost and mixer unitaries with $2p$ variational parameters, and the INTERP heuristic produces starting angles for depth $p+1$ by interpolating the local optimum found at depth $p$. The route graph's average valency, the number of routes sharing flights with a given route, is used as the diagnostic for problem difficulty.","core_discovery":"The paper's central claim is that the cost-weighted Tail Assignment Problem, reduced to a set-partitioning problem, can be solved by QAOA with INTERP parameter initialization on realistic small instances: success probability rises with circuit depth and reaches roughly 90% on low-connectivity route graphs with up to 10 routes, while higher average valency degrades that performance. Measured by time-to-solution, QAOA scales worse than both branch-and-price and quantum annealing in the 4-to-14-route range. The paper presents the algorithm as a viable solver for very small simplified instances, with scalability limited by both circuit depth and route-graph connectivity.","pith_inferences":["Restoring tail-route eligibility and tail-usage constraints would turn the set-partitioning QUBO back into the full Tail Assignment Problem, so the reported success rates are likely an upper bound for the harder problem.","The time-to-solution model assumes two-qubit gates are executed sequentially; QAOA's disadvantage relative to classical solvers could shrink on hardware that parallelizes entangling gates.","The INTERP initialization recipe is not problem-specific and could be tested on other set-partitioning QUBOs, with route-graph valency serving as a general hardness predictor."],"forward_implications":["With enough layers, QAOA distinguishes the minimum-cost route set from suboptimal feasible sets on the tested instances.","The number of layers needed grows with route-graph connectivity, so instances where flights appear in many routes are harder regardless of qubit count.","Time-to-solution grows faster for QAOA than for branch-and-price and quantum annealing in the 4-to-14-route range, so QAOA is not competitive on current sizes.","Including route costs extends earlier feasibility-only formulations without increasing the number of qubits.","Any practical quantum advantage would only appear at instance sizes where branch-and-price slows down, which current quantum hardware cannot reach."],"supporting_citations":[{"why":"Supplies the base TAP formulation, the route-graph valency measure, and the feasibility-only version this paper extends with route costs.","marker":"[5]"},{"why":"Defines the QAOA algorithm as the hybrid quantum-classical framework used here.","marker":"[6]"},{"why":"Introduces the INTERP parameter-initialization heuristic that sets QAOA's starting angles.","marker":"[7]"},{"why":"Supplies the US airline on-time performance data used to build the realistic flight instances.","marker":"[16]"},{"why":"Provides the operating cost per block hour used to assign costs to routes.","marker":"[17]"},{"why":"Defines branch-and-price, the classical exact algorithm used as a baseline in the time-to-solution comparison.","marker":"[19]"},{"why":"Provides the quantum annealing approach used as the second quantum baseline.","marker":"[20]"}],"fun_headline_variants":["QAOA finds optimal routes for small sets, scaling lags","Small tail-assignment: QAOA succeeds, then scaling fails","QAOA solves tiny TAP, loses ground as routes scale"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The load-bearing premise is that every flight can be assigned, enough aircraft exist, and any aircraft can fly any route, so the tail-usage constraint and aircraft eligibility can be dropped from the model; if those constraints are active, the reported results do not carry over to the full Tail Assignment Problem.","fun_headline_variants_meta":{"raw":{"variants":["QAOA finds optimal routes for small sets, scaling lags","Small tail-assignment: QAOA succeeds, then scaling fails","QAOA solves tiny TAP, loses ground as routes scale"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000909,"raw_usage":{"total_tokens":3827,"prompt_tokens":786,"completion_tokens":3041,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":402,"completion_tokens_details":{"reasoning_tokens":2985}},"tokens_in":402,"tokens_out":3041,"duration_ms":21461,"temperature":1.0,"reasoning_tokens":2985,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-11T13:44:44.344970+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Re-solve one of the paper's 10-route instances after restoring the tail-usage constraint (each aircraft can fly at most one route and some aircraft cannot serve some flights); if QAOA's success probability falls well below 90% at the same layer counts, the simplified set-partitioning result does not transfer to the full problem.","supporting_citations":[{"cited_title":"The INTERP strategy was used for the results, executing each instance 5 times to achieve more reliable results","cited_arxiv_id":null,"evidence_quote":"Supplies the base TAP formulation, the route-graph valency measure, and the feasibility-only version this paper extends with route costs."},{"cited_title":"Gr¨ onkvist,The Tail Assignment Problem, Phd thesis, Chalmers University of Technology and G¨ oteborg Uni- versity (2005)","cited_arxiv_id":null,"evidence_quote":"Defines the QAOA algorithm as the hybrid quantum-classical framework used here."},{"cited_title":"Ruther, N","cited_arxiv_id":null,"evidence_quote":"Introduces the INTERP parameter-initialization heuristic that sets QAOA's starting angles."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Supplies the US airline on-time performance data used to build the realistic flight instances."}],"review_version":1}