{"id":"96d500b0-efbe-4ea4-b418-b53e7cf93852","arxiv_id":"2608.04058","paper_version":1,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":6.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":4,"one_line_summary":"Graph-aware symmetry, filtering, and cached distance profiles make exact static qubit allocation up to 13x faster and feasible on one multicore server.","lead":"This paper combines graph-aware pruning rules and reusable device profiles in an exact branch-and-bound solver for static qubit allocation, cutting search time on quantum-device benchmark instances. On a single 60-core server it certifies optimal mappings for all 22 test instances within about 30 minutes, where prior work used a large cluster.","discovery_kind":"extension","skeptic_critique":{"model":"deepseek-v4-flash","headline":"The headline single-thread speedups in Table 4 are measured with an oracle cutoff using reference optima z* from [3], and no no-oracle sequential comparison is reported, so the speedup claim may overstate practical performance.","rationale":"The reader's weakest_assumption identifies exactly the load-bearing risk in the sequential ablation: the oracle cutoff z*+1 supplies the solver with the optimal value from prior work, so the measured speedups quantify search effort against a known target rather than end-to-end exact solving. I agree with that assessment. The concern is load-bearing because the paper's own abstract states the single-thread speedups as a principal result, and the paper does not report a no-oracle single-thread version of Table 4, even though Section 4.3 explicitly develops an incumbent heuristic for practical use. The final 60-thread experiment is less exposed: it uses heuristic incumbents, solves all instances, and returns the reference optima, so it provides substantial support for the exactness and practical feasibility claims. The mathematical content of the paper also appears sound: the symmetry argument is standard, the GLB derivation is valid, and the conditioned-parent-LAP propositions are coherent. Therefore the concern does not justify rejecting the paper or changing the conditional verdict; it justifies requiring either a no-oracle sequential ablation or an explicit reframing of the sequential speedups as an oracle-controlled ablation. The concrete test of rerunning Table 4 with the heuristic incumbent would directly show whether the speedup claim survives without reference-optimum knowledge.","tokens_in":22096,"tokens_out":12980,"duration_ms":153892,"concrete_test":"Re-run the Section 4.1 single-thread ablation without the oracle cutoff, using the Section 4.3 BudgetedSearch(30 s) heuristic to supply the initial incumbent to every configuration, and recompute the geometric-mean speedups over the same RD11–RD16 Boeblingen set. If the 13.27x figure drops by more than about 20% relative to the G baseline, or if the configurations complete different instances than under the oracle cutoff, the headline speedup claim is not robust to removing oracle knowledge.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The central quantitative claim—single-thread geometric-mean speedups of 2.98x on Melbourne and 13.27x on the six completed Boeblingen instances (Section 4.1, Table 4)—is obtained under an oracle cutoff set to z*+1, where z* is the reference optimum from Valois et al. [3]. The paper explicitly states this is an oracle cutoff used to isolate bound and node-processing costs, not a feasible incumbent generated by the solver. If any of these reference optima is not the true optimum, the search effort under this cutoff is not representative of practical exact solving: a too-low cutoff can prune large parts of the tree, and a too-high cutoff leaves extra search work, so the measured ratios do not describe how the solver performs when it must discover and certify the optimum on its own. The final 60-thread experiment in Table 9 uses the practical K0 heuristic incumbent and does not rely on z* for pruning, but that is a different configuration and does not validate the sequential speedup headline. The abstract, however, presents the sequential speedups as a main result. In addition, the released code is not pinned to a commit hash and no independent optimality certificates are provided, so the final \"certified optimal\" claim is not independently re-verifiable as reported; this is secondary because the mathematical reductions in Section 3 appear valid and the proofs are coherent.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","summary":"This paper develops exact branch-and-bound techniques for static qubit allocation, formulated as a rectangular quadratic assignment problem. The main algorithmic contributions are three graph-aware reductions: an assigned-cost filter P, root-orbit and prefix-stabilizer symmetry pruning S0/S*, and a conditioned parent-LAP screening operator L, together with an engineering bundle E that precomputes device-distance profiles for fast row-relaxation terms. The authors prove the safety of the reductions in Propositions 1-3 and evaluate them on Melbourne, Boeblingen, and Cairo benchmarks. The abstract claims single-thread geometric-mean speedups of 2.98x on Melbourne and 13.27x on Boeblingen relative to a GLB baseline, and a 60-thread experiment certifying all 22 final Boeblingen-Cairo instances within 29.6 minutes per instance, excluding one-time device-artifact construction.","tokens_in":22301,"tokens_out":8517,"duration_ms":80910,"significance":"If the results hold, the paper demonstrates a substantial reduction in the computational resources required for exact static qubit allocation, moving from a distributed 8192-core setting to a single 60-core shared-memory machine for the benchmark scale. The proofs of the combinatorial reductions are clear and appear correct, the ablation structure cleanly separates combinatorial gains from engineering gains, and the experiments report coefficient-of-variation information. The code is publicly available. The main weakness is that the headline sequential speedup numbers are measured under an oracle cutoff z*+1, which is not a practical setting; this must be clearly qualified or supplemented with a no-oracle sequential experiment.","major_comments":[{"comment":"The sequential geometric-mean speedups of 2.98x on Melbourne and 13.27x on Boeblingen are obtained with the pruning cutoff set to z*+1, where z* is the reference optimum from Valois et al. [3]. This is an oracle cutoff that is unavailable in practice. The abstract presents these speedups as a main result without stating this condition, which overstates the practical single-thread performance of the solver. The later 60-thread experiment (Section 4.5) uses a heuristic incumbent and does not rely on z*, but that is a different configuration. Please add a practical single-thread experiment that uses the released greedy or the 30-second budgeted heuristic as the incumbent, or explicitly qualify the abstract and conclusion that the sequential speedups are an oracle-cutoff ablation that isolates bound and node-processing costs.","section":"§4.1, Table 4, and Abstract"},{"comment":"The claim that all 22 final Boeblingen and Cairo cases are ‘certified optimal’ within 29.6 minutes rests on the solver’s own arithmetic and on the reference optima reported by Valois et al. The repository is not pinned to a commit hash and no machine-checkable certificates are provided, so the certification claim cannot be independently verified as reported. Please pin the exact code version and, if feasible, provide per-instance certificates or a verified checker that can confirm optimality without rerunning the entire search.","section":"§4.5 and Data and code availability"}],"minor_comments":[{"comment":"The phrase ‘relatively easy Melbourne instances’ is subjective; please either specify a concrete criterion (e.g., instance size, runtime, or tree size) or replace it with a neutral descriptor such as ‘smaller instances’.","section":"Abstract"},{"comment":"The sentence ‘Every completed run returned the reference optimum from [3]’ is tautological under an oracle cutoff; it should be rephrased to clarify that the runs used the reference optimum as the cutoff, not that they independently rediscovered it.","section":"§4.1"},{"comment":"The sentence ‘The negative (less than 1× speedup) wall-time result’ uses ‘negative’ incorrectly; replace with ‘the slowdown’ or ‘the sub-1× wall-time result’.","section":"§4.6"},{"comment":"There is a typo in ‘Thıs experiment’; it should be ‘This experiment’.","section":"§4.5"},{"comment":"In line 7 of Algorithm 3, ‘if the iteration number is event’ should read ‘even’; otherwise the condition is undefined.","section":"§2.3, Algorithm 3"},{"comment":"Please specify the exact commit identifier or version tag of the GitHub repository that was used for the experiments reported in the paper.","section":"Data and code availability"}],"recommendation":"major_revision","confidential_remarks":"The paper is a solid algorithmic contribution with correct proofs, but the oracle-cutoff issue in the headline speedups should be resolved before acceptance. The fit to a quantum-information venue is reasonable given the benchmark problems, though the journal may wish to consider whether the emphasis on exact combinatorial optimization matches its scope. The author’s use of AI assistants is disclosed and does not affect my assessment."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Read it: the paper makes a genuine contribution to exact static qubit allocation, and the final 60-thread certification result is the part to trust. The headline sequential speedups (2.98x Melbourne, 13.27x Boeblingen) are measured with an oracle cutoff z*+1, so they isolate bound-processing cost, not practical search behavior. That is disclosed, but the abstract presents them as main results. The separate Table 9 experiment, which uses a 30-second heuristic incumbent and certifies all 22 Boeblingen-Cairo instances on one 60-core server, does not depend on the oracle and is the more meaningful claim.\n\nWhat is new: the combination of incremental prefix-stabilizer symmetry (S*), conditioned parent-LAP screening (L), and the all-subset free-set/candidate distance histograms (DDOT) for exact GLB assembly. The components are known individually, but the integration is novel and the ablations isolate each contribution. The proofs in Section 3 look correct; I checked Propositions 1-3 and they hold. The GLB and HHB baselines are standard, and the comparison to Valois et al. is fair. Experiments are run five times with coefficient-of-variation reporting, which is better than typical for this area.\n\nSoft spots, in proportion: the oracle-cutoff issue is real but not fatal, because the final practical experiment does not use z* for pruning. The release is not pinned to a commit hash and the certificates are not independently verified, so the 'certified optimal' claim is not fully re-verifiable as reported; that is minor since the math seems sound. The Cairo device profile is 7.8 GB, and the paper honestly reports that the cache hurts wall time on short instances—good to see. The scaling experiment uses only RD14-RD18, so the parallel-efficiency claims are narrowly based.\n\nWho it's for: researchers working on exact qubit mapping or QAP branch-and-bound; heuristic mapper developers who want reference optima. It deserves a serious referee. My recommendation: send it out, but ask the authors to add a no-oracle sequential comparison (e.g., with their 30-second heuristic incumbent) so the headline speedups reflect practical performance, and to pin the code version and provide a checksum or CI artifact.","headline":"Solid engineering-plus-algorithm paper with a real caveat: the headline sequential speedups rest on an oracle cutoff, but the final practical 60-thread results stand on their own.","tokens_in":22887,"tokens_out":1674,"would_cite":true,"duration_ms":16163,"reading_group":"maybe","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["90C27","81P68"],"pacs":[],"model":"deepseek-v4-flash","headline":"This paper claims that exact static qubit allocation can be made dramatically faster by pruning branch-and-bound with device-graph symmetries and reusing per-device distance profiles, so that all 22 benchmark instances are certified…","keywords":["static qubit allocation","quadratic assignment problem","exact branch-and-bound","graph automorphism","Gilmore-Lawler bound","device distance profiles","symmetry pruning","quantum circuit mapping"],"falsifier":"Rerun the single-thread ablation without the oracle cutoff: replace the published optimum z* with the solver's own 30-second heuristic incumbent and check whether the 2.98x and 13.27x geometric-mean speedups survive; if some previously completed instances time out or the speedups collapse, the headline speedups are an artifact of knowing the answer in advance. The 60-thread certification runs, which use only heuristic incumbents, would remain the stronger evidence in either case.","tokens_in":1715,"feed_emoji":"⚛️","tokens_out":1736,"duration_ms":70046,"temperature":0.7,"pith_summary":"This paper is about making exact static qubit allocation fast enough to run on one multicore server. Static qubit allocation chooses which physical qubits on a quantum chip should hold which logical qubits of a circuit, minimizing an interaction-weighted distance cost; the problem is a quadratic assignment problem whose search space is enormous. The author claims that three exact graph-aware reductions—recording cost already fixed by partial assignments, pruning branches that differ only by automorphisms of the device graph, and reusing the parent assignment-bound certificate to reject children early—together with precomputed per-device distance profiles, cut the search so sharply that all benchmark instances in the final experiment are certified optimal within half an hour on one 60-core machine. If true, exact mapping becomes a practical reference for heuristic mappers on moderate chips, not only a cluster-scale exercise.","feed_headline":"60 cores now certify optimal qubit maps in under 30 minutes","feed_subtitle":"Graph-aware pruning and reusable device profiles replace a cluster-scale search with a single shared-memory machine.","key_machinery":"The load-bearing mechanism is a branch-and-bound node at which three exact filters run before the more expensive residual bound is assembled: the already-unavoidable assigned cost $C_{A,A}$, the pointwise prefix stabilizer $\\Gamma_A$ of the device automorphism group that maps equivalent free physical qubits so only one representative is branched on, and a conditioned parent-LAP value computed via shortest paths on the residual graph between the parent's Hungarian matching and dual potentials. Supporting these is the DDOT engineering bundle: an exhaustive table of every free-set/candidate distance histogram, built once per physical device and reused across circuits, which turns the GLB row-relaxation term into an $O(1)$ lookup. The Gilmore–Lawler bound itself is the cheaper residual certificate that makes this node pipeline tractable.","core_discovery":"The central claim is that the previous approach's expensive four-index dual bound can be replaced by a cheaper Gilmore–Lawler assignment bound inside branch-and-bound, provided the search is pruned with structural reductions derived from the device graph. The reductions are exact: assigned-cost filtering records only cost already made unavoidable, root and prefix symmetry branch on one representative of each device-automorphism orbit, and conditioned parent-LAP screening prices every child from the parent's Hungarian certificate, so no optimal allocation is ever discarded. In the single-thread ablation, the final configuration gives geometric-mean speedups of 2.98x over the GLB baseline on Melbourne and 13.27x on Boeblingen; with 60 threads, all 22 Boeblingen and Cairo instances are certified optimal within 29.6 minutes end-to-end on one server. For the hardest Cairo case, the paper reports 29.6 minutes on 60 cores, compared with 6,795 seconds for the prior distributed baseline on 64 nodes of 128 cores, while noting the architectures differ.","pith_inferences":["If the oracle-cutoff caveat is set aside, the single-thread speedups suggest that the cost bottleneck for exact allocation has shifted from the bound itself to node-processing overhead; device profiles and certificate reuse attack exactly that bottleneck.","The all-subsets profile table is exponential in the number of physical qubits, but a selective cache over only encountered free-set masks could extend the same exact-lookup idea to larger devices where the $2^N$ table is infeasible.","A persistent device-profile service would remove the 5.8-9.1 second per-process load penalty for short circuits, making the cache profitable on easy instances as well.","The same combination of symmetry pruning and assignment-certificate reuse applies to other rectangular quadratic assignment problems, such as facility layout with fewer facilities than sites."],"forward_implications":["The same certified optima previously reported on a large cluster are reproduced on one 60-core shared-memory server, suggesting that exact allocation benchmarking for instances of this scale no longer requires distributed hardware.","The prefix-stabilizer symmetry reduction, which adds a further 1.30x retained-tree reduction on Boeblingen beyond root-only symmetry, should transfer to any device whose coupling graph has nontrivial automorphisms.","Conditioned parent-LAP screening avoids roughly 19.9 million child GLB computations on one Boeblingen instance, so the same certificate-reuse idea could speed other assignment-based branch-and-bound codes.","The reusable device-profile artifact is a one-time per-device cost; the 60-thread certification times include the 30-second heuristic and profile loading, showing the engineering bundle pays for itself on longer searches.","The final configuration extends six-hour single-thread coverage of the Boeblingen set from six of ten instances to nine of ten, and certifies all Cairo instances within the same shared-memory run."],"supporting_citations":[{"why":"Supplies the baseline exact qubit-allocation framework, its HHB bound, the benchmark instances, and the reference optima used throughout the comparisons.","marker":"[3]"},{"why":"Introduces the Hahn–Grant dual lower bound used by the HHB control configuration, which the paper retains as the expensive baseline.","marker":"[1]"},{"why":"Presents the branch-and-bound algorithm for the quadratic assignment problem based on the Hungarian method that underlies the HHB implementation.","marker":"[2]"},{"why":"Gilmore's bound is the basis of the GLB row-relaxation construction used as the cheaper baseline bound G.","marker":"[8]"},{"why":"Lawler's quadratic-assignment formulation provides the rectangular linear-assignment relaxation that defines the GLB value.","marker":"[9]"},{"why":"The Hungarian algorithm solves the rectangular assignment subproblems and supplies the matchings and dual potentials reused by the conditioned parent-LAP screen.","marker":"[12]"},{"why":"Defines the partial-node symmetry test among free sites that the paper's S0 and S* reductions implement incrementally.","marker":"[14]"},{"why":"Applies structural-symmetry reduction to exact qubit allocation, the direct prior idea realized here as an incremental prefix stabilizer.","marker":"[15]"},{"why":"Provides the alternating-path and reduced-cost machinery that the conditioned parent-LAP screen uses to price each child from the parent certificate.","marker":"[16]"}],"fun_headline_variants":["Exact qubit allocation: 13x speedup, 30 min on one server","Qubit mapping solved exactly in 30 min on 60 cores","Graph-aware pruning makes exact qubit mapping 13x faster","One server beats 64-node cluster for optimal qubit maps","60 cores certify optimal qubit maps in half an hour"],"cache_read_input_tokens":24960,"weakest_assumption_plain":"The single-thread speedup numbers are measured with an oracle cutoff set to the published reference optimum plus one; if any reference optimum is not the true optimum, the search effort under that cutoff could be artificially small and the practical speedups could be lower.","fun_headline_variants_meta":{"raw":{"variants":["Exact qubit allocation: 13x speedup, 30 min on one server","Qubit mapping solved exactly in 30 min on 60 cores","Graph-aware pruning makes exact qubit mapping 13x faster","One server beats 64-node cluster for optimal qubit maps","60 cores certify optimal qubit maps in half an hour"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.00021,"raw_usage":{"total_tokens":1404,"prompt_tokens":934,"completion_tokens":470,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":550,"completion_tokens_details":{"reasoning_tokens":377}},"tokens_in":550,"tokens_out":470,"duration_ms":4922,"temperature":1.0,"reasoning_tokens":377,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-08T00:45:49.427486+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Rerun the single-thread ablation without the oracle cutoff: replace the published optimum z* with the solver's own 30-second heuristic incumbent and check whether the 2.98x and 13.27x geometric-mean speedups survive; if some previously completed instances time out or the speedups collapse, the headline speedups are an artifact of knowing the answer in advance. The 60-thread certification runs, which use only heuristic incumbents, would remain the stronger evidence in either case.","supporting_citations":[{"cited_title":"Valois, G","cited_arxiv_id":null,"evidence_quote":"Supplies the baseline exact qubit-allocation framework, its HHB bound, the benchmark instances, and the reference optima used throughout the comparisons."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Presents the branch-and-bound algorithm for the quadratic assignment problem based on the Hungarian method that underlies the HHB implementation."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Gilmore's bound is the basis of the GLB row-relaxation construction used as the cheaper baseline bound G."},{"cited_title":"Mautor, C","cited_arxiv_id":null,"evidence_quote":"Defines the partial-node symmetry test among free sites that the paper's S0 and S* reductions implement incrementally."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Applies structural-symmetry reduction to exact qubit allocation, the direct prior idea realized here as an incremental prefix stabilizer."}],"review_version":1}