Robust sparse IQP sampling in constant depth

Abstract

Between NISQ (noisy intermediate scale quantum) approaches without any proof of robust quantum advantage and fully fault-tolerant quantum computation, we propose a scheme to achieve a provable superpolynomial quantum advantage (under some widely accepted complexity conjectures) that is robust to noise with minimal error correction requirements. We choose a class of sampling problems with commuting gates known as sparse IQP (Instantaneous Quantum Polynomial-time) circuits and we ensure its fault-tolerant implementation by introducing the tetrahelix code. This new code is obtained by merging several tetrahedral codes (3D color codes) and has the following properties: each sparse IQP gate admits a transversal implementation, and the depth of the logical circuit can be traded for its width. Combining those, we obtain a depth-1 implementation of any sparse IQP circuit up to the preparation of encoded states. This comes at the cost of a space overhead which is only polylogarithmic in the width of the original circuit. We furthermore show that the state preparation can also be performed in constant depth with a single step of feed-forward from classical computation. Our construction thus exhibits a robust superpolynomial quantum advantage for a sampling problem implemented on a constant depth circuit with a single round of measurement and feed-forward.

References in corpus (10)

• Logical quantum processor based on reconfigurable atom arrays
• Topological Quantum Distillation
• Restrictions on Transversal Encoded Quantum Gate Sets
• Classical simulation of commuting quantum computations implies collapse of the polynomial hierarchy
• Topological Computation without Braiding
• Exact Topological Quantum Order in D=3 and Beyond: Branyons and Brane-Net Condensates
• Universal transversal gates with color codes - a simplified approach
• A polynomial-time classical algorithm for noisy random circuit sampling
• Limitations of Linear Cross-Entropy as a Measure for Quantum Advantage
• Fault-tolerant quantum speedup from constant depth quantum circuits

Cited by in corpus (5)

• Logical quantum processor based on reconfigurable atom arrays
• Quantum computational advantage with constant-temperature Gibbs sampling
• Unconditionally separating noisy ${\mathsf{QNC}}^0$ from bounded polynomial threshold circuits of constant depth
• Performance analysis of a filtering variational quantum algorithm
• Color code with a logical control-$S$ gate using transversal $T$ rotations