Kakuro problem - revised and tighter definition

[swish]

Can we just get an approved list of only equality/inequality constraints between qubits? Otherwise, there are too many classical ambiguities regarding how to go forward. Are we doing classical boolean formula reduction or quantum circuit synthesis here, right? Ideally, no classical simplification argument should be involved and there would be just one unambiguous starting circuit for each constraint, so the task is just to combine and optimize them into a minimal one.

[nati]

We have done the classical simplification for you. You can now focus on the quantum synthesis questions, like:

1. How would you implement an inequality check between two registers? And what happens when they have different sizes?
2. How would you implement a quantum adder? Is there a better way to implement a+b+c for the last constraint?
3. How would you implement a logical and operator with the minimum number of cnot gates?

[Naman]

Do the xi’s given in the updated list of constraints refer to the true value or the qubit value? It seems that both of these are used interchangeably while defining the constraints.

[nati]

All of the constraints refer to the qubit value.
Are there constraints you want to ask about?

[Naman]

Sorry, my bad. I interpreted it differently. It’s all clear now. Thanks!

[kcLin2708]

Why there don’t exist x3!=x4 and x1!=x5?
Thank you for the explaination.

[nati]

Both of these constraints exist in the list you need to implement.
This is the full list of the constraints:

@nati

             "(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)"

[mgt_tinubu]

Hi everyone,

Is there a limit when it comes to the number of ancillary qubits that can be used to verify the constraints of the problem ?

[nati]

Hi,

There isn’t a limit on the number of qubits.
However, you need to make sure your code works correctly.
If you would create a circuit that is too large to check on a simulator, I would suggest:

• Unit testing on the different blocks you write (for instance, the inequality block).
• Supply a detailed explanation of why your circuit is correct. If you want, you can supply the unit testing or the method you used to test your code.

[kcLin2708]

Can somebody please explain why x2 + x4 + x3 == 3 instead 5? Thank you!

[QubitGuy]

There is a longer explanation near the top of the thread, but basically, when we look at 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. We thus decide that a single qubit will encode x0 and x2 and we will note that true_value = qubit_value + 2 .

So while x2 is indeed only 2 or 3, it is encoded as 0 or 1 and thus ‘x2 + x4 + x3’ are set to 3 instead of 5

[JulienMellaerts]

Hello,

To be sure to well understand what is requiered or not, is it possible to optimize the list of constraints under some assumption, or is it mandatory to implement all these constraints ?

Thank you.

[QubitGuy]

Yes, you have to implement the constraints as is. There may be some optimization in how to implement each individual constraint, but you still have to implement all constraints.

[JulienMellaerts]

Thank you for your answer, it is clear for me now.

[swish]

Does the final MCX gate over 11 constraints require a decomposition or does only a CX number for each constraint count toward the solution? You can’t go around it, right? As we encode constraints and decompose them separately, we should AND them together with a 12-qubit MCX gate, any optimization over it is the same as additional fiddling with constraints, which is not allowed.

And the same goes for the Grover diffusion/amplification part of a circuit…

[nati]

Hi,
You should decompose the mcx gate, as we measure the score based on the number of cx gates. Also, note that we don’t restrain the number of qubits.

Regarding the diffuser operator - we only score the oracle, so you don’t have to decompose it.

[tdcwilliams]

Hi, 11 constraints crashes my computer, which is a reasonably powerful laptop.
A quick 30s look at the puzzle itself tells me that if x3=2, most of the other variables are 0 or 1,
so nearly all the constraints involving x3 are satisfied automatically (the exception being the last one). That brings the problem down to 6 constraints (giving 12 qubits in total) which still takes a long time to build the oracle, but my laptop can just do it without crashing if there are no other programs going. Can the list of constraints be relaxed a bit further perhaps? Or maybe I am missing something, being a relative beginner…

[nati]

Hi @tdcwilliams
You’re right that x3 == 2 might relax many other constraints.
However, Kakuro (and Soduko) are puzzles that may be solved classically in linear time by relaxing the constraints. We relaxed the constraints just enough to calculate it on a simulator and stopped there, so there will still be a challenge in how to optimize the circuit best.
I’m sorry that it crashes your laptop. May I suggest you try the following:

• Have you tried to unit test your code? When creating a gate that performs an inequality check between a size 1 and size 2 registers (like in the constraint x3 != x4), try to test it apart from the whole Grover circuit.
• In the same way you can unit test parts of the code, I suggest trying to optimize each function separately.

I hope this helps.

[tdcwilliams]

thanks for the tips @nati, I’ll try those ideas

[JosJesus]

When submitting our solutions do we give the true values of X0, X1, … X6 (i.e the values that we get from the algorithm for X0 and X2 +2) or the values that we get from the algorythm?