Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

DQM definition could be clarified #114

Closed
jackraymond opened this issue Jan 27, 2021 · 1 comment · Fixed by #115
Closed

DQM definition could be clarified #114

jackraymond opened this issue Jan 27, 2021 · 1 comment · Fixed by #115

Comments

@jackraymond
Copy link

jackraymond commented Jan 27, 2021

Description
I think the definition of DQM might be clarified. It is not made clear (enough) what is the variable space, and what (if any) are the constraints.
The current definition is here:
https://docs.ocean.dwavesys.com/en/stable/concepts/dqm.html
I make a suggestion below, but it may create other issues. On balance, I believe presenting both polynomials will allow people to make a clearer connection between their problems, and BQMs.

Beginning from:
"... each with 𝑛𝑖 cases." A discrete quadratic model may be defined as
H(d) = \sum_{i} a(d_i) + \sum_{i,j} b_{ij}(d_i,d_j) + c (-1-)
where a() and b() are real valued functions.

We can represent any DQM by an equivalent model over binary variables, each discrete state d_i may be replaced by a vector of binary variables using one hot encoding, where exactly one binary variable is True (value 1) and all others are False (0). A discrete quadratic model is then defined by
AS CURRENTLY WRITTEN (-2-)
subject to one hot constraints \sum_a x_{i,a} = 1 \forall i.
Representations (1) and (2) are equivalent over the feasible space meeting the one hot encoding constraints. Representation (2) ascribes energies both to the feasible space satisfying constraints, and an infeasible space violating constraints. Representation (2) is used by ocean SDK.

To Reproduce
Documentation issue

Expected behavior
Definitions of BQM and DQM should follow similar patterns. Specification of the model, specification of the variable space, specification of constraints. This might be applied to future model classifications as well.

Environment:

  • OS: [Ubuntu 16.04.4 LTS]
  • Python version: [e.g. 3.7.0]

Additional context
Add any other context about the problem here.

@mcfarljm
Copy link
Contributor

This makes sense to me, and I like the new representation (1), as it is simpler and seems more intuitive. It might even make sense to just replace the current representation with this new one, as opposed to keeping them both.

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Labels
None yet
Projects
None yet
Development

Successfully merging a pull request may close this issue.

2 participants