Rasengan: A Transition Hamiltonian-based Approximation Algorithm for Solving Constrained Binary Optimization Problems

---

Review Form

Reviewer: The Guardian (Adversarial Skeptic)

Summary

The authors propose "Rasengan," a variational quantum algorithm for constrained binary optimization. The core idea deviates from traditional VQAs by expanding the search space from a single known feasible solution rather than shrinking it from a global superposition. This expansion is driven by a proposed "transition Hamiltonian," derived from the homogeneous basis of the problem's linear constraints. To make the algorithm deployable, the authors introduce several optimization techniques: Hamiltonian simplification/pruning, a "segmented execution" strategy to manage circuit depth, and a "purification" step for error mitigation. The paper claims significant improvements in both accuracy (ARG) and circuit depth over existing methods like penalty-term QAOA and commute-Hamiltonian-based QAOA (Choco-Q).

While the paper presents a novel approach built on a sound linear algebra foundation, its claims of superiority rest on a series of methodological choices and dramatic optimizations that warrant severe scrutiny. The core algorithm appears undeployable in its pure form, and its claimed practical success is almost entirely dependent on a segmented, measurement-heavy execution model that challenges its classification as a cohesive quantum algorithm.

Strengths

1. Conceptual Foundation: The core concept of building the solution space from a known feasible solution (xp) and the null space (u) of the constraint matrix (C) is sound from a linear algebra perspective. Framing this expansion in the language of a "transition Hamiltonian" is a clear and direct way to map the classical concept to a quantum operator.

2. Problem Formulation: The paper is well-structured and clearly identifies a key weakness in existing VQAs for constrained problems—namely, the inefficiency of searching a vast, mostly infeasible space. The proposed "expand-from-feasible" approach is a logical alternative.

3. Ablation Study: The inclusion of an ablation study (Section 5.6, Figures 15 and 16) is commendable, as it provides some insight into the relative impact of each proposed optimization. However, the interpretation of these results is debatable, as I will detail below.

Weaknesses

1. The "Segmented Execution" Breaks Coherent Quantum Evolution: The paper's claim to deployability hinges critically on the "segmented execution" strategy (Section 4.2). This technique partitions the sequence of Hamiltonians, executes each segment, measures the result, and uses the output probability distribution to initialize the next segment. This is not a continuous, coherent quantum evolution. It is a sequence of distinct quantum-classical steps. By collapsing the wavefunction to a classical probability distribution between segments, any quantum coherence and entanglement that might have been built up across segments is destroyed. This raises a fundamental question: is Rasengan a true quantum algorithm, or a classical heuristic that uses a quantum computer as a parameterized sampler at each step? The claim that it "preserves the probability information" (Section 4.2, Page 7) is insufficient; the crucial aspect of a quantum algorithm is the evolution of amplitudes in a superposition, which is explicitly broken here.

2. Misleading Baseline Comparisons: The primary claims of algorithmic superiority are based on potentially unfair comparisons. In Table 2, the baselines (HEA, P-QAOA, Choco-Q) are run with a fixed five layers. However, the paper's own analysis in Figure 9 demonstrates that the performance of Choco-Q improves dramatically with more layers, approaching Rasengan's accuracy at 14 layers. Therefore, the headline claim of a 4.12x accuracy improvement (from the abstract) is derived from comparing Rasengan against under-parameterized and non-optimized baselines. A rigorous comparison would benchmark algorithms against a fixed resource budget (e.g., total circuit depth or number of CNOTs), not a fixed, arbitrary layer count.

3. Grossly Overstated Real-Hardware Performance: The 379x improvement claim on real hardware (Section 5.4, Figure 11) is profoundly misleading. The data shows that the baseline algorithms produce ARGs greater than 90, which indicates a complete failure to find any meaningful solution—they are effectively outputting noise. Rasengan's achievement is not outperforming them in a meaningful way, but simply not failing as catastrophically. Attributing a "379x improvement" to this is statistically questionable. This success is likely due to the segmented, shallow-depth nature of the execution and the aggressive post-selection, which makes it more resilient to decoherence, rather than inherent algorithmic superiority.

4. "Purification" is Trivial Post-Selection: The "Error Mitigation by Purification" (Section 4.3) is presented as a novel technique. It is not. It is simply checking if a measurement result satisfies the classical constraints (Cx = b) and discarding it if it does not. This is standard post-selection. While necessary, its impact is misrepresented. The 100% in-constraints rate reported in noisy experiments (Figure 11b) is not an achievement of the algorithm in handling noise, but a direct artifact of this filtering process. Furthermore, the massive 303x ARG improvement on hardware attributed to Opt 3 (which includes purification) in Figure 16 reveals that this filtering step is responsible for the vast majority of the claimed performance, masking the poor quality of the raw quantum output.

5. Contradictory Circuit Complexity Narrative: The paper initially presents a transition Hamiltonian that requires "34k CX gates" where k is the number of non-zero elements in the basis vector (Section 3.2, Page 5). For non-trivial problems, this is undeployable on any NISQ device. The paper only achieves a deployable depth (~50, Section 4) via the "segmented execution" method, which, as argued in point #1, fundamentally changes the nature of the algorithm. The narrative presents a single algorithm, "Rasengan," but its theoretical formulation and its practical implementation are two vastly different procedures.

Questions to Address In Rebuttal

1. Please provide a theoretical justification for how "segmented execution" (Section 4.2), which involves intermediate measurements and classical handoffs, preserves the quantum computational advantage of superposition and entanglement across the entire problem evolution. How does this method differ from a classical search heuristic that uses a quantum device as a parameterized sampler at each step?

2. Given that Figure 9 shows Choco-Q's ARG improves significantly with more layers, how can the authors justify the fixed 5-layer comparison in Table 2 and the resulting 4.12x improvement claim? A fair comparison would require comparing both algorithms under an equivalent resource budget (e.g., total circuit depth or execution time).

3. Can the authors defend the 379x hardware improvement claim (Figure 11) when the baselines are performing at near-random levels (ARG > 90)? Does this result demonstrate genuine algorithmic superiority, or merely that the baselines are more fragile to noise and Rasengan's segmented, post-selected approach is less so?

4. Please clarify the contribution of the "purification" technique (Section 4.3). Since this is equivalent to post-selecting valid solutions, how does it address the underlying noise in the quantum computation itself, rather than simply filtering the final, noisy output distribution? Does this post-selection not risk biasing the final solution, especially if noise affects different basis states non-uniformly?

---

Review Form

Reviewer: The Synthesizer (Contextual Analyst)

Summary

This paper introduces Rasengan, a novel variational quantum algorithm (VQA) for solving constrained binary optimization problems. The work's essential contribution is a fundamental inversion of the typical VQA search strategy. Instead of starting with a superposition of all possible states (both feasible and infeasible) and attempting to "shrink" the search space towards an optimal solution, Rasengan begins with a single, classically-found feasible solution and uses a specially constructed "transition Hamiltonian" to "expand" the search space to cover all other feasible solutions.

This transition Hamiltonian is elegantly derived from the homogeneous basis vectors (the null space) of the problem's linear constraint matrix, ensuring that every step of the quantum evolution remains strictly within the feasible subspace. The authors complement this core algorithmic idea with a suite of pragmatic algorithm-hardware co-design techniques—including Hamiltonian simplification, pruning of redundant transitions, segmented execution to manage circuit depth, and a purification step for error mitigation. These optimizations make the conceptually powerful idea deployable on near-term quantum hardware. The paper presents a comprehensive evaluation demonstrating significant improvements in both accuracy and circuit depth over existing state-of-the-art methods like penalty-based and commute-Hamiltonian QAOA.

Strengths

1. Powerful Conceptual Shift: The most significant strength of this work is its core idea of "expanding" the feasible space rather than "shrinking" the total space (beautifully illustrated in Figure 2, page 4). This directly addresses a primary source of inefficiency in many quantum optimization algorithms, which expend vast computational resources navigating a huge, mostly infeasible search space. By constraining the search to the relevant subspace from the very beginning, the algorithm promises a much more efficient use of quantum resources.

2. Elegant Connection Between Linear Algebra and Quantum Dynamics: The formulation of the transition Hamiltonian (Section 3.1, page 4) based on the homogeneous basis vectors of the constraint system Cx=b is a particularly insightful contribution. It provides a rigorous mathematical bridge between the classical, algebraic structure of the problem's constraints and the quantum evolution needed to explore the solution space. This is a far more structured and problem-aware approach than the generic mixers used in standard QAOA or the adaptive layers of a Hardware Efficient Ansatz (HEA).

3. Pragmatic Co-Design for NISQ-era Reality: The authors do not stop at a purely theoretical proposal. The optimization techniques presented in Section 4 (page 6) show a mature understanding of the practical limitations of current quantum computers. Segmented execution, in particular, is a clever strategy to execute deep logical circuits on hardware with short decoherence times. This combination of a strong theoretical idea with practical, hardware-aware engineering is a major strength and is what makes the impressive real-hardware results (Figure 11, page 10) believable and impactful.

4. Strong Empirical Validation: The experimental evaluation is extensive and convincing. The authors test their method against relevant baselines across five different problem domains (Table 2, page 8), analyze scalability (Figure 10, page 9), and demonstrate performance on real IBMQ hardware. The reported 4.12x accuracy improvement over the state-of-the-art Choco-Q and the staggering 379x improvement on a real quantum device are compelling evidence of the method's potential.

Weaknesses

My critiques are less about fundamental flaws and more about clarifying the boundaries and assumptions of the proposed method, which will help contextualize its applicability.

1. Dependence on an Initial Feasible Solution: The entire framework is predicated on the ability to classically and efficiently find at least one feasible solution to initialize the algorithm. The authors state this can often be done in linear time (Section 5.1, page 7), which is true for the benchmarks chosen (e.g., facility location, set cover). However, for other classes of problems, particularly those with very tight or complex constraints (e.g., certain integer linear programs), finding any feasible solution can be an NP-hard problem in itself. This assumption represents a key boundary on the applicability of Rasengan.

2. Limited Scope of Constraints: The methodology is presented for problems with linear equality constraints (Cx=b). While the paper notes that inequalities can be handled by introducing slack variables, this standard technique can significantly increase the number of required qubits, which is the most precious resource in the NISQ era. The work would be strengthened by a more thorough discussion of its applicability and potential performance degradation when applied to problems dominated by inequalities or those with non-linear constraints.

3. Implicit Assumptions on Basis Sparsity: The performance of the algorithm, especially the complexity of the transition Hamiltonian circuit, depends on the number of non-zero elements in the homogeneous basis vectors. While the Hamiltonian simplification technique (Section 4.1, page 6) is designed to mitigate this, the paper does not fully explore the worst-case scenario where the basis vectors are pathologically dense. This could lead to circuits that remain prohibitively deep even after optimization, representing another potential boundary condition.

Questions to Address In Rebuttal

1. Could the authors comment on the applicability of Rasengan to problems where finding an initial feasible solution is itself computationally difficult? Does the framework offer any recourse in such scenarios, or would it be considered out-of-scope for this method?

2. Regarding the handling of inequality constraints, could the authors provide some analysis or experimental data on how the introduction of slack variables impacts Rasengan's performance? Specifically, how does the increase in qubit count affect the circuit depth and overall accuracy compared to methods that handle inequalities more natively?

3. While the Hamiltonian simplification and pruning are shown to be effective on the chosen benchmarks, could the authors elaborate on the theoretical limitations of these techniques? Are there known problem structures or constraint topologies that would result in dense homogeneous basis vectors for which these optimizations would provide limited benefit?

---

Review Form

Reviewer: The Innovator (Novelty Specialist)

Summary

The paper introduces "Rasengan," a variational quantum algorithm (VQA) for constrained binary optimization problems with linear constraints. The central claim of novelty lies in its core methodology: instead of starting with a superposition of all possible states and "shrinking" the search space towards a feasible optimum (the standard QAOA paradigm), Rasengan starts from a single, classically-determined feasible solution and "expands" the search space to cover all other feasible solutions.

This expansion is achieved through a novel construct the authors term the "transition Hamiltonian," which is derived directly from the homogeneous basis of the problem's linear constraint matrix. The algorithm iteratively applies these transition Hamiltonians to navigate exclusively between basis states corresponding to feasible solutions. The paper also presents a set of co-design optimizations (Hamiltonian simplification/pruning, segmented execution, and purification) to make this approach viable on NISQ-era hardware.

Strengths

My evaluation identifies the following genuinely novel contributions:

1. Core Algorithmic Paradigm Shift: The primary strength and most significant novel contribution is the conceptual reversal from a "shrinking" to an "expanding" search space. To my knowledge, existing VQAs for this problem class, such as penalty-based QAOA or commute-Hamiltonian QAOA (like Choco-Q [43]), operate by either penalizing infeasible states or designing mixers that confine the evolution within the feasible subspace. Rasengan's approach of structured, generative exploration from a single point using the algebraic properties of the constraints is a fundamentally new and distinct VQA design pattern. This is clearly articulated in Figure 2 (page 4).

2. The "Transition Hamiltonian" Construct: The specific formulation of the transition Hamiltonian H(u) in Section 3.1 (Equation 7, page 5) is a novel piece of technical machinery. It translates a vector from the constraint's null space (u) directly into a quantum operator that performs a transition between two specific feasible solutions. This creates a direct, programmable link between the algebraic structure of the problem and the quantum evolution, which is a more tailored approach than the generic mixers used in standard QAOA.

3. Decoupling of Objective Function from Quantum Evolution: A subtle but profound novelty is that Rasengan’s quantum circuit is entirely agnostic to the objective function. Standard QAOA requires encoding the objective function into a (potentially complex) phase-separating Hamiltonian. Here, the quantum evolution's sole purpose is to navigate the feasible space. The objective function is evaluated purely classically on the measurement outcomes. This offloading of complexity from the quantum to the classical component represents a new way of structuring a hybrid quantum-classical workflow for optimization.

Weaknesses

My analysis identifies areas where the novelty is either overstated or not sufficiently demarcated from existing concepts:

1. Limited Novelty of Optimization Techniques in Isolation: The three optimization techniques presented in Section 4 (page 6) are novel in their specific integration but are conceptually derivative of prior art.

   • Segmented Execution (Section 4.2, page 7): The idea of breaking a deep circuit into shallower ones is well-established in the field, often under names like "circuit cutting" or in the context of dynamic circuits. The paper does not adequately compare its "probability-preserving" approach to this body of work to clearly isolate its novel contribution.
   • Error Mitigation by Purification (Section 4.3, page 7): This is a form of post-selection based on constraint satisfaction. Post-selection is a standard, albeit costly, error mitigation technique. Its application between segments is a specific implementation choice, but the underlying concept is not new.
   • Hamiltonian Simplification (Section 4.1, page 6): The greedy search for a sparser basis for the null space is a classical heuristic. While its application to reducing quantum circuit complexity is clever, the novelty lies in the application, not the technique itself.

2. Dependence on Classical Pre-Processing: The algorithm's novelty is purely in the quantum search phase. The entire framework is predicated on the ability to classically and efficiently find an initial feasible solution and the homogeneous basis ({u}). For problems where this classical pre-computation is itself NP-hard, the practical novelty of the quantum speedup is diminished. The paper should more clearly define the boundary of its contribution, acknowledging this reliance.

3. Constrained Scope of Novelty: The formulation of the transition Hamiltonian is explicitly tied to linear equality constraints (Cx=b). The paper makes no claims about extending this core novel idea to problems with non-linear or inequality constraints, thus limiting the generality of the proposed paradigm.

Questions to Address In Rebuttal

The authors should use the rebuttal to clarify the precise boundaries of their novel contributions:

1. Regarding "Segmented Execution" (Section 4.2, page 7): Can you elaborate on the key difference between your proposed method and established circuit cutting techniques? Is the primary novelty simply the dynamic re-allocation of shots based on intermediate probabilities, or is there a more fundamental distinction?

2. The decoupling of the objective function from the quantum circuit is a significant architectural change from QAOA. To your knowledge, is Rasengan the first VQA for optimization that uses the quantum evolution solely for state space navigation while leaving the objective evaluation entirely classical? Please position this contribution with respect to prior art.

3. The proposed method is applicable to problems with linear constraints. How would the core novel idea—the construction of a "transition Hamiltonian" from the problem structure—be formulated for problems with non-linear constraints? Does the paradigm break down, or is there a conceivable path to generalization?

4. The complexity of finding the homogeneous basis is a classical pre-processing cost. For which important problem classes is this step guaranteed to be polynomial, and are there classes where it is not? How does this affect the overall novelty of the quantum algorithm's contribution to solving the end-to-end problem?