Can someone explain me Superposition of 4 bit strings solution code.

[microsoft]

Can someone explain me Superposition of 4 bit strings solution code.

[tcNickolas]

Have you solved the previous task, superposition of two bit strings? One of the possible solutions for it uses a similar approach, which is discussed in issue #66.

This task is based on the same principle; you can read about it in a bit more detail in the editorial for the contest in which it was used (problem A2).

Please let me know if these two sources help you or if after reading them you still have some questions. We are planning to write "workbooks" for some of the katas (including this one), which will provide not only the code answer but also the details on how to arrive to this code (both the math behind the solution and the insights into non-trivial features of Q#, if any are used in the code). These are some time away from being released, though - stay tuned!

[deathstroke111]

Thanks for the editorial @tcNickolas, It is really useful especially now when there's lack of structured information available on this topic.
And yeah, I have done the task on superposition of two bit strings .
But I am still hazy on the part (ControlledOnInt(i, X))(anc, qs[j]);
I am unsure of what exactly is happening here , and though I understand(from issue #66 ) the latter part code(below) is so that superposition doesn't collapse, but i don't get why the same uncomputing technique is cannot be used(as mentioned in issue #66 ).

      // Uncompute the ancillas, using patterns on main qubits as control
       for (i in 0 .. 3) {
           if (i % 2 == 1) {
               (ControlledOnBitString(bits[i], X))(qs, anc[0]);
           }
           if (i / 2 == 1) {
               (ControlledOnBitString(bits[i], X))(qs, anc[1]);
           }
       }

P.S.Please do keep me posted about those "workbooks".

[tcNickolas]

Let's look at the example from the statement: N = 3 and desired state |010⟩ + |100⟩ + |001⟩ + |110⟩ (I'm dropping normalization here, you can check more carefully that it works out).

After we apply H to the ancillas, we get a state (|00⟩ + |01⟩ + |10⟩ + |11⟩) ⊗ |000⟩ (the first two qubits are ancillas, the last 3 - the ones on which we prepare the state).

(ControlledOnInt(i, X))(anc, qs[j]); allows us to pick one of the ancilla states as control (if i = 0, the control state is |00⟩, etc.) and to set up the right bit pattern on the target qubits. If bits[0] = [false, true, false], we can convert the part of the superposition |00⟩ ⊗ |000⟩ into |00⟩ ⊗ |010⟩ to match the first term of the superposition we're trying to prepare.

After this step the state of the system is going to be |00⟩ ⊗ |010⟩ + |10⟩ ⊗ |100⟩ + |01⟩ ⊗ |001⟩ + |11⟩ ⊗ |110⟩ (ControlledOnInt uses little-endian order of bits).

For the uncomputing part of the solution, we need again to consider each part of the superposition and convert the state of the ancilla qubits in it back to |00⟩. For example, taking the second term, |10⟩ ⊗ |100⟩, we have to use the bit pattern 100 as control and flip the first ancilla bit to 0 - this is what ControlledOnBitString allows to do.

Try to work out this example in details, and it should get more clear for you how the overall solution works. Let me know if that helps!

[deathstroke111]

Okay I worked out the problem as you suggested @tcNickolas and i understood the use of ancillas.
And I abstractly understood the use of ControlledOnBitString function in this problem but could you elaborate on the what exactly it is (I tried the documentation but couldn't understand much perhaps an example of it in different problem would be helpful).

[tcNickolas]

ControlledOnBitString applies an operation to the target register if the control register is in the state described by the given bit string (instead of the |1...1> state like the normal controlled operation does). Internally it does the following steps:

• applies X gate to each qubit that corresponds to a 0 bit in the bit string;
• applies normally controlled version of the operation (apply operation if all control qubits are in |1> state) to the control and target registers;
• and applies X gate to each qubit that that corresponds to a 0 bit in the bit string again to return control register to its starting state.

[deathstroke111]

Initially i was having a hard time following through the steps but then I did some reading on oracles and controlled operations, now it all makes much more sense.
Thank you @tcNickolas .