Sampling (noisy) quantum circuits through randomized rounding

Victor Martinez, Omar Fawzi, Daniel Stilck França · 2025

Read Sampling (noisy) quantum circuits through randomized rounding by Victor Martinez, Omar Fawzi, Daniel Stilck França (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2507-21883.txt.

Introduction

Victor Martinez, Omar Fawzi, and Daniel Stilck França mimic noisy quantum circuits on classical machines through rounding. Their paper appeared in two thousand twenty-five. Today's processors hold hundreds of noisy qubits. Estimating averages from them is well understood classically. Some tasks need the actual bit-strings, though. Optimization problems encode candidate answers in those strings. Noisy samples alone rarely beat classic heuristics, yet classical copies are scarce.

The authors focus on goals set by two-body correlations, like Max-Cut. Gaussian randomized rounding, in the spirit of Goemans and Williamson, does the sampling. The method reaches beyond random circuits into structured problems. It gives a classical benchmark for noisy quantum output. Claims of quantum advantage face a sharper yardstick.

Catalog record

CREATORVictor Martinez, Omar Fawzi, Daniel Stilck França
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE86 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2507-21883

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

Sampling (noisy) quantum circuits through randomized rounding Victor Martinez, Omar Fawzi, Daniel Stilck França Abstract The present era of quantum processors with hundreds to thousands of noisy qubits has sparked interest in understanding the computational power of these devices and how to leverage it to solve practically relevant problems. For applications that require estimating expectation values of observables the community developed a good understanding of how to simulate them classically and denoise them. Certain applications, like combinatorial optimization, however demand more than expectation values: the bit-strings themselves encode the candidate solutions. While recent impossibility and threshold results indicate that noisy samples alone rarely beat classical heuristics, we still lack classical methods to replicate those noisy samples beyond the setting of random quantum circuits. Focusing on problems whose objective depends only on two-body correlations such as Max-Cut, we show that Gaussian randomized rounding in the spirit of Goemans-Williamson applied to the circuit’s two-qubit marginals—produces a distribution whose expected cost is provably close to that of the noisy quantum device. For instance, for Max-Cut problems we show that for any depth-D circuit affected by local depolarizing noise p, our sampler achieves an approximation ratio 1 − O ⁡ [ ( 1 − p ) D ] 1-O[(1-p)^{D}] , giving ways to efficiently sample from a distribution that behaves similarly to the noisy circuit for the problem at hand. Beyond theory we run large-scale simulations and experiments on IBMQ hardware, confirming that the rounded samples faithfully reproduce the full energy distribution, and we show similar behaviour under other various noise models. Our results supply a simple classical surrogate for sampling noisy optimization circuits, clarify the realistic power of near-term hardware for combinatorial tasks, and provide a quantitative benchmark for future error-mitigated or fault-tolerant demonstrations of quantum advantage. I Introduction Quantum computing is now at a pivotal stage, with its potential exceeding the limits of classical computing and posing challenges for simulating quantum devices through classical means AAB+ 19 . In light of this, the quantum computing community is working diligently to ascertain whether near-term quantum computers, despite inherent noise and the lack of effective quantum error correction, can surpass classical computers in tackling practical problems. A significant focus of recent research has been the application of near-term quantum devices to solve optimization problems in various areas, as well as approximating the ground-state energy of relevant physical Hamiltonians KMvB+ 19 ; MJE+ 19 ; AMR+ 22 ; YAK+ 25 . Contrasting with quantum advantage tests based on random circuit sampling, optimization offers tangible, real-world applications. Furthermore, it is relatively simple to compare the efficacy of a quantum device to a classical computer by evaluating which one achieves the lowest energy prediction. However, the inherent noise in current devices can significantly affect the accuracy and reliability of the results, making it difficult to obtain optimal solutions for complex combinatorial optimization problems. Two primary approaches exist for mitigating the effects of noise: error correction and error mitigation. Error correction represents a long-term, theoretically robust solution that aims to preserve quantum coherence and computation fidelity through the use of redundant quantum encoding and fault-tolerant protocols. However, this approach requires substantial overhead in terms of qubits and gates, making it currently impractical for near-term quantum devices. The resource-intensive nature of error correction Ter 15 , combined with the limitations of present-day quantum hardware, has pushed its implementation into a future where large-scale, fault-tolerant quantum computers may become feasible. Error mitigation, on the other hand, provides a more practical, short-term strategy for addressing noise. By leveraging classical post-processing techniques on the results of quantum computations, error mitigation allows us to approximate the outcomes of a noiseless quantum circuit without requiring significant additional quantum resources CBB+ 23 . Although error mitigation has shown promise in reducing the effects of noise YZW 23 ; SWZ+ 23 ; FICS 23 , it is inherently limited in scalability TEMG 22 ; QSFK+ 24 . However, error mitigation does not provide us with samples from the quantum circuit, only estimates of noiseless expecation values. Crucially, the actual bitstrings sampled from the output of the noiseless circuit are necessary to obtain an assignment to the optimization problem. Consequently, if we aim to obtain an actual assignment, we are constrained to using the samples generated by the noisy quantum device. This raises a critical question: can samples with similar performance be obtained at a smaller cost, e.g., without having to run the quantum circuit? Under depolarizing noise, a common noise model, we are beginning to develop a clearer understanding of the limitations quantum devices face. Previous work has established that there exists a constant noise threshold beyond which simple classical algorithms are expected to outperform quantum approaches SFGP 21 . This insight suggests that, as the noise level increases, quantum devices lose their computational advantage in solving combinatorial optimization problems. Nonetheless, sampling noisy quantum circuits directly remains computationally intractable in most cases LCG+ 24 . The behavior of quantum circuits at depths significantly smaller than this noise threshold remains poorly understood, and the situation becomes even more complex when considering nonunital noise models, such as amplitude damping BOGH 13 ; FGG+ 24 . We address this outstanding issue by observing that for many optimization problems such as MaxCut or Ising problems, only two-body correlations are relevant to the problem Luc 14 . We show that by employing randomized rounding techniques, it is possible to mimic the behavior of the quantum circuit designed to tackle the optimization problem. Specifically, we present a very simple algorithm with performance guarantees that generates samples from a distribution designed to replicate the noisy circuit, given only access to two-body expectation values. We prove various guarantees both a priori and a posteriori , which allow us to determine if sampling from a given noisy QAOA will be advantageous in solving the problem. Notably, even though our theoretical guarantees are focused on the approximation ratio, our algorithm appears to capture the entire distribution of values remarkably well in practice. Moreover, our method does not require the depth or noise level to be greater than a specific threshold, but its performance improves as the amount of noise increases, making it a versatile and robust approach for various scenarios. Thus, we provide a simple yet powerful algorithm that provably works and performs well in practice, offering a reliable way to benchmark noisy quantum circuits. We summarize the framework we will be working in along with our main contributions in Figure 1 . Quantum Classical noisy Exact expectation values Single qubit noise FRD+ 25 ; MAP+ 25 A priori bounds A posteriori bounds Max-Cut: Prop. IV.2 QUBO: Th. V.1 Max-Cut: Th. IV.2 QUBO: Th. V.1 Sampling Algorithm IV.1 Circuit \mathcal{C} error mitigation Small depths expectation values Small depths Expectation values \langle O_{i}\rangle={\operatorname{tr}}([\mathcal{C}]O_{i}) 00101 Figure 1 : Representation of the framework and main contributions. An optimization instance is given in the form of a graph, and \mathcal{C} is a quantum circuit to solve this instance. Expectation values are extracted from the quantum circuit, and sampling algorithms allow to recover samples from these along with guarantees on the quality of the samples. II Summary of main results II.1 Problem setting and objective In this paper, we are interested

Read the complete text