Starting part 3!

[TumCucTom]

You might consider using a MIQP opposed to the standard QP currently in use

in addition to the current binary variables used for determining wether a node is in either set, we have two other types of varriables:

path variables for whether a path exists between two nodes in the same partition
flow variables for whether edges are used in a path betwen two variables

We then want to convert our constraints made from these variables into penalties for our hamiltonian

This is our thoughts, please share if you have considered similar things or different things

What we're trying instead

[TumCucTom]

our issue is that we're finding it very hard to implement our constraints as penalties

[SidCh1]

I am just beginning to think about this task. My first observation is that if the line that cuts the graph into two goes through an leaf node's edge. That is the case when we would make some node disjoint.

[TumCucTom]

I am just beginning to think about this task. My first observation is that if the line that cuts the graph into two goes through an leaf node's edge. That is the case when we would make some node disjoint.

when you consider that a node can also be cut out with the cut going through all of it's edges (when it's not a 'leaf' - has more than one edge) that made it a lot harder for us and we had to rethink

[SidCh1]

Of course, like a star graph.

[TumCucTom]

we have achieved 0.1735 with our current work around implementations of the constraints as penalties

[SidCh1]

You might consider using a MIQP opposed to the standard QP currently in use

in addition to the current binary variables used for determining wether a node is in either set, we have two other types of varriables:

• path variables for whether a path exists between two nodes in the same partition
• flow variables for whether edges are used in a path betwen two variables

We then want to convert our constraints made from these variables into penalties for our hamiltonian

This is our thoughts, please share if you have considered similar things or different things

We are trying to see if we can do it with QP only but introducing new binary variables.

[TumCucTom]

You might consider using a MIQP opposed to the standard QP currently in use
in addition to the current binary variables used for determining wether a node is in either set, we have two other types of varriables:

• path variables for whether a path exists between two nodes in the same partition
• flow variables for whether edges are used in a path betwen two variables

We then want to convert our constraints made from these variables into penalties for our hamiltonian
This is our thoughts, please share if you have considered similar things or different things

We are trying to see if we can do it with QP only but introducing new binary variables.

what binary variables are you considering adding?

Do you know yet how you will convert those into a useful form in the hamiltonian? that's what we're struggling with the most!

[SidCh1]

This is what we are trying, please check the attachment.
IONQ—CH—3.pdf

[TumCucTom]

did you manage to implement this sucessfully?

[SidCh1]

So far not..

[TumCucTom]

So far not..

we've just tried to implement it and at least when the lambdas are 1 it's not working for us either

[TumCucTom]

This is what we're trying for out hamiltonian now

[vijeycreative]

This is how I formulated my Hamiltonian for Task 3. It was inspired from TumCumTom's post:

[TumCucTom]

I believe its an MIQP problem so if you want to formulate it as QUBO you need to make certain approximations hence you may struggle with many graphs.

do you have any suggestions so that we can move away from MIQP?

[light-oishikk]

what us ur score for connected ?

[Gopal-Dahale]

do you have any suggestions so that we can move away from MIQP?

I have but it complicates the stuff. one can binary expand the real/ integer variables that come up in the constraints but it's unlikely that the qubo will benefit from such a technique due to the high number of variables.

Let's stick to some approximate constraint which drives the solution towards the optimal one.

[vijeycreative]

does you implementation work? we're still stuggling on many graphs

Hey my implementation seems to work. However, you need to be very careful in your lambda value, d value, learning rate, and number of iterations. Both task 2 and task 3 are very sensitive to lambda value and learning rate.

[TumCucTom]

does you implementation work? we're still stuggling on many graphs

Hey my implementation seems to work. However, you need to be very careful in your lambda value, d value, learning rate, and number of iterations. Both task 2 and task 3 are very sensitive to lambda value and learning rate.

we don't find our part 2 lambda to be particularly sensative but will try to optimise our current implemention for 3 further if you're finding that's the case

[SidCh1]

This is what I tried to do, somehow it is not working and I don't know why:

[Gopal-Dahale]

Feels like you essentially added the objective function as a constraint. Since you don't know the cut beforehand, one needs to have constraints for every possible subset or introduce flow-based constraints as shown here.

[TumCucTom]

i also think you could be getting stuck in a local minima and never find the global minimum as the sections of you hamiltonian might be 'fighting' and end up in a state where they're only partially satisfied

[SidCh1]

Thank you guys. What about zero for lambda_d?

[mulliganaceous]

IonQ_challenge_notes_annotated.pdf
That last inequality, what a pain...

[Shivam2203]

oops

[rlosadagarcia]

Even though its already past the time of the challenge, I wanted to share the Hamiltonian we were using, which had 2 parameters that we tried to trial-error tune for some graphs. I think the connection restriction could be enforced much much better with other methods, but this is the simple case we came up with.