A 2048-spin bulk acoustic wave Ising machine for number partitioning and Sudoku
AuthorsVenkatesh Vadde, Roman Ovcharov, Victor H. González, Roman Khymyn, Artem Litvinenko, Johan Åkerman
Resources
This paper builds a 2,048-spin acoustic Ising machine that uses sound waves in solid-state delay lines to tackle hard optimization problems like MAX-CUT and Sudoku.
Key results
Active spins used in the BAWIM architecture
MHz center frequency of each quartz BAW delay line
µs circulation time per bulk acoustic wave delay line
ms to reach 90% of the best heated-ballistic simulated bifurcation energy
ms projected with a 16.455 GHz delay line
W total power draw of the current BAWIM implementation
What the paper found
This paper from the University of Gothenburg, with collaborators at Oakland University and Tohoku University, introduces a bulk acoustic wave Ising machine, or BAWIM, that replaces optical time-multiplexing with propagating RF pulse packets in quartz delay lines. The system uses two serially connected 20.5 MHz delay lines with 707 µs circulation time each, supporting 2048 active spins out of 2124 available pulse slots and all-to-all couplings at 15-bit resolution. In MAX-CUT tests on BiqMac graphs, the machine reaches 90% of the best heated-ballistic simulated bifurcation result in 341 ms, while a projected 16.455 GHz delay line could reduce this to 0.462 ms; across problem densities from 10% to 100%, it preserves up to 99.99% of the best simulated-bifurcation score. The authors then extend the same hardware to number partitioning and Sudoku, showing that BAWIM outperforms the same simulated bifurcation baseline on both tasks and can solve a 9×9 Sudoku encoded with 729 spins, even when near-ground-state Ising energy does not imply a valid puzzle solution. The platform is also positioned as far more practical than coherent Ising machines, with room-temperature operation, no post-selection, and about four orders of magnitude better thermal stability, while drawing 9.57 W in the current implementation.
Original abstract
Optical coherent Ising machines based on time-multiplexing have demonstrated significant progress in terms of connectivity and spin scalability. However, they are constrained by large physical footprints, high power consumption, poor thermal stability, and high cost. Here, we present a time-multiplexed Ising machine leveraging propagating wave packets in solid-state delay lines at microwave frequencies, enabling thermally stable, robust, low-power, tabletop, and affordable design. We use two serially connected 20.5 MHz, 707 μs bulk acoustic wave delay lines supporting 2,048 spins. Our design provides all-to-all connectivity with 15-bit coupling resolution and finds approximate MAX-CUT solutions in 341 ms, potentially scalable to sub-ms by using higher frequency delay lines. Additionally, we demonstrate solutions to number partitioning and Sudoku problems. Compared with state-of-the-art Coherent Ising machines, our machine exhibits four orders of magnitude higher thermal stability. Against the simulated bifurcation algorithm, our design achieves comparable results on the MAX-CUT problem, while outperforming it on the more complex number-partitioning and Sudoku problems.
Read the original paperMore in Optimization
Browse all 36 papers →An $Ω(κ_y^8ε^{-6})$ Lower Bound for Stochastic NC-SC Bilevel Optimization with First-order Oracles
Zhihao Gu, Qilong Wu, Junchi Yang
This work proves that stochastic bilevel optimization fundamentally requires up to epsilon^{-6} oracle queries, showing existing methods are asymptotically optimal.
Hyper Algorithm Design Agent: Evolving Learnable Optimizer from Zero
Zipei Yu, Yue-Jiao Gong, Zeyuan Ma, Yuncheng Jiang, Zhiguang Cao
A pair of self-improving coding agents evolves new learnable optimization algorithms from a simple template, reducing the need for handcrafted optimizer design.
Tight Regret Bound for Online Inverse Linear Optimization via Multiscale Matrix Weights
Shinsaku Sakaue
A new multiscale matrix-weights algorithm learns hidden linear preferences online with provably optimal dimension-dependent regret.