p-Bit Invertible Logic Looks Past Ground States: Learned Hamiltonians Cut a 77-Bit Multiplier to 0.46 of Hand-Written Updates
Synopsis
Probabilistic-bit invertible logic encodes a Boolean circuit as an energy and samples it to compute in any direction, but conventional encodings only enforce legal ground states and widen the minimum gap, while finite-time samplers spend their runs in excited states. This work casts Hamiltonian design as inverse statistical mechanics, fitting interactions up to fourth order by constrained maximum likelihood under a gap floor so that the Gibbs law approaches uniformity on each clamp case's legal states. On 44- to 77-bit multipliers in factor mode, the learned energies cut updates to 99% verified success to 0.55, 0.44, 0.52 and 0.46 of the hand-written encoding across nine tuned samplers, at the cost of more terms evaluated per update.
Interpretation
A Hamiltonian for invertible logic can be designed around its finite-temperature probability distribution, not only around which states are ground states. Hand-written encodings follow Ising-reduction and quantum-annealing conventions, enforcing legal ground states and widening the minimum gap to illegal states, while a finite-time trajectory spends its run among excited states. On 44- to 77-bit multipliers in factor mode, the learned energies cut updates to 99% verified success to 0.55 [0.45, 0.65], 0.44 [0.37, 0.47], 0.52 [0.38, 0.66] and 0.46 [0.38, 0.56] of the hand-written encoding across nine tuned samplers, surviving at every width.
The fit writes the energy as a polynomial over the circuit's spins and aims to spread each clamp case's Gibbs law as evenly as possible over its legal assignments. The objective is the Kullback-Leibler divergence between a uniform law on the legal set and the Gibbs law, a convex negative log-likelihood on a fixed candidate pool, solved by a logarithmic barrier Newton method with cutting planes, then pruned by coefficient magnitude and refitted. Every delivered structure is audited exactly over all clamp cases, and the 77-bit multiplier covers 4,647 factor and 16,384 multiply cases with a minimum case gap of 0.00470627, 79 parts per million above its floor.
Perspective
The demonstrated scope is factor mode on 44- to 77-bit multipliers and reverse mode on 8- to 32-bit adders, all evaluated under nine equally tuned samplers and reproduced bit-exactly against the software reference on a Kria KR260 FPGA with a single-replica color-sweep hard-threshold SSA core.
On the 77-bit multiplier, SA-M is unresolved at its tuning-selected length, where the learned tuning median rests on one success in 32 trials; in determined modes the hand-written encoding uses less work, and forward addition needs fewer updates from 12 bits upward; the multiplier series ends at 77 bits, with the planned 88-bit point not run.