PRX QUANTUM 6, 020338 (2025)
Fault-Tolerant Compiling of Classically Hard Instantaneous Quantum
Polynomial Circuits on Hypercubes
Dominik Hangleiter ,
1,*,†
Marcin Kalinowski ,
2,†
Dolev Bluvstein,
2,†
Madelyn Cain ,
2
Nishad Maskara ,
2
Xun Gao,
2,3
Aleksander Kubica ,
4,5
Mikhail D. Lukin,
2
and Michael J. Gullans
1
1
Joint Center for Quantum Information and Computer Science, NIST/University of Maryland,
College Park, Maryland 20742, USA
2
Department of Physics, Harvard University, Cambridge, Massachusetts 02138, USA
3
JILA and Department of Physics, University of Colorado, Boulder, Colorado 80309, USA
4
AWS Center for Quantum Computing, Pasadena, California 91125, USA
5
California Institute of Technology, Pasadena, California 91125, USA
(Received 13 June 2024; revised 10 February 2025; accepted 31 March 2025; published 28 May 2025)
Realizing computationally complex quantum circuits in the presence of noise and imperfections is a
challenging task. While fault-tolerant quantum computing provides a route to reducing noise, it requires
a large overhead for generic algorithms. Here, we develop and analyze a hardware-efficient, fault-tolerant
approach to realizing complex sampling circuits. We co-design the circuits with the appropriate quantum
error-correcting codes for efficient implementation in a reconfigurable neutral atom-array architecture,
constituting what we call a fault-tolerant compilation of the sampling algorithm. Specifically, we consider
a family of [[2
D
, D, 2]] quantum error-detecting codes whose transversal and permutation gate set can
realize arbitrary degree-D instantaneous quantum polynomial (IQP) circuits. Using native operations of
the code and the atom-array hardware, we compile a fault-tolerant and fast-scrambling family of such IQP
circuits in a hypercube geometry, realized recently in the experiments 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 provide
strong evidence that sampling from these hypercube IQP circuits is classically hard to simulate even at
relatively low depths. We analyze the linear cross-entropy benchmark (XEB) in comparison to the average
fidelity and, depending on the local noise rate, find two different asymptotic regimes. To realize a fully
scalable approach, we first show that Bell sampling from degree-4 IQP circuits is classically intractable
and can be efficiently validated. We further devise new families of [[O(d
D
), 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 realistic hardware.
DOI: 10.1103/PRXQuantum.6.020338
I. INTRODUCTION
Quantum computers hold a promise to significantly out-
perform classical computers at various tasks. However, for
many envisioned applications, very low error rates below
approximately 10
−10
are required [1–5], in stark contrast
to the state-of-the-art experimental physical error rates
*
Contact author: mail@dhangleiter.eu
†
D.H., M.K., and D.B. contributed equally.
Published by the American Physical Society under the terms of
the Creative Commons Attribution 4.0 International license. Fur-
ther distribution of this work must maintain attribution to the
author(s) and the published article’s title, journal citation, and
DOI.
of approximately 10
−3
. Quantum error correction (QEC)
provides a potential solution to this challenge by encod-
ing error-corrected “logical” qubits across many redundant
physical qubits [6–8]. In principle, QEC can exponen-
tially suppress the logical error rate by increasing the
code distance d, thereby promising a realistic route to low
error rates required for large-scale algorithms. However,
implementing QEC in practice is challenging. In addi-
tion to the large physical qubit overheads, QEC codes
typically realize a discrete gate set using native opera-
tions [9]. Although universal computation can be realized
through various techniques such as magic state distillation
[10–12] and code switching [13,14], these are generally
very resource intensive. Thus devising hardware-efficient
and fault-tolerant realizations of quantum algorithms is
2691-3399/25/6(2)/020338(50) 020338-1 Published by the American Physical Society
