By adding chaotic sequences to a neural network that solves combinatorial optimization problems, its performance improves much better than the case that random number sequences are added. It was already shown in a previous study that a specific autocorrelation of the chaotic noise makes a positive effect on its high performance. Autocorrelation of such an effective chaotic noise takes a negative value at lag 1, and decreases with dumped oscillation as the lag increases. In this paper, we generate a stochastic noise whose autocorrelation is C(tau) approximate to C x (-r)(tau), similar to effective chaotic noise, and evaluate the performance of the neural network with such stochastic noise. First, we show that an appropriate amplitude value of the additive noise changes depending on the negative autocorrelation parameter r. We also show that the performance with negative autocorrelation noise is better than those with the white Gaussian noise and positive autocorrelation noise, and almost the same as that of the chaotic noise. Based on such results, it can be considered that high solvable performance of the additive chaotic noise is due to its negative autocorrelation.