{"id":"2a6b10c2-600d-4911-907b-297ab36ecf95","arxiv_id":"2502.04100","paper_version":1,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":5.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":4,"one_line_summary":"DAPO dynamically sparsifies the QAOA phase Hamiltonian using the previous layer's most likely solution plus local search, improving approximation ratio and cutting RZZ gate count on small MaxCut and NAE3SAT instances.","lead":"This paper introduces DAPO, a QAOA variant that rebuilds the problem-encoding phase operator layer by layer from the circuit's own best measured bitstrings, refined by one-bit-flip neighborhood search. On small MaxCut and NAE3SAT simulations it reports higher approximation ratios while using fewer two-qubit RZZ gates than vanilla QAOA.","discovery_kind":"new_method","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Sparse phase layer can exclude the true optimum's cut edges; the paper's consistency claim is false in general, making DAPO's performance advantage an unsupported heuristic.","rationale":"The central claim has two parts: fewer RZZ gates and higher approximation ratios. The gate reduction is real but follows trivially from building phase layers from a subset of edges; it does not by itself validate the algorithm. The performance claim depends on the sparse phase operator encoding enough of the original objective to steer the state toward the true optimum. I examined the mechanism proposed in Section III.A and Algorithm 1. The local search picks the best Hamming-neighbor x' of the most probable bitstring, then all later phase layers use only C(x'). The states favored by such a layer are exactly the component-flip equivalence class of x' in the bipartite subgraph (V,C(x')). There is no argument, and no reason in general, that the original optimum belongs to this class. For example, in K4 a size-3 star cut yields a sparse subgraph whose favored states are the star cuts, while the original 4-edge MaxCut optima of K4 are not max cuts of the star. Thus the 'consistency' assertion in the Conclusion is not a harmless overstatement; it is the load-bearing assumption that turns a heuristic into a claimed algorithm. The reader flagged this as unproven; I agree and sharpen it: it is structurally false in general. For this reason the paper remains CONDITIONAL: DAPO may work as a heuristic, and the experiments are suggestive, but the central claim is not supported by the stated mechanism. The false complete-bipartite claim in Section III.C is a separate, less central error and does not change this assessment.","tokens_in":13456,"tokens_out":12513,"duration_ms":147120,"concrete_test":"Run exact statevector simulations (no sampling noise) of DAPO on the three Table I graphs and on 100 random 10-vertex graphs with known MaxCut optima. After each layer p>1, record the local-search output x', build the subgraph G'=(V,C(x')), and check whether every original MaxCut-optimal bitstring x* also cuts every edge in C(x') (equivalently, whether x* lies in the component-flip equivalence class of x'). Report the fraction of layers for which this fails. If it fails on any of the paper's own graphs, the Conclusion's consistency claim is false and the stated mechanism for DAPO's advantage is unsupported; if it never fails, the concern is refuted on the tested instances.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The load-bearing step is Algorithm 1, lines 18-20, together with Section III.A: for every layer p>1, the phase operator is built from the cut set C(x') of one bitstring x' obtained by single-bit-flip local search around the most probable measurement outcome. The paper's justification (Conclusion) is that this 'ensures that the ground state solutions of the Hamiltonians corresponding to the Ansatz and the original problem are consistent.' This is not merely unproven; it is structurally false in general. The sparse phase Hamiltonian contains only edges in C(x'), so the bitstrings it most strongly favors are the maximum cuts of the subgraph (V,C(x')). Those are exactly the assignments obtained from x' by flipping whole connected components of that subgraph. The original global optimum x* need not be of that form: when x* disagrees with x' inside a connected component of the sparse subgraph, x* cuts fewer than |C(x')| of the sparse edges and is not favored. Edges outside C(x') receive no phase rotation in any later layer, and the 'preserve the original cost function' remark in Section III.A only affects the classical parameter objective and final measurement; it does not restore the missing phase terms. Thus the RZZ reduction is real but is a direct consequence of dropping edges, while the higher-approximation-ratio claim rests on an unsupported and generally false spectral-preservation premise.","agreement_with_reader":"partial"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper proposes DAPO-QAOA, a QAOA variant in which every phase layer after the first is constructed from the cut set of a bitstring obtained by measuring the previous layer's optimized circuit and refining that bitstring with single-bit-flip neighborhood search. The authors claim that this dynamically constructed sparse phase operator both preserves the original problem's optimum and reduces the number of RZZ gates, and they report experiments on three 10-vertex MaxCut graphs and on NAE3SAT instances showing higher approximation ratios than vanilla QAOA and sparse-phase baselines.","tokens_in":13762,"tokens_out":9185,"duration_ms":96798,"significance":"If the empirical claims held, DAPO-QAOA would be a useful NISQ-era heuristic: it provides a transparent way to trade phase-operator complexity for per-layer adaptive information, and the resource-counting argument for RZZ reduction is easy to follow. The paper gives a clear pseudocode description of the MaxCut variant and positions the method against relevant sparse-phase and dropout baselines. However, the central consistency justification is asserted rather than proven and is in fact false as stated, and the experimental evidence is too thin to support the advertised quantitative claims. The significance therefore depends on a substantial revision that reframes the method as a heuristic and supplies adequate empirical support.","major_comments":[{"comment":"The assertion that constructing the next layer's phase operator from the cut set C(x') of the neighborhood-search solution x' 'ensures that the ground state solutions of the Hamiltonians corresponding to the Ansatz and the original problem are consistent' is not proven and is false in general. The sparse phase Hamiltonian contains only edges in C(x'), so the assignments it most strongly favors are the maximum cuts of the subgraph (V,C(x')), which are exactly the assignments obtained from x' by flipping whole connected components of that subgraph. An original optimum x* that differs from x' inside such a connected component cuts fewer than |C(x')| sparse edges and is therefore not favored. For example, on K4 with x'=1000, the sparse star subgraph has maximum cuts 1000 and 0111, whereas the original optimum 1100 cuts only two of the three sparse edges. Even if this particular x' is not reachable in a given run, the claim is stated unconditionally, and preserving the original cost function in the classical objective and final measurement does not restore the missing phase terms inside the circuit. This undermines the paper's central justification and leaves the performance advantage as an unsupported heuristic.","section":"Section III.A, Algorithm 1 lines 18-20, Conclusion"},{"comment":"The statement 'The maximum cut value |e| equals the total number of edges |E| only in the case of a complete bipartite graph' is false: any bipartite graph has a cut containing all of its edges, so max cut equals |E| for all bipartite graphs, not only complete bipartite ones. The subsequent inequality |e'| ≤ |e| is valid because e' is a feasible cut value, but the false characterization weakens the argument that dense graphs necessarily have a small optimal cut; dense bipartite graphs are a counterexample.","section":"Section III.C"},{"comment":"The experimental support consists of three fixed 10-vertex graphs (Table I) with no repeated trials, no error bars, no standard deviations, and no noise model, despite the NISQ motivation. The approximation-ratio curves in Figs. 8-10 appear to be single runs, and the '66% of RZZ gates' figure in the abstract and conclusion is not derived from a stated formula or error analysis. The claimed advantage over vanilla QAOA therefore rests on anecdotal evidence. The authors should report multiple random instances and seeds, give mean and variance, and define exactly how the 66% figure is computed.","section":"Section IV.A-C"},{"comment":"The NAE3SAT implementation is underspecified. The paper gives the Hamiltonian in Eq. (13) but does not explain how DAPO's neighborhood search and 'cut set' construction generalize to hyperedges or clauses, how the sparse phase operator is selected from a clause-satisfying assignment, or how the dropout baseline is configured. As a result, the NAE3SAT results in Figs. 11 and 12 cannot be reproduced or independently assessed.","section":"Section IV.D"}],"minor_comments":[{"comment":"The heading 'NAE3SA T' contains a typo.","section":"Section IV.D heading"},{"comment":"The stopping condition uses the quantities E*_p and E*_{p-1}, which are never defined; please clarify what E* denotes.","section":"Algorithm 1 line 14"},{"comment":"The paper alternates between counting RZZ gates and counting CNOT gates without stating the conversion; please specify which quantity is plotted and how the RZZ gate is decomposed.","section":"Section IV.C and Fig. 2"},{"comment":"The phrase 'QAOA allows us to obtain the optimal solution for each layer' is an overstatement; QAOA returns samples and expectation values, not certified optima.","section":"Section III.A"},{"comment":"No information is given about the number of measurement shots, the random-seed policy, or whether statevector simulation is used; please include these details for reproducibility.","section":"Section IV"}],"recommendation":"major_revision","confidential_remarks":"The paper is best read as a heuristic proposal with a clear resource-saving mechanism, but it currently overclaims both theoretical consistency and empirical support. The false consistency statement and the graph-theory error are load-bearing and should be fixed; the experimental section needs multiple instances, seeds, and error quantifiers. With those changes the paper could be a reasonable contribution to a quantum-algorithms venue."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Here's my quick take on DAPO-QAOA. The core idea is genuinely a small extension of existing sparsification tricks: instead of a fixed sparse phase operator, you build each layer's phase operator from the best bitstring of the previous layer, refined by one bit-flip local search. That specific feedback loop is new relative to graph sparsification [30] and QuantumDropout [31], and the gate-count reduction is real: you are literally dropping edges that aren't in the cut of your candidate solution. If all you want is a NISQ heuristic with fewer two-qubit gates, this is a plausible knob to turn.\n\nThe problems are in the justification and the evidence. The paper's Conclusion claims that using the cut set of the neighborhood-refined bitstring \"ensures that the ground state solutions of the Hamiltonians corresponding to the Ansatz and the original problem are consistent.\" That is false in general. The sparse phase Hamiltonian contains only edges from the cut set C(x'), so the bitstrings it most strongly favors are the maximum cuts of the subgraph (V,C(x')). The true global optimum x* need not be of that form; if it disagrees with x' inside a connected component of the sparse subgraph, it cuts fewer of the sparse edges and is not favored. Edges outside C(x') get no phase rotation in later layers. The \"preserve the cost function\" remark only protects the classical parameter objective, not the missing phase terms. So the higher-approximation-ratio claim does not follow from the construction. The RZZ savings are a direct consequence of dropping edges, and the performance claim rests on an unsupported premise. Referees should push on this hard.\n\nThe experiments are too thin to carry the performance claim on their own: three 10-vertex MaxCut graphs, no error bars, no multiple seeds, no noise model, and—most importantly—no classical baseline. They don't compare against using the cut set of an arbitrary greedy or random solution as a fixed sparse phase operator, so we don't know whether the dynamic adaptation is doing anything beyond warm-starting with a decent cut. The graph-theory statement in Section III.C that m = |E| only for complete bipartite graphs is simply wrong: any bipartite graph with at least one edge has a partition cutting all edges. Minor but sloppy. NAE3SAT details are missing, including how clauses are generated and what \"hard\" means.\n\nWho is this for? Practitioners working on QAOA heuristic improvements might find it an interesting idea to test, but it is not yet a reliable result. I would not cite its performance numbers. It deserves a serious referee, however, because the idea is concrete enough to be fixed with better benchmarking and an honest statement of what is heuristic.\n\nRecommendation: send to peer review with the understanding that the consistency claim must be corrected and the experiments need a classical baseline, error bars, and more instances. If those come back solid, this could be a decent short paper. As is, it's a \"conditional accept only after major revision\" situation.","headline":"DAPO's core adaptive-sparsification idea is real and gate savings are real, but the central consistency claim is false and the experiments are too thin to support higher approximation ratios.","tokens_in":14255,"tokens_out":4325,"would_cite":false,"duration_ms":41055,"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":"DAPO-QAOA builds each layer's phase operator from the previous layer's most likely bitstring, refined by single-bit-flip neighborhood search, and reports higher approximation ratios on MaxCut and NAE3SAT while using about 66% of the RZZ…","keywords":["DAPO-QAOA","Quantum Approximate Optimization Algorithm","MaxCut","NAE3SAT","RZZ gates","Hamiltonian sparsification","neighborhood search","NISQ"],"falsifier":"Take a dense MaxCut graph with a known global optimum and a bitstring that is locally optimal under single-bit flips but whose one-bit-flip neighborhood removes an edge that belongs to every global optimum; if DAPO on that graph converges to an approximation ratio no better than vanilla QAOA at matched total gate counts, the paper's central claim fails.","tokens_in":13264,"feed_emoji":"⚛️","tokens_out":13026,"duration_ms":103238,"temperature":0.7,"pith_summary":"This paper proposes DAPO-QAOA, a variant of QAOA in which each phase operator is constructed dynamically from the output of the previous layer rather than fixed in advance. After each layer, DAPO takes the most likely measured bitstring, improves it with a one-bit-flip neighborhood search, and uses the cut edges of that improved string to build a sparse phase operator for the next layer. The claim is that this scheme achieves higher approximation ratios than vanilla QAOA on MaxCut and NAE3SAT while using substantially fewer RZZ gates, about 66% at the same depth. If the claim holds, it offers a practical way to shrink the gate count and depth of QAOA circuits, directly addressing the main obstacle to running QAOA on near-term quantum hardware.","feed_headline":"QAOA with self-built phase layers beats vanilla at two-thirds gates","feed_subtitle":"DAPO reuses the best answer from the previous layer to cut RZZ gates and still improve MaxCut and NAE3SAT.","key_machinery":"The central object is the sparse phase operator. In vanilla QAOA, each layer applies $\\exp(-i\\gamma H_C)$ with the full problem Hamiltonian $H_C$, so every edge of the problem graph contributes one RZZ gate. DAPO instead builds $H_{C'}$ from the cut-edge set of the best bitstring found in the previous layer, refined by a neighborhood search that flips each bit and keeps the flip with the highest cut value. The original cost function is still used as the classical optimization objective, so the variational objective remains the exact problem energy while the circuit that produces the states contains only the sparse phase operators.","core_discovery":"DAPO-QAOA's central claim is that the phase operator in a QAOA layer does not have to be built from the full problem Hamiltonian. Instead, after the first layer, the algorithm reads the bitstring with the largest amplitude from the optimized circuit, improves it by flipping each bit once and keeping the best cut, and then uses the cut edges of that improved bitstring to define the sparse Hamiltonian that generates the next phase operator. The paper argues that this dynamic sparsification preserves the global optimum of the original problem while reducing the number of RZZ gates per layer from the total edge count of the graph to roughly the size of the best known cut. Experiments on three dense MaxCut instances and on NAE3SAT instances show higher approximation ratios than vanilla QAOA and graph-sparsification baselines, with the RZZ count at the same depth dropping to about 66% of the vanilla QAOA count.","pith_inferences":["A natural next step is to replace the single-bit-flip neighborhood search with a stronger classical local-search heuristic; the paper's demonstrated advantage is tied to that particular neighborhood, and stronger search could either improve the results or reveal a ceiling.","The argument that the sparse Hamiltonian preserves the global optimum is heuristic, not proven; a formal condition on the cut set that guarantees the same ground state would turn the empirical claim into a theorem.","The measured bitstring is consumed by the algorithm, so on real hardware its performance will depend on measurement noise and shot statistics; injecting depolarizing or readout errors in simulation would test how much of the reported advantage survives outside noiseless circuits."],"forward_implications":["Dense MaxCut instances become cheaper to solve with QAOA because the per-layer gate count scales with the best-known cut size rather than the total number of edges.","The same Hamiltonian-simplification strategy transfers to other Ising/QUBO-encoded optimization problems; the paper demonstrates it on NAE3SAT, where it also beats vanilla QAOA and the dropout baseline.","Because the sparse phase operators shorten each layer, deeper circuits become viable on noisy hardware, which could let QAOA reach solutions that current fixed-Hamiltonian circuits cannot.","The algorithm turns QAOA into a feedback loop that reuses its own intermediate measurement results, creating a new design space for combining measurement-guided phase layers with adaptive mixers or parameter-transfer heuristics."],"supporting_citations":[{"why":"Defines the vanilla QAOA framework that DAPO modifies.","marker":"[1]"},{"why":"Supplies the graph-sparsification baseline DAPO is compared against for phase-operator simplification.","marker":"[30]"},{"why":"Introduces Quantum Dropout, whose idea of preserving the cost function while dropping phase terms DAPO adopts.","marker":"[31]"},{"why":"Presents ADAPT-QAOA, an earlier adaptive-operator approach that DAPO's layer-by-layer construction extends.","marker":"[25]"},{"why":"Shows a measurement-driven feedback approach to parameter adjustment that motivates DAPO's use of previous-layer outputs.","marker":"[26]"},{"why":"Provides an alternative phase-operator optimization strategy (antidiabatic driving) that DAPO is compared with conceptually.","marker":"[27]"},{"why":"Offers a recursive problem-size reduction that is a competing strategy to DAPO's layer-wise simplification.","marker":"[28]"},{"why":"Removes unnecessary phase operators and is explicitly contrasted with DAPO because it does not simplify the phase-operator structure itself.","marker":"[29]"}],"fun_headline_variants":["QAOA that builds its own phase cuts gate count by a third","Adaptive QAOA phase operator cuts RZZ gates, improves MaxCut","DAPO-QAOA: self-built phase layers hit 66% gate cost","Neighborhood search lets QAOA rebuild its own phase, cutting gates"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The method assumes that the best answer QAOA has found so far, improved by flipping one bit at a time, contains enough of the true optimum's structure that building the next layer only from its cut edges will still steer the circuit to the global optimum.","fun_headline_variants_meta":{"raw":{"variants":["QAOA that builds its own phase cuts gate count by a third","Adaptive QAOA phase operator cuts RZZ gates, improves MaxCut","DAPO-QAOA: self-built phase layers hit 66% gate cost","Neighborhood search lets QAOA rebuild its own phase, cutting gates"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000838,"raw_usage":{"total_tokens":3663,"prompt_tokens":966,"completion_tokens":2697,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":582,"completion_tokens_details":{"reasoning_tokens":2617}},"tokens_in":582,"tokens_out":2697,"duration_ms":20880,"temperature":1.0,"reasoning_tokens":2617,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-08T23:31:43.676947+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Take a dense MaxCut graph with a known global optimum and a bitstring that is locally optimal under single-bit flips but whose one-bit-flip neighborhood removes an edge that belongs to every global optimum; if DAPO on that graph converges to an approximation ratio no better than vanilla QAOA at matched total gate counts, the paper's central claim fails.","supporting_citations":[{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Supplies the graph-sparsification baseline DAPO is compared against for phase-operator simplification."},{"cited_title":"But, these methods depend on the sparsity of the graph or the qual- ity of the initial solution","cited_arxiv_id":null,"evidence_quote":"Introduces Quantum Dropout, whose idea of preserving the cost function while dropping phase terms DAPO adopts."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Presents ADAPT-QAOA, an earlier adaptive-operator approach that DAPO's layer-by-layer construction extends."},{"cited_title":"Chandarana, N","cited_arxiv_id":null,"evidence_quote":"Provides an alternative phase-operator optimization strategy (antidiabatic driving) that DAPO is compared with conceptually."},{"cited_title":"Bravyi, A","cited_arxiv_id":null,"evidence_quote":"Offers a recursive problem-size reduction that is a competing strategy to DAPO's layer-wise simplification."},{"cited_title":"Yanakiev, N","cited_arxiv_id":null,"evidence_quote":"Removes unnecessary phase operators and is explicitly contrasted with DAPO because it does not simplify the phase-operator structure itself."}],"review_version":1}