Modifications to quantum mechanics have been proposed as potential solutions to the black hole information paradox. In particular, Maldecena and Horowitz have proposed a final-state projection model in which the black hole singularity constitutes a boundary to spacetime with an associated boundary condition for the wavefunction. This proposal has gained renewed interest in light of the AMPS "firewalls" argument. We examine the computational and information-theoretic implications of small deviations from unitarity that can arise in this model. We find that any nonunitarity allows signalling over arbitrary spacelike intervals, with channel capacity determined by the condition number of the black hole S-matrix. Furthermore, Grover search can be sped up using the nonunitary dynamics, but polynomial-time solution for exponential search problems implies a 1/polynomial channel capacity for instantaneous signaling. Thus, within this context, we find that the no-signaling principle implies the Grover search lower bound, and allowing exponential small deviations from no-signaling allows only exponentially small improvements to Grover search.