  We investigate the sign problem for full configuration interaction quantum
Monte Carlo (FCIQMC), a stochastic algorithm for finding the ground state
solution of the Schr\"odinger equation with substantially reduced computational
cost compared with exact diagonalisation. We find $k$-space Hubbard models for
which the solution is yielded with storage that grows sub-linearly in the size
of the many-body Hilbert space, in spite of using a wave function that is
simply linear combination of states. The FCIQMC algorithm is able to find this
sub-linear scaling regime without bias and with only a choice of Hamiltonian
basis. By means of a demonstration we solve for the energy of a 70-site
half-filled system (with a space of $10^{38}$ determinants) in 250 core hours,
substantially quicker than the $\sim$10$^{36}$ core hours that would be
required by exact diagonalisation. This is the largest space that has been
sampled in an unbiased fashion. The challenge for the recently-developed FCIQMC
method is made clear: expand the sub-linear scaling regime whilst retaining
exact on average accuracy. This result rationalizes the success of the
initiator adaptation (i-FCIQMC) and offers clues to improve it. We argue that
our results changes the landscape for development of FCIQMC and related
methods.
