Finite-Depth, Finite-Shot Guarantees for Constrained Quantum Optimization via Fejér Filtering

This paper establishes finite-depth and finite-shot, dimension-free lower bounds on the success probability of sampling optimal solutions for the Constraint-Enhanced Quantum Approximate Optimization Algorithm (CE-QAOA) by demonstrating that restricting cost angles to a harmonic lattice induces a positive Fejér filter effect.

The Gist

The Big Picture: Finding the Needle in a Haystack

Imagine you are trying to find the single best key (the optimal solution) that opens a treasure chest. However, you are in a giant room filled with millions of keys. Most of these keys are broken or don't fit the lock at all (they are infeasible). Only a tiny few actually fit the lock, and among those, only one is the "perfect" key.

This is the problem Quantum Computers try to solve using an algorithm called QAOA. The challenge is that quantum computers are noisy and can only run for a short time (limited depth) and can only take a limited number of measurements (limited shots). If the algorithm gets lost in the "broken keys" or takes too long to find the "perfect key," it fails.

This paper introduces a new way to guarantee success, even with limited time and resources. They call their method CE-QAOA with Fejér Filtering.

---

The Three Main Ingredients

1. The "Smart Room" (Constraint-Enhanced QAOA)

Standard algorithms wander randomly through the whole room, including the broken keys. This paper suggests building a Smart Room (a specific mathematical space called a manifold).

• The Analogy: Imagine instead of a giant messy room, you are in a hallway where every single object is guaranteed to be a working key. You can't accidentally pick up a broken key because the hallway is designed so that broken keys don't exist there.
• Why it matters: The algorithm doesn't waste time checking broken keys. It stays inside the "feasible zone" from the very start.

2. The "Mixing Dance" (The Mixer)

To find the best key, the quantum computer needs to shuffle the possibilities around, moving from one key to another.

• The Analogy: Think of the mixer as a DJ spinning a record. If the DJ spins too slowly or in a weird rhythm, the music (the probability of finding the right key) might get stuck.
• The Paper's Discovery: The authors prove that as long as the DJ (the mixer) spins at a "safe" speed (not hitting a specific mathematical "dead zone"), the dance will eventually cover every single spot in the hallway. This guarantees that the algorithm can reach the best key, provided it keeps dancing long enough.

3. The "Fejér Filter" (The Magic Sieve)

This is the paper's biggest innovation. Once the algorithm has shuffled the keys around, how do we make sure the best key pops up more often than the others?

• The Analogy: Imagine you have a sieve (a filter) with holes of a specific size.
  • The Problem: If you just shake the box, the best key might be buried under bad ones.
  • The Solution: The authors use a Fejér Filter. Think of this as a magical sieve that is shaped like a "bell curve" or a "hill."
  • How it works: The "perfect key" sits right at the top of the hill. The "okay keys" are on the slopes, and the "bad keys" are in the deep valleys.
  • The Fejér filter is designed so that it amplifies the top of the hill (the best solution) and suppresses the valleys (the bad solutions). It acts like a spotlight that shines brightest exactly where the answer is, while dimming the noise around it.

---

The "Harmonic Lattice" (The Secret Sauce)

For this magic sieve to work perfectly, the "heights" of the keys (their costs) need to follow a specific pattern, like steps on a staircase.

• The Analogy: Imagine the keys are musical notes. If the notes are perfectly in tune (on a "harmonic lattice"), the Fejér filter acts like a perfect amplifier for the right note.
• The Reality Check: In the real world, notes aren't always perfectly in tune. The authors show that even if the notes are slightly off (due to noise or messy data), you can just "shake" the filter a tiny bit (a technique called Riemann-Lebesgue averaging). This smooths out the imperfections, and the filter still works great.

---

The Guarantee: "How Many Times Do I Need to Try?"

The most exciting part of the paper is the Guarantee. Usually, with quantum computers, we say, "It might work, or it might not." This paper says, "We can calculate exactly how many times you need to try."

They derived a simple formula:
$$\text{Success Rate} \approx \frac{x}{1 + x}$$

Where $x$ depends on three things:

1. Depth ($p$): How many layers of the algorithm you run (how long you dance).
2. The Gap ($\delta$): How clearly the "best key" stands out from the "okay keys."
3. The Mass ($C_\beta$): How much of the "mixing dance" actually lands on the good keys.

The Magic Result:
If you run the algorithm for a specific, finite amount of time (depth) and the "gap" isn't too tiny, you are guaranteed to find the solution.

• Dimension-Free: This is huge. It means the number of tries you need does not depend on how big the problem is. Whether you are solving a puzzle with 10 pieces or 10,000 pieces, if the "gap" and "mixing" are good, the number of tries stays manageable.

Summary for the General Audience

Imagine you are looking for a specific person in a crowded stadium.

1. Old Way: You shout randomly and hope they hear you. It might take forever.
2. This Paper's Way:
   • You build a fence around the section where that person must be (Constraint-Enhanced).
   • You use a megaphone that has a special "Fejér" pattern. This pattern makes your voice boom loudly only in the exact seat where the person is sitting, while whispering everywhere else.
   • Even if the stadium is huge (large dimension), as long as the person isn't hiding in a seat that looks exactly like their neighbor's (the phase gap), you will find them quickly.

The Bottom Line: The authors have found a mathematical "safety net" that proves we can solve complex optimization problems on quantum computers with a predictable, limited number of attempts, without needing to know the exact size of the problem beforehand.

Technical Summary

1. Problem Statement

The paper addresses the challenge of providing rigorous feasibility and optimality guarantees for constrained quantum optimization algorithms, specifically the Constraint-Enhanced Quantum Approximate Optimization Algorithm (CE-QAOA).

• Context: Standard QAOA and its variants often struggle with constrained problems because shallow circuits may be dynamically misaligned with the geometry of the feasible set, leading to ineffective amplitude transport between valid configurations.
• Gap: While CE-QAOA (introduced in a prior work) operates natively on a "block one-hot" manifold to preserve constraints, there was a lack of theoretical guarantees regarding:
  1. Feasibility: Whether the algorithm can reach the feasible subspace at finite depth.
  2. Optimality: Whether the algorithm can sample the optimal solution with high probability using a finite number of shots (measurements) and finite circuit depth, independent of the problem dimension (Hilbert space size).

2. Methodology

The authors employ a novel analytical framework that combines quantum dynamics with harmonic analysis, specifically utilizing Fejér kernels.

A. The CE-QAOA Ansatz

The study focuses on CE-QAOA, which uses:

• Encoding: A fixed encoding into a block one-hot manifold (one excitation per block).
• Mixer: A normalized block-XY mixer ($U_M$) that preserves the constraint subspace.
• Cost Unitary: $U_C(\gamma) = e^{-i\gamma H_C}$, where $H_C$ includes both the objective function and penalty terms for constraints.

B. The "Classicalized" Reference Model

To derive analytical bounds, the authors introduce a cost-basis dephasing/twirling channel ($\mathcal{T}$) between layers.

• Purpose: This is an analytic device (not part of the actual hardware execution) that removes off-diagonal coherences. It transforms the quantum evolution into a classical Markov process on the diagonal of the density matrix.
• Result: This exposes the measurement probability distribution as a product of two terms:
  1. Mixer Envelope ($W_p$): A classical probability distribution induced by the mixer, representing the "exploration" capability.
  2. Positive Trigonometric Filter: A kernel acting on the cost phases, representing the "selection" capability.

C. Fejér Filtering Mechanism

By restricting the cost angles to a harmonic lattice ($\gamma_r = r\gamma$), the interference terms in the cost unitary sum up to form a Fejér kernel ($F_p$).

• The Fejér kernel is a positive, non-negative trigonometric polynomial.
• It acts as a filter that amplifies the probability mass at the optimal phase (peak) and suppresses mass at non-optimal phases (off-peak), provided there is a phase gap ($\delta$) between the optimal and suboptimal solutions.

3. Key Contributions

1. Existence of Constant Feasibility Probability

The authors prove that for the CE-QAOA mixer, the dynamics are ergodic and primitive on the encoded manifold.

• They establish that the mixer induces a Markov chain with strictly positive transition probabilities (except for measure-zero resonant angles).
• Theorem 13: Under a controllability hypothesis, there exists a finite depth $p$ and a set of angles such that the probability of sampling a feasible solution is arbitrarily close to 1 (specifically $\geq 1/2$). This guarantees that the algorithm does not get stuck in infeasible regions.

2. Dimension-Free Finite-Depth and Finite-Shot Bounds

The core theoretical contribution is a ratio-form guarantee for the success probability ($q_0$) of sampling an optimal solution.

• The Bound:
  $$q_0 \geq \frac{x}{1 + x}, \quad \text{where } x = (p+1)^2 \sin^2(\delta/2) C_\beta$$
  • $p$: Circuit depth.
  • $\delta$: Phase gap proxy (separation between optimal and suboptimal phases).
  • $C_\beta$: Mixer-envelope mass (the probability weight the mixer places on the optimal set before filtering).
• Significance: This bound is dimension-free. It does not depend on the ambient Hilbert space dimension ($N$), only on the instance-specific parameters ($\delta, C_\beta$) and the depth $p$.

3. Shot Complexity Analysis

Based on the success probability bound, the paper derives the required number of shots ($S$) to find an optimal solution with confidence $1-\epsilon$:
$$S \lesssim \left(1 + \frac{1}{x}\right) \ln(1/\epsilon)$$

• Regimes:
  • If $x \gg 1$ (good gap and envelope), $S \approx \ln(1/\epsilon)$ (optimal scaling).
  • If $x \ll 1$, shots scale inversely with $x$.
• This provides a concrete recipe for resource estimation: one only needs to ensure the product $(p+1)^2 \sin^2(\delta/2) C_\beta$ is $\Omega(1)$.

4. Robustness to Non-Lattice Costs

The authors extend the analysis beyond exact lattice-normalized costs using Riemann-Lebesgue averaging. By introducing a small random dither (noise) to the cost angles, they show that the positive filtering effect persists even when the cost spectrum is not perfectly commensurate, suppressing aliasing effects.

4. Key Results

• Feasibility Guarantee: The CE-QAOA mixer ensures that the feasible subspace is reachable and that the probability of finding a feasible state is bounded away from zero at finite depth.
• Optimality Guarantee: The Fejér filter provides a rigorous lower bound on the probability of sampling the global optimum.
• Phase Diagram: The paper identifies three regimes based on the parameter $x$:
  1. Small $x$: Weak gap/tiny envelope; requires many shots.
  2. Threshold $x \approx 1$: "Knife-edge" regime; shot complexity is bounded and dimension-free.
  3. Large $x$: Healthy gap/good envelope; near-optimal shot complexity.
• Order Reduction: The paper demonstrates that even if the exact Fejér profile is not perfectly realized (e.g., due to reduced depth or coarse angle grids), success is maintained as long as the main-lobe overlap with the optimal phase is preserved and off-peak suppression is adequate.

5. Significance and Outlook

• Theoretical Breakthrough: This is one of the first works to derive dimension-free, finite-shot guarantees for a constrained variational quantum algorithm. It moves beyond asymptotic convergence proofs to provide practical resource estimates.
• Conceptual Separation: The work conceptually separates exploration (handled by the mixer envelope $W_p$) from selection (handled by the Fejér filter). This clarifies why constrained mixers are necessary: they ensure $C_\beta$ is not exponentially small.
• Practical Implications: The results suggest that for many constrained problems, one does not need deep circuits or massive shot counts if the problem structure (phase gap) and mixer design (envelope mass) are favorable.
• Future Directions: The authors highlight the need for coherent realizations of these positive spectral filters. Currently, the Fejér filter is derived via a dephasing analysis; the next step is to implement hardware-efficient unitary circuits that naturally induce this positive filtering without the need for classicalization.

In summary, the paper provides a rigorous mathematical foundation for why CE-QAOA works, quantifying exactly how circuit depth, mixer design, and problem structure interact to guarantee success in constrained optimization, independent of the system size.