2024/04/29 by Hangleiter, Dominik, Kalinowski, Marcin, Bluvstein, Dolev +6 · 1 citation
#Atomic Physics (physics.atom-ph) #Computational Complexity (cs.CC) #FOS: Computer and information sciences #FOS: Physical sciences #Quantum Gases (cond-mat.quant-gas) #Quantum Physics (quant-ph) #Statistical Mechanics (cond-mat.stat-mech)
paper · doi:10.48550/arxiv.2404.19005
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 [[2D , 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 evidence that sampling from hypercube IQP circuits is classically hard to simulate and analyze the linear cross-entropy benchmark (XEB) in comparison to the average fidelity. 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(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 realistic hardware.