dimod.higherorder.utils.make_quadratic gives inconsistent / incorrect results

[Spider2themax]

Description D-Wave has indicated at least two approaches for reducing higher order terms to quadratic, namely Reduction by Substitution and Reduction by Minimum Selection. Both of these are shown to be mathematically correct approaches.

The issue is with the make_quadratic function. The function has at least one clear bug, which is that it returns completely different results if vartype = 'BINARY' or dimod.BINARY, which according to the vartype documentation those should both be identical.

For the trivial example case higher order polynomial: poly = {(0, 1, 2): 10}

If vartype = dimod.BINARY, we get the following output: BinaryQuadraticModel({0: 0.0, 1: 0.0, '0*1': 3.0, 2: 0}, {(0, 1): 1.0, (0, '0*1'): -2.0, (1, '0*1'): -2.0, ('0*1', 2): 10}, 0.0, Vartype.BINARY) This is exactly what you would expect if we were using the Reduction by Substitution approach. However, if vartype='BINARY', we get the following output: BinaryQuadraticModel({0: -5.0, 1: -5.0, '0*1': -5.0, 'aux0,1': -8.0, 2: 0}, {(0, 1): 2.0, (0, '0*1'): 2.0, (0, 'aux0,1'): 4.0, (1, '0*1'): 2.0, (1, 'aux0,1'): 4.0, ('0*1', 'aux0,1'): 4.0, ('0*1', 2): 10}, 9.0, Vartype.BINARY) Steps To Reproduce

import dimod

poly = {(0, 1, 2): 10}
bqm = dimod.make_quadratic(poly, 1.0, 'SPIN')
print(bqm)
print('\n')
bqm = dimod.make_quadratic(poly, 1.0, 'BINARY')
print(bqm)
print('\n')
bqm = dimod.make_quadratic(poly, 1.0, dimod.SPIN)
print(bqm)
print('\n')
bqm = dimod.make_quadratic(poly, 1.0, dimod.BINARY)
print(bqm)
print('\n')

assert dimod.make_quadratic(poly, 1.0, 'SPIN') == dimod.make_quadratic(poly, 1.0, dimod.SPIN)
assert dimod.make_quadratic(poly, 1.0, 'BINARY') == dimod.make_quadratic(poly, 1.0, dimod.BINARY)

Expected Behavior I would expect 3 things that are currently missing in the code:

1. Consistency: the two assert statements in the code above should always be true.
2. Clarity: documentation should make clear either the option to choose the reduction method, or clarify which reduction method is being used explicitly.
3. Correctness: a unit test is required that validates the exact expected output for several different input QUBOs / Ising Hamiltonians.

A final note: it seems inconsistent that somehow make_quadratic requires only 1 ancilla qubit for BINARY and 2 ancilla qubits for SPIN, as converting between the two expressions require no ancilla qubits whatsoever.

Environment

• OS: Mac High Sierra 10.13.6
• Python version: Python 3.7.4

Additional Context No additional context required.

[arcondello]

The inconsistent behaviour comes from problems parsing the vartype input, this is fixed by #551.

For the documentation, we do use the "substitution" method. I agree the documentation should call that out. One problem is (as you noticed) we use different substitutions for BINARY and SPIN. We could convert all polynomials to BINARY and use the substitution method in the docs, but this would actually increase the density of the resulting BQM, relative to doing the substituion in SPIN-space (which requires an additional aux variable). This should all be documented with examples.

I also agree it would be nice to allow the user to select the method.

[KyleBooth]

Adding to this as my issue seems related.

I am using the make_quadratic function and it seems like the output is inconsistent over multiple runs of the program. For example, running the following:

poly = {(1,2,3,4): 2}
bqm = dimod.make_quadratic(poly, 5, dimod.BINARY) 
print (bqm.variables)

sometimes produces a model with bqm.variables equal to Variables([3, 4, '3*4', 1, 2, '1*2']) and other times equal to Variables([3, 4, '3*4', 1, '1*3*4', 2]). Any idea what's going on here?

[arcondello]

I have not been able to reproduce, I always get Variables([3, 4, '3*4', 1, 2, '1*2']). What version of Python/dimod are you using?

[KyleBooth]

I have tried with both Python 3.7.13 and 3.10.3 with dimod 0.11.6. You may have to run it a few times to see the inconsistent behavior (and of course, if you're using a notebook make sure to reset kernel).