{"id":"46adcf09-6414-4ea4-bec2-e9db523117d2","arxiv_id":"2412.17841","paper_version":2,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":6.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":3,"one_line_summary":"Semi-symmetries in QUBO matrices can be factored into ancilla qubits, reducing couplings and QAOA depth by up to 45% while preserving the ground state if the anchoring parameter is large enough.","lead":"QUBO matrices are compressed by detecting 'semi-symmetries' between variables and replacing shared couplings with a single ancilla qubit, cutting non-zero couplings and QAOA circuit depth by up to 45% in experiments. The practical interest is a generic preprocessing step that could make quantum optimization more hardware-efficient, assuming the correctness caveats hold.","discovery_kind":"new_method","skeptic_critique":{"model":"deepseek-v4-flash","headline":"The correctness proof covers only a single ENHANCE step; with fixed z, a later factorization involving a previous ancilla can require a bound as large as 2z, so the iterative ground-state guarantee is unproven.","rationale":"The reader's weakest assumption identifies the same load-bearing concern: Proposition 1 is single-step, while Algorithm 1 iterates with a fixed z. I read the paper in good faith and find the single-step algebra of Proposition 1 internally coherent when z is large enough, and the conflict-detection condition in GETCONFLICTLIST is a sufficient (conservative) condition for Definition 1, so I do not see a more fundamental correctness flaw. The real vulnerability is exactly the unproven iteration: after one ENHANCE, new ±2z couplings enter the matrix, so the domination bound needed in the next step can exceed the original z unless the algorithm is restricted to original-qubit pairs and syms, a restriction the pseudocode does not state. The proof-of-concept numbers (z=3, z=9) are below the proposition's sufficient bound, and Figure 2 itself shows that invalid-solution energies can fall below original energies at z=3, so the authors' own data illustrate that the theorem's condition is not necessary but also not a guarantee for the actual runs. Because the paper could be repaired by adding an inductive argument or an explicit restriction, and because the experimental results may still be valid for the restricted regime, the CONDITIONAL verdict remains appropriate. A concrete exhaustive search is the fastest way to see whether the missing proof hides a real counterexample or merely a presentation gap.","tokens_in":16765,"tokens_out":14754,"duration_ms":139477,"concrete_test":"Implement Algorithm 1 verbatim with z set to the total absolute coupling sum of the original Q and numAncillas=2. Exhaustively enumerate all random QUBO instances with n<=6 and entries in {-3,-1,0,1,3}, and for each output Qmod check (i) min_a H_mod(x,a) >= H(x) for every original bit-string x, and (ii) equality of the global minimum value and argmin between H and Qmod. Stop at the first violation and record the original Q, the chosen z, and the exact sequence of ENHANCE calls, noting whether any factored pair or syms set includes a previously added ancilla. This directly determines whether the missing inductive step is a genuine failure of the algorithm or only a gap in the proof.","verdict_should_be":"UNCHANGED","load_bearing_attack":"Proposition 1 in Section 4.2 proves correctness for exactly one application of ENHANCE under the assumption z is at least the total absolute coupling sum of the current Q. Algorithm 1, however, loops ENHANCE with a single fixed input z and never restricts the chosen semi-symmetric pair or the supporting set syms to original qubits. After the first ENHANCE, the matrix contains new entries of magnitude 2z (Q_{i,n}, Q_{j,n}, Q_{i,j}) and z (Q_{n,n}), so the total absolute coupling sum grows by roughly 7z. If a later iteration factors a pair involving a previous ancilla, the quantity z - sum_{k in syms} Q_{i,k} that appears in Cases 2, 3 and 8 can involve a coupling of size ±2z, making the fixed z insufficient. The paper provides no inductive argument that min_ancillas H_mod(x,a) >= H(x) for all x, nor that equality at the original optimum is preserved after multiple steps. The proof-of-concept uses z=3 and z=9, both far below the proposition's stated bound for the 6-node clique matrix, and Figure 2 shows z=3 already allows invalid solutions to drop below their original energies; only the global optimum happens to survive. Thus the central claim 'same energy spectrum' and even the weaker ground-state preservation claim are not established by the supplied proof. If Algorithm 1 is intended to factor only original-qubit semi-symmetries, that restriction is absent from the pseudocode and the experiments do not report whether ancilla-involving pairs were ever selected.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper introduces the concept of semi-symmetries in QUBO matrices, proposes Algorithm 1 to identify pairs of conflicting qubits that share at least three identical non-zero couplings to other qubits, and factor them out into an ancilla qubit via the ENHANCE transformation. The authors claim that the modified QUBO matrix Qmod retains the same energy spectrum as the original Q, and they report experiments on Maximum Clique, Hamilton Cycles, Graph Coloring, and Graph Isomorphism showing reduced numbers of couplings, lower QAOA circuit depth, and improved quantum-annealing embedding metrics.","tokens_in":17117,"tokens_out":3545,"duration_ms":29216,"significance":"If the correctness guarantee held for the iterative algorithm, this would be a practically useful preprocessing technique for QAOA and quantum annealing. The paper's strengths are its explicit algebraic construction, a formal proposition, complete pseudocode, and proof-of-concept experiments rather than only a heuristic recipe. However, the central proof currently covers only a single transformation step, and the headline claim of an identical energy spectrum is not established for the loop actually executed by Algorithm 1.","major_comments":[{"comment":"The proof of Proposition 1 considers exactly one ENHANCE application with z equal to the total absolute coupling sum of the current Q. Algorithm 1, however, iterates ENHANCE with a fixed input z and never restricts the chosen semi-symmetric pair to original qubits. After one step, ENHANCE creates entries of magnitude 2z (Q_{i,n}, Q_{j,n}, Q_{i,j}) and z (Q_{n,n}), so the total absolute coupling sum increases by roughly 7z; a later factorization involving the ancilla can then require a bound as large as roughly 2z in Cases 2, 3, and 8. No inductive argument shows that min_{ancillas} H_mod(x) >= H(x) for all x after multiple steps, so the ground-state preservation claim is unproven for the algorithm as written.","section":"Section 4.2, Proposition 1 and Algorithm 1"},{"comment":"The abstract and Section 6 state that Qmod retains the same energy spectrum as Q, but Figure 2 (upper plot, z=3) shows invalid solutions with lower energy in Qmod than in Q, so the spectra are not the same. Even when z is large enough for the non-decrease property, Qmod has extra states (ancilla values), and the spectra can only coincide after minimizing over ancillas; the claim should be restricted to preservation of the original optimum or to the min-ancilla energy ordering.","section":"Abstract and Section 6 vs. Figure 2"},{"comment":"Proposition 1 assumes that (i,j) are conflicting in the sense of Definition 1, but GETCONFLICTLIST uses the criterion Q_{i,j} > -Z[i] - Z[j] with Z[i] equal to the sum of negative entries in row i. The paper gives no proof that this criterion is equivalent to Definition 1 for general QUBO matrices; since the conflict list drives the loop, a mismatch would invalidate the application of Proposition 1 to the algorithm's actual choices.","section":"Algorithm 1, GETCONFLICTLIST vs. Definition 1"},{"comment":"The proof-of-concept uses z=3 and z=9, values below the total absolute coupling sum of the QUBO matrix in Table I (which is at least 24). Figure 2 itself shows that z=3 violates the non-decrease property for invalid solutions. The experiments therefore do not exercise the regime required by Proposition 1, and the claim that 'we can verify the proposition if we choose z big enough' is not backed by a quantitative check against the required bound.","section":"Section 4.3"}],"minor_comments":[{"comment":"Case 6 is stated as 'xi = 0, x j = 1, xa = 0: analogous to case 4', but the ancilla value should be xa = 1 to be analogous to Case 4; as written it duplicates Case 5.","section":"Section 4.2, proof of Proposition 1"},{"comment":"The caption says 'the lower graph in both plots being the energetically more favorable choice of the ancilla value', but the two plots in Figure 2 have different z values; please clarify which curve corresponds to which ancilla value in each plot.","section":"Figure 2 caption"},{"comment":"GETMOSTSYMQUBITS breaks ties by the first pair encountered because bestSyms is initialized to an empty list; the tie-breaking rule should be stated explicitly since it affects which semi-symmetry is factored out.","section":"Algorithm 1, GETMOSTSYMQUBITS"},{"comment":"The definition of H(x) uses x_i x_j Q_{ij} for i <= j, which is standard, but the matrix Q is described as symmetric; for clarity, state how the off-diagonal entries are counted (upper-triangular convention).","section":"Section 2.1"}],"recommendation":"major_revision","confidential_remarks":"The paper's central theoretical claim is currently not proven for the iterative algorithm, and the empirical section uses z values below the proposition's bound. However, the single-step algebraic identity in Proposition 1 is correct under its assumptions, and the paper would be salvageable by either modifying Algorithm 1 to recompute z or to restrict factorization to original qubits, or by rewriting the claims to match the proven statement. The overstatement in the abstract should be corrected. The experiments themselves are otherwise reasonable as a heuristic demonstration."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Jonas,\n\nQuick take on 2412.17841. The concept of semi-symmetries is genuinely new and the basic idea is attractive: identify pairs of qubits that are both conflicting and share at least three equal non-zero couplings, then factor them into an ancilla to reduce QUBO density. The single-step algebra in Proposition 1 is correct when z is chosen at least the total absolute coupling sum. The paper does a nice job of showing the potential benefits across Max Clique, Hamilton Cycles, Graph Coloring, and Graph Isomorphism, with up to 45% coupling reduction and corresponding improvements in annealer chain length and success rate. That part is worth taking seriously.\n\nThe soft spots are in the proof and the claims. First, the 'same energy spectrum' statement in the abstract and conclusion is false as written. Valid solutions keep their energy, but invalid solutions get shifted upward, so the spectra are not identical. Their own Figure 2 shows this for z=3. The proposition itself only proves ground-state preservation, not spectrum equality, so the wording should change.\n\nSecond, and more important, the correctness guarantee is proven for exactly one ENHANCE step. Algorithm 1 loops, and the pseudocode does not restrict later factorizations to original qubits. After the first step, the matrix has entries of size 2z, so a fixed z may not be large enough for a later iteration. The paper gives no inductive argument, and its own PoC uses z=3 and z=9 for a matrix whose total absolute coupling sum is 33. That's a genuine gap, not a nitpick. It can likely be fixed by either choosing z adaptively after each step or by proving an invariant that restricts which pairs are factored, but as written the iteration is unproven.\n\nAlso minor: the conflict list condition in GETCONFLICTLIST is a heuristic that's not derived from the definition of conflicting qubits, and the paper doesn't report z in the main experiments or release code/data. For a preprocessing method, the practical impact depends on how z scales; leaving it out of the experiments makes the empirical claims hard to reproduce.\n\nNet: the core idea is plausible and likely useful, but the paper needs a revised proof for the iterative algorithm, a corrected spectrum claim, and full disclosure of z and implementation details. I'd send it to serious peer review; it's the kind of paper that will improve with a good referee. I'd also bring it to reading group to discuss the gap and whether adaptive z fixes it.","headline":"Genuinely new QUBO preprocessing idea, but the iterative proof doesn't hold and the 'same energy spectrum' claim is overstated.","tokens_in":17678,"tokens_out":3722,"would_cite":true,"duration_ms":31373,"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":"Factoring out semi-symmetries in QUBO matrices yields sparser quantum-optimization circuits with the same ground state.","keywords":["QUBO","QAOA","quantum annealing","semi-symmetry","ancilla qubits","coupling reduction","circuit depth","combinatorial optimization"],"falsifier":"Take a small QUBO with two overlapping semi-symmetric pairs, run Algorithm 1 with z set to the original total absolute coupling sum, and enumerate every assignment of the original variables plus ancillas. If any valid original assignment changes its energy in Qmod, or if any invalid assignment falls below the original ground-state energy, the multi-step correctness claim collapses. The paper's own 6-node max-clique example with z=3 already places some invalid solutions below their original energies, so checking the same 64-configuration spectrum after a second ENHANCE step is a concrete place to look.","tokens_in":16551,"feed_emoji":"⚛️","tokens_out":9636,"duration_ms":75846,"temperature":0.7,"pith_summary":"The paper introduces a structural pattern it calls a semi-symmetry in QUBO matrices: two qubits that are mutually exclusive in every valid solution and share identical nonzero couplings to at least three other qubits. It then proposes an algorithm that rewrites the matrix by moving those shared couplings onto a new ancilla qubit, producing a larger but sparser QUBO. The central theoretical claim is that, with a sufficiently large auxiliary parameter, every valid solution keeps exactly its original energy and no invalid solution drops in energy, so the ground state and optimal assignments of the original problem are preserved. Experiments on Maximum Clique, Hamilton Cycles, Graph Coloring, and Graph Isomorphism report up to 45% fewer couplings and shallower transpiled QAOA circuits, along with sparser annealing embeddings and improved success rates. This matters because near-term quantum optimization is bottlenecked by the number of nonzero couplings in the problem graph, and the method offers a way to make constrained QUBOs sparser without changing the optimum.","feed_headline":"Factoring out QUBO symmetries cuts couplings up to 45%","feed_subtitle":"Semi-symmetric pairs move to ancilla qubits, preserving the optimum while shortening QAOA circuits and annealer chains.","key_machinery":"The load-bearing object is the semi-symmetry transformation ENHANCE, applied to a conflicting pair (i, j) with a shared neighbor set syms. The transformation adds z to the diagonals of i, j, and the new ancilla n; sets the i-j coupling to 2z; couples the ancilla to i and j with -2z; and moves each shared coupling Q_{i,k} = Q_{j,k} entirely onto the ancilla row, zeroing the i-k and j-k entries. The single parameter z controls the energy trade-offs across the eight possible assignments of the two original bits plus the ancilla bit. Proposition 1 shows that setting z to the total absolute coupling sum makes the best-ancilla energy of every valid x exactly the original energy while keeping invalid x at or above their original energy. The conflict-list check GETCONFLICTLIST decides which pairs can be factored by testing Q_{i,j} > -Z[i] - Z[j], where Z[i] is the sum of negative couplings in row i, and GETMOSTSYMQUBITS chooses the pair with the largest common coupling neighborhood.","core_discovery":"The central claim is that many QUBO matrices contain semi-symmetries, and factoring these shared couplings into an ancilla qubit yields a larger but sparser matrix Qmod whose low-energy spectrum coincides with the original. Formally, Proposition 1 states: if z is chosen as the total absolute coupling sum of the original matrix, then for every original solution x there is a choice of ancilla bit such that x together with that ancilla bit has the same energy in Qmod, and no assignment gives an energy below x's original energy when x is invalid. Therefore the ground-state energy and the set of optimal x are unchanged. The algorithm identifies conflicting qubit pairs by comparing coupling strengths to row-sum-derived thresholds, chooses the pair whose members share the most identical couplings, and applies an ENHANCE transformation that moves the shared couplings onto the new ancilla row. Iterating this procedure over all detected semi-symmetries is what produces the reported reductions.","pith_inferences":["Editorial inference: the single-step proof does not, on its face, extend to the iterative loop in Algorithm 1; after each ENHANCE the total absolute coupling sum changes, so an invariant on z would be needed to make the exactness claim for multi-step runs as written.","Editorial inference: the method trades qubits for couplings, so its advantage is empirical and depends on the ratio of removed shared couplings to added ancilla couplings; a crossover size below which the trade is unfavorable is likely to exist.","Editorial inference: the semi-symmetry test could be relaxed to approximately equal couplings or to common neighborhoods smaller than three, which would find more reductions in dense matrices at the cost of giving up the exactness guarantee.","Editorial inference: since z controls the penalty on invalid solutions independently of the structure, one could search per instance for the minimal z that still preserves the ground state, yielding a sparser matrix with a flatter energy landscape than the worst-case bound requires."],"forward_implications":["Practitioners can preprocess a QUBO before QAOA or annealing, trading extra qubits for a sparser coupling graph while preserving the optimum.","In QAOA, each removed coupling removes 2p CNOT operations from the cost operator, so the method directly reduces circuit depth and error exposure on near-term hardware.","For quantum annealing, sparser QUBOs embed with shorter qubit chains, fewer couplers, and lower chain-break fractions, which the experiments associate with higher success probability.","Because the four benchmark problems are NP-hard and all naturally exhibit semi-symmetries, the technique applies to a broad class of constrained optimization QUBOs beyond the tested instances.","The reported benefit grows with problem size: larger instances contain more semi-symmetries, so the reduction is not a constant offset."],"supporting_citations":[{"why":"Defines QAOA, the target algorithm whose CNOT count is linear in the number of QUBO couplings.","marker":"Farhi et al., 2014"},{"why":"Supplies the QUBO/Ising formulations used for Maximum Clique, Hamilton Cycles, Graph Coloring, and Graph Isomorphism.","marker":"Lucas, 2014"},{"why":"Gives the standard QUBO formulation and its NP-hardness, fixing the problem setting.","marker":"Glover et al., 2018"},{"why":"Catalogs qubit-permutation and bit-flip symmetries, the background against which semi-symmetry is a weakened notion.","marker":"Shaydulin et al., 2020"},{"why":"Shows how existing QUBO symmetries can shorten QAOA circuits, the approach the paper extends.","marker":"Shaydulin and Galda, 2021"},{"why":"Represents the heuristic coupling-removal baseline that alters the energy landscape, which the paper's exactness guarantee is meant to beat.","marker":"Sax et al., 2020"},{"why":"Reports CNOT error rates and hub-based graph partitioning, motivating coupling reduction and supplying per-CNOT overhead figures.","marker":"Ayanzadeh et al., 2023"}],"fun_headline_variants":["Semi-symmetry trick slashes QUBO couplings by up to 45%","Ancilla qubits cut QUBO circuit depth up to 45%","QUBO sparsification via semi-symmetries","Factor out QUBO quirks to shorten quantum circuits","Semi-symmetries trim QUBO links and circuit depth"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The correctness guarantee rests on the assumption that one fixed value of z, chosen as the total absolute coupling sum of the original Q, remains large enough after each iterative ENHANCE step to keep every invalid solution's energy from falling below its original value; Proposition 1 proves this bound only for a single factoring step, and the paper gives no argument that it survives the loop.","fun_headline_variants_meta":{"raw":{"variants":["Semi-symmetry trick slashes QUBO couplings by up to 45%","Ancilla qubits cut QUBO circuit depth up to 45%","QUBO sparsification via semi-symmetries","Factor out QUBO quirks to shorten quantum circuits","Semi-symmetries trim QUBO links and circuit depth"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000949,"raw_usage":{"total_tokens":4083,"prompt_tokens":1014,"completion_tokens":3069,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":630,"completion_tokens_details":{"reasoning_tokens":2982}},"tokens_in":630,"tokens_out":3069,"duration_ms":19533,"temperature":1.0,"reasoning_tokens":2982,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-11T12:49:29.226186+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Take a small QUBO with two overlapping semi-symmetric pairs, run Algorithm 1 with z set to the original total absolute coupling sum, and enumerate every assignment of the original variables plus ancillas. If any valid original assignment changes its energy in Qmod, or if any invalid assignment falls below the original ground-state energy, the multi-step correctness claim collapses. The paper's own 6-node max-clique example with z=3 already places some invalid solutions below their original energies, so checking the same 64-configuration spectrum after a second ENHANCE step is a concrete place to look.","supporting_citations":[{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Supplies the QUBO/Ising formulations used for Maximum Clique, Hamilton Cycles, Graph Coloring, and Graph Isomorphism."},{"cited_title":"Classical symmetries and the Quantum Approximate Optimization Algorithm","cited_arxiv_id":"2012.04713","evidence_quote":"Catalogs qubit-permutation and bit-flip symmetries, the background against which semi-symmetry is a weakened notion."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Represents the heuristic coupling-removal baseline that alters the energy landscape, which the paper's exactness guarantee is meant to beat."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Reports CNOT error rates and hub-based graph partitioning, motivating coupling reduction and supplying per-CNOT overhead figures."}],"review_version":1}