BQM with quadratic zero terms
Hi,
I found out that the EmbeddingComposite for BQMs with zero values for quadratic terms uses more physical qubits than necessary.
BinaryQuadraticModel({'x_0': 76.53, 'x_1': -66.4, 'x_2': 0.0, 'x_3': -100.0, 'x_4': 42.93}, {('x_1', 'x_0'): 132.8, ('x_2', 'x_0'): -200.0, ('x_2', 'x_1'): 0.0, ('x_3', 'x_0'): 0.0, ('x_3', 'x_1'): 0.0, ('x_3', 'x_2'): 200.0, ('x_4', 'x_0'): -85.86, ('x_4', 'x_1'): 0.0, ('x_4', 'x_2'): 0.0, ('x_4', 'x_3'): 0.0}, 0.0, 'BINARY')
This one will use 6 physical qubits (on pegasus).
Reducing the dict to only non-zero entries:
({'x_0': 76.53, 'x_1': -66.4, 'x_2': 0.0, 'x_3': -100.0, 'x_4': 42.93}, {('x_1', 'x_0'): 132.8, ('x_2', 'x_0'): -200.0, ('x_3', 'x_2'): 200.0, ('x_4', 'x_0'): -85.86}, 0.0, 'BINARY')
is the same problem but only uses 5 qubits
Here is a little experiment:
For fully connected cases(sparity=0) nothing can be done, but for sparse problems (sparsity=1 -> for n agents and n-1 edges) the reduction in physical qubits used is more than 50%
I think this should be automatically handled by the embedding
Best regards
Daniel
Comments
Hello,
Thank you for getting involved with the community and for your feedback!
All h and J terms are zero by default, so you are correct, leaving zero valued terms out of the problem formulation does reduce the complexity of the problem, and therefore the complexity of the embedding.
We do intentionally allow for these terms to be added explicitly, so that it is possible to reliably do so in some way. We would advise excluding zero-valued terms from your input, as it makes the distinction of zero and non-zero terms less arbitrary, more intentional, and as you've stated will simplify the embeddings produced. As a side note, it might be more efficient to check upstream in place of adding and removing the values.
Hopefully this helps shed some light on the design decision. Please feel free to reach out with more questions.
Please sign in to leave a comment.