This is a competition. I’ll solve it the hard way.
1 Like
I suggest the constraints should only be what is expressly forbidden. Otherwise, just post the puzzle and allow competitors to solve it.
1 Like
Hello! What bit ordering will be used to judge this problem? To be precise:
- should the two qubits making $x_3$ bo ordered as $first\times 2 + second \times 1$ or $first \times 1 + second \times 2$?
- Should the 8-qubit oracle input register represent the values of [x0, x1, x2, …, x6] or [x6, x5, …, x0]?
In other words, the only four options I can see regarding this questions are as follows:
- [x0, x1, x2, x3_MSB, x3_LSB, x4, x5, x6], or
- [x0, x1, x2, x3_LSB, x3_MSB, x4, x5, x6], or
- [x6, x5, x4, x3_MSB, x3_LSB, x2, x1, x0], or
- [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.
You may use the ordering that you prefer, just be consistent and tell us what you chose. That’s true for both questions
So 59652 cx gates after transpiling these 16 constraints directly, is it in the right order or what? 
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!
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}
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
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 
1 Like
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
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 
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
Hi, can we use in the solution the fact all variables except x3 are of size 1 qubit?
1 Like
another question: can I contact organizers somehow? I have a question which may be too big hint for everyone
2 Likes
Yes, we encourage participants to define all variables as 1 qubit, except x3 which is 2 qubits.
1 Like
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.
We have done the classical simplification for you. You can now focus on the quantum synthesis questions, like:
- How would you implement an inequality check between two registers? And what happens when they have different sizes?
- How would you implement a quantum adder? Is there a better way to implement a+b+c for the last constraint?
- How would you implement a logical and operator with the minimum number of cnot gates?
1 Like
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.
1 Like
All of the constraints refer to the qubit value.
Are there constraints you want to ask about?
1 Like