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

Published

May 28, 2025

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

Pub Type

Journals

Download Paper

https://doi.org/10.1103/PRXQuantum.6.020338

Local Download

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 26, 2025)