Shallow quantum circuits for deeper problems