BEIT Qubo Solver is a SaaS product that allows for solving instances of the Quadratic Unconstrained Binary Optimisation problem known as QUBO. We offer python SDK compatible with D-WAVE dimod package as well as low-level API access.
QUBO problem is formally defined as follows. Given $M \in \mathbb R^{n \times n}$ a matrix of coefficients find binary vector $v \in \lbrace 0, 1\rbrace^n$ minimizing expression $v^T M v$. From the graph theory perspective this can be thought as the task of finding the minimal weighted induced subgraph of the graph (with loops) with weighted adjacency matrix $M$.
Currently, we offer two distinct modes of operation: more restrictive but exact solver and fully-connected, heuristic sampler.
Our solver accepts instances embedded into Chimera architecture of maximum size $8 \times 16$ units, where each unit contains 8, totaling 1024 qubits. The instance is not automatically embedded, so variable labels must be integers and are interpreted according to the numbering provided in the link above. Coefficients $M_{ij}$ must be integers with values satisfying $-31 \leq M_{ij} \leq 31$.
Solver will return an optimal solution. If more than one optimal solution exists solver will return one of them.
To use our solver please use BEITSolver class from the SDK.
Size of the instance provided to the solver is defined as the largest used variable index. Solving is billed on pay-per-request basis, cost may in future depend on the size of requests. Please refer to the Pricing section for details.
In general instances of size smaller than 512 are much quicker to solve then the larger ones.
Sampler accepts instances with an arbitrary topology and by the means of simulated annealing will generate a list of possible solutions. To generate low energy solutions, longer computation may be required. This setting can be adjusted via API. There are a few technical constraints for the instance provided, namely:
To run our sampler please use BEITUnconstrainedSampler class from the SDK.
The cost of a request depends solely on the computation time. Please refer to the Pricing section for details. There is no size-based cost, but more computation time may be required for finding adequate solutions to larger instances.
There are several parameters impacting execution that can be specified
timeout: Number of seconds the computation will runsample_count: Number of samples returned. Solver may return fewer samples in case of a very small instance or when the execution time was too short.| Request type | Price |
|---|---|
| Exact solution | 30¢ / request |
| Heuristic sampling | 30¢ for each 100s started |
SDK consists of three classes
class AWSSolverConnection(SolverConnection):
def __init__(self, customer_key: str):
"""
Creates a connection to AWS api. Customer key is granted
upon registration and should be kept secret.
"""
QuboInstance = Mapping[Tuple[Hashable, Hashable], Union[float, np.floating, np.integer]]
class BEITSolver(dimod.Sampler, dimod.Structured):
"""
This is an exact solver for QUBO. It works only with
chimera architecture (max size being (8, 16, 4))
"""
def __init__(self, solver_connection: SolverConnection):
"""
Creates new BEITSolver instance out of the solver connection.
"""
@property
def edgelist(self) -> List[Tuple[Hashable, Hashable]]:
"""
Returns list of edges allowed by chimera architecture.
"""
@property
def nodelist(self) -> List[Hashable]:
"""
Returns list of vertices allowed by chimera architecture.
"""
def sample_qubo(self, qubo_instance: QuboInstance, **parameters):
"""
Solves given QUBO instance exactly.
"""
class BEITUnconstrainedSampler(dimod.Sampler):
def __init__(self, solver_connection: SolverConnection):
"""
Creates new BEITUnconstrainedSampler instance out of the solver connection.
"""
@property
def parameters(self) -> Dict[str, Any]:
return {
"timeout": [],
"sample_count": ["Number of samples returned, returned value can differ from requested."],
}
@property
def properties(self) -> Dict[str, Any]:
return {
"max_timeout": 60 * 12, # 12 minutes
"max_combined_sample_size": [10 ** 6, "Number of variables times number of samples can not exceed this number."]
"weights_range": [10 ** 6, "Maximum absolute value for any single weight (biases and couplers)"],
"max_num_weights": [5000, "Maximum number of weights in a problem (biases and couplers)"],
}
def sample_qubo(self, qubo_instance: QuboInstance, sample_count: int = 1, **parameters):
"""
Samples from the space of possible solutions of the qubo_instance by the means of simulated annealing.
"""
Our SDK is available in pypi under the name beit-qubo-solver. You can grab it with pip via
pip install beit-qubo-solver
Before executing any code via our SDK, one needs to register via AWS marketplace and obtain a customer key. For basic usage just initialize AWSSolverConnection with your customer key and then create BEITSolver instance using aforementioned connection. Example code:
from beit.qubo_solver.solver_connection import AWSSolverConnection
from beit.qubo_solver.beit_solver import BEITSolver
connection = AWSSolverConnection("PUT-HERE-YOUR-CUSTOMER-KEY")
solver = BEITSolver(connection)
solver.sample_qubo({(0, 0) : 1, (4, 4) : 1, (0, 4): -4})
Sampler can be used in a similar manner, but have few parameters that can be adjusted. Example usage can be seen below:
from beit.qubo_solver.solver_connection import AWSSolverConnection
from beit.qubo_solver.beit_solver import BEITUnconstrainedSampler
connection = AWSSolverConnection("PUT-HERE-YOUR-CUSTOMER-KEY")
solver = BEITUnconstrainedSampler(connection)
solver.sample_qubo(
{(0, 0) : 1, (4, 4) : 1, (0, 4): -4},
sample_count=2,
timeout=10,
)
It may take a few minutes for a request to complete. During that time SDK polls for the result, so do not cancel the process lest you lose your results.
In case of technical problems, please contact us via mail at qubo-solver@beit.tech.