⚛️ quantum physics

Sampling (noisy) quantum circuits through randomized rounding

This paper introduces a classical Gaussian randomized rounding method based on two-qubit marginals that efficiently samples from noisy quantum circuits for combinatorial optimization problems like Max-Cut, achieving provable approximation ratios and faithfully reproducing energy distributions as validated by large-scale simulations and IBMQ hardware experiments.

Original authors: Victor Martinez, Omar Fawzi, Daniel Stilck França

Published 2026-04-09

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Victor Martinez, Omar Fawzi, Daniel Stilck França

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 have a very expensive, high-tech kitchen appliance (a noisy quantum computer) that is supposed to bake the perfect cake (solve a complex optimization problem like Max-Cut or QUBO). The problem is, this appliance is currently broken. It's old, the oven door is slightly ajar, and the temperature fluctuates wildly. Every time you try to bake a cake, it comes out a bit burnt, a bit soggy, or just weirdly shaped.

The big question scientists have been asking is: "Is this broken machine still better than a human with a basic toaster (a classical computer)?"

For a long time, the answer was "maybe, but it's hard to tell." If the machine is too broken, the cakes are so bad that a human could just guess a better one. But if it's only slightly broken, maybe the machine is still winning. The trouble is, to know for sure, you have to actually run the machine, wait for the cake, and taste it. This is slow, expensive, and the machine is hard to access.

This paper introduces a clever "recipe hack" that lets us predict exactly what the broken machine would have baked, without ever turning it on.

Here is the simple breakdown of their solution:

1. The "Flavor Profile" vs. The "Whole Cake"

When you bake a cake, you care about the final taste (the solution). But to understand why the cake tastes the way it does, you look at the ingredients and how they interact (the correlations).

The authors realized that for these specific types of "cakes" (optimization problems), you don't need to see the whole messy cake to know what it tastes like. You only need to know how the ingredients pair up.

The Quantum Machine: It produces a chaotic cloud of possibilities (samples).
The Hack: Instead of waiting for the machine to spit out a random cake, the researchers just asked the machine: "Hey, how much do Ingredient A and Ingredient B like each other?" (These are called two-qubit marginals or expectation values).

2. The "Gaussian Rounding" Trick

Once they have these "pairing scores" (which are much easier to calculate or simulate than the whole cake), they use a mathematical trick called Gaussian Randomized Rounding.

Think of it like this:

Imagine you have a map of how all the ingredients feel about each other. Some are best friends (positive correlation), some are enemies (negative correlation).
The algorithm takes this map and generates a random weather pattern (a Gaussian distribution) that respects those friendships and rivalries.
Then, it makes a simple decision: "If the weather at this spot is sunny, put the ingredient in the 'Yes' pile. If it's rainy, put it in the 'No' pile."
This creates a finished "cake" (a bitstring solution) that looks and tastes remarkably similar to what the broken quantum machine would have produced.

3. The Magic of "Broken" Machines

Here is the most surprising part: The more broken the machine is, the better this hack works.

Usually, when a machine breaks, you expect it to get worse. But in this specific scenario, as the noise (the "brokenness") increases, the quantum machine starts to act more like a random guesser. The researchers proved that their "recipe hack" can mimic this randomness perfectly.

Low Noise: The machine is trying to be smart but is failing. The hack mimics its specific failures.
High Noise: The machine is just random. The hack mimics the randomness perfectly.

They showed that for a machine with a certain amount of noise, their classical method produces samples that are statistically almost identical to the quantum machine's output.

4. Why This Matters

This is a huge deal for three reasons:

It's a Reality Check: It tells us that for many current quantum computers, we don't actually need to run them to see if they are useful. We can just run this simple math trick on a regular laptop. If the trick works well, the quantum computer isn't doing anything special yet.
It Saves Time and Money: Instead of waiting hours for a quantum computer to give you a "noisy" answer, you can get a "simulated noisy" answer in seconds on a classical computer.
It Sets the Bar: It gives us a clear benchmark. If a future quantum computer wants to prove it's "quantum advantage," it has to beat this simple classical hack. If it can't beat the hack, it's not beating the classical world.

The Bottom Line

The authors built a classical "shadow" of the noisy quantum computer. They showed that for the kinds of problems we are trying to solve right now (like finding the best route for a delivery truck or splitting a group of people into two teams), a broken quantum computer isn't doing anything magic that a regular computer can't mimic using a little bit of math and randomness.

It's like realizing that a broken, shaking camera takes photos that look just like a blurry photo you could take with your phone. Until the camera gets fixed (error correction), there's no point in paying for the expensive, broken one if your phone can do the same job.

1. Problem Statement

The paper addresses a critical gap in the current era of Noisy Intermediate-Scale Quantum (NISQ) devices. While classical methods exist to simulate noisy quantum circuits and estimate expectation values (e.g., via error mitigation or classical light-cone simulations), there is a lack of efficient classical methods to sample bitstrings that faithfully replicate the output distribution of a noisy quantum circuit.

The Challenge: Many practical applications, such as combinatorial optimization (Max-Cut, QUBO), require actual bitstring assignments (solutions) rather than just expectation values.
The Limitation: Directly sampling from noisy quantum circuits is computationally intractable for classical computers in the general case. Furthermore, recent results suggest that for sufficiently noisy circuits, classical heuristics often outperform quantum devices in finding optimal solutions, yet we lack a way to generate samples that mimic the specific behavior of the noisy quantum device to benchmark it fairly.
The Goal: To develop a classical algorithm that, given only the two-body marginal expectation values (covariance matrix) of a noisy quantum circuit, generates bitstrings whose expected cost is provably close to that of the noisy quantum device.

2. Methodology

The authors propose a Gaussian Randomized Rounding algorithm applied to the circuit's two-qubit marginals. The approach is inspired by the Goemans-Williamson algorithm for Max-Cut but adapted to use the quantum circuit's specific correlation data rather than a Semidefinite Programming (SDP) relaxation.

Core Algorithm (Algorithm 4.1)

Input: A quantum circuit $C$ (noisy or noiseless) and its associated mean vector $\mu$ and variance-covariance matrix $\Sigma$ , where $\Sigma_{ij} = \text{tr}(\rho Z_i Z_j)$ .
Sampling: Sample a vector $y \in \mathbb{R}^n$ from a multivariate Gaussian distribution $\mathcal{N}(\mu, \Sigma)$ .
Rounding: Convert the continuous vector $y$ into a binary bitstring $z \in \{-1, +1\}^n$ by taking the sign of each component: $z_i = \text{sign}(y_i)$ .
Output: The bitstring $z$ serves as a candidate solution to the optimization problem.

Theoretical Framework

Recovery Ratio ( $\alpha$ ): The quality of the sampler is measured by the ratio of the expected cost of the classical samples to the expected cost of the noisy quantum samples:
$\alpha = \frac{\mathbb{E}_{z \sim A(C)}[C(z)]}{\mathbb{E}_{z \sim M([C]_N)}[C(z)]}$
The goal is to show $\alpha \approx 1$ .
Noise Models: The analysis focuses primarily on local depolarizing noise ( $N_{DP}$ ) and amplitude damping noise ( $N_{AD}$ ).
Computing Inputs: The paper leverages recent advances (e.g., Pauli backpropagation) showing that computing the noisy expectation values ( $\mu$ and $\Sigma$ ) can be done efficiently in polynomial time for many circuit classes, even though sampling the full distribution is hard.

3. Key Contributions

A. Theoretical Guarantees for Max-Cut

Noiseless Case: The algorithm recovers the Goemans-Williamson bound of $\alpha \geq 0.87856$ .
Noisy Case: The authors prove that under local depolarizing noise with strength $p$ and circuit depth $D$ , the recovery ratio improves as noise increases. Specifically, for regular graphs:
$\alpha_{MC} \geq 1 - O((1-p)^D)$
This implies that as the circuit becomes noisier (or deeper), the quantum output becomes more random, and the classical rounding algorithm (which captures the remaining correlations) can reproduce the noisy distribution with high fidelity.

B. Theoretical Guarantees for QUBO

Noiseless Case: The algorithm achieves a recovery ratio of $\alpha \geq 2/\pi \approx 0.6366$ .
Noisy Case: Similar to Max-Cut, the authors derive bounds showing that the recovery ratio approaches 1 as the noise strength increases or depth grows, provided the depth is sufficient (logarithmic in $n$ for rigorous bounds, though practical performance is better).

C. End-to-End Classical Sampler

The paper constructs a complete pipeline:

Use Pauli backpropagation to classically compute the noisy expectation values ( $\Sigma$ ) in polynomial time.
Project the estimated matrix onto the Positive Semidefinite (PSD) cone to ensure valid Gaussian sampling.
Apply Gaussian randomized rounding to generate samples.
This creates a classical surrogate that operates in polynomial time and mimics the noisy quantum circuit.

4. Results

Numerical Simulations and Hardware Experiments

The authors validated their method on IBM Quantum (IBMQ) hardware (127-qubit chips) and large-scale simulations.

Faithful Distribution Reproduction: Unlike methods that only match the mean, the proposed algorithm reproduces the entire energy distribution of the noisy quantum circuit. This includes the "tail" of the distribution (the best solutions), which is crucial for optimization.
Performance vs. Depth/Noise:
- In the intermediate noise regime, the algorithm outperforms the theoretical worst-case bounds (e.g., achieving ratios significantly higher than 0.878 for Max-Cut).
- As noise increases, the recovery ratio improves, confirming the theoretical prediction that the classical sampler tracks the noisy quantum device effectively.
- The method works for both Depolarizing and Amplitude Damping noise models.
Comparison to Direct Sampling: The classical sampler generates samples that are statistically indistinguishable from those obtained by running the quantum circuit directly, even when the quantum circuit is too noisy to provide a quantum advantage.

5. Significance and Implications

Benchmarking Quantum Advantage: The paper provides a rigorous quantitative benchmark. If a noisy quantum optimizer cannot be outperformed by this simple classical sampler, it implies the quantum device is not providing a computational advantage for that specific task.
Clarifying NISQ Capabilities: It clarifies that for combinatorial optimization, near-term hardware may not offer a "quantum advantage" in terms of finding better solutions than classical heuristics, but it does offer a specific distribution of solutions that can be efficiently simulated classically.
Practical Utility: The method offers a reliable, low-cost alternative to running quantum hardware for sampling tasks. If the goal is to obtain samples similar to a noisy quantum circuit (e.g., for testing error mitigation strategies), one can use this classical surrogate instead of expensive quantum runs.
Error Mitigation Context: The work highlights that while error mitigation can recover expectation values, it cannot easily recover samples. This method fills that gap by generating samples that match the noisy device's behavior.

Conclusion

The paper demonstrates that for a broad class of variational quantum circuits used in optimization, Gaussian randomized rounding on two-body marginals is a powerful, provably effective classical surrogate. It successfully replicates the sampling distribution of noisy quantum devices, offering a new tool to demarcate the boundary where genuine quantum advantage must reside and providing a standard for evaluating future fault-tolerant or error-mitigated quantum processors.