Pith. sign in

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 →

arxiv 2411.08824 v1 pith:2RVEODDY submitted 2024-11-13 quant-ph

classification quant-ph MSC 81P68 PACS 03.67.Ac
keywords QAOAQUBOsemi-symmetriesancillaqubitscircuitdepthcouplingreductionIsingmodelParetofront
verification ladder T0 review T1 audit T2 compute T3 formal

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The reading

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.

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.

Watch

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

Editorial extensions of the paper, not claims the author makes directly.

  • 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.
Share X Bluesky LinkedIn Reddit HN

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Referee Report

4 major / 5 minor

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)
  1. [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.
  2. [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.
  3. [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.
  4. [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)
  1. [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.
  2. [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.
  3. [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.
  4. [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.
  5. [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

0 steps flagged · score 0.0 of 10

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 2 free parameters · 3 assumptions · 0 invented entities

The central claim rests on two unproven algorithmic assumptions: the conflict-detection heuristic and the iterative soundness with a fixed z. The Maximum Clique Hamiltonian is misstated, which undermines one of the five benchmark demonstrations. No new physical entities are introduced.

free parameters (2)
  • z (penalty value) = unspecified in experiments; recommended z = sum |Qij|
    Correctness of the enhancement depends on z being at least the sum of absolute moved couplings; the paper does not report the z used in the depth experiments, and the iterative algorithm with fixed z is unproven.
  • numAncillas (budget) = 0 to 29 in experiments
    User-chosen resource budget controlling the trade-off; does not affect correctness but shapes the reported reductions.
assumptions (3)
  • ad hoc to paper The conflict detection condition (Q[i,j] > -Z[i]-Z[j]) identifies conflicting qubits per Definition IV.1.
    Algorithm 1's getConflictList uses this inequality, but the paper never proves it is sufficient for the pairwise energy inequalities in Definition IV.1.
  • ad hoc to paper Repeated enhancement steps with a fixed z preserve the global optimum.
    Proposition IV.3 proves only a single enhancement; the algorithm loops until budget exhausted. No invariant or inductive argument is given for the composition.
  • domain assumption The Maximum Clique QUBO Hamiltonian H = sum -x_i + A*sum_{E} x_i x_j encodes maximum clique.
    This formulation penalizes edges rather than non-edges and would make the empty set the optimum; it is inconsistent with the standard Lucas formulation cited as [18].

how reviews work

0 comments
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 reproduced from arXiv: 2411.08824 by the authors.

Figure 1
Figure 1. A simple graph for demonstrating proof-of-concept. [PITH_FULL_IMAGE:figures/full_fig_p005_1.png] view at source ↗
Figure 2
Figure 2. The green line represents the sorted energy spectrum of the left QUBO in Table I. The orange lines represent the energy spectrum [PITH_FULL_IMAGE:figures/full_fig_p006_2.png] view at source ↗
Figure 3
Figure 3. This plot shows the results of our experiments on reducing the depth of QAOA circuits by factoring out [PITH_FULL_IMAGE:figures/full_fig_p007_3.png] view at source ↗
Figures from the paper (1 more)
Figure 4
Figure 4. Figure 4: Pareto Front of # Ancilla Qubits and # Couplings for 5 different optimization problems and 3 problem parameter settings each. Based on the results of this first experiment, we tran￾spiled the QAOA circuits for each QUBO QnumAncillas mod using p ∈ {1, 2, 3}. The plots i…

Discussion (0). Continue with ORCID to comment.

Forward citations

Cited by 1 Pith paper

Reviewed papers in the Pith corpus that reference this work. Sorted by Pith novelty score. Full citation record

  1. Analytical Expressions for the Quantum Approximate Optimization Algorithm and its Variants

    quant-ph 2024-11 conditional novelty 7.0 of 10

    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

33 extracted references · 23 canonical work pages · cited by 1 Pith paper

  1. [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

  2. [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

  3. [3]

    Adiabatic quantum algorithms for the NP-complete maximum-weight independent set, exact cover and 3SAT problems

    Vicky Choi. Adiabatic quantum algorithms for the NP-complete maximum-weight independent set, exact cover and 3SAT problems. 2010

  4. [4]

    Different adiabatic quantum optimization algorithms for the NP-complete exact cover and 3SAT problems

    Vicky Choi. Different adiabatic quantum optimization algorithms for the NP-complete exact cover and 3SAT problems. 2011

  5. [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

  6. [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

  7. [7]

    A quantum approximate optimization algorithm

    Edward Farhi, Jeffrey Goldstone, and Sam Gutmann. A quantum approximate optimization algorithm. arXiv preprint arXiv:1411.4028 , 2014

  8. [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

Show all 33 references
  1. [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

  2. [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

  3. [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

  4. [12]

    On the computational complexity of combinatorial problems

    Richard M Karp. On the computational complexity of combinatorial problems. Networks, 5(1):45–68, 1975

  5. [13]

    A survey on hamiltonian cycles

    Ken-ichi Kawarabayashi. A survey on hamiltonian cycles. Interdisci- plinary Information Sciences , 7(1):25–39, 2001

  6. [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

  7. [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

  8. [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

  9. [17]

    On np-intermediate, isomorphism problems, and polynomial hierarchy

    Xin Lu. On np-intermediate, isomorphism problems, and polynomial hierarchy

  10. [18]

    Ising formulations of many np problems

    Andrew Lucas. Ising formulations of many np problems. Frontiers in physics, 2:5, 2014

  11. [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

  12. [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

  13. [21]

    Mathematical foundation of quantum annealing

    Satoshi Morita and Hidetoshi Nishimori. Mathematical foundation of quantum annealing. Journal of Mathematical Physics , 49(12), 2008

  14. [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

  15. [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

  16. [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

  17. [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

  18. [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

  19. [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

  20. [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

  21. [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

  22. [30]

    Classical symmetries and qaoa

    Ruslan Shaydulin, Stuart Hadfield, Tad Hogg, and Ilya Safro. Classical symmetries and qaoa. arXiv preprint arXiv:2012.04713 , 2020

  23. [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

  24. [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

  25. [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...

Pith tools

Reviewed August 12, 2026 · model on record in the stance chip above.