{"id":"6e7438c3-f283-4cde-b98b-3ba3b22cacb8","arxiv_id":"2502.02245","paper_version":1,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":6.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":5,"one_line_summary":"A variational quantum algorithm carries out r-local search on a neighborhood of size l using only ceil(log2 l) qubits, with numerical demonstrations on MaxCut-512 and a 191-vertex graph coloring problem.","lead":"Researchers describe a quantum algorithm that searches through a huge set of neighboring solutions to an optimization problem using only about the logarithm of the neighborhood size in qubits. If it works at scale, it could let near-term quantum computers attack larger MaxCut and graph coloring problems than current methods allow.","discovery_kind":"new_method","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Finite-shot sampling caps the effective neighborhood at the number of shots N, so the claimed ability to handle classically intractable l is unsupported for near-term devices.","rationale":"The paper's strongest claim is that the algorithm can implement r-local search with O(log l) qubits and 'potentially work with classically intractable neighborhood sizes.' The mathematical construction of the auxiliary function (Eq. 9) and its local-minima correspondence to r-local search is sound. However, the actual algorithm optimizes circuit parameters, not q directly, so the correspondence is lost; the authors admit this in Sec. 3. My review identifies a more specific structural obstacle: the empirical probability vector from N shots is N-sparse, and via Eq. (11) every unobserved outcome maps to q_mu=1, meaning that group is never flipped. Thus no more than N distinct groups can ever be considered. On a near-term device with, say, 10^4 shots, the effective neighborhood is at most 10^4 groups, even if l is billions. The resource analysis of Sec. 4.2 optimizes estimation accuracy under this sparsity but does not address that it bounds the search space. The numerical evidence either uses exact statevector simulation (where sparsity is absent) or finite shots with l<N. Consequently, the central claim is not established, and the proposed test would decide whether the algorithm offers any advantage over classical random sampling of N neighbors. For these reasons I recommend REJECTION of the current claim, with the route to resubmission being a rigorous finite-shot analysis and experiments in the regime l>N.","tokens_in":20431,"tokens_out":15291,"duration_ms":152255,"concrete_test":"Run the MaxCut-512 r=4 experiment (l=6367, Nq=13) under a finite-shot simulation with N=500 shots per cost/gradient evaluation (as in Sec. 6.4) and compare final solution quality to (a) the exact-statevector version and (b) a classical algorithm that randomly samples N groups per round and applies the best flip. Also record the number of distinct outcomes ever observed during optimization. If the finite-shot quantum algorithm does not outperform the classical N-group random sampling and matches the exact simulation, the effective neighborhood is bounded by N and the central claim fails.","verdict_should_be":"REJECT","load_bearing_attack":"The auxiliary function in Eq. (9) has local minima matching r-local search only when optimized directly over the continuous variables q in [-1,1]^l. The algorithm instead optimizes circuit parameters theta, and Sec. 3 explicitly abandons the equivalence. The more concrete problem is the mapping Eq. (11): q_mu(0)=1, so any group whose measurement outcome is never observed receives q_mu=1, i.e., it is never flipped. With N measurement shots, at most N distinct outcomes occur, so at most N groups can have q_mu<1. During finite-shot optimization, unobserved outcomes contribute neither to E nor to its gradient, so the optimizer cannot redirect probability toward a good group unless that group happens to have been sampled. The effective neighborhood is therefore at most N groups, independent of the encoded l. Sec. 4.2 notes that the estimate has 'no more than N nonzero components' and treats this sparsity as a computational advantage, but it is also a search-space bound. To actually explore a classically intractable l, N would need to be comparable to l, making the shot complexity classically intractable. The main numerical claims (Sec. 6.2, 6.3) use exact statevector simulation where all 2^Nq outcomes are visible, which is not available on near-term hardware; the only finite-shot experiment (Sec. 6.4) has l=128 < N=1000. Thus the central claim about classically intractable neighborhoods is unsupported and structurally questionable for the finite-shot setting.","agreement_with_reader":"partial"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper introduces a variational quantum algorithm for local search on Ising/QUBO optimization problems. The authors define an auxiliary continuous function over group-flip variables whose local minima coincide with those of r-local search, map measurement-outcome probabilities to those auxiliary variables through a tanh transformation, and optimize a hardware-efficient ansatz. The claimed contribution is a qubit-efficient scheme using only ceil(log2 l) qubits that can in principle handle classically intractable neighborhood sizes on near-term devices. Numerical demonstrations include MaxCut-512, a graph coloring instance (myciel7), and a small QPU experiment.","tokens_in":20746,"tokens_out":6458,"duration_ms":68347,"significance":"If the central near-term scalability claim were valid, the paper would represent a significant step toward using few qubits for large combinatorial optimization problems. The formal reduction in Sec. 2, connecting the auxiliary function's local minima to r-local search, is correct and clearly presented; the variable number of qubits and problem-specific neighborhood selection for graph coloring are also useful ideas. The resource analysis in Sec. 4.2 and the sparse-evaluation observation in Sec. 4.3 are reasonable for fixed-point estimation. However, the central claim about classically intractable neighborhoods is not supported once finite-shot sampling and the actual optimization over circuit parameters are taken into account. The paper's own acknowledgement in Sec. 3 that the local-minima analysis no longer applies, together with the finite-shot bottleneck discussed below, means that the advertised advantage rests on unproven and structurally questionable assumptions.","major_comments":[{"comment":"The finite-shot sampling step severely limits the effective neighborhood size to at most N groups. With N measurement shots, at most N outcomes have non-zero estimated probability; every other outcome is assigned q_mu = 1 via Eq. (11), meaning that the corresponding group is never flipped and contributes nothing to the objective or to the gradient in Eq. (13). During finite-shot optimization, the optimizer cannot redirect probability toward a good group unless that group has been sampled. The claim that the algorithm 'can potentially work with classically intractable neighborhood sizes' (Abstract, Sec. 4.3) is therefore unsupported for near-term devices. The only finite-shot experiment (Sec. 6.4) uses l = 128 with N = 1000 shots, while the large-l results in Secs. 6.2 and 6.3 use exact state-vector simulation where all 2^Nq outcomes are visible. A concrete test would be to run the optimization with N << l and measure success probability as a function of N; without such evidence, the central scalability claim is not established.","section":"Sec. 3.4, Eq. (11)"},{"comment":"The authors explicitly state that 'the previous analysis of the local minima is no longer applicable' once the circuit parameters, rather than the auxiliary variables q, are optimized. This removes the theoretical guarantee that the algorithm implements r-local search. The numerical evidence in Sec. 6.2 is heuristic, uses per-instance hyperparameters, and shows only average approximation ratios relative to classical local search; it does not establish that optimizing theta over the hardware-efficient ansatz subspace yields r-local-search-quality solutions in general. The central theoretical contribution of the paper is therefore limited to direct optimization of the auxiliary function, not to the variational quantum algorithm as actually executed.","section":"Sec. 3, first paragraph"},{"comment":"The MSE analysis addresses fixed-point estimation of the auxiliary function, not the difficulty of optimizing it. The observation that the MSE starts decreasing only when N is comparable to M is consistent with the finite-shot bottleneck, and the left panel of Fig. 4 shows that MSE decreases for larger l only because the landscape becomes flatter. Flatness is itself a trainability obstacle, as the authors acknowledge in Sec. 2.2 and Sec. 4.1. Therefore the conclusion that 'the number of shots required to estimate it with a fixed accuracy doesn't grow with l' does not support the stronger claim that optimization can handle classically intractable l.","section":"Sec. 4.2, Fig. 4"},{"comment":"The graph coloring result is based on 19 successful runs out of 100 on a single instance (myciel7), with problem-specific group selection and hyperparameters. The claim of solving 'the largest graph coloring instance tackled by a quantum algorithm' is weakened by the low success rate and by the absence of a direct comparison to a classical local search baseline within the same neighborhood. Without such a baseline, it is difficult to attribute the obtained solutions to the quantum algorithm rather than to the restart strategy or the problem-specific neighborhood construction.","section":"Sec. 6.3"}],"minor_comments":[{"comment":"The typesetting of Eq. (11) is ambiguous: the placement of the quotient and the '+1 - 1' term is unclear. Please rewrite the formula with explicit parentheses so that the intended functional form is unambiguous.","section":"Sec. 3.2, Eq. (11)"},{"comment":"The statement that the quantum algorithm achieves solutions 'slightly superior' to classical local search attributes the improvement to multiple optimization rounds, but the classical baseline is not given the same restart (R = 10) treatment. A fairer comparison would allow the classical local search to restart from the same initial solutions.","section":"Sec. 6.2"},{"comment":"The classical local search uses a first-improvement strategy with a fixed lexicographic ordering of groups. The choice of ordering can significantly affect local search outcomes; a brief discussion or sensitivity check would be helpful.","section":"Sec. 5.2"},{"comment":"The discussion of the flat landscape for large l in the left panel of Fig. 4 would benefit from an explicit caveat that the reduced MSE is a consequence of reduced variance in a flat landscape, not an indication that optimization becomes easier.","section":"Sec. 4.2"}],"recommendation":"reject","confidential_remarks":"The finite-shot bottleneck is, in my view, a fundamental limitation of the proposed measurement-to-variable mapping, not a gap that can be patched by additional experiments or minor rewording. The paper's strongest advertised claim—handling classically intractable neighborhoods on near-term hardware—is structurally inconsistent with the fact that at most N groups can have q_mu < 1 after N shots. The mathematical auxiliary-function construction in Sec. 2 is sound and could potentially be published as a classical relaxation result, but the variational quantum algorithm built on top of it does not, as it stands, deliver the promised scalability."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"You should know two things about this paper. First, the core construction is legitimate: an auxiliary function over group-flip variables whose local minima coincide with r-local search, plus a log-qubit encoding of the group index and a tanh map from measurement probabilities to flip probabilities. The Proposition 2 argument is correctly applied, and the paper is unusually candid; it explicitly states in Section 3 that the local-minima equivalence no longer holds once you optimize circuit parameters theta instead of q directly. Second, the headline claim about classically intractable neighborhood sizes is not supported by the paper's own finite-shot analysis. The stress-test note is right: q_mu(0)=1, so any group that is never sampled is never flipped. With N shots you see at most N distinct outcomes, so at most N groups ever get q_mu<1, and the optimizer receives no gradient signal for unsampled groups. The effective neighborhood is bounded by N, independent of the encoded l. Section 4.2's observation that the estimate has 'no more than N nonzero components' cuts both ways: it is a search-space bound, not just a sparse-format convenience. Exploring l much larger than N would require shot counts comparable to l, which is exactly the classical cost the abstract promises to escape.\n\nCredit where it is due: the numerical work is real, if heuristic. MaxCut-512 with l up to 6367 groups shows the encoding working for moderate l, and performance tracks or slightly beats classical local search in the same neighborhood; though that is partly a consistency check by construction, since the auxiliary minima were designed to match. The myciel7 coloring result (19/100 runs) is a concrete data point, but with no classical baseline, per-instance hyperparameters, and no code or data, I would not lean on the 'largest instance solved by a quantum method' claim. The shot-accuracy analysis (MSE scaling as 1/N, independent of l) is genuinely useful and under-appreciated.\n\nWho should read it: anyone working on qubit-efficient variational optimization or NISQ heuristics. It deserves a serious referee; the encoding is novel relative to the minimal-encoding literature, and the authors are honest about the trainability gap. But the scalability claim needs re-framing around the shot budget, and the authors should be pressed to release code and data. I would referee it, and I would condition acceptance on addressing the N-versus-l bound.","headline":"The group-flip encoding is a real and honestly presented idea, but finite-shot sampling structurally caps the effective neighborhood at the number of shots, so the classically-intractable-l claim does not survive contact with near-term hardware.","tokens_in":21291,"tokens_out":3771,"would_cite":true,"duration_ms":36297,"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":"A variational quantum circuit runs r-local search over a neighborhood of size l with only logarithmically many qubits.","keywords":["variational quantum algorithm","qubit-efficient encoding","r-local search","combinatorial optimization","MaxCut","graph coloring","QUBO","Ising model"],"falsifier":"On a fixed 3-regular MaxCut-512 graph, run the algorithm with r=1 (l=512, 9 qubits) and r=4 (l=6367, 13 qubits) from the same random initial solutions at the same circuit depth; if the r=4 approximation-ratio distribution does not stochastically dominate the r=1 one and reach the classical r=4 local-search baseline, the central claim that larger neighborhoods improve solutions would be refuted. A second check targets the shot-count claim: for fixed M=200 on a MaxCut-256 graph, the mean-squared-error curve versus shot count should be independent of r; a measured rightward shift as r grows from 1 to 7 would falsify it.","tokens_in":20211,"feed_emoji":"⚛️","tokens_out":11687,"duration_ms":108112,"temperature":0.7,"pith_summary":"This paper claims that a variational quantum algorithm can perform r-local search, the routine at the heart of most optimization metaheuristics, over a neighborhood of size l using only $\\lceil \\log_2 l \\rceil$ qubits. The key move is to encode not the candidate solution itself but the probabilities of flipping groups of variables, and to minimize an auxiliary multilinear function whose local minima coincide with those of r-local search. If the claim holds, near-term devices with modest qubit counts could search neighborhoods that are classically intractable to enumerate, and increasing the neighborhood size would improve solution quality without a blow-up in the required number of measurements. The authors demonstrate this numerically on MaxCut instances up to 512 nodes and on a 191-vertex graph coloring problem, the largest graph coloring instance solved by a quantum method to date, plus a test on a real noisy processor.","feed_headline":"Logarithmic qubits run local search over vast neighborhoods","feed_subtitle":"A 13-qubit circuit matches classical r-local search and solves the largest graph-coloring instance yet tackled by a quantum method.","key_machinery":"The load-bearing object is the auxiliary multilinear function $E(\\vec{q})$ of Eq. (9), built by writing each original spin as a product of flip variables over a chosen collection of groups, then relaxing the discrete flip variables to continuous values in $[-1,1]$. Its local minima are exactly the solutions that beat every neighbor reachable by flipping one encoded group, so minimizing it is r-local search over that neighborhood. The quantum part encodes group indices in $\\lceil \\log_2 l \\rceil$ qubits, converts measured outcome probabilities $P_\\mu$ into auxiliary variables $q_\\mu$ through the monotone transformation $q_\\mu = \\frac{2\\tanh(\\alpha(1-MP_\\mu))+1}{\\tanh \\alpha + 1} - 1$ (Eq. (11)), and optimizes the composite function with a hardware-efficient circuit using the parameter-shift rule for gradients. Sparse problems restrict groups to connected subgraphs, which provably removes redundant neighbors, and the finite-shot estimate of the auxiliary function runs in time polynomial in the problem size, the shot count, the layer count, and $\\log l$, not in $l$.","core_discovery":"The paper's central claim is that r-local search can be quantized by replacing discrete flip variables with continuous probabilities attached to flips of chosen groups of spins, then minimizing the resulting auxiliary function with a parametrized quantum circuit. For a chosen neighborhood of size l, the algorithm needs only $\\lceil \\log_2 l \\rceil$ qubits: each computational basis outcome is decoded into a group of spins to flip, and the measured probabilities are mapped to auxiliary variables in $[-1,1]$ through a monotone transformation. The authors establish that local minima of the auxiliary function correspond exactly to solutions better than all neighbors in the encoded neighborhood, so optimizing it is equivalent to r-local search; the finite-shot estimate of the function has mean-squared error whose onset depends on the hyperparameter M, not on the neighborhood size l. Numerically, increasing the neighborhood size improves approximation ratios on MaxCut-512, the myciel7 graph coloring problem is solved in 19 of 100 runs with 13 qubits, and the r=n limit matches complete-encoding VQE while r=1 outperforms minimal encoding at shallow depth.","pith_inferences":["An implication the authors leave implicit is that the group-selection step is the real problem-design lever: for constrained problems, choosing flip groups that preserve feasibility, as the color-switch groups do for graph coloring, is what converts an infeasible 1-local search landscape into a useful one, and the same recipe should transfer to other constraint-heavy QUBO formulations.","Because the algorithm outputs a ranked list of most-probable flip sets rather than a single solution, it could serve as the neighborhood generator inside classical metaheuristics such as tabu search or simulated annealing; the paper only notes this direction in passing.","A testable prediction implicit in Fig. 7 is that the number of variational parameters needed to match classical r-local search grows sublinearly in l; checking whether this holds for larger r or on fully connected graphs would separate a property of the encoding from a property of the sparse MaxCut instances used.","The M-hyperparameter bound on negative $q_\\mu$ components means each round can realize at most about M improving flips from the initial solution, which is why restarts are needed; this suggests a natural hybrid variant in which the quantum circuit proposes candidates and a classical routine verifies them, a combination the authors hint at but do not develop."],"forward_implications":["Any problem whose neighborhood can be decoded from a bitstring becomes addressable with $\\lceil \\log_2 l \\rceil$ qubits, so neighborhood sizes that are classically intractable to enumerate are in principle reachable on near-term hardware.","Increasing the neighborhood size improves solution quality once the circuit is deep enough; the MaxCut-512 experiments show the average approximation ratio rising from r=1 to r=4 at fixed depth.","The shot count needed for fixed-accuracy estimation of the auxiliary function is governed by the hyperparameter M, not by l, so a user can trade measurements against the effective number of local-search steps per round.","At the r=n limit the method matches complete-encoding VQE, while at r=1 it matches bilinear relaxation and improves on minimal encoding for shallow circuits, so the encoding continuously interpolates between the two established extremes.","Sampling several most-probable solutions from the final flip-probability distribution mitigates hardware noise, because a distorted distribution still ranks many good candidates near the top."],"supporting_citations":[{"why":"Defines the minimal-encoding baseline; the paper argues its multiple local minima limit quality and that the new method removes them by enlarging the encoded neighborhood.","marker":"[8, 9]"},{"why":"Establishes that local minima of the bilinear relaxation sit at vertices and thus coincide with 1-local-search minima, the property the auxiliary function generalizes to r-local search.","marker":"[23]"},{"why":"Provides the hardware-efficient ansatz family used for the variational circuit and the basis for the layer-count scaling study.","marker":"[29]"},{"why":"Supplies the parameter-shift rule used to compute gradients of the measured probability distribution with respect to circuit angles.","marker":"[30]"},{"why":"Gives the QUBO formulation of graph coloring and the prior quantum graph-coloring work that the myciel7 demonstration extends with a larger instance.","marker":"[35]"},{"why":"Supplies the myciel7 benchmark graph used in the numerical demonstration.","marker":"[36]"},{"why":"Identifies barren plateaus, the acknowledged trainability limitation that bounds how far the larger-neighborhood claims can be extrapolated.","marker":"[25]"}],"fun_headline_variants":["Quantum local search uses log qubits for huge neighborhoods","13 qubits solve biggest quantum graph coloring yet","Log-scale qubits for local search, solve largest quantum graph coloring","Quantum local search: log qubits, exponential neighborhoods"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"Everything rests on the assumption that optimizing the circuit's rotation angles, rather than the flip probabilities directly, drives the measured distribution to a minimum of the auxiliary function that is as good as r-local search; the paper states in Section 3 that the local-minima proof no longer applies once the circuit parameters are optimized, and the numerical evidence covers only moderate neighborhood sizes.","fun_headline_variants_meta":{"raw":{"variants":["Quantum local search uses log qubits for huge neighborhoods","13 qubits solve biggest quantum graph coloring yet","Log-scale qubits for local search, solve largest quantum graph coloring","Quantum local search: log qubits, exponential neighborhoods"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000529,"raw_usage":{"total_tokens":2550,"prompt_tokens":948,"completion_tokens":1602,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":564,"completion_tokens_details":{"reasoning_tokens":1537}},"tokens_in":564,"tokens_out":1602,"duration_ms":11839,"temperature":1.0,"reasoning_tokens":1537,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-09T12:49:46.540871+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"On a fixed 3-regular MaxCut-512 graph, run the algorithm with r=1 (l=512, 9 qubits) and r=4 (l=6367, 13 qubits) from the same random initial solutions at the same circuit depth; if the r=4 approximation-ratio distribution does not stochastically dominate the r=1 one and reach the classical r=4 local-search baseline, the central claim that larger neighborhoods improve solutions would be refuted. A second check targets the shot-count claim: for fixed M=200 on a MaxCut-256 graph, the mean-squared-error curve versus shot count should be independent of r; a measured rightward shift as r grows from 1 to 7 would falsify it.","supporting_citations":[{"cited_title":"Pseudo-boolean optimization","cited_arxiv_id":null,"evidence_quote":"Establishes that local minima of the bilinear relaxation sit at vertices and thus coincide with 1-local-search minima, the property the auxiliary function generalizes to r-local search."},{"cited_title":"On the practical usefulness of the Hardware Efficient Ansatz","cited_arxiv_id":null,"evidence_quote":"Provides the hardware-efficient ansatz family used for the variational circuit and the basis for the layer-count scaling study."},{"cited_title":"Evaluating analytic gradients on quantum hardware","cited_arxiv_id":null,"evidence_quote":"Supplies the parameter-shift rule used to compute gradients of the measured probability distribution with respect to circuit angles."},{"cited_title":"Quantum Optimization for the Graph Coloring Problem with Space-Efficient Embedding","cited_arxiv_id":null,"evidence_quote":"Gives the QUBO formulation of graph coloring and the prior quantum graph-coloring work that the myciel7 demonstration extends with a larger instance."},{"cited_title":"Graph coloring Instances","cited_arxiv_id":null,"evidence_quote":"Supplies the myciel7 benchmark graph used in the numerical demonstration."},{"cited_title":"Barren plateaus in quantum neural network training landscapes","cited_arxiv_id":null,"evidence_quote":"Identifies barren plateaus, the acknowledged trainability limitation that bounds how far the larger-neighborhood claims can be extrapolated."}],"review_version":1}