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?
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?
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?
Suppose that using some optimization technique I get that x2 < 2. Can I use only one bit for the value of x2?
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:
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.
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).
Yes, you can. Don’t forget to justify it in your solution, like all of the other optimizations you have made.
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?
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.