Measurement-Guided State Refinement for Shallow Feedback-Based Quantum Optimization Algorithm

1. Problem Statement

The paper addresses a critical bottleneck in Noisy Intermediate-Scale Quantum (NISQ) computing: the limitation of circuit depth due to noise and decoherence.

• The Context: Combinatorial optimization problems (e.g., MaxCut) are often solved using variational algorithms (like QAOA) or feedback-based algorithms (like FALQON).
• The Limitation of FALQON: The Feedback-Based Algorithm for Quantum Optimization (FALQON) is a non-variational, constructive algorithm that updates parameters layer-by-layer based on measurement feedback, guaranteeing a monotonic decrease in cost energy. However, to reach high-quality solutions, standard FALQON typically requires deep circuits (many layers), which are currently infeasible on noisy hardware.
• The Gap: Existing improvements to FALQON (e.g., SO-FALQON, counterdiabatic control) still generally require deep circuits. Furthermore, standard implementations initialize the algorithm with a uniform superposition state, ignoring information gathered from previous runs. The authors ask: Can we retain the non-variational, feedback-driven advantages of FALQON while strictly limiting the circuit to a shallow depth?

2. Methodology: Measurement-Guided Initialization (MGI)

The authors propose Measurement-Guided Initialization (MGI), an iterative strategy that refines the starting state of the FALQON algorithm using data from previous shallow executions. This approach replaces the need for deep unitary evolution with measurement-driven iterative refinement.

Core Workflow (MGI-FALQON):

The algorithm operates in an outer loop of $R$ iterations. In each iteration $r$:

1. Execution: A fixed-depth (shallow) FALQON circuit is executed starting from a current initial state $|\psi^{(r)}_0\rangle$.
2. Measurement & Filtering: The circuit is measured $N_{shots}$ times. The resulting bitstrings are sorted by frequency. A subset $S_n$ containing the $n$ most frequent bitstrings is selected to filter out noise and high-energy configurations.
3. Marginal Estimation: Single-qubit marginal probabilities are calculated from the filtered set. For qubit $i$, the probability $c^{(r)}_i$ of measuring state $|1\rangle$ is estimated as the weighted frequency of $|1\rangle$ in the top $n$ bitstrings.
4. Biased State Preparation: A new initial state $|\psi^{(r+1)}_0\rangle$ is prepared as a biased product state. This is achieved by applying local $R_y$ rotations to the $|0\rangle$ state, where the rotation angle $\theta^{(r)}_i$ is derived from the marginal probability:
   $$\theta^{(r)}_i = 2 \arcsin\left(\sqrt{c^{(r)}_i}\right)$$
   This effectively compresses the measurement statistics into a product-state initialization that biases the search toward promising regions of the Hilbert space.

Key Distinctions:

• Non-Variational: Unlike QAOA, MGI-FALQON does not use a classical optimizer to tune parameters. The feedback is purely quantum-measurement driven.
• Iterative Refinement: Instead of increasing circuit depth to concentrate probability, the algorithm increases the quality of the initial state through iterations.
• Adaptive Filtering: The paper explores strategies for the number of selected bitstrings ($n$). It finds that adaptive strategies (starting with a large $n$ to capture broad structure and decreasing $n$ as the distribution concentrates) often yield the best results.

3. Key Contributions

1. Novel Framework: Introduction of MGI, a method that trades circuit depth for iterative measurement-based state refinement, specifically designed for the FALQON algorithm.
2. Theoretical Insight: The authors frame the reinitialization step as a projection onto a product-state manifold. By minimizing the Kullback-Leibler divergence between the empirical distribution and a factorized distribution, the method effectively creates a "mean-field" approximation of the dominant low-energy region.
3. Scalability Analysis: The method is validated not just on small instances but also on larger graphs (up to 20 vertices), demonstrating that the qualitative convergence behavior holds as system size increases.
4. Resource Efficiency: The study quantifies the trade-off, showing that MGI-FALQON can achieve energy targets comparable to deep standard FALQON circuits using significantly shallower circuits (e.g., $L=5$ vs. $L \approx 100+$).

4. Results

The authors evaluated the method on weighted MaxCut instances (mapping QUBO problems) using random complete graphs with 8, 12, and 20 vertices.

• Performance on Shallow Circuits:
  • Standard FALQON with shallow depths (e.g., $L < 20$) failed to converge to high-quality solutions.
  • MGI-FALQON with the same shallow depths ($L=2$ to $L=20$) showed a consistent decrease in expected energy and an increase in the probability of measuring the optimal solution across iterations.
• Comparison of Strategies:
  • Fixed $n$: Large $n$ (e.g., 30) worked better for very shallow circuits, while small $n$ (e.g., 5) was better for deeper circuits.
  • Adaptive $n$: Strategies that decreased $n$ over iterations (e.g., $30 \to 5$) consistently outperformed fixed strategies in shallow regimes, balancing exploration (early iterations) and refinement (later iterations).
• Depth Efficiency:
  • To reach a normalized energy gap of $\delta \le 0.1$ (90% of the possible improvement), standard FALQON required depths in the range of $O(10^2)$ to $O(10^3)$.
  • MGI-FALQON achieved similar results with fixed depths of $L=2$ (for 8 vertices), $L=5$ (for 12 vertices), and $L=20$ (for 20 vertices).
• Robustness: Results averaged over 1,000 random graph instances confirmed that the method is robust and not dependent on specific problem instances.

5. Significance and Conclusion

• NISQ Compatibility: MGI-FALQON offers a practical pathway for solving combinatorial optimization problems on current noisy hardware where deep circuits are impossible. It allows the algorithm to "simulate" the effect of deep evolution through repeated shallow executions and state updates.
• Preservation of Structure: The method preserves the non-variational and feedback-driven nature of FALQON, avoiding the "barren plateau" issues and classical optimization overhead associated with variational algorithms like QAOA.
• Future Directions: The authors suggest that while product-state initialization is effective, future work could incorporate multi-qubit correlations (entangled initial states) to capture more complex structures in the solution space. Additionally, testing on real quantum processors is the next logical step to evaluate performance under realistic noise.

In summary, the paper demonstrates that measurement statistics can be effectively reused to iteratively reshape the initial state of a quantum algorithm, allowing shallow circuits to achieve the performance of much deeper ones without introducing classical parameter optimization.