  We show that families of Instantaneous Quantum Polynomial (IQP) circuits
corresponding to nontrivial Bell tests exhibit nonlocality. However, we also
prove that this nonlocality can only be demonstrated using post-selection or
nonlinear processing of the measurement outcomes. Therefore if the output of a
computation is encoded in the parity of the measurement outcomes, then families
of IQP circuits whose full output distributions are hard to sample still only
provide a computational advantage relative to locally causal theories under
post-selection. Consequently, post-selection is a crucial technique for
obtaining a computational advantage for IQP circuits (with respect to decision
problems) and for demonstrating nonlocality within IQP circuits, suggesting a
strong link between these phenomena.
