Feeding the multitude: A polynomial-time algorithm to improve sampling.

Area of Science:

• Computational Physics
• Quantum Computing
• Optimization Algorithms

Background:

• Optimization techniques often exhibit sampling bias, favoring certain solutions and potentially excluding others.
• Degenerate Boolean optimization problems are particularly susceptible to biased sampling, limiting the discovery of diverse solutions.

Purpose of the Study:

• To develop a postprocessing technique that enhances fair sampling for optimization algorithms.
• To improve the ability to find multiple uncorrelated solutions for optimization problems.
• To address sampling biases in both quantum and classical optimization approaches.

Main Methods:

• A postprocessing technique generating new solutions from a pool of optimal configurations using rejection-free cluster updates at zero temperature.
• Application of the method to data from a D-Wave 2X quantum annealer and 3D Ising spin glasses.
• Inclusion of suboptimal states to assess their impact on sampling improvement.

Main Results:

• The proposed technique demonstrably improves fair sampling for biased optimization outputs.
• Effectiveness shown in enhancing exponentially biased data from quantum annealers.
• Sampling improvement observed even when suboptimal states are considered.

Conclusions:

• The postprocessing method offers a general approach to mitigate sampling bias in optimization.
• Fair sampling is typically improved, although ergodicity is not guaranteed.
• The technique shows promise for improving results from quantum and classical optimization methods.