I don't think that's quite true. The product state has exponential size so you'd also need some kind of tensor oracle that could manipulate an exponential quantity of information in linear time.
It's true that the product state is exponential in size. That's why the size of the quadratic matrix SU(N) matrix is N = 2^M, where M is the number of qubits. To my knowledge that's the only thing that is exponential there.