Pith. sign in

REVIEW 5 major objections 5 minor 16 references

Quantum Approximate and Quantum Walk Optimization Approaches to Set Balancing

T0 review · 5 major / 5 minor · reviewed 2026-08-04 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗

Pith's one-line read The paper claims that implementing QAOA mixer unitaries with a scaled-exponential Pauli-string decomposition yields better approximation ratios and faster convergence than conventional circuits, even at depth one versus depth five.

desk verdict A sound QUBO formulation and a useful worked example, but the central decomposition-performance claim rests on a depth-1-vs-depth-5 comparison and is not supported as written. read the letter →

arxiv 2509.07200 v1 pith:MZ6F5TP6 submitted 2025-09-08 quant-ph

Nikhil Kowshik , Sayan Manna , Sudebkumar Prasant Pal This is my paper
classification quant-ph
keywords setbalancingQAOAQUBOquantumwalkoptimizationPauli-stringdecompositionmixerHamiltonianShannonentropydiscrepancytheory
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

This paper sets out to show that a purely implementation-level change — how the mixer unitary is compiled into gates — can substantially improve a variational quantum optimizer for the NP-hard set balancing problem. It maps the problem of splitting subjects into treatment and control groups so every binary attribute is balanced into a QUBO Ising Hamiltonian, then runs QAOA with six different mixer Hamiltonians and QWOA. The central claim is that realizing all mixer unitaries with a scaled-exponential Pauli-string decomposition produces consistently better approximation ratios and faster convergence than conventional circuit decompositions, even at depth 1 compared with depth 5. It also proposes a Shannon-entropy post-processing rule to choose among equal-energy solutions and reports that QWOA, while converging on small instances, is less efficient than QAOA because the feasible space is the whole binary cube. If true, the result points to circuit compilation as an underappreciated lever in near-term quantum optimization.

What carries the argument

The scaled-exponential Pauli-string circuit decomposition is the central mechanism: any Pauli string σ on n qubits can be conjugated by CNOTs and single-qubit gates into a simple form with a single X on one qubit, so e^{-iθσ} is built with only H, S, Rx rotations, and CNOTs on a star-like connectivity graph. The paper composes mixer unitaries from exponentials of single and summed Pauli strings using this construction, and attributes the observed QAOA performance gains to this implementation choice rather than to any change in the mixer Hamiltonian itself.

What would settle it

On a noiseless simulator, instantiate one mixer (say X or XY) at fixed parameters, run it at the same depth with both the conventional decomposition and the scaled-exponential decomposition, and compare the final expectation values over many shots; if the two disagree beyond shot noise, the implementations are not equivalent and the comparison is invalid, and if they agree, any claimed advantage must be reproduced at equal depth before attributing it to the decomposition.

Watch

Extended reading notes

Core claim

The paper's central discovery claim is that for set balancing, QAOA's performance depends strongly on how the mixer unitaries e^{-iβH_M} are decomposed into elementary gates. Using the scaled-exponential Pauli-string construction — which realizes e^{-iθσ} for any n-qubit Pauli string σ with single-qubit rotations and CNOTs in a star-like connectivity pattern — the authors report approximation ratios in the range 0.83–0.95 at just depth p=1 across matrix sizes up to 14×14, outperforming conventional (e.g., independent Rx-based, XY, SWAP, and Grover) mixer implementations at depth p=5. They emphasize that the mixer Hamiltonians themselves are unchanged; only the circuit implementation differs.

Load-bearing premise

The claimed performance gain rests on the assumption that the conventional circuits used as baselines implement exactly the same mixer unitaries as the scaled-exponential circuits, and that a depth-1 run of the new implementation is a fair comparison against depth-5 runs of the old ones; if the unitaries differ in accuracy or the depth difference is doing the work, the improvement is not attributable to the decomposition.

Editorial extensions

If this is right

  • If the decomposition advantage holds, QAOA users can get better approximation ratios with far fewer layers, reducing circuit depth and CNOT count for the same solution quality.
  • The QUBO formulation H(b)=b^T A^T A b gives a direct route from any binary attribute matrix to a quantum cost Hamiltonian, making set balancing and similar discrepancy problems accessible to variational solvers.
  • The Shannon-entropy post-processing rule provides a deterministic way to break ties among equal-energy bicolorings by favoring uniform feature distributions across partitions.
  • The claim that QWOA underperforms QAOA on full-hypercube solution spaces suggests quantum-walk optimizers should be reserved for problems with genuine constraints that shrink the feasible space.

Reading between the lines

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

  • A same-depth, same-parameter head-to-head of conventional versus scaled-exponential mixer circuits is the natural control; until that is shown, the depth-1 vs depth-5 comparison leaves room for the advantage to come from parameter-landscape differences rather than the decomposition itself.
  • The scaled-exponential decomposition's star-like connectivity could translate into even larger gains on real hardware, where limited qubit coupling and gate noise dominate — a testable extension beyond the simulator results reported here.
  • The Shannon-entropy selection metric is likely applicable beyond set balancing to any QUBO with row structure, such as portfolio balancing or stratified sampling, as a generic post-processor for degenerate optima.
  • The proposed QAOA-plus-Grover-oracle subspace method for QWOA could be evaluated separately to see whether restricting the walking space restores QWOA's competitiveness against QAOA.
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

5 major / 5 minor

Summary. The paper applies QAOA and QWOA to the NP-hard set balancing problem, formulated as a QUBO/Ising model. The authors derive a cost Hamiltonian from the squared L2 norm of the imbalance vector, implement QAOA with six mixer Hamiltonians, and compare a scaled-exponential Pauli-string circuit decomposition against standard circuit decompositions. They report that the decomposition yields improved approximation ratios even at lower depth. They also describe QWOA on the same problem, concluding it is less efficient than QAOA because the feasible space is the full Boolean hypercube, and propose a Shannon-entropy-based post-processing criterion for selecting among degenerate low-energy bicolorings.

Significance. If the central claim were established, the paper would be a useful case study in how circuit-level compilation of mixer unitaries can affect QAOA performance on a practical combinatorial problem. The QUBO-to-Ising mapping in Eqs. (4.3)-(4.7) is standard and appears correct, and the single worked QAOA example is plausible. However, the paper provides no reproducible code, no dataset description, no error bars, and no clearly specified baseline implementations. The load-bearing performance claim is based on a depth-1 versus depth-5 comparison, which cannot separate the effect of the decomposition from the effect of depth and parameter count. The entropy-based post-processing is a proposal without quantitative validation. The paper's ideas are worth testing, but in its current form the experimental evidence is insufficient to support the advertised conclusions.

major comments (5)
  1. [§4.3, §4.4, Figs. 9-10] The central claim that scaled-exponential Pauli-string decomposition yields superior QAOA performance rests on comparing depth p=1 decomposed circuits (Fig. 10) with depth p=5 conventional circuits (Fig. 9). QAOA performance generally depends on depth and parameter count, so the observed improvement in approximation ratio could be an artifact of the depth/parameter mismatch rather than of the decomposition. The comparison must be repeated at matched depth (or matched parameter and gate counts), with a unitary-fidelity check confirming that both circuits implement the same mixer unitaries. Without this, the abstract claim of 'superior performance' is not supported.
  2. [§4.4] The experimental section reports '20 iterations per mixer' and averages of approximation ratios, but no standard deviations, seeds, instance-generation procedure, or raw data are given. The claims that α falls to about 0.7 at size 14×14 for standard mixers and remains in [0.83,0.95] for the decomposition cannot be assessed without these details. Please provide a table with means, variances, and a precise description of the random matrices used.
  3. [§4.2.2-4.2.4, §4.3] For non-commuting mixer terms (XY, Full-SWAP, Ring-SWAP), the circuits in Figs. 4-6 implement products of terms such as RXX(β)RYY(β)..., which are not equal to exp(-iβ∑H_ij) unless the terms commute. The text does not specify whether the baseline and decomposed implementations use the same Trotterization/ordering and error tolerance. If they differ, the comparison conflates circuit-implementation error with the decomposition method. Specify the exact unitary realized by each mixer and verify equality (e.g., via state-vector fidelity) for both implementations.
  4. [§5.2, §5.3] The QWOA analysis is not a controlled comparison. The conclusion that 'QWOA is not efficient' is based on a single 10×10 instance, without comparing resource counts (depth, parameters, calls) against QAOA on the same instance. The modified method of §5.2 (QAOA-p=1 + Grover oracle + restricted QWOA) is described but never implemented or tested. This section should either be removed or supported by comparable experiments.
  5. [§6] The Shannon-entropy post-processing and the 3D radial metric are proposed but not validated. No experiment shows that selecting bicolorings by minimizing D/E or r improves the objective value or achieves better feature balance than simply taking the lowest-energy QAOA solutions. As written, this is a suggestion rather than a result; please add a quantitative evaluation.
minor comments (5)
  1. [§2] Equation (3.1) is numbered as if it belongs to Section 3; renumber or fix the cross-reference.
  2. [Eq. (4.7)] The notation Z_{n-i}, Z_{n-j} is confusing. Use Z_i, Z_j with explicit qubit labeling to indicate which qubits the Pauli-Z operators act on.
  3. [References] Reference [16] is cited for QWOA but appears to be a fermionic-view QAOA paper; the QWOA references should be [3] and [11].
  4. [§5.3] Typos: 'increawsing', 'quantum waklker', 'increawsing number of depths'. Please proofread.
  5. [Figures 8-10] The figures are referenced but their axes, legends, and exact data points are not described in the text. Add detailed captions or tables so the reader can interpret the plotted approximation ratios.

Circularity Check

0 steps flagged · score 1.0 of 10

No significant circularity; the core QUBO/QAOA derivation is self-contained, though the decomposition-performance claim is empirically under-supported.

full rationale

The paper's formal derivations are not circular. The set-balancing QUBO objective is obtained directly from the squared L2 imbalance: Eq. 4.3 gives b^T A^T A b, and the Pauli-Z cost Hamiltonian in Eq. 4.7 is a term-by-term translation of the same quadratic form. The scaled-exponential Pauli-string mixer implementation is imported from an external reference [14], and the paper's own performance comparison is an experimental claim rather than a derivation from that citation. I considered the possibility that the central claim in §4.3—that the scaled-exponential decomposition 'consistently produced improved approximation ratios and faster convergence'—is circular because the decomposition is compared against 'conventional' implementations at a different depth. However, this is a methodological confound, not a circular reduction: the paper does not define the conventional baseline's unitary in terms of the decomposition, nor does it fit a parameter and then rename it a prediction. The comparison in §4.4 uses depth p=1 for the decomposition and p=5 for conventional mixers (Figs. 9 vs 10), and the text does not establish that the two implementations realize identical unitaries. That is a significant correctness risk, but it does not make the derivation equivalent to its inputs. The citation to [14] is not a self-citation by the present authors, and the acknowledgment of Sabyasachi Chakrobarty does not turn the method into a circular premise. Overall, no circular step is exhibited; the score is low because the empirical performance claim is under-supported, not because it is circular.

Assumptions & free parameters 1 free parameters · 4 assumptions · 0 invented entities

The paper introduces no new physical or mathematical entities. The central empirical claim depends on assumptions about the equivalence of circuit implementations and the representativeness of the benchmarks, neither of which is verified.

free parameters (1)
  • Entropy tolerance epsilon
    Introduced in Eq (6.5) as a threshold to retain bicolorings with r <= epsilon; no value is assigned and it is not used in any reported experiment.
assumptions (4)
  • domain assumption The QUBO objective b^T A^T A b with b in {+1,-1} correctly represents the squared L2 imbalance of set balancing.
    Section 3.3, Eq (4.3). Standard but unproven in this paper; it is the basis of the cost Hamiltonian.
  • domain assumption The scaled-exponential Pauli-string circuit decomposition from [14] exactly implements the mixer unitaries and was implemented correctly for all six mixers.
    Section 4.3 relies entirely on this external method; the authors thank a co-author of [14] for the implementation, so the correctness is inherited, not demonstrated.
  • domain assumption The randomly generated matrices used for benchmarking are representative instances of the set balancing problem.
    Section 4.4 says 'randomly generated graphs' but gives no generator, size range, density, or seeds, so the results cannot be interpreted or reproduced.
  • standard math A noiseless quantum simulator is used, so the circuit implementation should not affect the ideal expectation values.
    The paper claims the simulator results depend on the circuit decomposition (Section 4.3), which contradicts the assumption of exact unitaries; this tension is unresolved.

how reviews work

0 comments
Cite this review

Pith. "Pith review of Quantum Approximate and Quantum Walk Optimization Approaches to Set Balancing." pith.science (2026). https://pith.science/paper/MZ6F5TP6

@misc{pith2026250907200,
  author       = {Pith},
  title        = {Pith review of: Quantum Approximate and Quantum Walk Optimization Approaches to Set Balancing},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/MZ6F5TP6}},
  note         = {Machine review of arXiv:2509.07200}
}
read the original abstract

We explore the application of variational quantum algorithms to the NP-hard set balancing problem, a critical challenge in clinical trial design and experimental scheduling. The problem is mapped to an Ising model, with tailored Quadratic Unconstrained Binary Optimization (QUBO) formulations and cost Hamiltonians expressed in Pauli-Z form. We implement both the Quantum Approximate Optimization Algorithm (QAOA) and the Quantum Walk Optimization Algorithm (QWOA), evaluating them in separate experimental settings. For QAOA, we perform a comparative analysis of six mixer Hamiltonians (X, XY, Full-SWAP, Ring-SWAP, Grover, and Warm-Started), employing scaled-exponential Pauli-string realizations of the mixer unitaries, which yield superior performance over conventional circuit decompositions. Additionally, we introduce a Shannon-entropy-based post-processing technique that refines solutions by maximizing feature-distribution uniformity across partitions. These results underscore the importance of mixer choice and circuit implementation in enhancing QAOA performance for combinatorial optimization.

Figures

Figures reproduced from arXiv: 2509.07200 by the authors.

Figure 1
Figure 1. Alternating layers of HC (represented here as HP )and HM form the quantum circuit and are optimized by a classical optimizer. Source for image is [1] 3. Set Balancing : Problem Definition The Set Balancing problem is a fundamental problem in discrepancy theory [4, 12] with significant applications in statistical experiment design, computational geometry, and combinatorial optimization. This problem involves finding … view at source ↗
Figure 2
Figure 2. Standard QAOA circuit on 10 qubits with depth=3 [PITH_FULL_IMAGE:figures/full_fig_p010_2.png] view at source ↗
Figure 3
Figure 3. X-Mixer Here, RX(β) = cos β 2  −isin β 2  −isin β 2  cos β 2  ! The overall unitary operator for the circuit is: HX-mixer = RX(β) (q0) ⊗ RX(β) (q1) ⊗ RX(β) (q2) ⊗ RX(β) (q3) (4.10) where RX(β) (qk) acts on qubit qk. 4.2.2 XY-Mixer The XY-mixer includes two-qubit interactions and preserves Hamming weight of the quantum states. It is given by: HM = X ⟨i,j⟩ (XiXj + YiYj ) (4.11) 11 [PITH_FULL_IMAGE:figures/full_fi… view at source ↗
Figures from the paper (15 more)
Figure 4
Figure 4. Figure 4: XY-Mixer for 4 qubits Where, RXX(θ) = e −i θ 2 (X⊗X) , RY Y (θ) = e −i θ 2 (Y ⊗Y ) RXX(θ) =   cos θ 2  0 0 −isin θ 2  0 cos θ 2  −isin θ 2  0 0 −isin θ 2  cos θ 2  0 −isin θ 2  0 0 cos θ 2    RY Y (θ) =   cos θ 2  0 0 isin θ 2  0 cos θ 2  −…
Figure 5
Figure 5. Figure 5: Full Swap mixer for 3 qubits thus, ZZ(θ) =   e −i θ 2 0 0 0 0 e i θ 2 0 0 0 0 e i θ 2 0 0 0 0 e −i θ 2   The overall unitary operator for the circuit is: HFull-SWAP = ZZ(β)q0q1 · RY Y (β)q0q1 · RXX(β)q0q1 · ZZ(β)q0q2 · RY Y (β)q0q2 · RXX(β)q0q2 · ZZ(β)q1q2 …
Figure 6
Figure 6. Figure 6: Ring-SWAP mixer for 3 qubits The overall unitary operator for the circuit is: HRing-SWAP = ZZ(β)q0q2 · RY Y (β)q0q2 · RXX(β)q0q2 · ZZ(β)q0q1 · RY Y (β)q0q1 · RXX(β)q0q1 · ZZ(β)q1q2 · RY Y (β)q1q2 · RXX(β)q1q2 (4.16) 13 [PITH_FULL_IMAGE:figures/full_fig_p013_6.png]
Figure 7
Figure 7. Figure 7: Grover mixer for 3 qubits. Global phase: [PITH_FULL_IMAGE:figures/full_fig_p014_7.png]
Figure 8
Figure 8. Figure 8: Comparison between brute force and QAOA methods for different matrix sizes [PITH_FULL_IMAGE:figures/full_fig_p016_8.png]
Figure 9
Figure 9. Figure 9: Comparison between various Mixers’ performances for the Set Balancing Prob [PITH_FULL_IMAGE:figures/full_fig_p016_9.png]
Figure 10
Figure 10. Figure 10: Comparison between various Mixers’ performances for the Set Balancing Prob [PITH_FULL_IMAGE:figures/full_fig_p017_10.png]
Figure 11
Figure 11. Figure 11: Schematic diagram of the QWOA circuit paired with a classical optimizer. [PITH_FULL_IMAGE:figures/full_fig_p018_11.png]
Figure 12
Figure 12. Figure 12: At depth=5 [PITH_FULL_IMAGE:figures/full_fig_p020_12.png]
Figure 13
Figure 13. Figure 13: At depth=8 [PITH_FULL_IMAGE:figures/full_fig_p020_13.png]
Figure 14
Figure 14. Figure 14: At depth=12 20 [PITH_FULL_IMAGE:figures/full_fig_p020_14.png]
Figure 15
Figure 15. Figure 15: At depth=16 [PITH_FULL_IMAGE:figures/full_fig_p021_15.png]
Figure 16
Figure 16. Figure 16: At depth=20 [PITH_FULL_IMAGE:figures/full_fig_p021_16.png]
Figure 17
Figure 17. Figure 17: At depth=50 21 [PITH_FULL_IMAGE:figures/full_fig_p021_17.png]
Figure 18
Figure 18. Figure 18: At depth=60 Therefore with the increawsing number of depths, the probability at being in the min￾imum energy state is increasing. At depth=60, only nonzero probability exists at energy level=4. Therefore, minimum objective function value is 4. Corresponding bicoloring…

Discussion (0). Sign in to comment.

Reference graph

Works this paper leans on

16 extracted references · 13 canonical work pages

  1. [14]

    Scalable quantum circuits for exponential of pauli strings and hamiltonian simulations, 2024

    Rohit Sarma Sarkar, Sabyasachi Chakraborty, and Bibhas Adhikari. Scalable quantum circuits for exponential of pauli strings and hamiltonian simulations, 2024

    work page 2024

  2. [1]

    ResearchGate, 2022

    Variational quantum algorithm applied to collision avoidance of unmanned aer- ial vehicles - scientific figure on researchgate. ResearchGate, 2022. Avail- able from:https://www.researchgate.net/figure/QAOA-circuit-diagram_ fig3_365507469[accessed 13 Nov 2024]

    work page 2022

  3. [2]

    Tameem Albash and Daniel A. Lidar. Adiabatic quantum computation.Reviews of Modern Physics, 90(1):015002, 2018

    work page 2018

  4. [3]

    Tavis Bennett, Edric Matwiejew, Sam Marsh, and Jingbo B. Wang. Quantum walk- based vehicle routing optimisation.Frontiers in Physics, 9:730856, 2021

    work page 2021

  5. [4]

    Cam- bridge University Press, 2000

    Bernard Chazelle.The Discrepancy Method: Randomness and Complexity. Cam- bridge University Press, 2000

    work page 2000

  6. [5]

    A quantum approximate op- timization algorithm.arXiv preprint arXiv:1411.4028, 2014

    Edward Farhi, Jeffrey Goldstone, and Sam Gutmann. A quantum approximate op- timization algorithm.arXiv preprint arXiv:1411.4028, 2014. 28

    arXiv 2014

  7. [6]

    A quantum adiabatic evolution algorithm applied to random instances of an np-complete prob- lem.arXiv preprint quant-ph/0001106, 2000

    Edward Farhi, Jeffrey Goldstone, Sam Gutmann, and Michael Sipser. A quantum adiabatic evolution algorithm applied to random instances of an np-complete prob- lem.arXiv preprint quant-ph/0001106, 2000

    arXiv 2000

  8. [7]

    Oliver and Boyd, 1935

    Ronald Aylmer Fisher.The Design of Experiments. Oliver and Boyd, 1935

    work page 1935

Show all 16 references
  1. [8]

    A tutorial on formulating and using qubo models.arXiv preprint arXiv:1811.11538, 2018

    Fred Glover, Gary Kochenberger, and Yu Du. A tutorial on formulating and using qubo models.arXiv preprint arXiv:1811.11538, 2018

    2018 arXiv

  2. [9]

    From the quantum approximate optimization algorithm to a quantum alternating operator ansatz.Algorithms, 12(2):34, 2019

    Stuart Hadfield, Zhihui Wang, Bryan O’Gorman, Eleanor G Rieffel, Davide Ven- turelli, and Rupak Biswas. From the quantum approximate optimization algorithm to a quantum alternating operator ansatz.Algorithms, 12(2):34, 2019

    2019

  3. [10]

    Ising formulations of many np-hard problems.Frontiers in Physics, 2014

    Andrew Lucas. Ising formulations of many np-hard problems.Frontiers in Physics, 2014

    2014

  4. [11]

    Combinatorial optimisation via highly efficient quantum walks.Phys

    Samuel Marsh and Jingbo Wang. Combinatorial optimisation via highly efficient quantum walks.Phys. Rev. Research, 2:023302, 2020

    2020

  5. [12]

    Roth, and Pascal O

    Arya Mazumdar, Ron M. Roth, and Pascal O. Vontobel. On linear balancing sets. arXiv preprint arXiv:0901.3170, 2009

    2009 arXiv

  6. [13]

    Cambridge University Press, 2005

    Michael Mitzenmacher and Eli Upfal.Probability and Computing: Randomized Al- gorithms and Probabilistic Analysis. Cambridge University Press, 2005

    2005

  7. [15]

    Six standard deviations suffice.Transactions of the American Math- ematical Society, 289(2):679–706, 1985

    Joel Spencer. Six standard deviations suffice.Transactions of the American Math- ematical Society, 289(2):679–706, 1985

    1985

  8. [16]

    Zhihui Wang, Stuart Hadfield, Zhang Jiang, and Eleanor G. Rieffel. Quantum ap- proximate optimization algorithm for max-cut: A fermionic view.Physical Review A, 97(2):022304, 2018. 29

    2018

Pith tools

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