Spherical Cubes: Optimal Foams from Computational Hardness Amplification