REVIEW 4 major objections 5 minor 1 cited by
Reducing QAOA Circuit Depth by Factoring out Semi-Symmetries
T0 review · 4 major / 5 minor · reviewed 2026-08-12 · deepseek-v4-flash
Pith's one-line read Factoring out semi-symmetries onto ancilla qubits cuts QAOA circuit depth while preserving the original optimum.
desk verdict 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. 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 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.
What would settle it
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.
Extended reading notes
Core claim
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.
Load-bearing premise
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.
Editorial extensions
If this is right
- 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.
Reading between the lines
- 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.
Editorial analysis
A structured set of objections, weighed in public.
Referee Report
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.
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 (4)
- [Abstract and Section IV-B, Proposition IV.3] 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.
- [Algorithm 1 and Proposition IV.3] 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.
- [Algorithm 1, getConflictList] 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 II-C, Maximum Clique] 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.
minor comments (5)
- [Section IV-B, Proposition IV.3 proof] 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 IV-B, Proposition IV.3 proof] 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 V, Figure 3] 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 V, experiments] 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 II-A, Eq. (1)] 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.
Circularity Check
No significant circularity: Proposition IV.3 is a self-contained algebraic proof, and the reported reductions are measured outputs of Algorithm 1 rather than fitted inputs.
full rationale
Proposition IV.3 is a self-contained algebraic proof: given z = sum |Qij| and the definition of conflicting qubits, the eight cases compute E_mod and compare it with E, and the inequalities follow from z being the total absolute coupling sum. No fitted parameter is renamed as a prediction; the coupling and depth reductions are measured by running Algorithm 1 on sampled QUBO instances. The only in-house citation ([28], which includes two current co-authors) is a related-work contrast about heuristic QUBO simplification and is not load-bearing for the correctness argument. The abstract's claim that Q_mod 'describes the same energy spectrum' exceeds the proposition, which preserves only valid-solution energies and does not decrease invalid-solution energies; Figure 2 indeed shows extra ancilla-dependent energies. In addition, Proposition IV.3 is proved for a single enhance() call, while Algorithm 1 loops with a fixed z and no inductive argument re-establishes z = sum |Qij| after new entries of magnitude 2z are introduced. These are correctness and support gaps (an overclaim and an omitted inductive proof), not circularity: no equation is identical to its input by construction, and no conclusion is justified solely by a self-citation.
Assumptions & free parameters
free parameters (2)
- z (penalty value) =
unspecified in experiments; recommended z = sum |Qij|
- numAncillas (budget) =
0 to 29 in experiments
assumptions (3)
- ad hoc to paper The conflict detection condition (Q[i,j] > -Z[i]-Z[j]) identifies conflicting qubits per Definition IV.1.
- ad hoc to paper Repeated enhancement steps with a fixed z preserve the global optimum.
- domain assumption The Maximum Clique QUBO Hamiltonian H = sum -x_i + A*sum_{E} x_i x_j encodes maximum clique.
Cite this review
Pith. "Pith review of Reducing QAOA Circuit Depth by Factoring out Semi-Symmetries." pith.science (2026). https://pith.science/paper/2RVEODDY
@misc{pith2026241108824,
author = {Pith},
title = {Pith review of: Reducing QAOA Circuit Depth by Factoring out Semi-Symmetries},
year = {2026},
howpublished = {\url{https://pith.science/paper/2RVEODDY}},
note = {Machine review of arXiv:2411.08824}
}
abstract
QAOA is a quantum algorithm for solving combinatorial optimization problems. It is capable of searching for the minimizing solution vector $x$ of a QUBO problem $x^TQx$. The number of two-qubit CNOT gates in the QAOA circuit scales linearly in the number of non-zero couplings of $Q$ and the depth of the circuit scales accordingly. Since CNOT operations have high error rates it is crucial to develop algorithms for reducing their number. We, therefore, present the concept of \textit{semi-symmetries} in QUBO matrices and an algorithm for identifying and factoring them out into ancilla qubits. \textit{Semi-symmetries} are prevalent in QUBO matrices of many well-known optimization problems like \textit{Maximum Clique}, \textit{Hamilton Cycles}, \textit{Graph Coloring}, \textit{Vertex Cover} and \textit{Graph Isomorphism}, among others. We theoretically show that our modified QUBO matrix $Q_{mod}$ describes the same energy spectrum as the original $Q$. Experiments conducted on the five optimization problems mentioned above demonstrate that our algorithm achieved reductions in the number of couplings by up to $49\%$ and in circuit depth by up to $41\%$.
Figures
Figures from the paper (1 more)
Forward citations
Cited by 1 Pith paper
-
Analytical Expressions for the Quantum Approximate Optimization Algorithm and its Variants
Exact analytical expressions are derived for QAOA cost expectation values, unifying product-mixer variants and giving the first exact multi-layer results for Grover-type mixers, which are shown to be sensitive to cycl...
Reference graph
Works this paper leans on
-
[1]
Applications of graph coloring in modern computer science
Shamim Ahmed. Applications of graph coloring in modern computer science. International Journal of Computer and Information Technology, 3(2):1–7, 2012
work page 2012
-
[2]
Frozenqubits: Boosting fidelity of qaoa by skipping hotspot nodes
Ramin Ayanzadeh, Narges Alavisamani, Poulami Das, and Moinuddin Qureshi. 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, 2023
work page 2023
-
[3]
Vicky Choi. Adiabatic quantum algorithms for the NP-complete maximum-weight independent set, exact cover and 3SAT problems. 2010
work page 2010
-
[4]
Vicky Choi. Different adiabatic quantum optimization algorithms for the NP-complete exact cover and 3SAT problems. 2011
work page 2011
-
[5]
An introduction to the ising model
Barry A Cipra. An introduction to the ising model. The American Mathematical Monthly, 94(10):937–959, 1987
work page 1987
-
[6]
The maximum clique enumeration problem: Algorithms, applications and implementations
John D Eblen, Charles A Phillips, Gary L Rogers, and Michael A Langston. The maximum clique enumeration problem: Algorithms, applications and implementations. In International Symposium on Bioinformatics Research and Applications , pages 306–319. Springer, 2011
work page 2011
-
[7]
A quantum approximate optimization algorithm
Edward Farhi, Jeffrey Goldstone, and Sam Gutmann. A quantum approximate optimization algorithm. arXiv preprint arXiv:1411.4028 , 2014
arXiv 2014
-
[8]
Quantum supremacy through the quantum approximate optimization algorithm
Edward Farhi and Aram W Harrow. Quantum supremacy through the quantum approximate optimization algorithm. arXiv preprint arXiv:1602.07674, 2016
arXiv 2016
Show all 33 references
-
[9]
A tutorial on formulating and using qubo models
Fred Glover, Gary Kochenberger, and Yu Du. A tutorial on formulating and using qubo models. arXiv preprint arXiv:1811.11538 , 2018
2018 arXiv
-
[10]
Quantum bridge analytics I: A tutorial on formulating and using QUBO models
Fred Glover, Gary Kochenberger, and Yu Du. Quantum bridge analytics I: A tutorial on formulating and using QUBO models. 2019
2019
-
[11]
Impact of graph structures for qaoa on maxcut
Rebekah Herrman, Lorna Treffert, James Ostrowski, Phillip C Lotshaw, Travis S Humble, and George Siopsis. Impact of graph structures for qaoa on maxcut. Quantum Information Processing , 20(9):289, 2021
2021
-
[12]
On the computational complexity of combinatorial problems
Richard M Karp. On the computational complexity of combinatorial problems. Networks, 5(1):45–68, 1975
1975
-
[13]
A survey on hamiltonian cycles
Ken-ichi Kawarabayashi. A survey on hamiltonian cycles. Interdisci- plinary Information Sciences , 7(1):25–39, 2001
2001
-
[14]
Locating a cycle in a transportation or a telecommunications network
Gilbert Laporte and Inmaculada Rodr ´ıguez Mart ´ın. Locating a cycle in a transportation or a telecommunications network. Networks: An International Journal, 50(1):92–108, 2007
2007
-
[15]
Parameters fixing strategy for quantum approximate optimization algo- rithm
Xinwei Lee, Yoshiyuki Saito, Dongsheng Cai, and Nobuyoshi Asai. Parameters fixing strategy for quantum approximate optimization algo- rithm. In 2021 IEEE international conference on quantum computing and engineering (QCE) , pages 10–16. IEEE, 2021
2021
-
[16]
Mapping NP-hard and NP-complete optimisation prob- lems to quadratic unconstrained binary optimisation problems
Bas Lodewijks. Mapping NP-hard and NP-complete optimisation prob- lems to quadratic unconstrained binary optimisation problems. 2020
2020
-
[17]
On np-intermediate, isomorphism problems, and polynomial hierarchy
Xin Lu. On np-intermediate, isomorphism problems, and polynomial hierarchy
-
[18]
Ising formulations of many np problems
Andrew Lucas. Ising formulations of many np problems. Frontiers in physics, 2:5, 2014
2014
-
[19]
Depth optimized ansatz circuit in qaoa for max-cut
Ritajit Majumdar, Debasmita Bhoumik, Dhiraj Madan, Dhinakaran Vinayagamurthy, Shesha Raghunathan, and Susmita Sur-Kolay. Depth optimized ansatz circuit in qaoa for max-cut. arXiv preprint arXiv:2110.04637, 2021
2021 arXiv
-
[20]
Map- ping NP-hard problems to restructed adiabatic quantum architectures
Gary Mooney, Sam Tonetto, Charles Hill, and Lloyd Hollenberg. Map- ping NP-hard problems to restructed adiabatic quantum architectures. 2019
2019
-
[21]
Mathematical foundation of quantum annealing
Satoshi Morita and Hidetoshi Nishimori. Mathematical foundation of quantum annealing. Journal of Mathematical Physics , 49(12), 2008
2008
-
[22]
More efficient parameter initialization strategy in qaoa for maxcut
Xiao-Hui Ni, Bin-Bin Cai, Hai-Ling Liu, Su-Juan Qin, Fei Gao, and Qiao-Yan Wen. More efficient parameter initialization strategy in qaoa for maxcut. arXiv preprint arXiv:2306.06986 , 2023
2023 arXiv
-
[23]
Optimizing qaoa: Success probability and runtime dependence on circuit depth
Murphy Yuezhen Niu, Sirui Lu, and Isaac L Chuang. Optimizing qaoa: Success probability and runtime dependence on circuit depth. arXiv preprint arXiv:1905.12134, 2019
1905 arXiv
-
[24]
Efficient depth selection for the implementation of noisy quantum approximate opti- mization algorithm
Yu Pan, Yifan Tong, Shibei Xue, and Guofeng Zhang. Efficient depth selection for the implementation of noisy quantum approximate opti- mization algorithm. Journal of the Franklin Institute , 359(18):11273– 11287, 2022
2022
-
[25]
Automatic depth optimization for a quantum approximate optimization algorithm
Yu Pan, Yifan Tong, and Yi Yang. Automatic depth optimization for a quantum approximate optimization algorithm. Physical Review A , 105(3):032433, 2022
2022
-
[26]
Graph decompo- sition techniques for solving combinatorial optimization problems with variational quantum algorithms
Moises Ponce, Rebekah Herrman, Phillip C Lotshaw, Sarah Powers, George Siopsis, Travis Humble, and James Ostrowski. Graph decompo- sition techniques for solving combinatorial optimization problems with variational quantum algorithms. arXiv preprint arXiv:2306.00494, 2023
2023 arXiv
-
[27]
Parallel maximum clique algorithms with applications to network analysis
Ryan A Rossi, David F Gleich, and Assefaw H Gebremedhin. Parallel maximum clique algorithms with applications to network analysis. SIAM Journal on Scientific Computing , 37(5):C589–C616, 2015
2015
-
[28]
Approximate approximation on a quantum annealer
Irmi Sax, Sebastian Feld, Sebastian Zielinski, Thomas Gabor, Claudia Linnhoff-Popien, and Wolfgang Mauerer. Approximate approximation on a quantum annealer. In Proceedings of the 17th ACM International Conference on Computing Frontiers , pages 108–117, 2020
2020
-
[29]
Error mitigation for deep quantum optimization circuits by leveraging problem symmetries
Ruslan Shaydulin and Alexey Galda. 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
2021
-
[30]
Classical symmetries and qaoa
Ruslan Shaydulin, Stuart Hadfield, Tad Hogg, and Ilya Safro. Classical symmetries and qaoa. arXiv preprint arXiv:2012.04713 , 2020
2012 arXiv
-
[31]
Exploiting symmetry reduces the cost of training qaoa
Ruslan Shaydulin and Stefan M Wild. Exploiting symmetry reduces the cost of training qaoa. IEEE Transactions on Quantum Engineering , 2:1–9, 2021
2021
-
[32]
Experimental quantum annealing: case study involving the graph isomorphism prob- lem
Kenneth M Zick, Omar Shehab, and Matthew French. Experimental quantum annealing: case study involving the graph isomorphism prob- lem. Scientific reports, 5(1):11168, 2015
2015
-
[33]
Multiscale quantum approximate optimization algorithm
Ping Zou. Multiscale quantum approximate optimization algorithm. arXiv preprint arXiv:2312.06181 , 2023. APPENDIX V = 30, E= 87 V = 30, E= 174 V = 60, E= 354 V = 6, E= 10 V = 6, E= 8 V = 8, E= 16 V = 10, E= 31 V = 10, E= 20 V = 20, E= 114 K = 3 K = 3 K = 3 V = 30, E= 131 V = 3...
2023 arXiv
Reviewed August 12, 2026 · model on record in the stance chip above.
Discussion (0). Continue with ORCID to comment.