Quantum Circuits Solve Complex Problems with Physics

Moe Shimada and colleagues at Tokyo University of Agriculture and Technology have developed extraction-type majority voting logic (E-MVL), which mimics thermal spin dynamics to efficiently search for solutions. E-MVL consistently explores the solution space, achieving better performance than simulated annealing (SA), and solves exact solutions for problems with up to 1600 spins, exceeding SA’s 400-spin limit. The team’s insights also led to improvements in SA’s temperature scheduling and a roughly six-fold increase in solution speed when implemented on a field-programmable gate array, establishing E-MVL as a strong optimiser and a method for boosting SA performance.

Extraction-type majority voting logic surpasses simulated annealing in solving large-scale spin

The Sherrington-Kirkpatrick (SK) model has now been solved with up to 1600 spins using extraction-type majority voting logic (E-MVL), a significant leap beyond the 400-spin limit of the best simulated annealing (SA) baselines. This advance tackles complex combinatorial optimisation problems previously intractable due to exponential computational demands. E-MVL, a quantum-inspired algorithm utilising digital logic circuits, achieves this through a ‘sparsity control mechanism’ that consistently searches the solution space, independent of the problem’s characteristics.

A field-programmable gate array implementation of E-MVL is approximately six-fold faster than SA, suggesting potential for practical hardware applications. Detailed analysis of equilibrium states revealed the ‘sparsity control mechanism’ consistently navigates the solution space whether the problem employs bimodal or Gaussian coupling distributions. This consistency is notable because standard simulated annealing (SA) often struggles with Gaussian distributions, a common feature of real-world optimisation challenges. Furthermore, insights derived from E-MVL directly informed improvements to SA’s temperature scheduling, boosting its performance and demonstrating a synergistic benefit beyond direct competition.

Sparsity control mechanisms emulate annealing for combinatorial optimisation

Extraction-type majority voting logic (E-MVL) digitally mimics simulated annealing, a technique for finding optimal solutions by gradually reducing randomness, similar to cooling metal. Instead of probabilistic temperature adjustments, E-MVL employs a ‘sparsity control mechanism’ to selectively weaken connections between interacting elements, known as ‘spins’. This controlled sparsification allows the algorithm to focus its search on the most promising areas of the solution space, analogous to carefully pruning branches to reveal the lowest energy state. The algorithm successfully found exact solutions for problems involving up to 1600 spins, sharply exceeding the 400-spin limit of the best simulated annealing baselines tested.

E-MVL algorithm excels at the Sherrington-Kirkpatrick model but faces generalisation challenges

Researchers has developed a new algorithm, extraction-type majority voting logic (E-MVL), capable of solving extraordinarily complex optimisation problems. However, the focus on the Sherrington-Kirkpatrick model raises a key question regarding its broader applicability. While E-MVL consistently outperforms simulated annealing (SA) on this benchmark, the authors acknowledge that generalising these results to other ‘NP-hard’ problems remains unproven, limiting immediate real-world impact.

This work demonstrates that extraction-type majority voting logic, or E-MVL, consistently navigates complex problem spaces irrespective of their specific characteristics, establishing a new approach to combinatorial optimisation. By mimicking thermal processes digitally, E-MVL solved instances of the Sherrington-Kirkpatrick model containing up to 1600 ‘spins’, exceeding the capabilities of simulated annealing, a conventional optimisation technique. This success expands the scale of solvable problems and offers a methodology for improving existing algorithms; insights from E-MVL directly enhanced the performance of simulated annealing’s temperature scheduling.

E-MVL successfully solved complex optimisation problems involving up to 1600 spins, outperforming simulated annealing which was limited to 400 spins. This demonstrates the algorithm’s ability to efficiently search for solutions within challenging problem spaces, regardless of the specific distribution of the problem’s parameters. The research also provides a method for improving the performance of simulated annealing through optimised temperature scheduling. The authors suggest this work establishes E-MVL as both an effective optimiser and a tool for enhancing existing techniques.