Authors: Brian Mao [Head of Algorithms], Ethan Wang [Mathematical Algorithms Developer] & Saavan Patel PhD [Chief Technology Officer]: InfinityQ Technology
Introduction
TitanQ is a quantum-inspired solver that can be utilized to solve many different optimization problems that arise in the real world.
To help understand how this new platform works in comparison to other commercially available solvers, we have benchmarked the TitanQ platform against other quantum and quantum-inspired solvers.
This post provides benchmarks regarding its performance across several quadratic unconstrained binary optimization (QUBO) problems.
While solving QUBO problems is important, we believe this is just the beginning for quantum and quantum-inspired methods.
The performance of TitanQ is compared against four different quantum-inspired solvers specialized for QUBO problems:
D-Wave Hybrid Solver Service (HSS) [HSS hybrid BQM solver version 2.0 accessed via Leap Cloud].
Toshiba Simulated Bifurcation Machine (SBM)[Version 1.5.1].
Fujitsu Digital Annealer (DA)[fujitsuDA2PT solver accessed via DA Center Japan].
Simulated Annealing (SA) [Using D-Wave neal version 0.5.7].
                             Â
The instances investigated throughout the benchmarks include the SAT-UNSAT phase transition point of random not-all-equal 3-SAT (NAE 3-SAT), the Ising spin glass Sherrington-Kirkpatrick (SK) model, and real problems from MQLib.
The performance from the 4 competitors listed above are all gathered from Oshiyama & Ohzeki (2022).
The paper also provides a more detailed explanation regarding each of the problem types within each of the instances benchmarked for further information.
Â
Problem Types
Many different real-world combinatorial optimization problems can be mapped to QUBO models, which are NP-hard. In a QUBO problem, the objective is to minimize a quadratic cost function of the form:
with binary variables
In total, 45 different instances are analyzed and are broken down into the following 9 categories based on relative size and density:
The exact instance files are all available from hss-overview-benchmarks.
Â
Benchmark Results
Throughout all of the benchmarks, each solver was run for 300 seconds (5 minutes).
The current solution after this entire runtime for each solver was recorded as the final solution for that particular solver.
The best-known solution is defined as the best solution found from the other 4 competitors after the entire 5 minutes of runtime.
The following table highlights the 12 different instances in which TitanQ either matched or outperformed all of the other solvers from DWAVE, Toshiba, and Fujitsu:
The full results across all 45 instances are available within the PDF:
The general performance of TitanQ is quite competitive with each of the other solvers across all 45 instances.
The bar chart below summarizes these results where the optimality is calculated as the calculated cost from TitanQ divided by the best-known solution across the other 4 solvers:
All of the final solutions generated from TitanQ are within at least 99% of the best-known solution across all 45 instances.
In addition, 21 out of the 45 instances are within 99.9% of the best-known solution.
Finally, 12 instances are at 100.0% or beyond the best solutions discovered by the solvers from DWAVE, Toshiba, and Fujitsu after 5 minutes of solve time.
It is worth noting that these 12 instances incorporate small, medium, and large instance sizes as well as both sparse and dense problems.
In particular, the TitanQ solver was able to match or improve upon some of the largest instances, including the largest 10,000 variable challenge problem.
This shows that TitanQ is a flexible platform to solve problems across various problem sizes and systems.
Â
Results Replication
Each result presented throughout this post from TitanQ can also be easily re-verified by any reader with the following Jupyter notebook:Â
The only required specifications from the user to generate results are the following:
Instance Name
Number of Runs
TitanQ API Key
File Path where Instances are Stored
Â
Conclusion
The TitanQ platform gave results within 99% of optimal on all of the presented instances, while matching or exceeding the best-known result on 12 of the 45 problems.
This is an exciting development showing that the TitanQ platform is state-of-the-art.
While QUBO problems are important in many real-world applications, the TitanQ platform goes beyond native QUBO formulations to solve native formulations of many hard problems on its platform.
We believe this creates enhanced usefulness in settings beyond QUBO as shown below:
Contact sales@infinityq.tech for access to a TitanQ API Key.
Note that free licenses are available for academic researchers and start-ups.
Â
About the Authors
Brian Mao, MMath
Brian is the Head of Algorithms at InfinityQ Technology Inc. with a background in both mechanical engineering and applied mathematics.
Prior to InfinityQ, he was the Path Planning and Controls Lead at MIT Driverless where he led multiple sub-teams to program a racecar to drive fully autonomously at over 240 km/h.
He also worked at Apple Inc. under the Metal Tooling team where he developed an internal iOS app and created simulations of various manufacturing processes.
Brian continues to pursue the intersection between engineering and mathematics through solving many different mathematical optimization problems at InfinityQ.
Â
Ethan Wang
Ethan is a Mathematical Algorithms Developer on the Algorithms team at InfinityQ Technology Inc.
He is currently pursuing an undergraduate major in mathematical finance and a minor in pure math and statistics at the University of Waterloo.
Before InfinityQ, Ethan worked as a software developer at BMO where he led the integration of an audit service that aimed to enhance observability of internal data pipelines.
Despite his work history in software development, his true passion lies in mathematics and problem solving. Ethan’s mathematical expertise and interest in quantitative finance pushes InfinityQ to explore new areas of application.
Â
Saavan Patel, PhD
Saavan is the Chief Technology Officer at InfinityQ Technology Inc.
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.