How to find sets of edges in a graph?
Given a network with 9 vertices with (9*8)/2 = 36 edges. Each edge has it specific cost (distance).
You have to find 3 sets of 3 connected edges and minimize the total cost.
I thought to let a Qubit represent an edge.
x_1 to x_36
In terms of QUBO:
- the cost of the edges are represented in Q_i,i (diagonal terms of matrix Q)
- nonzero off -diagonterms express to constraint of having a interconnected set a 3 edges
How can I program the constraints of qubits sum (x1,x2,x3,x4,x5,x6,x7,x8) = 2 etc ?
Thanks for your time.
Comments
Hello Michel,
Thanks for the detailed problem description! For your constraint:
I would recommend taking a look at the article Using QUBOs to Represent Constraints. The article gives a detailed explanation of how to create QUBO biases from logical constraints.
You will end up with a list of linear and quadratic biases for each constraint - these can be summed together to create the global QUBO.
Hope this helps!
When expressed as a QUBO, we obtain:
E(x1,x2,x3,x4,x5,x6,x7,x8)=
2 x1x2 + 2 x1x3 + 2 x1x4 + 2 x1x5 + 2 x1x6 + 2 x1x7 + 2 x1x8 +
2 x2x3 + 2 x2x4 + 2 x2x5 + 2 x2x6 + 2 x2x7 + 2 x2x8 +
2 x3x4 + 2 x3x5 + 2 x3x6 + 2 x3x7 + 2 x3x8
2 x4x5 + 2 x4x6 + 2 x4x7 + 2 x4x8 +
2 x5x6 + 2 x5x7 + 2 x5x8 +
2 x6x7 + 2 x6x8 +
2 x7x8 +
- x1 - x2 - x3 - x4 - x5 - x6 - x7 - x8 + 4
Is this correct?
Hi Michel,
Looking briefly at your expanded terms, I believe that the linear terms should be:
Recall that for binary variables x^2 = x, so x1^2 + (-4)x1 = (-3)x1 etc.
A good way to check if you have created a valid constraint is to create a truth table and plug in known "good" (valid) and "bad" (invalid) combination of variables. The "good" states should always end up in the lowest energy state, while "bad" states will have higher energy. There is an example of a truth table in the above article I linked.
luca is right :-)
just put (x1+x2+x3+x4+x5+x6+x7+x8-2)^2 into WolframAlpha and you get:
x1^2 + 2 x1 x2 + 2 x1 x3 + 2 x1 x4 + 2 x1 x5 + 2 x1 x6 + 2 x1 x7 + 2 x1 x8 - 4 x1 + x2^2 + 2 x2 x3 + 2 x2 x4 + 2 x2 x5 + 2 x2 x6 + 2 x2 x7 + 2 x2 x8 - 4 x2 + x3^2 + 2 x3 x4 + 2 x3 x5 + 2 x3 x6 + 2 x3 x7 + 2 x3 x8 - 4 x3 + x4^2 + 2 x4 x5 + 2 x4 x6 + 2 x4 x7 + 2 x4 x8 - 4 x4 + x5^2 + 2 x5 x6 + 2 x5 x7 + 2 x5 x8 - 4 x5 + x6^2 + 2 x6 x7 + 2 x6 x8 - 4 x6 + x7^2 + 2 x7 x8 - 4 x7 + x8^2 - 4 x8 + 4
then apply that - as luca said - x1^2 = x1 and you get the linear terms as -3x1 - 3x2 ...
Please sign in to leave a comment.