On the power of geometrically-local classical and quantum circuits

Understand

We show a relation, based on parallel repetition of the Magic Square game, that can be solved, with probability exponentially close to $1$ (worst-case input), by $1D$ (uniform) depth $2$, geometrically-local, noisy (noise below a threshold), fan-in $4$, quantum circuits.

• We show that the same relation cannot be solved, with an exponentially small success probability (averaged over inputs drawn uniformly), by $1D$ (non-uniform) geometrically-local, sub-linear depth, classical circuits consisting of fan-in $2$ NAND gates.
• Quantum and classical circuits are allowed to use input-independent (geometrically-non-local) resource states, that is entanglement and randomness respectively.
• To the best of our knowledge, previous best (analogous) depth separation for a task between quantum and classical circuits was constant v/s sub-logarithmic, although for general (geometrically non-local) circuits.