Fault-tolerant compiling of classically hard IQP circuits on hypercubes

Abstract

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 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(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.

28 + 20 pages, 13 Figures, v2: generalized analytical results to degree D, extended discussion

References in corpus (86)

• Supplementary information for "Quantum supremacy using a programmable superconducting processor"
• Universal Quantum Computation with ideal Clifford gates and noisy ancillas
• Improved Simulation of Stabilizer Circuits
• Characterizing Quantum Supremacy in Near-Term Devices
• Logical quantum processor based on reconfigurable atom arrays
• Elucidating Reaction Mechanisms on Quantum Computers
• A simple formula for the average gate fidelity of a quantum dynamical operation
• How to factor 2048 bit RSA integers in 8 hours using 20 million noisy qubits
• Noise tailoring for scalable quantum computation via randomized compiling
• High-fidelity parallel entangling gates on a neutral atom quantum computer
• Direct Fidelity Estimation from Few Pauli Measurements
• Simulating quantum computation by contracting tensor networks
• Restrictions on Transversal Encoded Quantum Gate Sets
• High-threshold and low-overhead fault-tolerant quantum memory
• A fault-tolerant one-way quantum computer
• Stim: a fast stabilizer circuit simulator
• Repeated Quantum Error Detection in a Surface Code
• Improved classical simulation of quantum circuits dominated by Clifford gates
• Demonstration of fault-tolerant universal quantum gate operations
• Classical simulation of commuting quantum computations implies collapse of the polynomial hierarchy
• Average-case complexity versus approximate simulation of commuting quantum computations
• Quantum Supremacy and the Complexity of Random Circuit Sampling
• Simulation of quantum circuits by low-rank stabilizer decompositions
• Emergent statistical mechanics of entanglement in random unitary circuits
• Characterizing large-scale quantum computers via cycle benchmarking
• Universal fault-tolerant quantum computation with only transversal gates and error correction
• Two-dimensional transport and transfer of a single atomic qubit in optical tweezers
• Achieving quantum supremacy with sparse and noisy commuting quantum computations
• A detailed study of Gaussian Boson Sampling
• Instantaneous Quantum Computation
• Quantum Hypergraph States
• Fault-tolerant conversion between the Steane and Reed-Muller quantum codes
• Randomized Benchmarking with Confidence
• Preparing random states and benchmarking with many-body quantum chaos
• Single-shot fault-tolerant quantum error correction
• Computational advantage of quantum random sampling
• Solving the sampling problem of the Sycamore quantum circuits
• Unfolding the color code
• Quantum advantage with noisy shallow circuits in 3D
• Universal transversal gates with color codes - a simplified approach
• Efficient estimation of Pauli channels
• Quantum Computational Advantage via High-Dimensional Gaussian Boson Sampling
• Encoding a magic state with beyond break-even fidelity
• Phase transition in Random Circuit Sampling
• Fault-tolerant error correction with the gauge color code
• Architectures for quantum simulation showing a quantum speedup
• Hierarchy of universal entanglement in 2D measurement-based quantum computation
• High Fidelity Single-qubit Gates of a Single Neutral Atom in the Magic-Intensity Optical Dipole Trap
• Diagonal gates in the Clifford hierarchy
• Three-dimensional surface codes: Transversal gates and fault-tolerant architectures
• How many qubits are needed for quantum computational supremacy?
• Dispersive optical systems for scalable Raman driving of hyperfine qubits
• Efficient Verification of Hypergraph States
• Entanglement and nonclassical properties of hypergraph states
• Hamiltonian Simulation Algorithms for Near-Term Quantum Hardware
• Verified measurement-based quantum computing with hypergraph states
• Benchmarking highly entangled states on a 60-atom analog quantum simulator
• Scalable Architecture for Quantum Information Processing with Atoms in Optical Micro-Structures
• On Optimality of CSS Codes for Transversal $T$
• Tropical Tensor Network for Ground States of Spin Glasses
• Tight bounds on the convergence of noisy random circuits to the uniform distribution
• From estimation of quantum probabilities to simulation of quantum circuits
• The disjointness of stabilizer codes and limitations on fault-tolerant logical gates
• Sample complexity of device-independently certified "quantum supremacy"
• Semi-Clifford operations, structure of ${\mathcal{C}}_k$ hierarchy, and gate complexity for fault-tolerant quantum computation
• Limitations of Linear Cross-Entropy as a Measure for Quantum Advantage
• Changing the circuit-depth complexity of measurement-based quantum computation with hypergraph states
• Benchmarking Quantum Simulators using Ergodic Quantum Dynamics
• Computing solution space properties of combinatorial optimization problems via generic tensor networks
• Verifying commuting quantum computations via fidelity estimation of weighted graph states
• Efficient color code decoders in $d\ge 2$ dimensions from toric code decoders
• Bell sampling from quantum circuits
• How to simulate quantum measurement without computing marginals
• Local unitary symmetries of hypergraph states
• A Family of Quantum Codes with Exotic Transversal Gates
• Learning time-dependent noise to reduce logical errors: Real time error rate estimation in quantum error correction
• Pauli channels can be estimated from syndrome measurements in quantum error correction
• Deterministic Fast Scrambling with Neutral Atom Arrays
• Learning logical Pauli noise in quantum error correction
• A graphical calculus for integration over random diagonal unitary matrices
• On Groups in the Qubit Clifford Hierarchy
• Fault-tolerant quantum speedup from constant depth quantum circuits
• Efficient diagnostics for quantum error correction
• Permutation-Invariant Quantum Codes with Transversal Generalized Phase Gates
• Polynomial-Time Classical Simulation of Noisy IQP Circuits with Constant Depth
• Onset of scrambling as a dynamical transition in tunable-range quantum circuits

Cited by in corpus (1)

• Gibbs Sampling gives Quantum Advantage at Constant Temperatures with O(1)-Local Hamiltonians