BEIT’s Quest for QUBOs

BEIT has been in the business of solving Quadratic Unconstrained Binary Optimization (QUBO) problems since 2018. Our solutions are all available on the Amazon Web Services marketplace link.

• Our first product was an exact solver, patented in 2019, released in 2022, which can get exact solutions to small QUBOs. A free demo version can be found on our website.
• Our second product was a quantum-inspired annealer, released in 2022, which can get good approximate solutions to large QUBOs.
• Our newest product is an exact multi-sampler, which can perfectly and efficiently give large samples of the Boltzman distribution associated with a small QUBO.

Why do we care so much about QUBOs?

A big reason is that they’re a domain where quantum computers are fighting for advantage. QUBOs can be naturally re-formulated in a physics language, where the optimization problem becomes the task of finding lowest energy states in an “Ising model” system. Finding the lowest energy states is what nature does best: cool something down and it’ll become low energy. Strategically performing this cooling to reach your desired solution can be done with adiabatic quantum computation.

Adiabatic quantum computation is the most direct way of using quantum systems to perform possibly-useful computations. It was first pioneered successfully by Canadian quantum computing company D-WAVE, whose adiabatic quantum computer can purportedly solve many QUBOs with quantum advantage. However, advantage can be difficult to hold onto once it’s obtained:

[Quantum advantage] is a moving target, due to the ever-increasing capabilities of classical computers

One of BEIT’s company missions is to be a target-mover. When somebody claims quantum advantage, we like to push classical algorithms to the limit to see if we can do better.

As with most battlegrounds, quantum advantage for QUBOs is case dependent. For small instances, there’s no reason to use an adiabatic process: our exact solver works perfectly. Current quantum computers yield approximations which are rarely exactly correct.

For larger cases, we run into one of quantum processing’s key issues: “fully connectedness” vs. “topological constraint”. The physical connections on a quantum chip limit what QUBOs can be solved. Namely, the QUBO’s interactions have to follow the “topology” of the chip. This means large highly-connected QUBOs are difficult to run on quantum computers. You’ll have to use a classical annealer like ours in those cases.

Embedding QUBOs with few connections onto a quantum chip can still be hard. This cuts to one of the core issues with QUBOs: embedding. It’s a well-known theorem that almost every hard problem can be made into a QUBO. In computer science lingo, QUBOs are “NP-hard”. The issue is re-stating your problem as a QUBO efficiently. This is especially true when there are topological constraints to worry about.

At BEIT, we pride ourselves on making easily interfaceable software. Not only is our annealer fully connected, but we also work with clients to help phrase their problems in terms of QUBOs. For tasks which cannot be efficiently stated with QUBOs, our annealing software is adaptable on a client-wise basis. For instance, our annealer has been used for quantum circuit optimization as well as for rederiving state-of-the-art combinatorial results.

Preliminary reviews from users all show very positive sentiments. We’re now working in various directions, such as putting our software on high-performance ASIC chips, and anticipate many more great products to come.

Cheers to an exciting future!