quantum-computing

Sampling (noisy) quantum circuits through randomized rounding

Quantum Journal

28 min read

0 likes

⚡ Quantum Brief

Researchers developed a classical method to replicate noisy quantum circuit outputs for combinatorial optimization problems like Max-Cut, addressing a key limitation of near-term quantum devices. The approach uses Gaussian randomized rounding on two-qubit marginals, inspired by the Goemans-Williamson algorithm, to generate bitstrings matching noisy quantum samples with provable accuracy. For circuits with depth D under local depolarizing noise p, the sampler achieves a recovery ratio of 1-O[(1-p)^D], effectively mimicking quantum hardware performance within polynomial time. Experiments on IBMQ hardware and simulations confirmed the method faithfully reproduces energy distributions across various noise models, validating its practical utility. This work establishes a classical benchmark for evaluating noisy quantum optimization, clarifying realistic performance limits of current hardware and guiding future error-mitigation efforts.

Sampling (noisy) quantum circuits through randomized rounding

Summarize this article with:

AbstractThe 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 a recovery ratio $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.Featured image: Framework overview: For a graph-based optimization instance, expectation values are extracted from a quantum circuit $\mathcal{C}$. Our classical sampling algorithms then leverage these values to generate candidate solutions with provable quality guarantees.Popular summaryCurrent quantum processors are scaling up but remain limited by hardware noise. For combinatorial optimization, evaluating the average performance, or expectation values, of a quantum circuit is insufficient: practical applications require sampling the actual bitstrings that encode candidate solutions. While noisy expectation values can often be efficiently estimated classically, sampling the actual bitstrings from these optimization-focused quantum circuits has historically remained out of reach without using a quantum computer. In this work, we introduce a classical method to generate samples that faithfully mimic the output of noisy quantum circuits for combinatorial optimization. More specifically, we focus on two-body problems like MaxCut, where the objective function depends entirely on pairwise qubit correlations. Our approach leverages these classically accessible expectation values and combines them with a Gaussian randomized rounding procedure, inspired by the Goemans-Williamson algorithm, to generate candidate solutions. We provide analytical guarantees on the quality of the samples produced, alongside empirical validation on IBM hardware. We prove that under local depolarizing noise, there is a fixed number of circuit layers (dependent only on the noise strength) that can be implemented before our classical surrogate performs just as well as the quantum device. When combined with classical techniques for estimating expectation values, this rounding procedure forms a polynomial-time classical pipeline for sampling from noisy variational circuits.► BibTeX data@article{Martinez2026samplingnoisy, doi = {10.22331/q-2026-04-15-2068}, url = {https://doi.org/10.22331/q-2026-04-15-2068}, title = {Sampling (noisy) quantum circuits through randomized rounding}, author = {Martinez, Victor and Fawzi, Omar and Fran{\c{c}}a, Daniel Stilck}, journal = {{Quantum}}, issn = {2521-327X}, publisher = {{Verein zur F{\"{o}}rderung des Open Access Publizierens in den Quantenwissenschaften}}, volume = {10}, pages = {2068}, month = apr, year = {2026} }► References [1] Frank Arute, Kunal Arya, Ryan Babbush, Dave Bacon, Joseph C. Bardin, Rami Barends, Rupak Biswas, Sergio Boixo, Fernando G. S. L. Brandao, David A. Buell, Brian Burkett, Yu Chen, Zijun Chen, Ben Chiaro, Roberto Collins, William Courtney, Andrew Dunsworth, Edward Farhi, Brooks Foxen, Austin Fowler, Craig Gidney, Marissa Giustina, Rob Graff, Keith Guerin, Steve Habegger, Matthew P. Harrigan, Michael J. Hartmann, Alan Ho, Markus Hoffmann, Trent Huang, Travis S. Humble, Sergei V. Isakov, Evan Jeffrey, Zhang Jiang, Dvir Kafri, Kostyantyn Kechedzhi, Julian Kelly, Paul V. Klimov, Sergey Knysh, Alexander Korotkov, Fedor Kostritsa, David Landhuis, Mike Lindmark, Erik Lucero, Dmitry Lyakh, Salvatore Mandrà, Jarrod R. McClean, Matthew McEwen, Anthony Megrant, Xiao Mi, Kristel Michielsen, Masoud Mohseni, Josh Mutus, Ofer Naaman, Matthew Neeley, Charles Neill, Murphy Yuezhen Niu, Eric Ostby, Andre Petukhov, John C. Platt, Chris Quintana, Eleanor G. Rieffel, Pedram Roushan, Nicholas C. Rubin, Daniel Sank, Kevin J. Satzinger, Vadim Smelyanskiy, Kevin J. Sung, Matthew D. Trevithick, Amit Vainsencher, Benjamin Villalonga, Theodore White, Z. Jamie Yao, Ping Yeh, Adam Zalcman, Hartmut Neven, and John M. Martinis. Quantum supremacy using a programmable superconducting processor. Nature, 574:505–510, 2019. doi:10.1038/s41586-019-1666-5. https://doi.org/10.1038/s41586-019-1666-5 [2] Dorit Aharonov, Xun Gao, Zeph Landau, Yunchao Liu, and Umesh Vazirani. A polynomial-time classical algorithm for noisy random circuit sampling. In Proceedings of the 55th Annual ACM Symposium on Theory of Computing, STOC ’23, 2023. doi:10.1145/3564246.3585234. https://doi.org/10.1145/3564246.3585234 [3] Srinivasan Arunachalam, Vojtech Havlicek, and Louis Schatzki. On the role of entanglement and statistics in learning, 2023. doi:10.48550/arXiv.2306.03161. https://doi.org/10.48550/arXiv.2306.03161 [4] David Amaro, Carlo Modica, Matthias Rosenkranz, Mattia Fiorentini, Marcello Benedetti, and Michael Lubasch. Filtering variational quantum algorithms for combinatorial optimization. Quantum Science and Technology, 7:015021, 2022. doi:10.1088/2058-9565/ac3e54. https://doi.org/10.1088/2058-9565/ac3e54 [5] Armando Angrisani, Antonio A. Mele, Manuel S. Rudolph, M. Cerezo, and Zoë Holmes. Simulating quantum circuits with arbitrary local noise using pauli propagation, 2025. doi:10.48550/arXiv.2501.13101. https://doi.org/10.48550/arXiv.2501.13101 [6] Noga Alon and Assaf Naor. Approximating the cut-norm via grothendieck's inequality. In Proceedings of the Thirty-Sixth Annual ACM Symposium on Theory of Computing, STOC '04, page 72–80, 2004. doi:10.1145/1007352.1007371. https://doi.org/10.1145/1007352.1007371 [7] Armando Angrisani, Alexander Schmidhuber, Manuel S. Rudolph, M. Cerezo, Zoë Holmes, and Hsin-Yuan Huang. Classically estimating observables of noiseless quantum circuits. Phys. Rev. Lett., 135:170602, 2025. doi:10.1103/lh6x-7rc3. https://doi.org/10.1103/lh6x-7rc3 [8] Yogesh J. Bagul and Ramkrishna M. Dhaigude. Simple efficient bounds for arcsine and arctangent functions. 2021. doi:10.21203/rs.3.rs-404784/v1. https://doi.org/10.21203/rs.3.rs-404784/v1 [9] Samantha V Barron, Daniel J Egger, Elijah Pelofske, Andreas Bärtschi, Stephan Eidenbenz, Matthis Lehmkuehler, and Stefan Woerner. Provable bounds for noise-free expectation values computed from noisy samples. Nat. Comput. Sci., 4:865–875, 2024. doi:10.1038/s43588-024-00709-1. https://doi.org/10.1038/s43588-024-00709-1 [10] Francisco Barahona, Martin Grötschel, Michael Jünger, and Gerhard Reinelt. An application of combinatorial optimization to statistical physics and circuit layout design. Operations Research, 36:493–513, 1988. doi:10.1287/opre.36.3.493. https://doi.org/10.1287/opre.36.3.493 [11] Sergey Bravyi, David Gosset, and Ramis Movassagh. Classical algorithms for quantum mean values. Nature Physics, 17:337–341, 2021. doi:10.1038/s41567-020-01109-8. https://doi.org/10.1038/s41567-020-01109-8 [12] Michael J. Bremner, Richard Jozsa, and Dan J. Shepherd. Classical simulation of commuting quantum computations implies collapse of the polynomial hierarchy. Proceedings of the Royal Society A: Mathematical, Physical and Engineering Sciences, 467:459–472, 2010. doi:10.1098/rspa.2010.0301. https://doi.org/10.1098/rspa.2010.0301 [13] Michael Ben-Or, Daniel Gottesman, and Avinatan Hassidim. Quantum refrigerator, 2013. doi:10.48550/arXiv.1301.1995. https://doi.org/10.48550/arXiv.1301.1995 [14] Stephen Boyd and Lieven Vandenberghe. Convex Optimization. 2004. doi:10.1017/cbo9780511804441. https://doi.org/10.1017/cbo9780511804441 [15] Piotr Czarnik, Andrew Arrasmith, Patrick J. Coles, and Lukasz Cincio. Error mitigation with clifford quantum-circuit data. Quantum, 5:592, 2021. doi:10.22331/q-2021-11-26-592. https://doi.org/10.22331/q-2021-11-26-592 [16] Zhenyu Cai, Ryan Babbush, Simon C. Benjamin, Suguru Endo, William J. Huggins, Ying Li, Jarrod R. McClean, and Thomas E. O'Brien. Quantum error mitigation. Rev. Mod. Phys., 95:045005, 2023. doi:10.1103/RevModPhys.95.045005. https://doi.org/10.1103/RevModPhys.95.045005 [17] H. Cramér. Mathematical Methods of Statistics.

Goldstine Printed Materials.

Princeton University Press, 1946. doi:10.1126/science.104.2706.450. https://doi.org/10.1126/science.104.2706.450 [18] M. Charikar and A. Wirth. Maximizing quadratic programs: Extending grothendieck’s inequality. 2004. doi:10.1109/focs.2004.39. https://doi.org/10.1109/focs.2004.39 [19] Abhinav Deshpande, Pradeep Niroula, Oles Shtanko, Alexey V. Gorshkov, Bill Fefferman, and Michael J. Gullans. Tight bounds on the convergence of noisy random circuits to the uniform distribution. PRX Quantum, 3, 2022. doi:10.1103/prxquantum.3.040329. https://doi.org/10.1103/prxquantum.3.040329 [20] Giacomo De Palma, Milad Marvian, Cambyse Rouzé, and Daniel Stilck Franca. Limitations of variational quantum algorithms: A quantum optimal transport approach. PRX Quantum, 4:010309, 2023. doi:10.1103/PRXQuantum.4.010309. https://doi.org/10.1103/PRXQuantum.4.010309 [21] Giacomo De Palma, Milad Marvian, Dario Trevisan, and Seth Lloyd. The quantum wasserstein distance of order 1. IEEE Transactions on Information Theory, 67:6627–6643, 2021. doi:10.1109/tit.2021.3076442. https://doi.org/10.1109/tit.2021.3076442 [22] G. Evenbly and G. Vidal. Algorithms for entanglement renormalization. Phys. Rev. B, 79:144108, 2009. doi:10.1103/PhysRevB.79.144108. https://doi.org/10.1103/PhysRevB.79.144108 [23] Edward Farhi, Jeffrey Goldstone, and Sam Gutmann. A quantum approximate optimization algorithm, 2014. doi:10.48550/arXiv.1411.4028. https://doi.org/10.48550/arXiv.1411.4028 [24] Bill Fefferman, Soumik Ghosh, Michael Gullans, Kohdai Kuroiwa, and Kunal Sharma. Effect of nonunital noise on random-circuit sampling. PRX Quantum, 5:030317, 2024. doi:10.1103/PRXQuantum.5.030317. https://doi.org/10.1103/PRXQuantum.5.030317 [25] Roland C. Farrell, Marc Illa, Anthony N. Ciavarella, and Martin J. Savage. Scalable circuits for preparing ground states on digital quantum computers: The schwinger model vacuum on 100 qubits, 2023. doi:10.48550/ARXIV.2308.04481. https://doi.org/10.48550/ARXIV.2308.04481 [26] A. Frieze and M. Jerrum. Improved approximation algorithms for maxk-cut and max bisection. Algorithmica, 18:67–81, 1997. doi:10.1007/bf02523688. https://doi.org/10.1007/bf02523688 [27] Enrico Fontana, Manuel S Rudolph, Ross Duncan, Ivan Rungger, and Cristina Cirstoiu. Classical simulations of noisy variational quantum circuits.

Npj Quantum Inf., 11:84, 2025. doi:10.1038/s41534-024-00955-1. https://doi.org/10.1038/s41534-024-00955-1 [28] James E. Gentle. Computational Statistics. 2009. doi:10.1007/978-0-387-98144-4. https://doi.org/10.1007/978-0-387-98144-4 [29] Bernd Gärtner and Jiri Matoušek. Semidefinite programming.

In Approximation Algorithms and Semidefinite Programming, pages 15–25. 2012. doi:10.1007/978-3-642-22015-9. https://doi.org/10.1007/978-3-642-22015-9 [30] Johnnie Gray. quimb: a python library for quantum information and many-body calculations. Journal of Open Source Software, 3:819, 2018. doi:10.21105/joss.00819. https://doi.org/10.21105/joss.00819 [31] Michel X. Goemans and David P. Williamson. Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming. Journal of the ACM, 42:1115–1145, 1995. doi:10.1145/227683.227684. https://doi.org/10.1145/227683.227684 [32] William J. Huggins, Sam McArdle, Thomas E. O'Brien, Joonho Lee, Nicholas C. Rubin, Sergio Boixo, K. Birgitta Whaley, Ryan Babbush, and Jarrod R. McClean. Virtual distillation for quantum error mitigation. Phys. Rev. X, 11:041036, 2021. doi:10.1103/PhysRevX.11.041036. https://doi.org/10.1103/PhysRevX.11.041036 [33] Matthew P. Harrigan, Kevin J. Sung, Matthew Neeley, Kevin J. Satzinger, Frank Arute, Kunal Arya, Juan Atalaya, Joseph C. Bardin, Rami Barends, Sergio Boixo, Michael Broughton, Bob B. Buckley, David A. Buell, Brian Burkett, Nicholas Bushnell, Yu Chen, Zijun Chen, Ben Chiaro, Roberto Collins, William Courtney, Sean Demura, Andrew Dunsworth, Daniel Eppens, Austin Fowler, Brooks Foxen, Craig Gidney, Marissa Giustina, Rob Graff, Steve Habegger, Alan Ho, Sabrina Hong, Trent Huang, L. B. Ioffe, Sergei V. Isakov, Evan Jeffrey, Zhang Jiang, Cody Jones, Dvir Kafri, Kostyantyn Kechedzhi, Julian Kelly, Seon Kim, Paul V. Klimov, Alexander N. Korotkov, Fedor Kostritsa, David Landhuis, Pavel Laptev, Mike Lindmark, Martin Leib, Orion Martin, John M. Martinis, Jarrod R. McClean, Matt McEwen, Anthony Megrant, Xiao Mi, Masoud Mohseni, Wojciech Mruczkiewicz, Josh Mutus, Ofer Naaman, Charles Neill, Florian Neukart, Murphy Yuezhen Niu, Thomas E. O'Brien, Bryan O'Gorman, Eric Ostby, Andre Petukhov, Harald Putterman, Chris Quintana, Pedram Roushan, Nicholas C. Rubin, Daniel Sank, Andrea Skolik, Vadim Smelyanskiy, Doug Strain, Michael Streif, Marco Szalay, Amit Vainsencher, Theodore White, Z. Jamie Yao, Ping Yeh, Adam Zalcman, Leo Zhou, Hartmut Neven, Dave Bacon, Erik Lucero, Edward Farhi, and Ryan Babbush. Quantum approximate optimization of non-planar graph problems on a planar superconducting processor. Nature Physics, 17:332–336, 2021. doi:10.1038/s41567-020-01105-y. https://doi.org/10.1038/s41567-020-01105-y [34] Richard M. Karp. Reducibility among Combinatorial Problems, page 85–103. 1972. doi:10.1007/978-1-4684-2001-2_9. https://doi.org/10.1007/978-1-4684-2001-2_9 [35] A Yu Kitaev. Quantum computations: algorithms and error correction.

Russian Mathematical Surveys, 52:1191–1249, 1997. doi:10.1070/rm1997v052n06abeh002155. https://doi.org/10.1070/rm1997v052n06abeh002155 [36] S. Khot, G. Kindler, E. Mossel, and R. O'Donnell. Optimal inapproximability results for max-cut and other 2-variable csps? In 45th Annual IEEE Symposium on Foundations of Computer Science, pages 146–154, 2004. doi:10.1109/FOCS.2004.49. https://doi.org/10.1109/FOCS.2004.49 [37] C. Kokail, C. Maier, R. van Bijnen, T. Brydges, M. K. Joshi, P. Jurcevic, C. A. Muschik, P. Silvi, R. Blatt, C. F. Roos, and P. Zoller. Self-verifying variational quantum simulation of lattice models. Nature, 569:355–360, 2019. doi:10.1038/s41586-019-1177-4. https://doi.org/10.1038/s41586-019-1177-4 [38] Subhash Khot and Assaf Naor. Linear equations modulo 2 and the l1 diameter of convex bodies. In 48th Annual IEEE Symposium on Foundations of Computer Science (FOCS'07), 2007. doi:10.1109/focs.2007.20. https://doi.org/10.1109/focs.2007.20 [39] Kecheng Liu and Zhenyu Cai. Quantum error mitigation for sampling algorithms, 2025. doi:10.48550/ARXIV.2502.11285. https://doi.org/10.48550/ARXIV.2502.11285 [40] Yong Liu, Yaojian Chen, Chu Guo, Jiawei Song, Xinmin Shi, Lin Gan, Wenzhao Wu, Wei Wu, Haohuan Fu, Xin Liu, Dexun Chen, Zhifeng Zhao, Guangwen Yang, and Jiangang Gao. Verifying quantum advantage experiments with multiple amplitude tensor network contraction. Phys. Rev. Lett., 132:030601, 2024. doi:10.1103/PhysRevLett.132.030601. https://doi.org/10.1103/PhysRevLett.132.030601 [41] Andrew Lucas. Ising formulations of many np problems. Frontiers in Physics, 2, 2014. doi:10.3389/fphy.2014.00005. https://doi.org/10.3389/fphy.2014.00005 [42] Victor Martinez, Armando Angrisani, Ekaterina Pankovets, Omar Fawzi, and Daniel Stilck França. Efficient simulation of parametrized quantum circuits under nonunital noise through pauli backpropagation. Phys. Rev. Lett., 134:250602, 2025. doi:10.1103/j1gg-s6zb. https://doi.org/10.1103/j1gg-s6zb [43] Tetsuhisa Miwa, A. J. Hayter, and Satoshi Kuriki. The evaluation of general non-centred orthant probabilities. Journal of the Royal Statistical Society Series B: Statistical Methodology, 65:223–234, 2003. doi:10.1111/1467-9868.00382. https://doi.org/10.1111/1467-9868.00382 [44] David C. McKay, Ian Hincks, Emily J. Pritchett, Malcolm Carroll, Luke C. G. Govia, and Seth T. Merkel. Benchmarking quantum processor performance at scale, 2023. doi:10.48550/arXiv.2311.05933. https://doi.org/10.48550/arXiv.2311.05933 [45] Sam McArdle, Tyson Jones, Suguru Endo, Ying Li, Simon C. Benjamin, and Xiao Yuan. Variational ansatz-based quantum simulation of imaginary time evolution. npj Quantum Information, 5, 2019. doi:10.1038/s41534-019-0187-2. https://doi.org/10.1038/s41534-019-0187-2 [46] Michael A. Nielsen and Isaac L. Chuang. Quantum Computation and Quantum Information: 10th Anniversary Edition. 2012. doi:10.1017/CBO9780511976667. https://doi.org/10.1017/CBO9780511976667 [47] Yu Nesterov. Semidefinite relaxation and nonconvex quadratic optimization. Optimization Methods and Software, 9:141–160, 1998. doi:10.1080/10556789808805690. https://doi.org/10.1080/10556789808805690 [48] Hidetoshi Nishimori. Statistical Physics of Spin Glasses and Information Processing: An Introduction. 2001. doi:10.1093/acprof:oso/9780198509417.001.0001. https://doi.org/10.1093/acprof:oso/9780198509417.001.0001 [49] Jon Nelson, Joel Rajakumar, Dominik Hangleiter, and Michael J. Gullans. Polynomial-time classical simulation of noisy circuits with naturally fault-tolerant gates, 2024. doi:10.48550/arXiv.2411.02535. https://doi.org/10.48550/arXiv.2411.02535 [50] Miha Papič, Adrian Auer, and Inés de Vega. Fast estimation of physical error contributions of quantum gates, 2023. doi:10.48550/ARXIV.2305.08916. https://doi.org/10.48550/ARXIV.2305.08916 [51] Alberto Peruzzo, Jarrod McClean, Peter Shadbolt, Man-Hong Yung, Xiao-Qi Zhou, Peter J. Love, Alán Aspuru-Guzik, and Jeremy L. O’Brien. A variational eigenvalue solver on a photonic quantum processor. Nature Communications, 5, 2014. doi:10.1038/ncomms5213. https://doi.org/10.1038/ncomms5213 [52] Christophe Piveteau, David Sutter, and Stefan Woerner. Quasiprobability decompositions with reduced sampling overhead. npj Quantum Information, 8, 2022. doi:10.1038/s41534-022-00517-3. https://doi.org/10.1038/s41534-022-00517-3 [53] Jan Poland and Thomas Zeugmann. Clustering pairwise distances with missing data: Maximum cuts versus normalized cuts. pages 197–208, 2006. doi:10.1007/11893318_21. https://doi.org/10.1007/11893318_21 [54] Yihui Quek, Daniel Stilck França, Sumeet Khatri, Johannes Jakob Meyer, and Jens Eisert. Exponentially tighter bounds on limitations of quantum error mitigation. Nature Physics, 20:1648–1658, 2024. doi:10.1038/s41567-024-02536-7. https://doi.org/10.1038/s41567-024-02536-7 [55] Manuel S. Rudolph, Enrico Fontana, Zoë Holmes, and Lukasz Cincio. Classical surrogate simulation of quantum systems with lowesa, 2023. doi:10.48550/arXiv.2308.09109. https://doi.org/10.48550/arXiv.2308.09109 [56] Daniel Stilck França and Raul Garcia-Patron. Limitations of optimization algorithms on noisy quantum devices. Nature Physics, 17:1221–1227, 2021. doi:10.1038/s41567-021-01356-3. https://doi.org/10.1038/s41567-021-01356-3 [57] A. M. Steane. Error correcting codes in quantum theory. Phys. Rev. Lett., 77:793–797, 1996. doi:10.1103/PhysRevLett.77.793. https://doi.org/10.1103/PhysRevLett.77.793 [58] Oles Shtanko, Derek S. Wang, Haimeng Zhang, Nikhil Harle, Alireza Seif, Ramis Movassagh, and Zlatko Minev. Uncovering local integrability in quantum many-body dynamics, 2023. doi:10.48550/ARXIV.2307.07552. https://doi.org/10.48550/ARXIV.2307.07552 [59] Thomas Schuster, Chao Yin, Xun Gao, and Norman Y. Yao. A polynomial-time classical algorithm for noisy quantum circuits. Phys. Rev. X, 15:041018, 2025. doi:10.1103/xct1-7kf2. https://doi.org/10.1103/xct1-7kf2 [60] Kristan Temme, Sergey Bravyi, and Jay M. Gambetta. Error mitigation for short-depth quantum circuits. Phys. Rev. Lett., 119:180509, 2017. doi:10.1103/PhysRevLett.119.180509. https://doi.org/10.1103/PhysRevLett.119.180509 [61] B.M. Terhal and D.P. DiVincenzo. Adaptive quantum computation, constant depth quantum circuits and arthur-merlin games. Quantum Information and Computation, 4:134–145, 2004. doi:10.26421/qic4.2-5. https://doi.org/10.26421/qic4.2-5 [62] Ryuji Takagi, Suguru Endo, Shintaro Minagawa, and Mile Gu. Fundamental limits of quantum error mitigation. npj Quantum Information, 8, 2022. doi:10.1038/s41534-022-00618-z. https://doi.org/10.1038/s41534-022-00618-z [63] Barbara M. Terhal. Quantum error correction for quantum memories. Rev. Mod. Phys., 87:307–346, 2015. doi:10.1103/RevModPhys.87.307. https://doi.org/10.1103/RevModPhys.87.307 [64] Richard S. Varga. Geršgorin and His Circles.

Springer Berlin Heidelberg, 2004. doi:10.1007/978-3-642-17798-9. https://doi.org/10.1007/978-3-642-17798-9 [65] Roman Vershynin. High-Dimensional Probability: An Introduction with Applications in Data Science. 2018. doi:10.1017/9781108231596. https://doi.org/10.1017/9781108231596 [66] Dominik S. Wild and Álvaro M. Alhambra. Classical simulation of short-time quantum dynamics. PRX Quantum, 4:020340, 2023. doi:10.1103/PRXQuantum.4.020340. https://doi.org/10.1103/PRXQuantum.4.020340 [67] Jonathan Wurtz and Danylo Lykov. Fixed-angle conjectures for the quantum approximate optimization algorithm on regular maxcut graphs. Phys. Rev. A, 104:052419, 2021. doi:10.1103/PhysRevA.104.052419. https://doi.org/10.1103/PhysRevA.104.052419 [68] Nobuyuki Yoshioka, Mirko Amico, William Kirby, Petar Jurcevic, Arkopal Dutt, Bryce Fuller, Shelly Garion, Holger Haas, Ikko Hamamura, Alexander Ivrii, Ritajit Majumdar, Zlatko Minev, Mario Motta, Bibek Pokharel, Pedro Rivero, Kunal Sharma, Christopher J. Wood, Ali Javadi-Abhari, and Antonio Mezzacapo. Krylov diagonalization of large many-body hamiltonians on a quantum processor. Nature Communications, 16, 2025. doi:10.1038/s41467-025-59716-z. https://doi.org/10.1038/s41467-025-59716-z [69] Hongye Yu, Yusheng Zhao, and Tzu-Chieh Wei. Simulating large-size quantum spin chains on cloud-based superconducting quantum computers. Phys. Rev. Res., 5:013183, 2023. doi:10.1103/PhysRevResearch.5.013183. https://doi.org/10.1103/PhysRevResearch.5.013183Cited byCould not fetch Crossref cited-by data during last attempt 2026-04-15 11:19:16: Could not fetch cited-by data for 10.22331/q-2026-04-15-2068 from Crossref. This is normal if the DOI was registered recently. Could not fetch ADS cited-by data during last attempt 2026-04-15 11:19:16: No response from ADS or unable to decode the received json data when getting the list of citing works.This Paper is published in Quantum under the Creative Commons Attribution 4.0 International (CC BY 4.0) license. Copyright remains with the original copyright holders such as the authors or their institutions. AbstractThe 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 a recovery ratio $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.Featured image: Framework overview: For a graph-based optimization instance, expectation values are extracted from a quantum circuit $\mathcal{C}$. Our classical sampling algorithms then leverage these values to generate candidate solutions with provable quality guarantees.Popular summaryCurrent quantum processors are scaling up but remain limited by hardware noise. For combinatorial optimization, evaluating the average performance, or expectation values, of a quantum circuit is insufficient: practical applications require sampling the actual bitstrings that encode candidate solutions. While noisy expectation values can often be efficiently estimated classically, sampling the actual bitstrings from these optimization-focused quantum circuits has historically remained out of reach without using a quantum computer. In this work, we introduce a classical method to generate samples that faithfully mimic the output of noisy quantum circuits for combinatorial optimization. More specifically, we focus on two-body problems like MaxCut, where the objective function depends entirely on pairwise qubit correlations. Our approach leverages these classically accessible expectation values and combines them with a Gaussian randomized rounding procedure, inspired by the Goemans-Williamson algorithm, to generate candidate solutions. We provide analytical guarantees on the quality of the samples produced, alongside empirical validation on IBM hardware. We prove that under local depolarizing noise, there is a fixed number of circuit layers (dependent only on the noise strength) that can be implemented before our classical surrogate performs just as well as the quantum device. When combined with classical techniques for estimating expectation values, this rounding procedure forms a polynomial-time classical pipeline for sampling from noisy variational circuits.► BibTeX data@article{Martinez2026samplingnoisy, doi = {10.22331/q-2026-04-15-2068}, url = {https://doi.org/10.22331/q-2026-04-15-2068}, title = {Sampling (noisy) quantum circuits through randomized rounding}, author = {Martinez, Victor and Fawzi, Omar and Fran{\c{c}}a, Daniel Stilck}, journal = {{Quantum}}, issn = {2521-327X}, publisher = {{Verein zur F{\"{o}}rderung des Open Access Publizierens in den Quantenwissenschaften}}, volume = {10}, pages = {2068}, month = apr, year = {2026} }► References [1] Frank Arute, Kunal Arya, Ryan Babbush, Dave Bacon, Joseph C. Bardin, Rami Barends, Rupak Biswas, Sergio Boixo, Fernando G. S. L. Brandao, David A. Buell, Brian Burkett, Yu Chen, Zijun Chen, Ben Chiaro, Roberto Collins, William Courtney, Andrew Dunsworth, Edward Farhi, Brooks Foxen, Austin Fowler, Craig Gidney, Marissa Giustina, Rob Graff, Keith Guerin, Steve Habegger, Matthew P. Harrigan, Michael J. Hartmann, Alan Ho, Markus Hoffmann, Trent Huang, Travis S. Humble, Sergei V. Isakov, Evan Jeffrey, Zhang Jiang, Dvir Kafri, Kostyantyn Kechedzhi, Julian Kelly, Paul V. Klimov, Sergey Knysh, Alexander Korotkov, Fedor Kostritsa, David Landhuis, Mike Lindmark, Erik Lucero, Dmitry Lyakh, Salvatore Mandrà, Jarrod R. McClean, Matthew McEwen, Anthony Megrant, Xiao Mi, Kristel Michielsen, Masoud Mohseni, Josh Mutus, Ofer Naaman, Matthew Neeley, Charles Neill, Murphy Yuezhen Niu, Eric Ostby, Andre Petukhov, John C. Platt, Chris Quintana, Eleanor G. Rieffel, Pedram Roushan, Nicholas C. Rubin, Daniel Sank, Kevin J. Satzinger, Vadim Smelyanskiy, Kevin J. Sung, Matthew D. Trevithick, Amit Vainsencher, Benjamin Villalonga, Theodore White, Z. Jamie Yao, Ping Yeh, Adam Zalcman, Hartmut Neven, and John M. Martinis. Quantum supremacy using a programmable superconducting processor. Nature, 574:505–510, 2019. doi:10.1038/s41586-019-1666-5. https://doi.org/10.1038/s41586-019-1666-5 [2] Dorit Aharonov, Xun Gao, Zeph Landau, Yunchao Liu, and Umesh Vazirani. A polynomial-time classical algorithm for noisy random circuit sampling. In Proceedings of the 55th Annual ACM Symposium on Theory of Computing, STOC ’23, 2023. doi:10.1145/3564246.3585234. https://doi.org/10.1145/3564246.3585234 [3] Srinivasan Arunachalam, Vojtech Havlicek, and Louis Schatzki. On the role of entanglement and statistics in learning, 2023. doi:10.48550/arXiv.2306.03161. https://doi.org/10.48550/arXiv.2306.03161 [4] David Amaro, Carlo Modica, Matthias Rosenkranz, Mattia Fiorentini, Marcello Benedetti, and Michael Lubasch. Filtering variational quantum algorithms for combinatorial optimization. Quantum Science and Technology, 7:015021, 2022. doi:10.1088/2058-9565/ac3e54. https://doi.org/10.1088/2058-9565/ac3e54 [5] Armando Angrisani, Antonio A. Mele, Manuel S. Rudolph, M. Cerezo, and Zoë Holmes. Simulating quantum circuits with arbitrary local noise using pauli propagation, 2025. doi:10.48550/arXiv.2501.13101. https://doi.org/10.48550/arXiv.2501.13101 [6] Noga Alon and Assaf Naor. Approximating the cut-norm via grothendieck's inequality. In Proceedings of the Thirty-Sixth Annual ACM Symposium on Theory of Computing, STOC '04, page 72–80, 2004. doi:10.1145/1007352.1007371. https://doi.org/10.1145/1007352.1007371 [7] Armando Angrisani, Alexander Schmidhuber, Manuel S. Rudolph, M. Cerezo, Zoë Holmes, and Hsin-Yuan Huang. Classically estimating observables of noiseless quantum circuits. Phys. Rev. Lett., 135:170602, 2025. doi:10.1103/lh6x-7rc3. https://doi.org/10.1103/lh6x-7rc3 [8] Yogesh J. Bagul and Ramkrishna M. Dhaigude. Simple efficient bounds for arcsine and arctangent functions. 2021. doi:10.21203/rs.3.rs-404784/v1. https://doi.org/10.21203/rs.3.rs-404784/v1 [9] Samantha V Barron, Daniel J Egger, Elijah Pelofske, Andreas Bärtschi, Stephan Eidenbenz, Matthis Lehmkuehler, and Stefan Woerner. Provable bounds for noise-free expectation values computed from noisy samples. Nat. Comput. Sci., 4:865–875, 2024. doi:10.1038/s43588-024-00709-1. https://doi.org/10.1038/s43588-024-00709-1 [10] Francisco Barahona, Martin Grötschel, Michael Jünger, and Gerhard Reinelt. An application of combinatorial optimization to statistical physics and circuit layout design. Operations Research, 36:493–513, 1988. doi:10.1287/opre.36.3.493. https://doi.org/10.1287/opre.36.3.493 [11] Sergey Bravyi, David Gosset, and Ramis Movassagh. Classical algorithms for quantum mean values. Nature Physics, 17:337–341, 2021. doi:10.1038/s41567-020-01109-8. https://doi.org/10.1038/s41567-020-01109-8 [12] Michael J. Bremner, Richard Jozsa, and Dan J. Shepherd. Classical simulation of commuting quantum computations implies collapse of the polynomial hierarchy. Proceedings of the Royal Society A: Mathematical, Physical and Engineering Sciences, 467:459–472, 2010. doi:10.1098/rspa.2010.0301. https://doi.org/10.1098/rspa.2010.0301 [13] Michael Ben-Or, Daniel Gottesman, and Avinatan Hassidim. Quantum refrigerator, 2013. doi:10.48550/arXiv.1301.1995. https://doi.org/10.48550/arXiv.1301.1995 [14] Stephen Boyd and Lieven Vandenberghe. Convex Optimization. 2004. doi:10.1017/cbo9780511804441. https://doi.org/10.1017/cbo9780511804441 [15] Piotr Czarnik, Andrew Arrasmith, Patrick J. Coles, and Lukasz Cincio. Error mitigation with clifford quantum-circuit data. Quantum, 5:592, 2021. doi:10.22331/q-2021-11-26-592. https://doi.org/10.22331/q-2021-11-26-592 [16] Zhenyu Cai, Ryan Babbush, Simon C. Benjamin, Suguru Endo, William J. Huggins, Ying Li, Jarrod R. McClean, and Thomas E. O'Brien. Quantum error mitigation. Rev. Mod. Phys., 95:045005, 2023. doi:10.1103/RevModPhys.95.045005. https://doi.org/10.1103/RevModPhys.95.045005 [17] H. Cramér. Mathematical Methods of Statistics.

Goldstine Printed Materials.

Read Original

Source Information

Source: Quantum Journal

Website: https://quantum-journal.org/feed/

Sampling (noisy) quantum circuits through randomized rounding

Tags

Source Information