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 (29)

• Quantum Computing in the NISQ era and beyond
• Good Quantum Error-Correcting Codes Exist
• Logical quantum processor based on reconfigurable atom arrays
• Topological Quantum Distillation
• How to factor 2048 bit RSA integers in 8 hours using 20 million noisy qubits
• Surface code quantum computing by lattice surgery
• Restrictions on Transversal Encoded Quantum Gate Sets
• A Game of Surface Codes: Large-Scale Quantum Computing with Lattice Surgery
• 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
• Topological Computation without Braiding
• What limits the simulation of quantum computers?
• Achieving quantum supremacy with sparse and noisy commuting quantum computations
• Quantum Sampling Problems, BosonSampling and Quantum Supremacy
• Instantaneous Quantum Computation
• Single-shot fault-tolerant quantum error correction
• Efficient classical simulation of random shallow 2D quantum circuits
• Quantum advantage with noisy shallow circuits in 3D
• Exact Topological Quantum Order in D=3 and Beyond: Branyons and Brane-Net Condensates
• Universal transversal gates with color codes - a simplified approach
• Quantum Circuits with Unbounded Fan-out
• Triangular color codes on trivalent graphs with flag qubits
• The cost of universality: A comparative study of the overhead of state distillation and code switching with color codes
• A polynomial-time classical algorithm for noisy random circuit sampling
• Quantum Commuting Circuits and Complexity of Ising Partition Functions
• Limitations of Linear Cross-Entropy as a Measure for Quantum Advantage
• Efficient color code decoders in $d\ge 2$ dimensions from toric code decoders
• 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