State-of-the-art of binary encoding in a Digital Annealer of an Ising Machine
Recently, I have been investigating about the best performace of the binary-integer encodings of an Ising Machine. Comparying three of the typical encoding ways, one-hot, binary and unary encodings, the conclusion is that the unary is the best option. Is there any other way to encode integers or real values that would improve the performace in an Ising Machine? How does an Ising Machine currently encode inequality constrains (2023)?
Thanks in advance.
Comments
Hello,
Thank you for reaching out to us and for your interest in our D-Wave Systems.
We can offer some insight into encoding problems directly onto the QPU, but for the CQM or other HSS Solvers we can't offer any information due to their proprietary nature.
Could you please give a little clarification regarding your question?
You mentioned three types of encoding: binary, one-hot, and unary.
This paper seems to use the three terms you had mentioned:
https://ieeexplore.ieee.org/stamp/stamp.jsp?tp=&arnumber=9435359
Is this the definition of these terms you're referring to?
If you haven't had a chance to look at this paper, it is a great resource and very insightful.
Please take a look at it and see what you think!
These two papers provide instance where the one-hot encoding provides the best results:
https://arxiv.org/abs/2102.12224
https://arxiv.org/abs/2108.12004
Please let us know if you have any questions.
Hi David, thank you for your detailed answer!
I have read the first paper and, as you mentioned, the unary encoding seems to be the best option compared with the binary and one-hot.
However, for the last two papers the domain-wall encoding is the one which presents the best performance...
My apologies. I have updated my last post to reflect that the two papers were referencing the one-hot approach, rather than the unary encoding.
At present research results are mixed as far as which is the best approach. This may also prove to be a situation where the best approach is problem dependent. For anyone looking for an active area of research, this would be a good area to delve into.
Hi David,
Maybe it is a confusion on my part, but I still click on the two last papers and they bring me to one-hot Vs. domain-wall encodings, nothing about the unary.
If I have understood correctly, with 'results are mixed' you mean that sometimes unary and sometimes domain-wall will appear as the best encoding option, as it will depend on the specific problem in question.
With reference to this, does the models DQM and CQM just implement one-hot codification? (As far as I have seen in the documentation) Isn't there any way to implement other codifications?
Does every model ultimately have to be transformed/translated into BQM?
Thanks for your time.
Hello,
That's right, sometimes the unary encoding is best, sometimes the one-hto encoding is best, etc. It depends on the specific problem.
Apologies for the confusion in the previous post. I was trying to give an example where one-hot was a better encoding, whereas the paper we had referenced before was pointing to the unary encoding as the best encoding for those problems.
All implementation of the HSS Solvers (BQM/DQM/CQM) is proprietary, so we can't comment on this.
That said, all implementations run on a given QPU will be formulated as Quantum Machine Instructions (QMI), which take into consideration that QPU's architecture. So you can think of problems being encoded as BQMs with a given structure.
See the introduction docs for more information about how problems are run on the QPU and see our topology docs for more information about the various structures of our QPUs. Embedding does abstract away QPU-specific topology, so generally the idea is to formulate the problem as a BQM.
Please sign in to leave a comment.