{"id":"10c53f9d-d06c-4f0e-bc1d-b70115877e94","arxiv_id":"2411.08824","paper_version":1,"verdict":"REJECT","confidence":"MODERATE","novelty_score":7.0,"correctness_risk":"high","formal_verification":"none","parameter_count":2,"one_line_summary":"A QUBO preprocessing algorithm factors out partial coupling symmetries into ancilla qubits, reducing QAOA CNOT count and circuit depth while preserving the ground state energy.","lead":"The paper introduces 'semi-symmetries' in QUBO problem matrices and an algorithm that moves shared couplings into ancilla qubits, cutting QAOA circuit couplings by up to 49 percent and depth by up to 41 percent. A generalist might care because fewer CNOT gates could make near-term quantum optimization circuits more reliable.","discovery_kind":"new_method","skeptic_critique":{"model":"deepseek-v4-flash","headline":"The iterative use of a fixed z in Algorithm 1 is not covered by Proposition IV.3, so the multi-ancilla reductions are unsupported; a concrete test is needed to see whether the algorithm actually fails or merely lacks an inductive proof.","rationale":"The reader's weakest assumption correctly identifies that only a single enhancement is proven and that the iterative algorithm with fixed z lacks a correctness argument. I agree this is the most load-bearing gap. However, I am not fully convinced the fixed-z algorithm must fail: a plausible invariant is that every sym-set in later iterations consists only of small copied original couplings, never the new ±2z or 2z entries, because the three vertices involved in a protected triangle are never re-selected as a conflicting pair. If that invariant holds, Proposition IV.3 extends to all iterations. The proposed brute-force test would determine whether the algorithm actually breaks. Regardless of the test outcome, the paper as written does not prove its central claim for the multi-ancilla regime, the abstract overstates the result by claiming identical energy spectra, and the Maximum Clique QUBO formula in Section II-C is incorrect as stated. These are load-bearing presentation and correctness gaps, so the reject verdict remains appropriate unless the authors supply the missing induction, fix the benchmark formulation, and correct the abstract.","tokens_in":12641,"tokens_out":27761,"duration_ms":376086,"concrete_test":"Run Algorithm 1 exactly as written, with z = sum of all |Q_ij| of the input Q, on an exhaustive or large random set of small QUBO matrices (n = 6..8, entries in {-3,...,3}) that contain at least two overlapping semi-symmetry structures, using numAncillas = 3. For each instance, brute-force compute min_x x^T Q x and min_{x, anc} x_mod^T Q_mod x_mod after each loop iteration. If any final global minimum differs from the original, the algorithm itself is incorrect. If no difference is found across a large sample, the remaining issue is the missing inductive proof, which a revised manuscript must supply together with a corrected Maximum Clique Hamiltonian and a softened 'same spectrum' claim.","verdict_should_be":"UNCHANGED","load_bearing_attack":"Proposition IV.3 proves a single enhance() preserves the global optimum when z equals the total absolute coupling sum S(Q) of the current QUBO matrix. Algorithm 1, however, loops with a fixed input z. After the first enhance(), S(Q) grows substantially: the new entries Q_{i,n} = -2z, Q_{j,n} = -2z, and Q_{i,j} = 2z add roughly 6z to S, so the hypothesis of Proposition IV.3 is not re-established for the second call. The paper supplies no inductive argument showing that the sym-sets entering the proof's inequalities remain within the original z bound, nor that the new large entries are never selected as semi-symmetry partners in later iterations. Since the experiments report up to 29 ancillas, the headline coupling and depth reductions are not backed by the theoretical result. In addition, the abstract's claim that Qmod describes 'the same energy spectrum' is contradicted by the paper's own Figure 2, where the modified spectrum contains extra ancilla-dependent energies even with a large z.","agreement_with_reader":"partial"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper introduces the concept of semi-symmetries in QUBO matrices: pairs of conflicting qubits that share at least three equal non-zero couplings to other qubits. It proposes an algorithm (Algorithm 1) that factors such semi-symmetries out into ancilla qubits, thereby reducing the number of non-zero couplings and, consequently, the number of CNOT gates and the depth of QAOA circuits. The authors claim a theoretical guarantee that the modified QUBO has the same energy spectrum as the original, and they report experimental reductions of up to 49% in couplings and 41% in circuit depth on Maximum Clique, Hamilton Cycles, Graph Coloring, Vertex Cover, and Graph Isomorphism instances.","tokens_in":12847,"tokens_out":9190,"duration_ms":79922,"significance":"If the central claim were fully established, the paper would provide a practical preprocessing technique for QAOA on QUBOs with repeated coupling patterns, with a tunable trade-off between ancilla qubits and circuit depth. The single-step formal result (Proposition IV.3) is a useful contribution: it correctly shows, under the stated assumptions, that the global optimum is preserved when the penalty z is chosen as the total absolute coupling sum. The paper also ships code and tests on random instances, which is commendable. However, the manuscript as written overclaims the theory: the 'same energy spectrum' statement is false, and the iterative algorithm is not covered by the proof. These gaps currently limit the practical validity of the reported reductions.","major_comments":[{"comment":"The abstract states that Qmod 'describes the same energy spectrum as the original Q', but this is contradicted by the paper's own Figure 2, which shows additional ancilla-dependent energies for Qmod even at large z. Proposition IV.3 only proves that valid solutions retain their energy when the ancilla is chosen optimally and that invalid solutions do not decrease in energy; it does not prove spectrum equality. This overclaim should be corrected, since the theoretical result is about preserving the global optimum, not the full spectrum.","section":"Abstract and Section IV-B, Proposition IV.3"},{"comment":"The correctness proof in Proposition IV.3 applies to a single enhance() call with z = sum_{(i,j)} |Q_{i,j}| for the current Q. Algorithm 1, however, loops with a fixed input z. After the first enhance(), the new entries Q_{i,n} = -2z, Q_{j,n} = -2z, and Q_{i,j} = 2z increase the total absolute coupling sum by at least 6z, so the hypothesis of Proposition IV.3 cannot be re-established for subsequent calls with the same z. The paper offers no inductive argument showing that the algorithm still preserves the global optimum after multiple ancillas. Since experiments use up to 29 ancilla qubits, the reported coupling and depth reductions are not backed by the theoretical result.","section":"Algorithm 1 and Proposition IV.3"},{"comment":"The conflict detection criterion Q[i,j] > -Z[i]-Z[j], with Z[i] = sum of negative Q[i,j], is introduced without proof that it is equivalent to, or even sufficient for, Definition IV.1 of conflicting qubits. If the criterion flags a pair that is not actually conflicting, the enhancement may penalize valid assignments and change the global optimum. A proof or a more conservative detection rule is needed for the algorithm's correctness.","section":"Algorithm 1, getConflictList"},{"comment":"The Maximum Clique Hamiltonian is written as H(x) = sum_i -x_i + A * sum_{(i,j) in E} x_i x_j, penalizing edges. The standard QUBO for maximum clique penalizes non-edges, i.e., pairs of selected vertices that are not connected; penalizing edges rewards selecting non-adjacent vertices and is the opposite of the intended constraint. This is a material error in the formulation for one of the five benchmark problems and must be corrected or clarified.","section":"Section II-C, Maximum Clique"}],"minor_comments":[{"comment":"Cases 5 and 6 in the proof are identical (both list xi=0, xj=1, xa=0); Case 6 should presumably be xi=0, xj=1, xa=1.","section":"Section IV-B, Proposition IV.3 proof"},{"comment":"The energy expressions in the proof omit the binary variables x_k in the sums over syms; for example, Case 3 uses 'z - sum Qi,k' where the actual contribution is 'z - sum x_k Q_{i,k}'. The inequalities still hold with the z = sum |Qij| choice, but the notation should be made precise.","section":"Section IV-B, Proposition IV.3 proof"},{"comment":"The text says the y-axis of Figure 3 is the number of couplings, while the figure caption says it is circuit depth; one of these is incorrect and should be fixed.","section":"Section V, Figure 3"},{"comment":"The manuscript does not report the values of the penalty parameter z and the problem-dependent penalty coefficient A used in the experiments, which is needed for reproducibility.","section":"Section V, experiments"},{"comment":"Equation (1) defines the Hamiltonian with an upper-triangular sum over j >= i, but the text calls Q symmetric; the proof later appears to rely on the symmetric convention. The convention should be stated explicitly and used consistently.","section":"Section II-A, Eq. (1)"}],"recommendation":"major_revision","confidential_remarks":"The main gap is the iterative use of a fixed z: the stress-test concern is real and lands. The single-step proof is sound but does not cover Algorithm 1 as written. The paper can likely be repaired by either updating z inside the loop (e.g., recomputing z from the current Q) and proving an invariant, or by showing that the large new entires are never selected as semi-symmetry partners; otherwise the experimental claims are unsupported. The 'same energy spectrum' claim must be retracted or replaced with the weaker ground-state preservation statement. I would not reject outright because the core idea is useful and the single-step result is a solid starting point."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"The core idea here is genuinely new: semi-symmetries, meaning two conflicting qubits that share identical nonzero couplings to at least three other qubits, are factored out into an ancilla. The single-step proof in Proposition IV.3 is algebraically correct, and the figures show the mechanism clearly. The experiments are extensive, cover five standard NP-hard problems, report up to 49% coupling and 41% depth reduction, and code is promised.\n\nBut the paper overclaims. The abstract says Qmod 'describes the same energy spectrum' as Q, but the proof only shows the global optimum is preserved for a single enhancement step, and the paper's own Figure 2 shows extra ancilla-dependent energies. Worse, Algorithm 1 loops with a fixed z, and Proposition IV.3's hypothesis (z = total absolute coupling sum) is not re-established after the first enhance, since new entries of size 2z appear. No inductive argument is given, so the multi-ancilla reductions are unsupported. This is a load-bearing gap.\n\nThe Maximum Clique Hamiltonian in Section II-C penalizes edges instead of non-edges, which is simply wrong for that problem. That undermines one of the five benchmark claims, though the algorithm itself would still reduce couplings for whatever QUBO you feed it. Also, the experiments omit the chosen z values and transpiler details, which hurts reproducibility despite the code.\n\nThe fix is clear: either prove a per-iteration z update or show the sym-sets stay bounded, and correct the Max Clique formulation. If those are addressed, this would be a solid contribution to the QAOA optimization toolkit. As is, it is a promising but unproven method.\n\nWho is this for? QAOA practitioners and anyone working on circuit compilation for variational algorithms. I would send it to a serious referee, with a request for major revision. The idea is worth engaging with, but the current version's central generalization is not proven.","headline":"A genuinely new idea for QAOA circuit reduction, but the proof only covers one factoring step and the abstract overclaims; the multi-ancilla algorithm is unproven.","tokens_in":13420,"tokens_out":2985,"would_cite":false,"duration_ms":25811,"reading_group":"maybe","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["81P68"],"pacs":["03.67.Ac"],"model":"deepseek-v4-flash","headline":"Factoring out semi-symmetries onto ancilla qubits cuts QAOA circuit depth while preserving the original optimum.","keywords":["QAOA","QUBO","semi-symmetries","ancilla qubits","circuit depth","coupling reduction","Ising model","Pareto front"],"falsifier":"Run Algorithm 1 twice on the Maximum Clique example of Table I with z=3, then exhaustively list all bit strings of the two-ancilla Qmod and compare the minimal-ancilla energy of each against the original 64 energies; finding any bit string whose best energy lies below the original ground state would refute the loop-level guarantee.","tokens_in":12414,"feed_emoji":"⚛️","tokens_out":8548,"duration_ms":76371,"temperature":0.7,"pith_summary":"The paper proposes a way to shrink QAOA circuits for QUBO problems by detecting repeated coupling patterns, called semi-symmetries, and moving them onto extra ancilla qubits. It claims that this rewrite leaves the energies of valid solutions unchanged and never lowers the energy of invalid solutions, so the ground state of the modified problem matches the original. Because the number of CNOT gates and the circuit depth in QAOA grow with the number of nonzero couplings, deleting couplings shortens the circuit. On Maximum Clique, Hamilton Cycles, Graph Coloring, Vertex Cover, and Graph Isomorphism, the reported reductions are up to 49 percent of couplings and up to 41 percent of transpiled circuit depth. The point matters for near-term quantum devices, where two-qubit gates are a dominant error source.","feed_headline":"Factoring semi-symmetries cuts QAOA circuit depth 41%","feed_subtitle":"Rewriting QUBO couplings onto ancilla qubits preserves the optimum while shrinking CNOT count and depth.","key_machinery":"The central object is a semi-symmetry: a conflicting pair of qubits whose coupling vectors agree, with nonzero entries, on at least three other qubits. The machinery that carries the proof is the enhancement step, which appends an ancilla a, adds z to the diagonals of i and j, sets the ancilla diagonal to z, sets the ancilla cross terms to -2z, sets Q_ij to 2z, copies the shared couplings to the ancilla row, and zeros the original shared couplings. With z equal to the total sum of absolute couplings, the eight possible assignments of (xi, xj, xa) either reproduce the original energy exactly or push the energy upward. This case analysis is what preserves the optimum and what makes the coupling reduction valid.","core_discovery":"The central claim is that a QUBO matrix with a semi-symmetry can be rewritten into an enlarged matrix whose ground state is unchanged. Two qubits i and j are conflicting when setting both to 1 always raises the energy, and they are semi-symmetric when they share the same nonzero coupling to at least three other qubits. The enhancement step copies those shared couplings onto a new ancilla qubit, zeros the originals, and adds diagonal and cross terms whose penalty is z, the sum of all absolute couplings. Proposition IV.3 argues that, with the ancilla chosen optimally, valid solutions have exactly their original energy under the modified matrix and invalid solutions do not decrease in energy. The paper therefore asserts that iterating this factoring procedure yields Qmod with the same optimal solution as Q while containing fewer couplings.","pith_inferences":["This suggests the same ancilla-factoring move could apply to classical Ising solvers or annealing hardware, where the number of programmable couplings also dominates implementation cost.","One testable extension is to make the penalty z grow adaptively with each enhancement, which could preserve the ground-state guarantee across multiple ancillas while using fewer total qubits.","Because semi-symmetries require exact equality of coupling rows, relaxing the equality to approximate equality could yield larger reductions at the cost of a controllable probability of shifting the optimum."],"forward_implications":["Each factored semi-symmetry removes at least three nonzero couplings from the original pair of rows while adding at most one ancilla per step, so the QUBO becomes sparser.","Because a QAOA layer uses two CNOT gates per nonzero coupling, the per-layer CNOT count of the modified problem drops in proportion to the coupling reduction.","Transpiled circuit depth falls correspondingly, with the largest reported drop being 41 percent (from 257 to 151 for a Hamilton Cycles instance at p=3).","The method produces a Pareto front between qubit count and circuit depth, so a user can choose the widest acceptable circuit to obtain the shallowest one."],"supporting_citations":[{"why":"Supplies the QAOA circuit formulation whose CNOT count and depth are the target of the reduction.","marker":"[7]"},{"why":"Gives the QUBO/Ising formulations of the five benchmark problems used in the experiments.","marker":"[18]"},{"why":"Defines the QUBO model and its energy function, fixing the notation x^T Q x.","marker":"[9]"},{"why":"Demonstrates prior symmetry exploitation in QAOA that the semi-symmetry concept extends.","marker":"[29]"},{"why":"Analyzes variable-permutation symmetries and their effect on QAOA output probabilities, providing the symmetry background.","marker":"[30]"},{"why":"Represents an earlier coupling-reduction heuristic that changes the energy landscape, contrasted with the exactness claim.","marker":"[28]"},{"why":"Motivates the work with CNOT error rates on current hardware and presents a hub-based partitioning alternative.","marker":"[2]"}],"fun_headline_variants":["Factoring semi-symmetries cuts QAOA depth up to 41%","Ancilla qubits absorb semi-symmetries, QAOA depth drops","New QUBO algorithm reduces QAOA circuit depth by 41%","Semi-symmetry factoring into ancillas trims QAOA depth","QAOA depth cut 41% by factoring out semi-symmetries"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The load-bearing premise is that the energy argument proven for a single enhancement step also holds when Algorithm 1 loops, even though each step creates new couplings of size 2z that the fixed penalty z was not chosen to cover.","fun_headline_variants_meta":{"raw":{"variants":["Factoring semi-symmetries cuts QAOA depth up to 41%","Ancilla qubits absorb semi-symmetries, QAOA depth drops","New QUBO algorithm reduces QAOA circuit depth by 41%","Semi-symmetry factoring into ancillas trims QAOA depth","QAOA depth cut 41% by factoring out semi-symmetries"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000552,"raw_usage":{"total_tokens":2628,"prompt_tokens":934,"completion_tokens":1694,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":550,"completion_tokens_details":{"reasoning_tokens":1593}},"tokens_in":550,"tokens_out":1694,"duration_ms":12301,"temperature":1.0,"reasoning_tokens":1593,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-12T21:19:26.712150+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Run Algorithm 1 twice on the Maximum Clique example of Table I with z=3, then exhaustively list all bit strings of the two-ancilla Qmod and compare the minimal-ancilla energy of each against the original 64 energies; finding any bit string whose best energy lies below the original ground state would refute the loop-level guarantee.","supporting_citations":[{"cited_title":"Error mitigation for deep quantum optimization circuits by leveraging problem symmetries","cited_arxiv_id":null,"evidence_quote":"Demonstrates prior symmetry exploitation in QAOA that the semi-symmetry concept extends."},{"cited_title":"Approximate approximation on a quantum annealer","cited_arxiv_id":null,"evidence_quote":"Represents an earlier coupling-reduction heuristic that changes the energy landscape, contrasted with the exactness claim."},{"cited_title":"Frozenqubits: Boosting fidelity of qaoa by skipping hotspot nodes","cited_arxiv_id":null,"evidence_quote":"Motivates the work with CNOT error rates on current hardware and presents a hub-based partitioning alternative."}],"review_version":1}