Robust sparse IQP sampling in constant depth
Open accessThe DOI matches its Crossref record; 48 of the 48 references it cites were found in a registry or an index.
Abstract
Between NISQ (noisy intermediate scale quantum) approaches without any proof of robust quantum advantage and fully fault-tolerant quantum computation, we propose a scheme to achieve a provable superpolynomial quantum advantage (under some widely accepted complexity conjectures) that is robust to noise with minimal error correction requirements. We choose a class of sampling problems with commuting gates known as sparse IQP (Instantaneous Quantum Polynomial-time) circuits and we ensure its fault-tolerant implementation by introducing the tetrahelix code. This new code is obtained by merging several tetrahedral codes (3D color codes) and has the following properties: each sparse IQP gate admits a transversal implementation, and the depth of the logical circuit can be traded for its width. Combining those, we obtain a depth-1 implementation of any sparse IQP circuit up to the preparation of encoded states. This comes at the cost of a space overhead which is only polylogarithmic in the width of the original circuit. We furthermore show that the state preparation can also be performed in constant depth with a single step of feed-forward from classical computation. Our construction thus exhibits a robust superpolynomial quantum advantage for a sampling problem implemented on a constant depth circuit with a single round of measurement and feed-forward.
Overview
The claims and statistics of this paper haven’t been checked yet.
Free: it reads the open-access text and checks the first 5 claims that cite a source we can check. Create a free account to check every claim.
Integrity signals
Registry
Cites
Statistics
Verification
Claims the paper makes
The claims and statistics of this paper haven’t been checked yet.
Free: it reads the open-access text and checks the first 5 claims that cite a source we can check. Create a free account to check every claim.
Claims other papers make about this one
Each is checked against this paper’s own text: does it say what the citing paper says it does?
The source backs part of the claim, not all of it — or backs it for a different population, condition or comparison.
In the citing paper
“More specifically, these circuits can be mapped to instantaneous quantum polynomial (IQP) circuits20,45,46.”
From Logical quantum processor based on reconfigurable atom arrays (2024) · cites this paper as [46]
Experimental — accuracy not yet measuredThe cited source says what the claim attributes to it.
In the citing paper
“We use these transversal operations to realize logical algorithms that are difficult to simulate classically45,46.”
From Logical quantum processor based on reconfigurable atom arrays (2024) · cites this paper as [46]
Self-check
Percentages, sums and reported differences re-computed from the paper’s own numbers.
The self-check needs the paper’s full text.
Citations
Cites
Quantum Computing in the NISQ era and beyond
Preskill, J. (2018) · Quantum · doi:10.22331/q-2018-08-06-79 · Cited by 8,830 · cited 1×
“…strategy to address the issue of noise is to focus on problems for which it is possible to add some level of fault-tolerance, in an intermediate manner between Noisy Intermediate-Scale Quantum (NISQ) processors available in the near term [11] and universal fault-tolerant quantum computation.”
BackgroundError Correcting Codes in Quantum Theory
Steane, A. M. (1996) · Physical Review Letters · doi:10.1103/physrevlett.77.793 · Cited by 2,677 · cited 1×
“Moreover, because these codes are CSS codes [27, 28], they also admit a transversal CNOT gate.”
Good quantum error-correcting codes exist
Calderbank, A. R., & Shor, P. W. (1996) · Physical Review A · doi:10.1103/physreva.54.1098 · Cited by 2,516 · cited 1×
“Moreover, because these codes are CSS codes [27, 28], they also admit a transversal CNOT gate.”
Logical quantum processor based on reconfigurable atom arrays
Bluvstein, D., Evered, S. J., Geim, A. A., Li, S. H., Zhou, H., Manovitz, T., Ebadi, S., Cain, M., Kalinowski, M., Hangleiter, D., et al. (2024) · Nature · doi:10.1038/s41586-023-06927-3 · Cited by 1,119 · cited 1×
“This would participate bringing the scheme further within reach of current experiments [46].”
BackgroundThe computational complexity of linear optics
Aaronson, S., & Arkhipov, A. (2011) · Proceedings of the forty-third annual ACM symposium on Theory of computing · doi:10.1145/1993636.1993682 · Cited by 874 · cited 1×
“Well-known examples of circuit families include linear optical circuits in the case of BosonSam-pling [3], random quantum circuits [4] and Instanta-neous Quantum Polynomial-time (IQP) circuits [5].”
MethodHow to factor 2048 bit RSA integers in 8 hours using 20 million noisy qubits
Gidney, C., & Ekerå, M. (2021) · Quantum · doi:10.22331/q-2021-04-15-433 · Cited by 830 · cited 1×
“More precisely, Theorem 1 (Classical hardness of sparse IQP sampling [18]) .”
Topological Quantum Distillation
Bombin, H., & Martin-Delgado, M. A. (2006) · Physical Review Letters · doi:10.1103/physrevlett.97.180501 · Cited by 700
Knill, E., Laflamme, R., & Zurek, W. H. (1998) · Science · doi:10.1126/science.279.5349.342 · Cited by 663 · cited 1×
“We remark that similar time complexities are often neglected in the literature of quantum fault-tolerance [19, 20, 21], and it may in fact not be a very problematic issue in practice.”
BackgroundSurface code quantum computing by lattice surgery
Horsman, D., Fowler, A. G., Devitt, S., & Meter, R. V. (2012) · New Journal of Physics · doi:10.1088/1367-2630/14/12/123011 · Cited by 598 · cited 2×
“As briefly mentioned in subsection 1.2.1, a tetrahe-lix code is obtained by merging tetrahedral codes in lattice surgery terms [29, 30, 36].”
BackgroundMethodInfluentialFault-Tolerant Quantum Computation with Constant Error Rate
Aharonov, D., & Ben-Or, M. (2008) · SIAM Journal on Computing · doi:10.1137/s0097539799359385 · Cited by 513
Cited by
Logical quantum processor based on reconfigurable atom arrays
Bluvstein, D., Evered, S. J., Geim, A. A., Li, S. H., Zhou, H., Manovitz, T., Ebadi, S., Cain, M., Kalinowski, M., Hangleiter, D., et al. (2024) · Nature · doi:10.1038/s41586-023-06927-3 · Cited by 1,119
“we find a similar Bell fidelity of 75(2)%, indicating high-fidelity performance of the readout and feedforward operations.”
BackgroundA Polynomial-Time Classical Algorithm for Noisy Quantum Circuits
Schuster, T., Yin, C., Gao, X., & Yao, N. Y. (2025) · Physical Review X · doi:10.1103/xct1-7kf2 · Cited by 148
Quantum Computational Advantage with Constant-Temperature Gibbs Sampling
Bergamaschi, T., Chen, C.-F., & Liu, Y. (2024) · Annual Symposium on Foundations of Computer Science · doi:10.1109/focs61266.2024.00071 · Cited by 63
Polynomial-Time Classical Simulation of Noisy IQP Circuits with Constant Depth
Rajakumar, J., Watson, J. D., & Liu, Y.-K. (2025) · Proceedings of the 2025 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA) · doi:10.1137/1.9781611978322.30 · Cited by 7
de Oliveira, M., Subramanian, S., Mendes, L. R. D. S., & Hsieh, M.-H. (2025) · Nature Communications · doi:10.1038/s41467-025-58545-4 · Cited by 13
“We have reiterated the interest of magic states in the constant-depth fault-tol-erantregimes 55,56 ,andremarkthatwebelievethatmagicstatefactories are unlikely to be parallelizable to the extent of being realizable by constant-depth quantum circuits.”
Metadata
- Authors
- Paletta, L., Leverrier, A., Sarlette, A., Mirrahimi, M., & Vuillot, C.
- Affiliations
- Centre National de la Recherche Scientifique (FR)
- Centre Inria de Paris (FR)
- Venue
- Quantum
- Published
- 2024-05-06
- Volume
- 8
- Pages
- 1337
- ISSN
- 2521-327X (ISSN-L)
- OpenAlex
- W4389101042
- Cited by
- 8
- References
- 42
- Citations by year
- 2026: 1 · 2025: 5 · 2024: 1
- FWCI
- 1.04
- Type
- journal article
- Language
- en
- Open access
- gold
- doi.org
- Locations
- Quantum (publishedVersion, cc-by)
- HAL (submittedVersion, cc-by)
- arXiv (Cornell University) (submittedVersion, cc-by)
- DOAJ (DOAJ: Directory of Open Access Journals) (submittedVersion)
- arXiv (Cornell University) (cc-by)
- Funders
- ANR (ANR-22-PETQ- 0006, HQI ANR-22-PNCQ-0002)
- Inria (Inria EQIP challenge.)
- Topics
- Physical Sciences › Computer Science › Artificial Intelligence › Quantum Computing Algorithms and Architecture
- Physical Sciences › Physics and Astronomy › Atomic and Molecular Physics, and Optics › Quantum Information and Cryptography
- Physical Sciences › Physics and Astronomy › Atomic and Molecular Physics, and Optics › Quantum many-body systems
- Keywords
- quantum sampling, quantum advantage, transversal gates, constant-depth circuits, fault-tolerant quantum computing, NISQ devices, noise robustness, feedforward
About these checks
Registry, retraction, Cites and statistics results are computed, not judged, with one exception: a printed reference that no index lists is read once by a model before it counts as a citation error. Claims are extracted by a model and kept only when their quote appears verbatim in the text; each cited source is then checked, with a model’s help, for whether it says what the claim relies on. Those verdicts can be wrong — read the claim’s quote and the cited source before relying on one.
Statistics and arithmetic are recomputed, not judged.
Confidence bands are shown only for fields calibrated on our annotated test set. None is calibrated yet, so no band is shown.
What counts as a claim ›How we measure confidence ›How we check this ›
Are you an author, or do you see a problem with this page? Request a review
How to cite
Cite CoChat for the checks on this page, and the paper for its own findings.
- This page
- CoChat. (2026). Citation check: Robust sparse IQP sampling in constant depth. https://app.cochat.ai/papers/10.22331/q-2024-05-06-1337
- The paper
- Paletta, L., Leverrier, A., Sarlette, A., Mirrahimi, M., & Vuillot, C. (2024). Robust sparse IQP sampling in constant depth. Quantum. https://doi.org/10.22331/q-2024-05-06-1337
Data sources
Bibliographic data: Semantic Scholar, OpenAlex, Crossref.
Contains information from the Semantic Scholar Academic Graph Datasets, made available under the ODC Attribution License (ODC-BY 1.0).
Semantic Scholar’s data is described in: Kinney, R., et al. (2023). The Semantic Scholar Open Data Platform. arXiv:2301.10140.