Kakuro problem - revised and tighter definition

Constraint satisfaction
1

Hi everyone,

We understand that the problem had a larger maneuver space then we planned beforehand. The main objective of the exercise is to create the quantum circuit, and that is why we decided you shouldn’t optimize the constraints at all. We will provide the list of constraints that define the problem.

Without any optimization on the problem, The pure constraints are as follows:

             "(x0 != x1) and" 
             "(x2 != x3) and" 
             "(x2 != x4) and" 
             "(x3 != x4) and" 
             "(x5 != x6) and" 
             "(x0 != x2) and" 
             "(x1 != x3) and" 
             "(x1 != x5) and" 
             "(x3 != x5) and" 
             "(x4 != x6) and" 
             "((x0 + x2) == 5) and" 
             "((x1 + x3+x5) == 3) and"
             "((x4 + x6) == 1) and" 
             "((x2 + x4+x3) == 5) and" 
             "((x0 + x1) == 3) and"
             "((x5 + x6) == 1)

These massive amounts of constraints might create a circuit with too many qubits to simulate. We want you to be able to test your solution yourself, and that is why we optimized these constraints a bit. We will provide an explanation in the comments to this post about the optimization process.

The constraints needed to solve the problem are:

             "(x0 != x1) and" 
             "(x2 + 2 != x3) and" 
             "(x3 != x4) and" 
             "(x1 != x3) and"
             "(x3 != x5) and"  
             "(x5 != x6) and" 
             "(x0 != x2) and" 
             "(x1 != x5) and" 
             "(x4 != x6) and" 
             "(x3 == 2) and" 
             "(x2 + x4 + x3 == 3)"

In terms of definitions of the variables - all of the variables are of size 1 qubit, except for x3 which is 2 qubits.

Good luck to all participants! Feel free to ask any further questions in this forum.

2 Likes
2

As promised, let’s explain how the optimization was done. (This is not a part of the problem anymore, it is for enrichment purposes only).

Let’s start with the variables - why could we define some of them with a single qubit only?

  • If we look at the constraint x4 + x6 == 1, we can deduce that both x4 and x6 can only be assigned with either 0 or 1. This means we can use a single qubit to describe them. The same explanation applies directly yo x5, since x5 + x6 == 1 as well.
  • What about the constraint x0 + x2 == 5? We can say that both x0 and x2 can be assigned only with 2 or 3 because allowable values for each of the ‘x’ variables are 0 to 3, and if x0 is 0 or 1, that will make x2 too large. This can also be described - using a single qubit - by the formula true_value = qubit_value + 2. We need to take that into account when defining the next constraints.
  • Lastly, we look at the constraint x0 + x1 == 3. We already know that x0 is either 2 or 3. This means that x1 can only be assigned with 0 or 1 - so it can also be described using a single qubit.

Now, let’s understand the constraints themselves.
What can we do about the addition constraints?

  • x4 + x6 == 1 and x4 != x6 are fully equivalent constraints when both bariables are of size 1. It is easier to create a circuit that checks different values instead of addition + equal values, so we can remove the first constraint. This explanation also applies for x5 + x6 == 1.
  • It is not as clear, but this explanation applies even for x0 + x1 == 3. That is because x0 is actually 2 or 3, which means we can change the constraint to x0 + 2 + x1 == 3, or x0 + x1 == 1. Note that x0 here means the qubit value of x0, and not the real value. Thus, we can remove this constraint, as long as we use x0 != x1.
  • This even applies for x0 + x2 == 5 - since both variable are replaced with a single qubit representation, this equation is also reduced to xo + x2 == 1 and cen be removed.
  • Regarding x1 + x3 + x5 == 3 - we can say that since x1 and x5 can only be 0 or 1 each, and they must be different, we know that x1 + x5 == 1, which means this can be reduced to x3 == 2.

We are left with a single addition constraint.
What can we do about the inequalities constraints?

  • Since we changed x2, we need to update the constraint x2 != x3 to check that the real values are different. we will use x2 + 2 != x3.
  • x2 and x4 are obviously different since x2 can be assigned with 2 or 3, and x4 can be assigned with 0 or 1. We can remove the constraint x2 != x4.

The rest of the constraints will remain as is.
It is important to note that we stopped the manual optimization at an arbitrary point - it should be just enough so you would be able to test your code.

3

Isn’t it somewhere in the rules to NOT do this?

4

According to Classic Coding Competition - Kakuro constraint satisfaction problem X2 + X3 + X4 == 5.

5

You are right. After we saw some of the competitors’ notes, we realized that the problem needs to be redefined.
Unlike before, now you should not optimize these constraints any further. This is the exact list of constraints you need to implement in your circuit.
We apologize for the inconvenience if you already started to solve it.

6

Since x2 can be either 2 or 3, it is represented as a single-qubit, where the real value of x2 is the quit value +2. That’s why the x2+x3+x4 constraint now equals 3 instead of 5.

7

This is a competition. I’ll solve it the hard way.

1 Like
9

I suggest the constraints should only be what is expressly forbidden. Otherwise, just post the puzzle and allow competitors to solve it.

1 Like
10

Hello! What bit ordering will be used to judge this problem? To be precise:

  1. should the two qubits making $x_3$ bo ordered as $first\times 2 + second \times 1$ or $first \times 1 + second \times 2$?
  2. Should the 8-qubit oracle input register represent the values of [x0, x1, x2, …, x6] or [x6, x5, …, x0]?
11

In other words, the only four options I can see regarding this questions are as follows:

  1. [x0, x1, x2, x3_MSB, x3_LSB, x4, x5, x6], or
  2. [x0, x1, x2, x3_LSB, x3_MSB, x4, x5, x6], or
  3. [x6, x5, x4, x3_MSB, x3_LSB, x2, x1, x0], or
  4. [x6, x5, x4, x3_LSB, x3_MSB, x2, x1, x0].

x3_MSB is the most significant bit of x3, ie. of value 2.
x3_LSB is the least significant bit of x3, ie. of value 1.

12

Hi @j.tulowiecki

You may use the ordering that you prefer, just be consistent and tell us what you chose. That’s true for both questions

13

So 59652 cx gates after transpiling these 16 constraints directly, is it in the right order or what? :smile:

15

The problem requires 11 constraints. 16 was before simplification. The constraints are listed above, but for reference, they are:

“(x0 != x1) and”
“(x2 + 2 != x3) and”
“(x3 != x4) and”
“(x1 != x3) and”
“(x3 != x5) and”
“(x5 != x6) and”
“(x0 != x2) and”
“(x1 != x5) and”
“(x4 != x6) and”
“(x3 == 2) and”
“(x2 + x4 + x3 == 3)”

Good luck!

16

These constraints are weird and wrong. Instead of one solution, it allows another 32.
Check this one for example
{x0==0,x1==1,x2==1,x3==2,x4==0,x5==0,x6==1}

17

This is actually the correct solution, since we defined x0 to be it’s qubit value + 2, and the same for x2.
Also note that the size of all variables is 1 except x3.
What other solutions are there?

1 Like
18

First of all, this is the original solution:
{x0==2,x1==1,x2==3,x3==2,x4==0,x5==0,x6==1}
Which doesn’t satisfy your last “simplified” constraint, which should be x2+x4+x3==5.

I’ve read the simplification carefully, so additional assumptions on top of these constraints are, that every variable is 1-bit except x3, and x0 and x2 are either 2 or 3, right?
So it’s the same as enumerating {x0,x1,x2,x3,x4,x5,x6} over these corresponding domains {{2,3},{0,1},{2,3},{0,1,2,3},{0,1},{0,1},{0,1}}, which results in these 2 solutions (not one):

{x0==2,x1==1,x2==3,x3==2,x4==0,x5==0,x6==1}
{x0==3,x1==0,x2==2,x3==2,x4==1,x5==1,x6==0}

So you need at least one more constraint to get rid of the extra solution: x2!=x3
Overall a very ill-defined problem I should say :face_with_spiral_eyes:

1 Like
19

By the way, what’s the intended challenge here? To turn classical constraints to boolean ones and turn them into decomposed quantum circuits? Should we develop our own MCXGate decomposition, a separate competition problem here, should restrictions on Qiskit’s unrollers be in place or something? Or is it about some unconventional synthesis of sub-circuits for each individual constraint?

1 Like
20

Hi,
The second solution you proposed contradicts this constraint: x2+2!=x3. This constraint means that the qubit value of x2 plus 2 (which is the real x2 value) is different from x3, and thus x2 can’t equal to 2.

The purpose of this challenge is to create the most efficient quantum circuit that implements these constraints. In this specific challenge, efficient means less 2 quit gates. Implement each constraint as efficient as you can, and then do the same for checking they all coexist. So to answer your question - you need to do both :slight_smile:
In the MCX challenge the purpose is less depth, so it might be a different implementation. MCX is a very common and helpful gate!

I hope that answers your questions, please ask us if something remain unclear!

1 Like
21

Hi, can we use in the solution the fact all variables except x3 are of size 1 qubit?

1 Like
22

another question: can I contact organizers somehow? I have a question which may be too big hint for everyone :slight_smile:

2 Likes