  The task of logic synthesis is to map a technology-independent representation
of an application to hardware-specific operations, taking into account various
constraints and trading off different costs associated with the implementation.
Constraints may include the target gate library and feasible connectivity,
whereas the costs capture, for example, the required chip area and delay. Here
we propose to use parallel tempering Monte Carlo to find low-level
implementations of a given Boolean function. In contrast to previous work
leveraging Markov chain Monte Carlo methods such as simulated annealing, we do
not start with an initially correct (but suboptimal) implementation that is
then further optimized. Instead, our approach starts with a random logic
network that is subsequently modified in order to reduce the error to zero. We
apply our method to the task of synthesizing Majority-$n$ in terms of
Majority-$3$ gates with and without inverters, aiming for a low Majority-$3$
count. Our method is able to find solutions that are on par or better than
previously known solutions. For example, for $n\in\{9,11,13\}$ our approach
successfully finds inverter-free implementations using between 7% and 42% fewer
Majority-$3$ gates.
