REVIEW 4 major objections 4 minor 35 references
Reducing QUBO Density by Factoring Out Semi-Symmetries
T0 review · 4 major / 4 minor · reviewed 2026-08-11 · deepseek-v4-flash
Pith's one-line read Factoring out semi-symmetries in QUBO matrices yields sparser quantum-optimization circuits with the same ground state.
desk verdict Genuinely new QUBO preprocessing idea, but the iterative proof doesn't hold and the 'same energy spectrum' claim is overstated. read the letter →
The pith
A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.
The reading
What carries the argument
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.
What would settle it
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.
Extended reading notes
Core claim
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.
Load-bearing premise
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.
Editorial extensions
If this is right
- 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.
Reading between the lines
- 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.
Editorial analysis
A structured set of objections, weighed in public.
Referee Report
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.
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 (4)
- [Section 4.2, Proposition 1 and Algorithm 1] 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.
- [Abstract and Section 6 vs. Figure 2] 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.
- [Algorithm 1, GETCONFLICTLIST vs. Definition 1] 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 4.3] 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.
minor comments (4)
- [Section 4.2, proof of Proposition 1] 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.
- [Figure 2 caption] 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.
- [Algorithm 1, GETMOSTSYMQUBITS] 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 2.1] 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).
Circularity Check
No significant circularity: the energy-preservation argument is a direct algebraic verification, and self-citations are not load-bearing.
full rationale
Proposition 1 (Section 4.2) is a case-by-case expansion of the modified energy E_mod = (x+[x_a])^T Q_mod (x+[x_a]) for the conflicting pair and ancilla assignments, compared directly with E = x^T Q x. The choice z = sum |Q_{i,j}| is an explicit sufficient condition that makes the inequalities in Cases 2, 3 and 8 hold; it is not fitted to data, and the conclusion is not assumed in the inputs. The main caveat, that Algorithm 1 reuses a fixed input z over multiple ENHANCE iterations while Proposition 1 is stated for a single factoring step, is a soundness and completeness gap in the iterative guarantee rather than a circular reduction, because the claimed equivalence is not obtained by renaming a conclusion or by importing it from a self-citation. The Hamilton-cycle QUBO formulation is cited from the authors' earlier work, but that formulation is an input encoding used in experiments and is not used to prove the preservation theorem, so the self-citation is not load-bearing for the central claim. Coupling-reduction and depth improvements are benchmarked against D-Wave embedding and Qiskit transpilation, providing external support independent of the proof.
Assumptions & free parameters
free parameters (3)
- z (anchoring and penalty parameter) =
z=3 and z=9 in proof-of-concept; unspecified in main experiments
- numAncillas (number of ancilla qubits to add) =
5 or 10 in annealing experiments; 'all' in QAOA depth experiments
- Minimum common coupling threshold (|U| >= 3 in Definition 2) =
3
assumptions (4)
- domain assumption The conflict-detection condition Q_ij > -Z[i] - Z[j] is a sufficient test for the defining property of conflicting qubits (Definition 1).
- ad hoc to paper The same fixed z remains valid after each iterative application of ENHANCE.
- domain assumption The minimum over the ancilla value is the relevant energy for a solution x (the optimizer finds the best ancilla value).
- standard math Standard algebraic manipulation of quadratic forms is valid.
invented entities (1)
-
Semi-symmetry (as a formal QUBO property)
Cite this review
Pith. "Pith review of Reducing QUBO Density by Factoring Out Semi-Symmetries." pith.science (2026). https://pith.science/paper/ELTXT4NW
@misc{pith2026241217841,
author = {Pith},
title = {Pith review of: Reducing QUBO Density by Factoring Out Semi-Symmetries},
year = {2026},
howpublished = {\url{https://pith.science/paper/ELTXT4NW}},
note = {Machine review of arXiv:2412.17841}
}
abstract
Quantum Approximate Optimization Algorithm (QAOA) and Quantum Annealing are prominent approaches for solving combinatorial optimization problems, such as those formulated as Quadratic Unconstrained Binary Optimization (QUBO). These algorithms aim to minimize the objective function $x^T Q x$, where $Q$ is a QUBO matrix. However, the number of two-qubit CNOT gates in QAOA circuits and the complexity of problem embeddings in Quantum Annealing scale linearly with the number of non-zero couplings in $Q$, contributing to significant computational and error-related challenges. To address this, we introduce the concept of \textit{semi-symmetries} in QUBO matrices and propose an algorithm for identifying and factoring these symmetries into ancilla qubits. \textit{Semi-symmetries} frequently arise in optimization problems such as \textit{Maximum Clique}, \textit{Hamilton Cycles}, \textit{Graph Coloring}, and \textit{Graph Isomorphism}. We theoretically demonstrate that the modified QUBO matrix $Q_{\text{mod}}$ retains the same energy spectrum as the original $Q$. Experimental evaluations on the aforementioned problems show that our algorithm reduces the number of couplings and QAOA circuit depth by up to $45\%$. For Quantum Annealing, these reductions also lead to sparser problem embeddings, shorter qubit chains and better performance. This work highlights the utility of exploiting QUBO matrix structure to optimize quantum algorithms, advancing their scalability and practical applicability to real-world combinatorial problems.
Figures
Figures from the paper (1 more)
Reference graph
Works this paper leans on
-
[1]
write newline
" write newline "" before.all 'output.state := FUNCTION fin.entry add.period write newline FUNCTION new.block output.state before.all = 'skip after.block 'output.state := if FUNCTION new.sentence output.state after.block = 'skip output.state before.all = 'skip after.sentence 'output.state := if if FUNCTION not #0 #1 if FUNCTION and 'skip pop #0 if FUNCTIO...
-
[2]
Ahmed, S. (2012). Applications of graph coloring in modern computer science. International Journal of Computer and Information Technology , 3(2):1--7
work page 2012
-
[3]
Ayanzadeh, R., Alavisamani, N., Das, P., and Qureshi, M. (2023). Frozenqubits: Boosting fidelity of qaoa by skipping hotspot nodes. In Proceedings of the 28th ACM International Conference on Architectural Support for Programming Languages and Operating Systems, Volume 2 , pages 311--324
work page 2023
-
[4]
Bucher, D., N \"u lein, J., O'Meara, C., Angelov, I., Wimmer, B., Ghosh, K., Cortiana, G., and Linnhoff-Popien, C. (2023). Dynamic price incentivization for carbon emission reduction using quantum optimization. arXiv preprint arXiv:2309.05502
work page Pith review arXiv 2023
-
[5]
Eblen, J. D., Phillips, C. A., Rogers, G. L., and Langston, M. A. (2011). The maximum clique enumeration problem: Algorithms, applications and implementations. In International Symposium on Bioinformatics Research and Applications , pages 306--319. Springer
work page 2011
-
[6]
Farhi, E., Goldstone, J., and Gutmann, S. (2014). A quantum approximate optimization algorithm. arXiv preprint arXiv:1411.4028
arXiv 2014
-
[7]
Farhi, E. and Harrow, A. W. (2016). Quantum supremacy through the quantum approximate optimization algorithm. arXiv preprint arXiv:1602.07674
arXiv 2016
-
[8]
Glover, F., Kochenberger, G., and Du, Y. (2018). A tutorial on formulating and using qubo models. arXiv preprint arXiv:1811.11538
arXiv 2018
Show all 35 references
-
[9]
C., Humble, T
Herrman, R., Treffert, L., Ostrowski, J., Lotshaw, P. C., Humble, T. S., and Siopsis, G. (2021). Impact of graph structures for qaoa on maxcut. Quantum Information Processing , 20(9):289
2021
-
[10]
Kawarabayashi, K.-i. (2001). A survey on hamiltonian cycles. Interdisciplinary Information Sciences , 7(1):25--39
2001
-
[11]
and Mart \' n, I
Laporte, G. and Mart \' n, I. R. (2007). Locating a cycle in a transportation or a telecommunications network. Networks: An International Journal , 50(1):92--108
2007
-
[12]
Lee, X., Saito, Y., Cai, D., and Asai, N. (2021). Parameters fixing strategy for quantum approximate optimization algorithm. In 2021 IEEE international conference on quantum computing and engineering (QCE) , pages 10--16. IEEE
2021
-
[13]
Lodewijks, B. (2020). Mapping NP -hard and NP -complete optimisation problems to quadratic unconstrained binary optimisation problems
2020
-
[14]
On np-intermediate, isomorphism problems, and polynomial hierarchy
Lu, X. On np-intermediate, isomorphism problems, and polynomial hierarchy
-
[15]
Lucas, A. (2014). Ising formulations of many np problems. Frontiers in physics , 2:5
2014
-
[16]
Majumdar, R., Bhoumik, D., Madan, D., Vinayagamurthy, D., Raghunathan, S., and Sur-Kolay, S. (2021). Depth optimized ansatz circuit in qaoa for max-cut. arXiv preprint arXiv:2110.04637
2021 arXiv
-
[17]
Mooney, G., Tonetto, S., Hill, C., and Hollenberg, L. (2019). Mapping NP -hard problems to restructed adiabatic quantum architectures
2019
-
[18]
and Nishimori, H
Morita, S. and Nishimori, H. (2008). Mathematical foundation of quantum annealing. Journal of Mathematical Physics , 49(12)
2008
-
[19]
Ni, X.-H., Cai, B.-B., Liu, H.-L., Qin, S.-J., Gao, F., and Wen, Q.-Y. (2023). More efficient parameter initialization strategy in qaoa for maxcut. arXiv preprint arXiv:2306.06986
2023 arXiv
-
[20]
Y., Lu, S., and Chuang, I
Niu, M. Y., Lu, S., and Chuang, I. L. (2019). Optimizing qaoa: Success probability and runtime dependence on circuit depth. arXiv preprint arXiv:1905.12134
2019 arXiv
-
[21]
N \"u lein, J., Gabor, T., Linnhoff-Popien, C., and Feld, S. (2022). Algorithmic qubo formulations for k-sat and hamiltonian cycles. In Proceedings of the genetic and evolutionary computation conference companion , pages 2240--2246
2022
-
[22]
N \"u lein, J., Roch, C., Gabor, T., Stein, J., Linnhoff-Popien, C., and Feld, S. (2023). Black box optimization using qubo and the cross entropy method. In International Conference on Computational Science , pages 48--55. Springer
2023
-
[23]
Pan, Y., Tong, Y., Xue, S., and Zhang, G. (2022a). Efficient depth selection for the implementation of noisy quantum approximate optimization algorithm. Journal of the Franklin Institute , 359(18):11273--11287
2022
-
[24]
Pan, Y., Tong, Y., and Yang, Y. (2022b). Automatic depth optimization for a quantum approximate optimization algorithm. Physical Review A , 105(3):032433
2022
-
[25]
C., Powers, S., Siopsis, G., Humble, T., and Ostrowski, J
Ponce, M., Herrman, R., Lotshaw, P. C., Powers, S., Siopsis, G., Humble, T., and Ostrowski, J. (2023). Graph decomposition techniques for solving combinatorial optimization problems with variational quantum algorithms. arXiv preprint arXiv:2306.00494
2023 arXiv
-
[26]
Prasanna, D., Patton, R., Schuman, C., and Potok, T. (2019). Efficiently embedding QUBO problems on adiabatic quantum computers
2019
-
[27]
Roch, C., Ratke, D., N \"u lein, J., Gabor, T., and Feld, S. (2023). The effect of penalty factors of constrained hamiltonians on the eigenspectrum in quantum annealing. ACM Transactions on Quantum Computing , 4(2):1--18
2023
-
[28]
A., Gleich, D
Rossi, R. A., Gleich, D. F., and Gebremedhin, A. H. (2015). Parallel maximum clique algorithms with applications to network analysis. SIAM Journal on Scientific Computing , 37(5):C589--C616
2015
-
[29]
Sax, I., Feld, S., Zielinski, S., Gabor, T., Linnhoff-Popien, C., and Mauerer, W. (2020). Approximate approximation on a quantum annealer. In Proceedings of the 17th ACM International Conference on Computing Frontiers , pages 108--117
2020
-
[30]
and Galda, A
Shaydulin, R. and Galda, A. (2021). Error mitigation for deep quantum optimization circuits by leveraging problem symmetries. In 2021 IEEE International Conference on Quantum Computing and Engineering (QCE) , pages 291--300. IEEE
2021
-
[31]
Shaydulin, R., Hadfield, S., Hogg, T., and Safro, I. (2020). Classical symmetries and qaoa. arXiv preprint arXiv:2012.04713
2020 arXiv
-
[32]
and Wild, S
Shaydulin, R. and Wild, S. M. (2021). Exploiting symmetry reduces the cost of training qaoa. IEEE Transactions on Quantum Engineering , 2:1--9
2021
-
[33]
Zielinski, S., N \"u lein, J., Stein, J., Gabor, T., Linnhoff-Popien, C., and Feld, S. (2023a). Influence of different 3sat-to-qubo transformations on the solution quality of quantum annealing: A benchmark study. In Proceedings of the Companion Conference on Genetic and Evolut...
2023
-
[34]
Zielinski, S., N \"u lein, J., Stein, J., Gabor, T., Linnhoff-Popien, C., and Feld, S. (2023b). Pattern qubos: Algorithmic construction of 3sat-to-qubo transformations. Electronics , 12(16):3492
2023
-
[35]
Zou, P. (2023). Multiscale quantum approximate optimization algorithm. arXiv preprint arXiv:2312.06181
2023 arXiv
Reviewed August 11, 2026 · model on record in the stance chip above.
Discussion (0). Continue with ORCID to comment.