The quantum mechanical state vector is a complicated object. In particular, the amount of data that must be given in order to specify the state vector (even approximately) increases exponentially with the number of quantum systems. Does this mean that the universe is, in some sense, exponentially complicated? I argue that the answer is yes, if the state vector is a one-to-one description of some part of physical reality. This is the case according to both the Everett and Bohm interpretations. But another possibility is that the state vector merely represents information about an underlying reality. In this case, the exponential complexity of the state vector is no more disturbing that that of a classical probability distribution: specifying a probability distribution over N variables also requires an amount of data that is exponential in N. This leaves the following question: does there exist an interpretation of quantum theory such that (i) the state vector merely represents information and (ii) the underlying reality is simple to describe (i.e., not exponential)? Adapting recent results in communication complexity, I will show that the answer is no. Just as any realist interpretation of quantum theory must be non-locally-causal (by Bell's theorem), any realist interpretation must describe an exponentially complicated reality.