Robust sparse IQP sampling in constant depth

• DOI: 10.22331/q-2024-05-06-1337
• Publication Date: 2024-05-06T14:25:22Z
• Authors: Louis Paletta; Anthony Leverrier; Alain Sarlette; Mazyar Mirrahimi; Christophe Vuillot
• Keywords: Constant (computer programming); Quantum circuit

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