[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 aa, bb, 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+c−1)^2 = a^2+b^2+c^2+2ab+2ac+2bc−a−b−c+1
= a+b+c+2ab+2ac+2bc−a−b−c+1 // since a^2=a, b^2=b, c^2=c
= 2ab+2ac+2bc+1
Or am I misunderstanding something?
Comments
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.
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.
My question really is purely algebraic one. If
E(a,b,c)=(a+b+c−1)^2
and
a^2=a, b^2=b, c^2=c
then
(a+b+c−1)^2 = a^2+b^2+c^2+2ab+2ac+2bc−a−b−c+1
= 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:
E(a,b,c)=2ab+2ac+2bc−a−b−c+
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.
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.
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
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.
Please sign in to leave a comment.