Quantum Algorithms for OPI Variants Beyond Locality and Classical Decodability
A quantum-classical separation for Reed-Muller codes punctured at random points is proved, and an efficient classical algorithm under a stronger three-fold multiplication property is given, leaving intermediate regimes as candidates for quantum advantage.