Skip to main content
U.S. flag

An official website of the United States government

Official websites use .gov
A .gov website belongs to an official government organization in the United States.

Secure .gov websites use HTTPS
A lock ( ) or https:// means you’ve safely connected to the .gov website. Share sensitive information only on official, secure websites.

Fault-Tolerant Compiling of Classically Hard Instantaneous Quantum Polynomial Circuits on Hypercubes

Published

Author(s)

Dominik Hangleiter, Marcin Kalinowkski, Dolev Bluvstein, Madelyn Cain, Nishad Maskara, Xun Gao, Aleksander Kubica, Mikhail Lukin, Michael Gullans

Abstract

Quantum computational advantage is challenging to maintain asymptotically in the presence of noise. Fault-tolerant quantum computing provides a route to noiseless computations, but can have high overheads for generic algorithms. Here, we develop a fault-tolerant approach to quantum advantage that is both tailored to the quantum algorithm and hardware-efficient for reconfigurable atom arrays, constituting what we call a fault-tolerant compilation. We consider a family of [2D , D, 2] quantum error correcting codes whose transversal and permutation gate set can realize arbitrary degree-D instantaneous quantum polynomial (IQP) computations. Using only native operations of the code and the hardware, we then compile a fault-tolerant and fast-scrambling family of such IQP circuits in a hypercube geometry, realized on up to 48 logical qubits by Bluvstein et al. [Nature 626, 7997 (2024)]. We develop a theory of second-moment properties of degree-D IQP circuits for analyzing hardness and verification of random sampling by mapping to a statistical mechanics model. We find strong evidence that sampling from these hypercube IQP circuits is classically hard to simulate even at low depths. We analyze the linear cross-entropy benchmark (XEB) in comparison to the average fidelity, finding two different asymptotic regimes depending on the local noise rate. To make our approach fully scalable, we first show that Bell sampling from degree- 4 IQP circuits is classically intractable and can be efficiently validated. We further devise a new family of [O(dD ), D, d] color codes of increasing distance d, permitting exponential error suppression for transversal IQP sampling. Our results highlight fault-tolerant compiling as a powerful tool in co-designing algorithms with specific error-correcting codes and hardware constraints.
Citation
PRX Quantum
Volume
6
Issue
2

Keywords

quantum information science, quantum error correction, quantum algorithms

Citation

Hangleiter, D. , Kalinowkski, M. , Bluvstein, D. , Cain, M. , Maskara, N. , Gao, X. , Kubica, A. , Lukin, M. and Gullans, M. (2025), Fault-Tolerant Compiling of Classically Hard Instantaneous Quantum Polynomial Circuits on Hypercubes, PRX Quantum, [online], https://doi.org/10.1103/PRXQuantum.6.020338, https://tsapps.nist.gov/publication/get_pdf.cfm?pub_id=957831 (Accessed June 5, 2025)

Issues

If you have any questions about this publication or are having problems accessing it, please contact [email protected].

Created May 28, 2025, Updated June 2, 2025
Was this page helpful?