⚛️ quantum physics

A Compressive Sensing Inspired Monte-Carlo Method for Combinatorial Optimization

This paper introduces a Monte-Carlo Compressive Optimization algorithm that leverages random queries to estimate generalized moments and a repurposed compressive sensing greedy algorithm to efficiently solve combinatorial optimization problems, including those with black-box objectives, while offering theoretical justification and competitive performance against dual annealing.

Original authors: Baptiste Chevalier, Shimpei Yamaguchi, Wojciech Roga, Masahiro Takeoka

Published 2026-07-02

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Baptiste Chevalier, Shimpei Yamaguchi, Wojciech Roga, Masahiro Takeoka

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine you are trying to find the single best spot to set up a lemonade stand in a massive, invisible city. The city has billions of possible locations (every possible combination of street and avenue), but you don't have a map, and you can't visit every single spot. This is what Combinatorial Optimization is: finding the absolute best answer in a sea of possibilities.

Usually, solving this is like trying to taste every drop of water in the ocean to find the one that tastes the sweetest. It takes too long.

This paper introduces a new method called Monte-Carlo Compressive Optimization (MCCO). Think of it as a clever way to find that sweetest drop of water without tasting everything. Here is how it works, broken down into simple steps:

1. The Problem: The Black Box

Imagine the city is a "Black Box." You can ask, "How good is this specific location?" and it gives you a score. But you can't see the whole city at once. Traditional methods (like "Simulated Annealing") are like walking around the city, checking one spot, then moving to a neighbor, hoping to stumble upon the best one. It works, but it can be slow and might get stuck in a "good" spot that isn't the best one.

2. The New Idea: The "Sketch"

The authors propose a different approach inspired by Compressive Sensing. Think of this like taking a low-resolution "sketch" of the city instead of a high-definition photo.

The Sampling: Instead of checking every location, you randomly pick a few hundred spots (samples) and ask the Black Box for their scores.
The Sketching: You don't just look at the raw scores. You run them through a special filter (called a "sketch function"). Imagine this filter as a sieve that catches the most important patterns in the data while ignoring the noise. The paper tests different "sieves," like looking at groups of 4 spots at a time or groups of 5 spots at a time.
The Reconstruction: Using a mathematical trick (borrowed from how we compress data), the algorithm tries to rebuild a "map" of the city based only on those few samples and the patterns it found.

3. The Secret Sauce: Greedy vs. Perfect

In standard math, when you try to rebuild a picture from a sketch, you often try to make it perfectly match the few samples you have. The authors say, "No, don't do that!"

Overfitting: If you try to match the samples perfectly, you are just memorizing the specific spots you visited, not learning the shape of the whole city. This is like memorizing the answer to one specific math problem instead of learning the formula.
The Greedy Approach: Instead, their method uses a "greedy" algorithm. It looks for the biggest, most obvious patterns that explain the data. It's okay if the map isn't perfect; as long as it points you in the right direction to find the highest peak, it works.

4. The Results: Tasting the Water

The authors tested this new method against the old "walking around" method (Dual Annealing) on a computer.

The Setup: They used a "city" with 12 bits (a small version of the problem, but still huge for a computer to check every spot).
The Outcome: The new method (MCCO) found the best spot more often than the old method.
- When using specific "sieves" (looking at groups of 4 or 5 spots), the new method found the true best location about 58% of the time, compared to 46% for the old method.
- Even when it didn't find the exact best spot, it found a spot that was very close (within a few steps) to the best one.
- Interestingly, if they used a "random" sieve, the method didn't do better than guessing, proving that the type of pattern you look for matters.

5. Why It Works (The Theory)

The paper explains that for this to work, the "city" (the problem) needs to be compressible. This means the rules of the city aren't totally chaotic; there are some underlying patterns or short formulas that determine the scores.

The math shows that if you take enough random samples, the "gap" between the best spot and the second-best spot usually stays wide enough that the algorithm doesn't get confused.
The "thresholding" (ignoring very low scores) helps reduce the noise, making the signal clearer.

Summary

The paper presents a new tool called MCCO that solves hard optimization problems by:

Taking random samples.
Filtering them to find hidden patterns (sketching).
Rebuilding a rough map to find the best spot.

It is faster and often more accurate than traditional methods for a specific class of problems where the rules follow a pattern (like certain physics problems or complex puzzles). The authors have even made this tool available as a free software library called TrOMA, so anyone can try it on their own problems.

What the paper does NOT claim:

It does not claim this works for every type of problem (it specifically targets "compressible" ones).
It does not claim this is a medical cure or a clinical tool.
It does not claim to solve problems instantly on a quantum computer yet, though it mentions the library can connect to quantum hardware in the future.

Technical Summary: A Compressive Sensing Inspired Monte-Carlo Method for Combinatorial Optimization

Problem Statement

The paper addresses the challenge of solving combinatorial optimization problems, specifically those involving discrete binary cost functions $f: \{0,1\}^N \to \mathbb{R}^+$ . These problems are characterized by a solution space of size $2^N$ , rendering naive brute-force methods exponential in cost. While continuous, convex, or differentiable functions allow for efficient gradient-based solutions, combinatorial problems—often modeled as generalized Ising Hamiltonians or "Black-Box" functions—lack these simplifying features. Standard meta-heuristics like simulated annealing or genetic algorithms are currently the state-of-the-art, but the authors note that efficient methods for general binary cost functions remain limited, particularly when the function structure is complex or unknown.

Methodology: Monte-Carlo Compressive Optimization (MCCO)

The authors propose a novel algorithm, Monte-Carlo Compressive Optimization (MCCO), which integrates principles from compressive sensing, statistical compressive learning, and Monte-Carlo methods. The core hypothesis is that the location of a global maximum can be recovered from a small number of random samples (sketches) of the objective function, even if the maximum itself is never directly sampled.

The algorithm proceeds through the following steps:

Random Sampling: A sample $S_f$ is generated by drawing $n$ indices uniformly from the domain $\{0,1\}^N$ and evaluating the cost function $f$ at these points.
Hard Thresholding: A thresholding operator $T_t$ is applied to the sample, zeroing out values below a specific threshold $t$ . This step is crucial for reducing variance and focusing on significant features.
Sketching (Measurement): A sketching map $\Phi$ $Φ$ is applied to the thresholded sample to produce a sketch vector $y = \Phi(T_t S_f)$ $y = Φ (T_{t} S_{f})$ . This vector contains empirical estimates of generalized moments of the distribution. The paper utilizes three types of sketch functions:
- Quadruplets/Quintuplets: Structured deterministic maps based on interactions of 4 or 5 consecutive bits (modeled as tensor products).
- Random: A matrix with coefficients drawn from a Gaussian distribution.
Decoding (Recovery): A greedy decoding procedure $\Delta$ (specifically Orthogonal Matching Pursuit in the numerical experiments) is applied to $y$ to reconstruct an estimate $\tilde{f}$ . Unlike $\ell_1$ minimization (Basis Pursuit), which emphasizes strict constraints and risks overfitting to the sample, greedy methods emphasize sparsity, aiming to identify the most significant global features of the distribution.
Optimization: The input corresponding to the largest value in the reconstructed function $\tilde{f}$ is selected as the estimated optimum.

The method targets a class of problems defined as "compressible." A function is compressible if its values are determined by a short set of rules (e.g., specific bit-string patterns) that can be embedded into the optimization space, even if the explicit compressed representation is not known a priori.

Key Contributions

Algorithmic Framework: The introduction of MCCO, a method that repurposes greedy compressive sensing algorithms for global optimization rather than signal recovery.
Theoretical Justification: The paper provides theoretical evidence (Theorem 1) demonstrating that under sufficient sampling, the probability of the global maximum surviving the sketching and decoding process depends on the mean and variance of the gap between the largest and second-largest values of the function. It establishes that the maximum can be preserved even when the function is sampled, provided the sketch matrix satisfies specific properties (e.g., quasi-isometry, low coherence).
Open-Source Implementation: The development of TrOMA (Tractable Optimization Modeling Approach), an end-to-end, problem-agnostic Python library that implements MCCO. The library supports various backends, including classical dynamic programming and heuristic methods for quantum computers (compatible with real IBM quantum hardware).
Sketch Function Analysis: The identification and testing of structured sketch functions (Quadruplets and Quintuplets) which outperform random linear sketches in the context of combinatorial optimization.

Numerical Results

The authors evaluated MCCO on a class of compressible problems with $N=12$ (a space dimension of $2^{12}$ ), comparing performance against Dual Annealing (a combination of simulated annealing and fast annealing).

Performance Metrics: The study measured the average distance to the real optimum and the Hamming distance between the estimated solution and the true optimum.
Comparison with Dual Annealing:
- Success Rate: MCCO using Quintuplet sketches recovered the global maximum in 49% of cases, and Quadruplet sketches in 58% of cases. In contrast, Dual Annealing found the global optimum in only 46% of cases.
- Local Optima Quality: When failing to find the global maximum, MCCO estimates were more likely to be high-quality local optima. The probability of finding a solution within one standard deviation ( $\sigma$ ) of the optimum was 87% (Quadruplet) and 79% (Quintuplet) for MCCO, compared to 71% for Dual Annealing.
- Hamming Distance: MCCO solutions were consistently closer in Hamming distance to the true optimum. For Quadruplet sketches, 91% of solutions were within a Hamming distance of 1, compared to 81% for Dual Annealing.
Random Sketches: MCCO with random sketch functions performed no better than Dual Annealing (recovering the global optimum only 6% of the time), though it did not perform worse than a random guess in terms of Hamming distance.

Significance and Claims

The paper claims that MCCO offers a competitive alternative to established meta-heuristics for compressible combinatorial problems. The significance of the work lies in:

Efficiency: The method can find high-quality solutions with a sample size that scales polynomially, potentially outperforming annealing methods, particularly in scenarios with limited computational resources (small sample sizes).
Robustness: The algorithm is robust to modeling errors; the location of the maximum can be recovered even if the underlying model is only loosely approximated.
Flexibility: The ability to tune heuristic parameters (such as the sketch function and threshold) allows the method to adapt to available computational resources, making it suitable for both classical and quantum computing environments.
Accessibility: By providing the TrOMA library, the authors enable the community to easily test the method on arbitrary combinatorial problems, provided a cost function can be defined.

The authors maintain a modest stance regarding the scope of applicability, acknowledging that the exact class of functions for which MCCO works "to perfection" is not fully defined. However, they argue that the class of "compressible" problems is broad and includes many NP-complete tasks like the Knapsack and Traveling Salesman problems, as well as Black-Box scenarios.