TenSolver.jl

Tensor Network-based solver for Quadratic Unconstrained Binary Optimization (QUBO) problems.

$$\begin{array}{rl} \min_x & x' Q x \\ \text{s.t.} & x \in \mathbb{B}^{n} \end{array}$$

Installation

This package is currently not registered. Install it directly from the git url:

using Pkg

Pkg.add(url="https://github.com/SECQUOIA/TenSolver.jl.git")

Usage

The simplest way to use this package is passing a matrix to the solver

using TenSolver

Q = randn(40, 40)

E, psi = TenSolver.minimize(Q)

The returned argument E is the calculated estimate for the minimum value, while psi is a probability distribution over all possible solutions to the problem. You can sample Boolean vectors from it. These vectors are the (approximate) optimal solutions to the original optimization problem.

x = TenSolver.sample(psi)

JuMP interface

Alternatively, we also provide an Optimizer for solving QUBOs described as JuMP models.

using JuMP, TenSolver

dim = 40
Q   = randn(dim, dim)

begin
  m = Model(TenSolver.Optimizer) # <-- The important line
  @variable(m, x[1:dim], Bin)
  @objective(m, Min, x'Q*x)

  optimize!(m)                   # <-- Equivalent to running TenSolver.minimize(Q)
end

Running on GPU

The solver uses the tensor networks machinery from ITensors.jl which comes with GPU support for tensor contractions.

To run the code in a GPU, all you have to do is passing the appropriate accelerator as a keyword to the solver. For example, the code below optimizes the QUBO using CUDA.jl.

using TenSolver
import CUDA: cu

Q = randn(4, 4)

E, psi = minimize(Q; device = CUDA.cu)

Since ITensor's GPU platform support is always improving, be sure to check out their documentation to know which GPUs are accepted.