{"id":"e0ae89c6-1248-41ae-be39-0f0391adcbe3","arxiv_id":"2412.19434","paper_version":2,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":4.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":3,"one_line_summary":"Restricting each mobile phone to its best or second-best base station yields a QUBO formulation that uses fewer qubits and gives more accurate approximate solutions on quantum and simulated annealing for the tested instances.","lead":"This paper compares two QUBO formulations for assigning mobile phones to base stations in a quantum annealing context. A formulation that lets each phone choose only between its best and second-best base station uses fewer qubits and produces better approximate solutions than the standard full-assignment formulation, especially as problem size grows.","discovery_kind":"new_application","skeptic_critique":{"model":"deepseek-v4-flash","headline":"The top-2 restriction can make Eq. (11) infeasible or far from the original optimum; the reported SA/QA advantage may be a heuristic-search artifact rather than evidence of better solution quality.","rationale":"The reader's weakest assumption correctly identifies the untested gap between the restricted search space and the original optimum. My stress-test sharpens this into a concrete, load-bearing mechanism: the top-2 restriction can make the proposed QUBO infeasible under the paper's own biased distributions, and even feasible instances may have a large optimality gap to the original problem. Both possibilities are empirically checkable and directly determine whether the relative-error comparisons support the central claim or merely reflect the relative hardness of the two QUBO landscapes for SA and QA. The qubit-count reduction argument is sound and independently supported by the embedding results, so the paper still has value. The appropriate verdict remains CONDITIONAL because the claims about accuracy, especially at larger problem sizes, should not be accepted until the restricted-optimum gap and feasibility rates are reported. The reader's verdict already conditions on such additional analysis, so I do not move the verdict.","tokens_in":8603,"tokens_out":4742,"duration_ms":50168,"concrete_test":"Re-run the exact instances from Fig. 7 through Gurobi to solve the proposed QUBO (11) to optimality, explicitly checking whether a feasible capacity-satisfying assignment exists for each instance. Then compute the relative error of the restricted exact optimum against the original optimum from Eq. (8), i.e., (E_restricted^* - E^*)/E^*. If infeasibility occurs or this gap grows with N, the claimed advantage is an artifact of the heuristic search space rather than a property of the proposed formulation's solution quality.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The central claim is that the proposed formulation (11) yields 'more accurate approximate solutions' as problem size grows, based on relative error to the Gurobi-optimal solution of the original problem (8). This claim requires that the restricted search space, in which each phone chooses between its best and second-best base station (Eq. 10), can represent solutions close to the original optimum and that feasible assignments exist. Neither condition is verified. With M=3 and equal capacities C_a=N/3, the restricted problem is a bipartite assignment where every phone is limited to two stations; such instances can be infeasible. For example, if most phones have the same best and second-best station, capacity constraints cannot be met even in principle. The biased test patterns used in the paper, where 60% of phones are placed near one base station, could readily produce such demand concentration. When the restricted QUBO is infeasible, a 'feasible solution with lowest cost' selected after sampling is actually violating capacity constraints, so the reported relative error compares an infeasible proposed solution against a feasible original optimum. Even when feasible, the exact optimum of Eq. (11) may be substantially worse than the original optimum; the paper never computes or reports this restricted-optimum gap. Consequently, the superiority of the proposed formulation in Figs. 5 and 7 may reflect the smaller and smoother QUBO landscape being easier for SA and QA to navigate, not an objectively better approximation to the original problem. The conclusion that the proposed formulation provides better solutions as N increases is therefore not established by the presented evidence.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper proposes a QUBO formulation for optimizing the connection pattern between mobile phones and base stations, in which each phone is restricted to connecting to either its highest-SINR or second-highest-SINR base station (Eq. 10, used in Eq. 11). This reduces the number of logical variables from N×M in the naive formulation (Eq. 9) to N. The authors compare the two formulations on D-Wave Advantage 6.4 and simulated annealing, measuring the required number of qubits and the relative error of the obtained solution with respect to the exact optimum computed by Gurobi. They report that the proposed formulation uses fewer qubits and yields smaller relative errors, with the gap increasing with problem size in the SA comparison (Figs. 4, 5, 7).","tokens_in":8832,"tokens_out":7898,"duration_ms":69366,"significance":"If validated, the variable-reduction strategy is practically attractive because it allows larger instances to be embedded on current quantum annealers and appears to improve the quality of approximate solutions obtained by QUBO heuristics. The paper has a concrete experimental design: random instances, four test patterns, a comparison against Gurobi's exact optimum, and a classical counterpart (SA). These are strengths. However, the central empirical claim that the proposed formulation yields 'more accurate approximate solutions' to the original problem is not yet supported because the paper does not establish that the top-2 restriction can represent the original optimum (or a close approximation of it), nor does it check feasibility of the restricted problem.","major_comments":[{"comment":"The restricted formulation (11) assumes every phone can be assigned to its best or second-best base station, but the paper never verifies that the resulting capacity constraints can be satisfied. In the biased test patterns (Table 1), 60% of phones are placed near one base station, so many phones may share the same top-2 set; with M=3 and equal capacities C_a=N/3, the capacity of the remaining base station may become unsatisfiable, making Eq. (11) infeasible. In such cases no feasible sample exists, so the 'feasible solution with the lowest cost' selected in the experiments is undefined, and the relative error (E-E*)/E* in Fig. 5 would compare an infeasible assignment against a feasible optimum. The authors need to report the feasibility rate of Eq. (11) for every test pattern and either exclude infeasible instances or handle them explicitly.","section":"Proposed formulation (Eq. (11))"},{"comment":"The comparison against the original optimum E* does not separate the loss caused by the top-2 restriction from the loss caused by heuristic suboptimality. If the exact optimum of the restricted problem (11) is substantially worse than E*, then the proposed formulation cannot be claimed to provide more accurate approximate solutions to the original problem, regardless of how well SA or QA explores the restricted space. The authors should compute the optimum of Eq. (11) (e.g., with Gurobi) on the same instances and report this restricted-optimum gap. Without it, the observed advantage may simply reflect that the naive QUBO (9) has a harder penalty landscape for the heuristics, rather than that the proposed search space is better.","section":"Experiments, Figs. 5 and 7"},{"comment":"The central scaling claim that the proposed formulation outperforms the naive formulation as N grows is based on Fig. 7, but this figure has no error bars and the text does not state how many random instances were used for each value of N. The crossover near N=30-40 could be due to random fluctuation. The authors should report the number of instances and confidence intervals (or at least standard deviations) for each N, and ideally apply the same statistical treatment to Fig. 5.","section":"Fig. 7"},{"comment":"The values of the penalty parameters λ1 and λ2 in Eq. (9) and λ' in Eq. (11) are not specified. The relative performance of the two formulations can depend substantially on these weights; in particular, a poorly chosen λ2 in the naive formulation may produce solutions that violate capacity constraints or, conversely, force a poor SINR trade-off. For reproducibility and a fair comparison, the paper must report the penalty values used (or the tuning procedure) and ideally show how the main conclusions vary over a reasonable range of these hyperparameters.","section":"Experiments, hyperparameters"}],"minor_comments":[{"comment":"'his is not ideal' is a typo and should read 'This is not ideal.'","section":"Section 3.1 (after Eq. (9))"},{"comment":"The relation between the half-power beam width θ and σ is incorrectly typeset; the standard expression is θ = 2√(2 ln 2) σ, not the form displayed.","section":"Eq. (6)"},{"comment":"Reference [19] cites only a presentation title ('Qubits2023'); the proposed formulation is taken from that prior work, so the paper should provide a citable reference or enough procedural detail to make the formulation self-contained.","section":"Reference [19]"},{"comment":"The symbol N is used both for the number of mobile phones and for the noise power in Eq. (1); using a different symbol (e.g., N0) for the noise would avoid confusion.","section":"Notation in Eq. (1)"},{"comment":"The concrete parameters of the SINR model (frequency f, noise power, transmission antenna gain, and the linear value of the sidelobe level) are not reported, which hampers reproduction of the SINR values and thus of the QUBO coefficients.","section":"Problem setting and experiments"}],"recommendation":"major_revision","confidential_remarks":"The paper's reference [19] is to the authors' own prior conference presentation, which is not publicly accessible from the reference list; this makes it difficult to verify novelty attribution. The baseline comparison is reasonable but narrow: the paper does not compare against standard classical heuristics for the original assignment problem (e.g., Lagrangian relaxation, local search, or a MINLP solver), so the headline claim of 'better solutions than the conventional formulation' is limited to the specific QUBO formulation and the two heuristics used. The feasibility issue raised in the major comments is the most serious concern because it directly affects the validity of the experimental metric."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"The paper applies the top-2 QUBO formulation from Ohzeki's Qubits2023 talk to mobile phone–base station assignment. What's new is the application and the scaling evidence: with M=3, logical variables drop from 3N to N, embedding qubits drop correspondingly, and on D-Wave and SA the reduced QUBO gives smaller relative error to the Gurobi optimum on the tested instances. That is a genuinely useful result for practitioners who want to put assignment problems on a quantum annealer.\n\nWhat it does well: Equations (9) and (11) are correct as written. The experimental setup is honest: Gurobi for exact optima, 100 instances for QA, SA comparison, four test patterns. The qubit count comparison in Fig. 4 is straightforward and convincing. The fact that SA also shows the crossover around N=30–40 is interesting and suggests the effect is not purely hardware noise.\n\nWhere the soft spots are: the central claim—that the proposed formulation gives more accurate approximate solutions as N grows—requires that the restricted search space can represent solutions close to the original optimum. That is not established. Each phone is limited to its top-2 base stations; with M=3 and equal capacities N/3, instances can be infeasible under that restriction, especially in the biased placement where 60% of phones cluster near one station. The paper never reports feasibility rates, never computes the exact optimum of the restricted QUBO, and never reports how often a phone would need its third-best station. So the reported relative error in Figs. 5 and 7 may partly reflect that the naive QUBO is harder for heuristics, not that the reduced formulation is objectively better. This is the main gap.\n\nMinor issues: Fig. 7 lacks error bars and an instance count. The penalty coefficients λ1, λ2, and λ′ are not reported. The paper does not say how many of the 1000 samples were feasible vs infeasible. These are easy to fix and matter for reproducibility.\n\nThe stress-test concern about infeasibility is legitimate and should be addressed head-on. I do not think it kills the paper—the authors explicitly concede the reduced formulation can miss the original optimum—but it means the \"better accuracy\" headline needs qualification. If the restricted-optimum gap is small on these instances, the claim holds; if not, the conclusion changes.\n\nWho this is for: researchers and engineers using D-Wave for assignment-like problems. It is a useful case study with a clear formulation. I would bring it to a reading group and would cite it if I were working on QUBO formulations for capacity-constrained assignment.\n\nRecommendation: worth sending to peer review. The core idea is sound, the experimental gaps are fixable, and a careful revision could close them. I would ask for feasibility statistics, a restricted-optimum comparison, error bars, and reported penalty coefficients.","headline":"Useful application of a known variable-reduction trick to base-station assignment; the empirical advantage claim is plausible but rests on an unverified top-2 feasibility assumption.","tokens_in":9452,"tokens_out":1942,"would_cite":true,"duration_ms":16983,"reading_group":"yes","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":[],"pacs":[],"model":"deepseek-v4-flash","headline":"Restricting phones to the top two base stations cuts qubit needs and improves solution accuracy as problems grow.","keywords":["quantum annealing","QUBO","variable reduction","base station assignment","SINR maximization","capacity constraints","simulated annealing","wireless network optimization"],"falsifier":"Construct a three-station instance with $N \\approx 50$ and biased phone placement whose unique exact optimum assigns at least one phone to its third-best base station; then the reduced QUBO cannot represent that optimum and has a strictly positive floor on its relative error. Checking whether that floor grows with $N$ would settle whether the reported accuracy advantage is intrinsic to the reduced search space or an artifact of the heuristics struggling with the naive QUBO.","tokens_in":8363,"feed_emoji":"📡","tokens_out":14363,"duration_ms":117249,"temperature":0.7,"pith_summary":"The paper tries to establish that a reduced QUBO formulation, in which each mobile phone may connect only to the base station giving the highest or second-highest SINR, is better suited to quantum annealing than the standard assignment QUBO. Because the one-hot “connect to exactly one station” constraint disappears, the number of logical variables drops from $N \\times M$ to $N$, so far fewer qubits are needed to embed the problem on an annealer. In experiments with three base stations and up to roughly fifty phones, the reduced formulation produced approximate solutions closer to the exact optimum across all tested placement and antenna-beam patterns, and its advantage over the naive formulation grew with problem size even under simulated annealing. A sympathetic reader would care because the variable reduction lets qubit-limited hardware address larger wireless connection-optimization instances, and the same “best-or-second-best” idea may transfer to other resource-allocation problems.","feed_headline":"Top-two base station routing cuts qubits 3x and beats naive QUBO","feed_subtitle":"Giving each phone a choice between its best and second-best station stays accurate as problem size grows, where the naive form degrades.","key_machinery":"The central object is the variable-reduction QUBO of Eq. (11). Each mobile phone gets one binary variable: 1 means connect to the base station with the highest SINR, and 0 means connect to the second-highest. The capacity constraint is imposed as a quadratic penalty on the total number of phones assigned to each base station, and because each phone automatically picks exactly one of its two allowed stations, the one-hot constraint of the naive formulation is unnecessary. This machinery reduces logical variables from $N \\times M$ to $N$, removes $N(M-1)$ redundant variables, and is the reason the qubit count and solution accuracy behave differently from the naive QUBO.","core_discovery":"The central claim is that the reduced variable formulation, defined by Eq. (11), is not merely a space-saver: it also returns more accurate approximate solutions. In this formulation, a single binary variable per phone records whether the phone connects to its highest-SINR or second-highest-SINR base station, so the one-hot constraint disappears and the logical variable count is $N$ instead of $N \\times M$. Experiments on a quantum annealer across four placement and beam-pattern combinations show smaller relative error for the reduced QUBO, and simulated-annealing runs show the advantage widening as the number of phones grows, with the accuracy crossing around $N = 30$ to $40$. The explanation offered is that fewer logical variables mean fewer physical qubits and fewer error sources on the device, and a smaller search space is easier for both heuristics.","pith_inferences":["An implication the paper leaves implicit is that the top-two restriction is a tunable prior: replacing “top two” with “top $k$” for small $k$ would create a family of formulations trading qubits against solution-space coverage, and the crossover where the reduced form loses to the naive form could be located empirically.","The accuracy crossover in simulated annealing around $N \\approx 30$ to $40$ likely depends on the penalty coefficients in the naive QUBO; retuning those coefficients for each problem size might push the crossover to larger $N$, a comparison the paper does not make.","If the same reduction is applied to other assignment problems where the “best two” assumption is less natural than in wireless connection planning, the qubit savings would survive but the accuracy advantage could invert; testing such a problem would separate the benefit of variable reduction from the benefit of domain structure.","A practical consequence not developed in the paper is that, since mobile positions change over time and connection patterns must be reoptimized periodically, a formulation using fewer qubits and staying accurate under simulated annealing could be run more frequently on classical hardware, not only on quantum annealers."],"forward_implications":["On a fixed annealer, the number of mobile phones that can be embedded rises substantially: with three base stations the logical variable count is one third of the naive QUBO, and the measured qubit count grows more slowly.","For a fixed problem size, quantum-annealer solutions have smaller relative error under the reduced formulation, across isotropic and Gaussian beam patterns and uniform and biased phone placements.","Under simulated annealing, the reduced formulation's relative error stays low as the number of phones grows from small values to roughly fifty, while the naive QUBO's error worsens after about thirty to forty phones.","Because the one-hot constraint is gone, the reduced QUBO no longer needs the penalty coefficient attached to that constraint, removing one tuning parameter from the optimization."],"supporting_citations":[{"why":"Defines the quadratic unconstrained binary optimization form that both the naive and proposed cost functions must take for the annealer.","marker":"[18]"},{"why":"Introduces the variable-reduction formulation that restricts each assignment to the best or second-best option, which the paper adapts from evacuation routing to base-station connection optimization.","marker":"[19]"},{"why":"Supplies simulated annealing, the classical heuristic whose scaling behavior is compared with the proposed and naive QUBOs.","marker":"[20]"},{"why":"Provides the minor-embedding heuristic used to measure the number of physical qubits each formulation requires on the annealer's hardware graph.","marker":"[21]"},{"why":"Provides the simulated-annealing sampler used to produce the classical results in the size-scaling experiments.","marker":"[22]"}],"fun_headline_variants":["Quantum anneal phone routing: top-two choices cut qubits and errors","Reduced QUBO for mobile routing: 3x fewer qubits, better accuracy","One bit per phone: smarter base station mapping via quantum annealing","Phone-to-tower optimization: variable reduction boosts quantum anneal"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The premise is that in the tested instances the capacity constraints never force so many phones onto their third-best or lower base stations that the top-two-only search space excludes solutions close to the true optimum.","fun_headline_variants_meta":{"raw":{"variants":["Quantum anneal phone routing: top-two choices cut qubits and errors","Reduced QUBO for mobile routing: 3x fewer qubits, better accuracy","One bit per phone: smarter base station mapping via quantum annealing","Phone-to-tower optimization: variable reduction boosts quantum anneal"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000243,"raw_usage":{"total_tokens":1498,"prompt_tokens":886,"completion_tokens":612,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":502,"completion_tokens_details":{"reasoning_tokens":533}},"tokens_in":502,"tokens_out":612,"duration_ms":6238,"temperature":1.0,"reasoning_tokens":533,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-11T00:35:47.167147+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Construct a three-station instance with $N \\approx 50$ and biased phone placement whose unique exact optimum assigns at least one phone to its third-best base station; then the reduced QUBO cannot represent that optimum and has a strictly positive floor on its relative error. Checking whether that floor grows with $N$ would settle whether the reported accuracy advantage is intrinsic to the reduced search space or an artifact of the heuristics struggling with the naive QUBO.","supporting_citations":[{"cited_title":"In presentation of Qubits2023","cited_arxiv_id":null,"evidence_quote":"Introduces the variable-reduction formulation that restricts each assignment to the best or second-best option, which the paper adapts from evacuation routing to base-station connection optimization."},{"cited_title":"Available in https://github.com/dwavesystems/dwave-neal","cited_arxiv_id":null,"evidence_quote":"Provides the simulated-annealing sampler used to produce the classical results in the size-scaling experiments."}],"review_version":1}