InfinityQ builds the World’s largest functioning Ising Machine and it's ready for industry applications, today.
20th October 2023, Montreal
ABSTRACT
Imagine being able to solve billion-parameter optimization problems with hundreds of thousands of variables in a matter of seconds. There are more possible solutions to these problems than there are atoms in the universe.
Too good to be true? Think again…
This is exactly what the research team at InfinityQ Technology Inc. (InfinityQ) is doing immediately with off the shelf commodity hardware. Leveraging the power of quantum theory, clever mappings, and intelligent hardware design, the research team at InfinityQ can have their cake and eat it too – breakneck solution speeds usually associated with quantum computing without the cryo-lab and scalability issues that come with supporting true quantum hardware.
This Quantum Alternative approach has enabled the InfinityQ team to build the largest functional Ising Machine to date at 112,000 binary variables, and achieve state-of-the-art solve speed. To top it all off, the cost to run is a fraction of any other similar solver making this technology ready for industry applications now.
BACKGROUND
In today’s world, data driven decisions make all the difference. While AI, ML, and Data Science have grown in capability to solve business problems, there are some problems for which they are not well suited. One such problem is combinatorial optimization. This is the problem where there exist large numbers of decision variables, all dependent on the values of the other variables. Computational complexity of this grows exponentially as the number of variables increases, putting these problems in the complexity class of NP-Hard, where no polynomial time solution exists.
Effectively, this means that the time to solve such problems on traditional computing hardware is impractical at best, taking hours if not days for even modest sized problems. However, these types of combinatorial optimization problems are used every day in various domains such as logistics, pharmaceuticals, finance, and astrophysics research.
In efforts to solve these problems in an efficient manner, a new paradigm of computing has arisen. This paradigm is based on an architecture called the Ising Model, a computational model based on statistical physics. Using a probabilistic extension of the Ising Model called the Restricted Boltzmann Machine (RBM), with methods developed through research from CTO Saavan Patel and Prof. Sayeef Salahuddin at UC Berkeley, the sampling of Ising Model energy states could be efficiently parallelized allowing convergence to a “ground state”, or globally optimized solution.
This Quantum Alternative model of computation uses many of the same underlying principles as pure quantum computation, namely the probabilistic nature of physical systems and interactions between particles. We map this model onto our hardware using our proprietary algorithms and methods to achieve state of the art performance in solving large combinatorial optimization problems.
The types of combinatorial optimization problems that the Ising Model solves are Quadratic Unconstrained Binary Optimization (QUBO) problems. Various problems map well to this encoding such as the traveling salesman problem, set assignment problem, quadratic assignment problem, and many others. One particularly difficult problem that has been studied by researchers at various cutting-edge research labs is the MAX-CUT problem. The MAX-CUT problem consists of partitioning a graph into two complimentary sets. This problem is heavily utilized in academic and industry research as it provides a well-defined benchmark of performance for NP-Hard combinatorial optimization solvers.
There have been many proposed methods to solve such problems, from quantum to quantum-inspired, to purely classical. Some notable past examples include the Hopfield Neural Network (HNN) heuristic which mimics brain-like behavior and Simulated Annealing (SA) which mimics cooling of material systems. Recently there have been further solvers and hardware implementations by Fujitsu Digital Annealer (DA), Toshiba Simulated Bifurcation (SB), Hitachi Momentum Annealing (MA), and D-Wave Quantum Annealer (D-Wave).
Each of these systems has differing underlying hardware and operates at various scales. InfinityQ’s research team builds off work done by the company’s CTO, Saavan Patel while at the University of California, Berkeley. Table 1 below summarizes the topologies of these various company and research groups' Ising solvers.
RESULTS
Of the research labs developing these solutions, there are varying levels of performance and scalability. Performance can be quantified in two ways, 1) time to solution and 2) solution quality. As all methods are non-deterministic, the results of the solvers have natural variance and none find a “true” ground state. Instead, heuristic methods are used such as running a well-documented algorithm to obtain a “target” solution of known good quality to compare against. Scalability is defined in terms of the number of binary variables or “nodes” which the model can compute on at a time.
Toshiba leads the pack in time to solution as well as solution quality using their proprietary Simulated Bifurcation algorithm and GPU-based hardware. Toshiba also supports extra-large-scale problems of up to 100,000 variables, the largest prior to InfinityQ’s work. Hitachi, while very fast computing a solution and supporting of extra-large-scale problems, lacks the result quality demonstrated by other labs. Fujitsu and their ASIC, while ultra-fast, does not support problems at any level of competitive scale, instead limited at 8192 variables. Finally, D-Wave, while generating excitement on their approach, is very limited to the number of binary variables supported and the quality of results, only supporting 5000 variables with a restricted connectivity architecture.
The prior research done at Berkeley, while able to support extra-large- scale problems, was notably slower to compute a solution. InfinityQ has built upon the base RBM developed at Berkeley to support extra- large-scale problems and achieve comparable solution quality and computation time to Toshiba.
The plot below shows the relative performance of the best-in-class solvers on a problem named the M100000. This specific problem definition has been used by various researchers in literature to benchmark their technology due to its incredibly complex nature. It is a MAX-CUT instance of a fully connected Ising Model with 100,000 variables, translating to approximately 5 billion parameters. Fully generated, the problem takes 40GB of memory.
This means that only solvers supporting extra-large-scale problems can hope to compute a solution. Memory and computational steps at this scale must be highly efficient to minimize these very expensive memory accesses and resulting latency bottleneck.
The resulting performance of Toshiba’s R&D efforts is quite substantial; their operating costs, however, are equally substantial. In order to run their model, 8 GPUs were used, racking up the total cost to solve the problem to a whopping $85,312 – for the accelerator cards alone! Toshiba also redesigned their own Simulated Annealing algorithm (SA) and ran this on a PC cluster to compare against their hardware accelerated results. This also came with a significant price tag of roughly $21,000. While the researchers at Berkeley were much more economical, the solve time and solution quality were notably less performant as seen in the plot above.
InfinityQ’s Nickel Solver proved to be the best of both worlds, providing excellent solution performance without breaking the bank. Only using $6,000 worth of hardware compared to Toshiba’s $85,000 to run, with only a slight performance decrease, InfinityQ is able to deliver high quality results for unthinkably massive optimization problems in seconds.
It is worth noting that for most practical applications, 98% solution convergence is more than sufficient, which was achieved by the team at InfinityQ in just 2.98 seconds.
We have had many questions from potential customers about comparison to Gurobi, a general optimization solver. While Gurobi, has touted their Gurobi Optimizer as the “world's fastest solver”, our results beg to differ. When comparing InfinityQ’s Nickel Solver to Gurobi on a 10,000 node, all connected Max-CUT problem, InfinityQ’s Nickel is >300x faster and produces solutions of better quality than Gurobi. With Gurobi’s Optimizer stopping at an Ising energy of -737622, it was unable to find a solution of comparable quality to InfinityQ, at -749284, even when given an hour of computation time.
On average, InfinityQ’s solver is 325x faster and supports extra-large-scale problems of hundreds of thousands of variables, while Gurobi does not.
Supporting the largest-to-date Ising Machine at 112,000 nodes, translating into ~6.3 billion parameters, InfinityQ’s research team is redefining what is possible. From reducing the cost to operate, achieving state-of-the-art runtimes, and providing outstanding solution quality, InfinityQ’s Nickel solver is ready to be deployed, in the cloud or on premises, to solve the most challenging computational and optimizations problems of any industry.
FUTURE WORK
The research lab at InfinityQ is just getting started. Since the beginning of the year, we have recruited top research talent from leading research groups internationally, and are rapidly growing. Stay tuned for more breakthroughs in Quantum Alternative computing.
Want to learn more? Contact sales@infinityq.tech to book a demo.
REFERENCES
Patel, S., Chen, L., Canoza, P. & Salahuddin, S. Ising model optimization problems on a fpga accelerated restricted boltzmann machine. arXiv preprint arXiv:2008.04436 (2020).
Hayato Goto et al., Combinatorial optimization by simulating adiabatic bifurcations in nonlinear Hamiltonian systems. Sci. Adv.5,eaav2372(2019).
Okuyama, T., Sonobe, T., Kawarabayashi, K.-i. & Yamaoka, M. Binary optimization by mo-mentum annealing. Physical Review E 100, 012111 (2019).
Aramon, M. et al. Physics-inspired optimization for quadratic unconstrained problems using a digital annealer. Frontiers in Physics 7, 48 (2019).
ABOUT THE AUTHORS
Kevin Jordan - Kevin is an early career researcher and GPU specialist, and has been the lead developer of InfinityQ’s Nickel solver. Kevin’s background includes research at University of California, Berkeley in the Berkeley SETI Research Center, advancing data processing infrastructure of radio telescope signals via GPU in the search for extraterrestrial intelligence. He has also conducted research at NASA Ames Research Center in planetary rover mission data synthesis and visualization platforms, and worked as a systems engineer integrating a state-of-the-art satellite constellation at MDA. Scientific computing and hardware accelerated solutions are what drive and excite him.
Saavan Patel, PhD - Saavan is currently the Chief Technology Officer at InfinityQ Technologies. Prior to InfinityQ, he was a PhD Candidate at University of California, Berkeley where he completed his studies under Professor Sayeef Salahuddin, working on developing accelerated solutions to optimization problems using quantum-inspired methods. He also spent time at Meta Reality Labs, working on Machine Learning hardware for next generation VR systems. His interests are broadly in optimization, quantum computation, machine learning, and hardware design.