An optimization device comprising: a plurality of calculation circuits, each of which calculates, for a plurality of bits corresponding to a plurality of spins included in an Ising model obtained by converting a problem to be calculated, in a case where the plurality of bits is divided into a plurality of groups, on the basis of a first local field value for a first bit having a value of 1 and a second local field value for a second bit having a value of 0 among a plurality of bits included in each of the plurality of groups, a first energy change of the Ising model due to a change of the value of the first bit from 1 to 0 and a change of the value of the second bit from 0 to 1; a selection circuit that outputs first bit identification information for identifying one of a plurality of the second bits that allows update of the value from 0 to 1 among the second bits included in each of the plurality of groups, on the basis of a magnitude relationship between the first energy change output by each of the plurality of calculation circuits and thermal excitation energy determined on the basis of an input temperature parameter and a random number; an identification information calculation unit that detects a first group to which the second bit allowed to be updated belongs on the basis of the first bit identification information output by the selection circuit, and outputs second bit identification information for identifying the first bit that belongs to the first group; an update unit that updates the value from 1 to 0 of the first bit that belongs to the first group on the basis of the second bit identification information output by the identification information calculation unit, and updates the value from 0 to 1 of the second bit allowed to be updated on the basis of the first bit identification information; a second storage unit that holds all rows corresponding to bit identification information for identifying a bit having a value of 1 in a matrix of weight values that indicate a magnitude of interaction between each of the plurality of bits held by a first storage unit, in each of the plurality of groups; and a local field generation unit that generates the first local field value and the second local field value, respectively on the basis of a first row corresponding to the first bit identification information read from the first storage unit on the basis of the first bit identification information output by the selection circuit and a second row corresponding to the second bit identification information read from the second storage unit. a plurality of calculation circuits, each of which calculates, for a plurality of bits corresponding to a plurality of spins included in an Ising model obtained by converting a problem to be calculated, in a case where the plurality of bits is divided into a plurality of groups, on the basis of a first local field value for a first bit having a value of 1 and a second local field value for a second bit having a value of 0 among a plurality of bits included in each of the plurality of groups, a first energy change of the Ising model due to a change of the value of the first bit from 1 to 0 and a change of the value of the second bit from 0 to 1; a selection circuit that outputs first bit identification information for identifying one of a plurality of the second bits that allows update of the value from 0 to 1 among the second bits included in each of the plurality of groups, on the basis of a magnitude relationship between the first energy change output by each of the plurality of calculation circuits and thermal excitation energy determined on the basis of an input temperature parameter and a random number; an identification information calculation unit that detects a first group to which the second bit allowed to be updated belongs on the basis of the first bit identification information output by the selection circuit, and outputs second bit identification information for identifying the first bit that belongs to the first group; an update unit that updates the value from 1 to 0 of the first bit that belongs to the first group on the basis of the second bit identification information output by the identification information calculation unit, and updates the value from 0 to 1 of the second bit allowed to be updated on the basis of the first bit identification information; a second storage unit that holds all rows corresponding to bit identification information for identifying a bit having a value of 1 in a matrix of weight values that indicate a magnitude of interaction between each of the plurality of bits held by a first storage unit, in each of the plurality of groups; and a local field generation unit that generates the first local field value and the second local field value, respectively on the basis of a first row corresponding to the first bit identification information read from the first storage unit on the basis of the first bit identification information output by the selection circuit and a second row corresponding to the second bit identification information read from the second storage unit.