[Solved] Trying to understand Favoring States with One True

I'm new to D-Wave and currently just started learning about it. In the docs there is this example:

We want to find a function E(a,b,c)E(a,b,c) that is at a minimum when this objective is true. We can express this as


or as


The problem with the second expression above is that when aabb, and cc are all 0, we get a result of 1−1, which is a lower energy than the TRUE states. The solution is to square the original equation:


Taking a closer look at the squared expression,


we can see that because the variables are binary (0 or 1),


our objective function becomes the quadratic equation


where the energy of the function E(a,b,c)E(a,b,c) is the value of the objective function.


Now my question is if a^2=a

shouldn't the computation be: 

(a+b+c1)^2 = a^2+b^2+c^2+2ab+2ac+2bcabc+1

                        = a+b+c+2ab+2ac+2bcabc+1  // since a^2=a, b^2=b, c^2=c                       

                        = 2ab+2ac+2bc+1

Or am I misunderstanding something?



  • Hello,

    In this case, the null solution will also be a low energy state:
    a=1, b=0, c=0
    2(1*0)+2(1*0)+2(0*0)+1 = 1

    a=0, b=0, c=0
    2(0*0)+2(0*0)+2(0*0)+1 = 1

    So this gets you the "choose one" but also the "choose none".

    Let us get back to you with an example of a "choose one" qubo.

    Comment actions Permalink
  • Something like this works:

    Q = {(0, 1): 4, (0, 2): 4, (1, 2): 4, (0, 3): -2, (1, 3): -2, (2, 3): -2, (3, 3): 1}

    Keep in mind that there are multiple solutions to this problem, just like there are multiple solutions to any logic or coding problem.

    A nice way of verifying your results for very simple/small problems is to use the dimod.ExactSolver. 
    It will enumerate all of the possible combinations of input values and give you the energies for each in ascending order.
    It will get very slow, very quickly as the problem size is increased, as many problems end up being exponentially hard to solve.

    I hope this was helpful!

    Please feel free to ask for more information or for clarification.

    Comment actions Permalink
  • My question really is purely algebraic one. If



    a^2=a, b^2=b, c^2=c


    (a+b+c1)^2  = a^2+b^2+c^2+2ab+2ac+2bcabc+

                             = a+b+c+

                            = 2ab+2ac+2bc+1

    That is my personal computation to the initial square problem. But why does the example in the docs give this anwser instead:


    Surely the +a and -a, b's and c's cancel out in the equation.

    I do appreciate your illuminating replies however. I am not quite into programming yet. Still trying to understand the machine.




    Comment actions Permalink
  • Hi all,

    I'm thinking there's a little confusion here. Let's fix it.

    Assume a, b, c are binary variables.

    (a + b + c - 1) ** 2

    (a + b + c - 1)(a + b + c - 1)

    a**2 + a*b + a*c - a + b*a + b*b + b*c - b + c*a + c*b + c*c - c - a - b - c + 1

    As Danny F noted, a**2 cancels one of the negative a's, but there are 2 of them. The same thing happens with b, and c. We get:

    2a*b + 2a*c + 2b*c - a - b - c + 1

    This is the famous "(2, -1, -1) solution" that occurs when we want 2 qubits to have different values.

    Comment actions Permalink
  • It looks like a simple mistake:

    (a + b + c - 1)(a + b + c - 1) = a^2 + ab + ac - a + ab + b^2 + bc - b + ac + bc + c^2 - c - a - b - c + 1

    = a^2 + b^2 + c^2 + 2ab + 2ac + 2bc - 2a - 2b - 2c + 1

    = a + b + c + 2ab + 2ac + 2bc - 2a - 2b - 2c + 1

    = 2ab + 2ac + 2bc - a - b - c + 1

    Comment actions Permalink
  • Yes a simple mistake in my part! My algebraic computation was wrong and the given output is correct.

    Thanks all. i have lots of other questions but I will address them in the appropriate forums.

    I can say I can close this thread. 

    Comment actions Permalink

Please sign in to leave a comment.

Didn't find what you were looking for?

New post