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

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 of the sampling algorithm. Specifically, we consider a family of <a:math xmlns:a="http://www.w3.org/1998/Math/MathML" display="inline"><a:mtext>⟦</a:mtext><a:msup><a:mn>2</a:mn><a:mi>D</a:mi></a:msup><a:mo>,</a:mo><a:mi>D</a:mi><a:mo>,</a:mo><a:mn>2</a:mn><a:mtext>⟧</a:mtext></a:math> quantum error-detecting codes whose transversal and permutation gate set can realize arbitrary degree-<c:math xmlns:c="http://www.w3.org/1998/Math/MathML" display="inline"><c:mi>D</c:mi></c:math> 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 [Nature 626, 7997 (2024)]. We develop a theory of second-moment properties of degree-<e:math xmlns:e="http://www.w3.org/1998/Math/MathML" display="inline"><e:mi>D</e:mi></e:math> 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 <g:math xmlns:g="http://www.w3.org/1998/Math/MathML" display="inline"><g:mtext>⟦</g:mtext><g:mi>O</g:mi><g:mo stretchy="false">(</g:mo><g:msup><g:mi>d</g:mi><g:mi>D</g:mi></g:msup><g:mo stretchy="false">)</g:mo><g:mo>,</g:mo><g:mi>D</g:mi><g:mo>,</g:mo><g:mi>d</g:mi><g:mtext>⟧</g:mtext></g:math> color codes of increasing distance <k:math xmlns:k="http://www.w3.org/1998/Math/MathML" display="inline"><k:mi>d</k:mi></k:math>, 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.