Fair sampling of ground-state configurations using hybrid quantum-classical MCMC algorithms

• URL: http://arxiv.org/abs/2512.14552v1
• Date: Tue, 16 Dec 2025 16:25:59 GMT
• Title: Fair sampling of ground-state configurations using hybrid quantum-classical MCMC algorithms
• Authors: Yuichiro Nakano, Keisuke Fujii,
• Abstract summary: We study the fair sampling properties of hybrid quantum-classical Markov chain Monte Carlo (MCMC) algorithms.<n>Using small Ising models, we show that MCMC post-processing corrects the sampling bias of quantum dynamics.<n>We also examine solution counting and find that the required number of transitions is comparable to that of WalkSAT.
• Score: 3.3083504598202733
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We study the fair sampling properties of hybrid quantum-classical Markov chain Monte Carlo (MCMC) algorithms for combinatorial optimization problems with degenerate ground states. While quantum optimization heuristics such as quantum annealing and the quantum approximate optimization algorithm (QAOA) are known to induce biased sampling, hybrid quantum-classical MCMC incorporates quantum dynamics only as a proposal transition and enforces detailed balance through classical acceptance steps. Using small Ising models, we show that MCMC post-processing corrects the sampling bias of quantum dynamics and restores near-uniform sampling over degenerate ground states. We then apply the method to random $k$-SAT problems near the satisfiability threshold. For random 2-SAT, a hybrid MCMC combining QAOA-assisted neural proposals with single spin-flip updates achieves fairness comparable to that of PT-ICM. For random 3-SAT, where such classical methods are no longer applicable, the hybrid MCMC still attains approximately uniform sampling. We also examine solution counting and find that the required number of transitions is comparable to that of WalkSAT. These results indicate that hybrid quantum-classical MCMC provides a viable framework for fair sampling and solution enumeration.

Related papers

• Matrix product state approach to lossy boson sampling and noisy IQP sampling [0.7066293026438526]
  We develop classical algorithms for lossy boson sampling and noisy instantaneous quantum-time sampling.<n>Our algorithm offers significantly improved control over the accuracy-efficiency trade-off.<n>It further extends the applicability of MPS simulation to broader classes of noisy quantum sampling models.
  arXiv  Detail & Related papers  (2025-10-28T07:23:10Z)
• Quantum Approximate Optimization Algorithm for MIMO with Quantized b-bit Beamforming [47.98440449939344]
  Multiple-input multiple-output (MIMO) is critical for 6G communication, offering improved spectral efficiency and reliability.<n>This paper explores the use of the Quantum Approximate Optimization Algorithm (QAOA) and alternating optimization to address the problem of b-bit quantized phase shifters both at the transmitter and the receiver.<n>We demonstrate that the structure of this quantized beamforming problem aligns naturally with hybrid-classical methods like QAOA, as the phase shifts used in beamforming can be directly mapped to rotation gates in a quantum circuit.
  arXiv  Detail & Related papers  (2025-10-07T17:53:02Z)
• Neural-network-assisted Monte Carlo sampling trained by Quantum Approximate Optimization Algorithm [0.8009842832476994]
  We propose a hybrid quantum-classical MCMC framework that combines a quantum circuit with a generative neural sampler (GNS)<n>GNS acts as a classical surrogate to efficiently emulate quantum outputs, thereby lifting circuit constraints.<n>These results establish the method as a viable sampling-based quantum algorithm for NISQ devices.
  arXiv  Detail & Related papers  (2025-06-02T05:26:26Z)
• Accelerating MCMC with Quantum Walks: Design, Implementation, and Results [3.004066195320147]
  We present the design and implementation of a novel MCMC algorithm based on the Discrete Quantum Walk (DQW) algorithm.<n>We demonstrate that it effectively captures the structure of the target distribution by leveraging quantum superposition.<n>In addition, we introduce a circuit extension that significantly improves convergence speed, which in turn enhances the scalability of the algorithm.
  arXiv  Detail & Related papers  (2025-04-16T13:53:32Z)
• Quantum-assisted variational Monte Carlo [1.283555556182245]
  We introduce a quantum-assisted variational Monte Carlo (QA-VMC) algorithm for solving the ground state of quantum many-body systems.<n>We demonstrate that the quantum-assisted proposal exhibits larger absolute spectral gaps and reduced autocorrelation times compared to conventional classical proposals.
  arXiv  Detail & Related papers  (2025-02-28T07:31:38Z)
• Unbiasing time-dependent Variational Monte Carlo by projected quantum evolution [44.99833362998488]
  We analyze the accuracy and sample complexity of variational Monte Carlo approaches to simulate quantum systems classically. We prove that the most used scheme, the time-dependent Variational Monte Carlo (tVMC), is affected by a systematic statistical bias. We show that a different scheme based on the solution of an optimization problem at each time step is free from such problems.
  arXiv  Detail & Related papers  (2023-05-23T17:38:10Z)
• QAOA-MC: Markov chain Monte Carlo enhanced by Quantum Alternating Operator Ansatz [0.6181093777643575]
  We propose the use of Quantum Alternating Operator Ansatz (QAOA) for quantum-enhanced Monte Carlo. This work represents an important step toward realizing practical quantum advantage with currently available quantum computers.
  arXiv  Detail & Related papers  (2023-05-15T16:47:31Z)
• A self-consistent field approach for the variational quantum eigensolver: orbital optimization goes adaptive [52.77024349608834]
  We present a self consistent field approach (SCF) within the Adaptive Derivative-Assembled Problem-Assembled Ansatz Variational Eigensolver (ADAPTVQE) This framework is used for efficient quantum simulations of chemical systems on nearterm quantum computers.
  arXiv  Detail & Related papers  (2022-12-21T23:15:17Z)
• Importance sampling for stochastic quantum simulations [68.8204255655161]
  We introduce the qDrift protocol, which builds random product formulas by sampling from the Hamiltonian according to the coefficients. We show that the simulation cost can be reduced while achieving the same accuracy, by considering the individual simulation cost during the sampling stage. Results are confirmed by numerical simulations performed on a lattice nuclear effective field theory.
  arXiv  Detail & Related papers  (2022-12-12T15:06:32Z)
• Error mitigation and quantum-assisted simulation in the error corrected regime [77.34726150561087]
  A standard approach to quantum computing is based on the idea of promoting a classically simulable and fault-tolerant set of operations. We show how the addition of noisy magic resources allows one to boost classical quasiprobability simulations of a quantum circuit.
  arXiv  Detail & Related papers  (2021-03-12T20:58:41Z)
• Sampling in Combinatorial Spaces with SurVAE Flow Augmented MCMC [83.48593305367523]
  Hybrid Monte Carlo is a powerful Markov Chain Monte Carlo method for sampling from complex continuous distributions. We introduce a new approach based on augmenting Monte Carlo methods with SurVAE Flows to sample from discrete distributions. We demonstrate the efficacy of our algorithm on a range of examples from statistics, computational physics and machine learning, and observe improvements compared to alternative algorithms.
  arXiv  Detail & Related papers  (2021-02-04T02:21:08Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.