API Reference

backend(model)::AbstractModel
backend(model::AbstractModel)::AbstractModel

Accesses the model's backend. Implementing this function allows one to profit from fallback implementations of other methods.

index(model::AbstractModel{V}, v::V) where {V}

Given a variable, returns the corresponding index.

indices(model)

Returns a sorted vector $[1, \dots, n]$ that matches the variable indices, where $n$ is the model's dimension.

hasindex(model::AbstractModel, i::Integer)::Bool

Given an index, returns whether it is valid for rhe model.

variable(model::AbstractModel, i::Integer)

Given an index, returns the corresponding variable.

variables(model)

Returns a sorted vector containing the model's variables.

hasvariable(model::AbstractModel{V}, v::V)::Bool where {V}

Given a variable, tells if it belongs to the model.

VariableMap{V}

Establishes a bijection between variables and their indices. The interface for accessing this mapping relies on QUBOTools.index and QUBOTools.variable.

varlt(u::V, v::V) where {V}

Compares two variables, $u$ and $v$, with respect to their length-lexicographic order.

Rationale

This function exists to define an arbitrary ordering for a given type and was created to address ^[MOI]. There is no predefined comparison between instances MOI's VariableIndex type.

[^MOI]: MathOptInterface Issue [#1985](https://github.com/jump-dev/MathOptInterface.jl/issues/1985)

Domain

Enum representing binary variable domains, BoolDomain and SpinDomain.

BoolDomain

Represents the boolean domain $\mathbb{B} = \lbrace{0, 1}\rbrace$.

Properties

\[x \in \mathbb{B}, n \in \mathbb{N} \implies x^{n} = x\]

SpinDomain

Represents the spin domain $\mathbb{S} = \lbrace{-1, 1}\rbrace$.

Properties

\[s \in \mathbb{S}, n \in \mathbb{Z} \implies s^{2n} = 1, s^{2n + 1} = s\]

domain(model::AbstractModel)

Returns the variable domain of a given model.

Sense

Enum representing the minimization and maximization objective senses, Min and Max.

sense(model)

Returns the objective sense of a model.

Frame(sense::Sense, domain::Domain)

frame(model)

Recasting the sense of a model preserves its meaning but the linear terms, quadratic terms and constant offset of a model will have its signs reversed, so does the overall objective function.

\[\begin{array}{ll} \min_{s} \alpha [f(s) + \beta] &\equiv \max_{s} -\alpha [f(s) + \beta] \\ &\equiv \max_{s} \alpha [-f(s) - \beta] \\ \end{array}\]

CastingError

Error while casting data between domains or senses.

AbstractModel{V,T,U}

Represents an abstract QUBO Model.

As shown in the example above, implementing a method for the QUBOTools.backend function gives access to most fallback implementations.

Model{V,T,U,F<:AbstractForm{T}} <: AbstractModel{V,T,U}

Reference AbstractModel implementation. It is intended to be the stardard in-memory representation for QUBO models.

MathOptInterface/JuMP Integration

Both V and T parameters exist to support MathOptInterface/JuMP integration. This is made possible by choosing V to match MOI.VariableIndex and T as in Optimizer{T}.

AbstractForm{T}

A form is a $7$-tuple $(n, \ell, Q, \alpha, \beta) \times (\textrm{sense}, \textrm{domain})$ representing a QUBO / Ising model.

• $n$, the dimension, is the number of variables.
• $\mathbf{\ell}$, the linear form, represents a vector storing the linear terms.
• $\mathbf{Q}$, the quadratic form, represents an upper triangular matrix containing the quadratic interactions.
• $\alpha$ is the scale factor, defaults to $1$.
• $\beta$ is the offset factor, defaults to $0$.

The inner data structures used to represent each of these elements may vary.

AbstractLinearForm{T}

Linear form subtypes will create a wrapper around data structures for representing the linear terms $\mathbf{\ell}'\mathbf{x}$ of the QUBO model.

AbstractQuadraticForm{T}

Quadratic form subtypes will create a wrapper around data structures for representing the quadratic terms $\mathbf{x}'\mathbf{Q}\,\mathbf{x}$ of the QUBO model.

form(src [, formtype::Type{<:AbstractForm{T}}]; sense, domain) where {T}
form(src [, formtype::Union{Symbol,Type}, T::Type = Float64]; sense, domain)

Returns the QUBO form stored within src, casting it to the corresponding (sense, domain) frame and, if necessary, converting the coefficients to type T.

The underlying data structure is given by formtype. Current options include :dict, :dense and :sparse.

For more informaion, see QUBOTools.Form and QUBOTools.AbstractForm.

linear_form(Φ::F) where {T,F<:AbstractForm{T}}

Returns the linear part of the QUBO form.

quadratic_form(Φ::F) where {T,F<:AbstractForm{T}}

Returns the quadratic part of the QUBO form.

qubo(args; kws...)

This function is a shorthand for form(args...; kws..., domain = :bool).

For more informaion, see QUBOTools.form.

ising(args; kws...)

This function is a shorthand for form(args...; kws..., domain = :spin).

For more informaion, see QUBOTools.form.

Form{T,LF,LQ}

formtype(spec::Type)
formtype(spec::Symbol)

Returns a form type according to the given specification.

formtype(src)

Returns the form type of a form or model.

DictForm{T}

This QUBO form is built using dictionaries for both the linear and quadratic terms.

DictLinearForm{T}

DictQuadraticForm{T}

DenseForm{T}

This QUBO form is built using a vector for the linear terms and a matrix for storing the quadratic terms.

DenseLinearForm{T}

DenseQuadraticForm{T}

SparseForm{T}

This QUBO form is built using a sparse vector for the linear terms and a sparse matrix for the quadratic ones.

SparseLinearForm{T}

SparseQuadraticForm{T}

State

AbstractSample

A sample is a triple $(\psi, \lambda, r)$ where $\psi \in \mathbb{U}^{n} \sim \mathbb{B}^{n}$ is the sampled vector, $\lambda \in \mathbb{R}$ is the associated energy value and $r \in \mathbb{N}$ is the number of reads, i. e., the multiplicity of the sample.

Sample{T,U}(state::Vector{U}, value::T, reads::Integer = 1) where{T,U}

This is the reference implementation for QUBOTools.AbstractSample.

sample(model, i::Integer)

Returns the $i$-th sample on the model's current solution, if available.

hassample(solution::AbstractSolution, i::Integer)

Tells if the $i$-th sample is available on the solution.

AbstractSolution

By definitioon, a solution is an ordered set of samples.

See QUBOTools.AbstractSample.

SampleSet{T,U}(
    data::Vector{Sample{T,U}},
    metadata::Union{Dict{String,Any},Nothing} = nothing;
    sense::Union{Sense,Symbol}   = :min,
    domain::Union{Domain,Symbol} = :bool,
) where {T,U}

Reference implementation of QUBOTools.AbstractSolution.

It was inspired by D-Wave's SampleSet^[dwave], with a few tweaks. For example, samples are automatically sorted upon instantiation and repeated samples are merged by adding up their reads field. Also, the solution frame is stored, allowing for queries and cast operations.

solution(model) where {T,U<:Integer}

Returns the model's current solution.

state(sample::AbstractSample{T,U}) where {T,U<:Integer}

Returns a vector containing the assingment of each variable in a sample.

state(model, i::Integer) where {U<:Integer}

Returns a vector corresponding to the bitstring of the $i$-th sample on the model's current solution, if available.

value(model)::T where {T}

value(model, i::Integer)::T where {T}
value(solution::AbstractSolution{T,U}, i::Integer)::T where {T,U}

value(model, state::AbstractVector{U}) where {U<:Integer}
value(solution::AbstractSolution{T,U}, state::AbstractVector{U})::T where {T,U<:Integer}

value(Q::Dict{Tuple{Int,Int},T}, ψ::Vector{U}, α::T = one(T), β::T = zero(T)) where {T}
value(h::Dict{Int,T}, J::Dict{Tuple{Int,Int},T}, ψ::Vector{U}, α::T = one(T), β::T = zero(T)) where {T}

energy

An alias for value.

reads(model)
reads(solution::AbstractSolution)

Returns the total amount of reads from each sample, combined.

reads(model, i::Integer)
reads(solution::AbstractSolution, i::Integer)

Returns the sampling frequency of the $i$-th sample on the model's current solution, if available.

SolutionError

Error occurred while gathering solutions.

linear_terms(model::AbstractModel{V,T,U}) where {V,T,U}

Returns an iterator for the linear nonzero terms of a model as Int => T pairs.

quadratic_terms(model::AbstractModel{V,T,U}) where {V,T,U}

Returns an iterator for the quadratic nonzero terms of a model as Tuple{Int,Int} => T pairs.

scale(model::AbstractModel)
scale(model::AbstractForm)

Returns the scaling factor of a model.

offset(model::AbstractModel)
offset(model::AbstractForm)

Returns the constant offset factor of a model.

data(form)
data(sol::AbstractSolution)

Retrieves the raw data behind solution and form wrappers.

metadata(model::AbstractModel)
metadata(sol::AbstractSolution)

Retrieves metadata from a model or solution as a JSON-compatible Dict{String,Any}.

id(model)

Returns a model identifier as an Int or nothing.

description(model)

Returns the model description as a String or nothing.

start(model::AbstractModel{V,T,U}; domain = domain(model))::Dict{Int,U} where {V,T,U}

Returns a dictionary containing a warm-start value for each variable index.

attach!(model::AbstractModel{V,T,U}, sol::AbstractSolution{T,U}) where {V,T,U}

Attaches solution to model, replacing existing data and solution metadata. It automatically casts the solution to the model frame upon attachment.

AbstractFormat

format(::AbstractString)::AbstractFormat
format(::Symbol)::AbstractFormat
format(::Symbol, ::Symbol)::AbstractFormat

Given the file path, tries to infer the type associated to a QUBO model format.

version(fmt::AbstractFormat)

Returns the version of a format protocol as a VersionNumber or nothing.

read_model(::AbstractString)
read_model(::AbstractString, ::AbstractFormat)
read_model(::IO, ::AbstractFormat)

write_model(::AbstractString, ::AbstractModel)
write_model(::AbstractString, ::AbstractModel, ::AbstractFormat)
write_model(::IO, ::AbstractModel, ::AbstractFormat)

read_solution(::AbstractString)
read_solution(::AbstractString, ::AbstractFormat)
read_solution(::IO, ::AbstractFormat)

write_solution(::AbstractString, ::AbstractSolution)
write_solution(::AbstractString, ::AbstractSolution, ::AbstractFormat)
write_solution(::IO, ::AbstractSolution, ::AbstractFormat)

FormatError

Error related to the format specification.

SyntaxError

Syntax error while parsing file.

dimension(model)::Integer

Counts the total number of variables in the model.

linear_size(model)

Counts the number of non-zero linear terms in the model.

quadratic_size(model)

Counts the number of non-zero quadratic terms in the model.

density(model)::Float64

Computes the density $\rho$ of non-zero terms in a model, according to the expression^[qplib]

\[\rho = \frac{n_{\ell} + 2 n_{q}}{n^{2}}\]

where $n_{\ell}$ is the number of non-zero linear terms, $n_{q}$ the number of quadratic ones and $n$ the number of variables.

If the model is empty, returns NaN.

linear_density(model)::Float64

Computes the linear density $\rho_{\ell}$, given by

\[\rho_{\ell} = \frac{n_{\ell}}{n}\]

where $n_{\ell}$ is the number of non-zero linear terms and $n$ the number of variables.

quadratic_density(model)::Float64

Computes the quadratic density $\rho_{q}$, given by

\[\rho_{q} = \frac{2 n_{q}}{n (n - 1)}\]

where $n_{q}$ is the number of non-zero quadratic terms and $n$ the number of variables.

topology(model)

Returns a Graphs.jl-compatible graph representing the quadratic interactions between variables in the model.

adjacency(model)

An alias for topology.

geometry

Returns a $n \times N$ matrix describing the placement of the $n$ variable sites in $N$-dimensional space.

AbstractArchitecture

GenericArchitecture()

This type is used to reach fallback implementations for AbstractArchitecture.

architecture(::Any)

It should be defined to provide automatic architecture recognition when writing QUBO Solver interfaces.

Example

struct Solver
    ...
end

struct SolverArchitecture <: AbstractArchitecture
    ...
end

architecture(::Solver) = SolverArchitecture()

AbstractDevice{A<:AbstractArchitecture,V,T,U} <: AbstractModel{V,T,U}

A device instance is meant to represent an specific hardware or software device. It is the concrete implementation of an architecture. For example, the topology of a device must be contained within the ideal topology of its architecture.

GenericDevice

A thin wrapper around a Model that fulfills the AbstractDevice interface.

Layout

layout(::Any)
layout(::Any, ::G) where {G<:AbstractGraph}

Returns the layout of a model, device architecture, i.e., a description of the geometrical placement of each site as long as the network of their connections.

AbstractProType{T}

generate(problem)
generate(rng, problem)

Generates a QUBO problem and returns it as a Model.

SherringtonKirkpatrick{T}(n::Integer, μ::T, σ::T)

Generates a Sherrington-Kirkpatrick model in $n$ variables. Coefficients are normally distributed with mean $\mu$ and variance $\sigma$.

Wishart{T}(n::Integer, m::Integer)

Represents the Wishart model on $n$ variables whose $\mathbf{W}$ matrix has $m$ columns.

When true, the discretize keyword limits the entries of the $\mathbf{R}$ matrix to $\pm 1$. The precision, on the other hand, is the amount of digits to round each entry $R_{i,j}$ after sampling from a normal distribution $\mathcal{N}(0, 1)$.

total_time(sol::AbstractSolution)

Retrieves the total time spent during the whole solution gathering process, as experienced by the user.

effective_time(sol::AbstractSolution)

Retrieves the time spent by the algorithm in the strict sense, that is, excluding time spent with data access, precompilation and other activities. That said, it is assumed that $t_{\text{effective}} \le t_{\text{total}}$.

success_rate(sol::AbstractSolution{T}, λ::T) where {T}

Returns the success rate according to the given solution and the target objective value $\lambda$.

time_to_target(sol::AbstractSolution{T}, λ::T, s::Float64=0.99) where {T}

Computes the time-to-target (TTT) given the solution and the target threshold $\lambda$. The success factor $s$ defaults to $0.99$.

time_to_target(t::Float64, p::Float64, s::Float64=0.99)

Computes the time-to-target (TTT) given the effective time $t$ spent running the algorithm and the success probability $p$. The success factor $s$ defaults to $0.99$.

\[\text{ttt}(t, p; s) = t \frac{\log(1 - s)}{\log(1 - p)}\]

ttt

Alias for time_to_target.

hamming_distance(x::Vector{U}, y::Vector{U}) where {U}
hamming_distance(x::Sample{T,U}, y::Sample{T,U}) where {T,U}

AbstractVisualization

Represents a conceptual visualization built from a set of data structures. Its realization may combine multiple plot recipes as well.

Examples

Model Density Heatmap

julia> using Plots

julia> p = QUBOTools.ModelDensityPlot(model)

julia> plot(p)

Solution Energy vs. Frequency

julia> using Plots

julia> s = QUBOTools.solution(model)

julia> p = QUBOTools.EnergyFrequencyPlot(s)

julia> plot(p)

or simply,

julia> using Plots

julia> p = QUBOTools.EnergyFrequencyPlot(model)

julia> plot(p)