Quantum Metropolis-Hastings via Penalised Qubitized Walks: Spectral Filtering and Circuit Implementation

1. Problem Statement

The Metropolis-Hastings (MH) algorithm is a cornerstone of Markov Chain Monte Carlo (MCMC) methods, widely used in physics, Bayesian inference, and machine learning. However, classical MCMC suffers from slow mixing in high-dimensional, multimodal, or rugged energy landscapes, where the chain gets trapped in local minima. The mixing time scales inversely with the spectral gap of the transition matrix.

Quantum walks, specifically those based on Szegedy's quantization framework, promise a quadratic speedup in mixing time by amplifying the spectral gap. However, a significant barrier exists: the standard Metropolis-Hastings algorithm involves rejected moves, which introduce intrinsic irreversibility. Directly implementing this rejection logic in a unitary quantum circuit is non-trivial.

While Claudon et al. (2025) proposed a theoretical framework to overcome this by working on a dual (edge) state space and using qubitized walks, the authors of this paper identify a critical flaw in its direct circuit implementation:

• Non-commutativity: The theoretical construction requires projecting onto the 1-eigenspace of the walk operator ($W$) and restricting the state to the image of a specific partial isometry ($\text{Im}(\boxtimes)$). These two subspaces do not commute, meaning sequential filtering operations interfere with each other, preventing the extraction of the correct stationary state.
• Degeneracy: The eigenvalue 1 is generally degenerate on the full Hilbert space, making it difficult to isolate the unique target state without additional mechanisms.

2. Methodology

The authors propose a complete, explicit circuit-level workflow to resolve these issues, moving from abstract theory to a runnable quantum algorithm.

A. The Penalised Qubitized Walk

To resolve the non-commutativity and degeneracy issues, the authors introduce a Penalised Qubitized Walk Operator ($V$):
$$V = \left( \Pi_{\boxtimes} + e^{i\phi}(\text{Id} - \Pi_{\boxtimes}) \right) W$$

• Mechanism: This operator applies a phase kick $e^{i\phi}$ to any state outside the image of the partial isometry $\boxtimes$, while leaving states inside $\text{Im}(\boxtimes)$ unchanged.
• Effect: This breaks the global degeneracy of the eigenvalue 1. The target stationary state (which lies in $\text{Im}(\boxtimes)$) remains at phase 0, while all other eigenstates with eigenvalue 1 are shifted to non-zero phases. This allows a spectral filter to isolate the target state without requiring simultaneous, non-commuting projections.

B. Spectral Filtering via Quantum Phase Estimation (QPE)

The workflow utilizes Quantum Phase Estimation (QPE) to filter the eigenstates of $V$.

• Filtering Strategy: Since the target state corresponds to an eigenphase of 0 (eigenvalue 1), the algorithm post-selects on the phase register measuring $|0\rangle$.
• Resolution Constraints: The paper analyzes the trade-off between the number of phase ancilla qubits ($m$) and the spectral gap ($\delta$). To resolve the target state from the first excited mode, the phase resolution $2^{-m}$ must be smaller than the angular gap $\Delta \approx \sqrt{\delta}$.
• Semiclassical Implementation: To reduce qubit overhead in simulations, the authors employ a semiclassical iterative phase estimation technique (using a single recycled phase ancilla) for the Ising model simulations, trading circuit width for depth.

C. Full Algorithmic Workflow

The proposed workflow consists of the following steps:

1. Initialization: Prepare a seed state in $\text{Im}(\boxtimes)$ (e.g., a uniform superposition over directed edges).
2. Penalised Walk Construction: Construct the operator $V$ using oracles for the proposal kernel ($T$) and acceptance kernel ($A$).
3. QPE Filtering: Apply QPE to $V$ and post-select on the phase register being $|0\rangle$. This isolates the unique 1-eigenstate.
4. Decoding: Apply a "dual-to-vertex" decoding transformation to map the state from the edge representation back to the vertex representation.
5. Sampling: Measure the position register to obtain samples from the target stationary distribution $\pi$.

3. Key Contributions

1. Identification of Implementation Obstacles: The paper rigorously demonstrates that the theoretical construction by Claudon et al. cannot be directly implemented due to the non-commutativity of the required projection operators.
2. The Penalised Walk Solution: The introduction of the penalised operator $V$ is a novel contribution that lifts eigenvalue degeneracy and ensures the target subspace is invariant under the filtering process, enabling a robust circuit implementation.
3. Explicit Circuit Construction: The authors provide the full quantum circuit details, including the construction of proposal and acceptance oracles for specific topologies (periodic grids and Hamming cubes), and the integration of the penalty mechanism.
4. Comprehensive Simulation Framework: They simulate the full algorithm on high-performance computing resources, analyzing the impact of finite phase resolution on the quality of the prepared state.

4. Results

The authors validated the algorithm on two systems: a 2D Double-Well Potential (4x4 grid) and a 4-Spin Ising Chain.

• Double-Well Potential:

  • Role of Penalisation: Comparing the penalised walk ($m=4$) against an unmodified walk ($m=5$), the unmodified walk failed to converge to the correct distribution despite higher phase precision, exhibiting a massive misallocation of probability mass between the two wells. The penalised walk successfully reproduced the target bimodal distribution.
  • Precision Dependence: As the number of phase ancillas ($m$) increased, the fidelity to the target distribution improved monotonically, and the total variation distance decreased significantly.

• Ising Model:

  • Spectral Gap Analysis: The algorithm was tested across varying inverse temperatures ($\beta$). As $\beta$ increases, the spectral gap narrows, requiring higher phase resolution ($m$) to maintain fidelity.
  • Under-Resolved Regime: When phase resolution is insufficient, the output state is not random but retains structured information. It correctly captures global order parameters (like magnetization) but exhibits errors in sensitive observables (like domain wall counts) and energy estimation.
  • Energy Filtering: The spectral filter acts hierarchically, suppressing high-energy sectors first. Even before full convergence, the state is biased toward low-energy configurations, suggesting potential utility as a high-quality initializer for classical refinement.

5. Significance and Future Outlook

• Feasibility: The work proves that a quantum version of Metropolis-Hastings is theoretically sound and practically implementable in a fault-tolerant regime, provided the spectral degeneracy is handled via penalization.
• Resource Requirements: The algorithm requires fault-tolerant quantum computers due to the depth of the QPE and walk operators. It is not currently suitable for NISQ devices.
• Hybrid Potential: The authors suggest a hybrid quantum-classical strategy: using the quantum algorithm to prepare a high-quality initial state that captures the global basin structure (overcoming slow mixing), followed by classical MCMC for local refinement.
• Limitations: The current implementation relies on classical simulation of state vectors, limiting the system size. The optimal choice of the penalty phase $\phi$ remains heuristic and requires further theoretical analysis.

In conclusion, this paper bridges the gap between abstract quantum walk theory and practical circuit implementation for MCMC, offering a concrete solution to the irreversibility problem and demonstrating that spectral filtering, when combined with degeneracy-breaking penalties, can effectively prepare Gibbs states.