 # Allowed and Disallowed Definitions for the Problem

You may define the problem as you wish
as long as […] the solutions are the same, no more and no less

Can you clarify what do mean by “solution” and what is allowed and what is not in problem definitions?

Consider the example from the problem statement. Let me denote values of cells as x0, …, x3. The unique solution for the example is `x0 = 2, x1 = 1, x2 = 1, x3 = 3`.

Can I define following mappings between qubits and the problem domain? And if not, why?

1. I have only one qubit `q0` and I map its measured value to cells as such: `x0 = 2, x1 = q0, x2 = 1, x3 = 3`, and the problem in my “definition” is whether `q0 = 1`. This problem has the same solutions as the original, hasn’t it?
So what does mean “solution” and why this “definition” is incorrect?
Do you mean that the set of possible puzzle states should be the same in the real problem and in my defintion?

2. By subtracting eq. 5 from eq. 7 you can get that `x2 = x1`. Can I use the same qubits for values of `x1` and `x2`?

3. Suppose that using some optimization technique I get that `x2 < 2`. Can I use only one bit for the value of `x2`?

2 Likes

Those are some excellent questions!

Generally, when solving constraints satisfaction problems, optimizing the model is a part of an effective search for a solution. However, since solving Kakuro can be done by optimizing the model, we wanted to limit that so that you’ll leave the core business to the quantum algorithm.
The basic rule is each variable should have its own register of qubits.

Now, let’s refer to your questions:

1. You are correct. Because we’re optimizing the constraints, you need to make sure that you are not changing the domain of the problem or the space of the possible solutions.
2. Since we want to keep a register for each variable, the answer is no. You can, however, reduce one of the constraints to `x2=x1` (as long as my answer to question 1 still holds).
3. Yes, you can. Don’t forget to justify it in your solution, like all of the other optimizations you have made.
2 Likes

@nati, thanks for the answer! It is very helpful.

However, I still don’t understand the difference between cases 2 and 3.

It seems to me that answer 3 contradicts to answer 1. If I use only one bit for `x2` then I can’t represent possible solution where `x2` is equal to 2 or 3, am I right?

1 Like

You are correct, but if there is no possible solution when `x2` is equal to 2 or 3 at all, then you can still find all valid answers.

Now I’m confused. What information can I use when optimizing my model?

I thought that I should use only basic Kakuro rules and some linear algebra facts to optimize a model, and treat values in the filled cells as some sort of parameters. But the example uses these values for optimization (e.g. at step 1).

Then I thought that my oracle should be able to accept any possible solution (e.g. all 4^4 of solutions in the example) as an input. But you say that I can leave out some of variables, if it does not affect valid answers.

Can you clarify what can I use to optimize my model?

• basic Kakuro rules
• values of the filled cells
• laws of logic (`p and q are true; therefore p is true` etc.)
• laws of linear algebra (e.g. properties of systems of equations)
• shrinking the input space, if no valid answers are lost (e.g. use one qubit instead of two to represent some input variables)

I believe that sufficiently advanced optimization using all of these facts gives a result that is indistinguishable from the manual solution.

I mean that after rigorous optimization you get constraints `x0=2, x1=1, x2=1, x3=3` (I can send you a proof in DM, if it is appropriate; I suppose it is against the rules to publish it here).
And after that you can use zero bits for each of x_i because there is no valid answers with other values.

I think you bring up a good point. We’ll try to clarify which constraints to use later today.

2 Likes

Here is a definition of the constraints you should use as well as an explanation (for informational purposes) on how we got there: Kakuro problem - revised and tighter definition

1 Like