Yi-Hua Chung
0%

qosf - cohort 5 - Task 3 - Find best results

Posted on Edited on In

Brefily Introduction

Original problem

This is the solution of qosf - cohort 5 - Task 3 - Find best results, including the original part and the bonus part of the full problem.

Briefly introducing this problem, we are playing tic-tac-toe. You are represented as ‘X’ and ‘O’ as your opponent.

And you find the situation in the figure below, next is your turn.
Try to develop a quantum algorithm to be able to find the best decisions with a higher probability within two rounds.

Original problem

The blank of the matrix is a qubit, for the state of the X’s is |1> O’s is |0>, and the empty cells are in an unknown state.

Finally, if you think the solution is put the values:

Sample output

The state output must be | 1100 >.

Bonus

What if we start one step earlier and your opponent has not chosen yet, as shown in the following image, it shows with higher probability the chances of you winning. Please refer to the above considerations.

Sample output

For the full problem, please refer to the qosf cohort 5.

Original problem

Method

For the original problem, as the hint mentioned in the question, there are only remaining 4 blanks to fill, and the game will end within two rounds.
Therefore, we only need to discuss at most 24 situations (4!) and find whether the situations can make ‘X’ win (NOTE: There are some duplicated situations).

After discussing by brutal force (by listing all the 24 cases), we can easily find out that there are only two reasonable solutions to this problem, including | 1100 > and | 1001 >.
Hence, I adopt the Qiskit - Grover Algorithm to amplify the probabilities of our willing results by designing the oracle and diffuser of Grover’s algorithm.
Since there are two reasonable answers, we only need to run oracle and diffuser for only one time per function.

Quantum circuit - Oracle

To make the states | 1100 > and | 1001 > reflect, I design the oracle circuit as below:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
def oracle (nqubits):
    qc = QuantumCircuit(nqubits)
    qc.cz(3,2) # 1, control, target
    qc.toffoli(3,0,2) # 2, control, control, target
    qc.mct([3,1,0], 2) # 3, multi-toffoli
    
    # 4, CCCZ, multi-control z, place on the target
    qc.h(0)
    qc.mct([3,2,1], 0)
    qc.h(0)

    qc.mct([3,2,1], 0) # 5, multi-toffoli

    # 6, CCCZ, multi-control z, place on the target
    qc.h(0)
    qc.mct([3,2,1], 0)
    qc.h(0)
 
    U_w = qc.to_gate()
    U_w.name = "U$_\omega$"
    return U_w

↔

  • For the convenience of explanation, I will represent binary as decimal representation in below. For example: | 1100 > is represented by 12, | 1111 > is represented by 15. The willing state-vectors are 9 and 12.
  • cz(3,2): making state-vectors include 12, 13, 14, 15 reflect
  • toffoli(3,0,2): making exchange between (A ↔ B) for: (9 ↔ 13) and (11 ↔ 15). 
      After applying this gate, the reflecting state-vectors include **12, 9, 14, 11**
  • mct([3,1,0], 2), CCCNOT, for control=[3,1,0], target=2: making exchange between(11 ↔ 15)
       After applying this gate, the reflecting state-vectors include **12, 9, 14, 15**
  • CCCZ, multi-control z, for control=[3,2,1], target=0: making reflection on 15, the reflecting state-vectors include 12, 9, 14
  • mct([3,2,1], 0), CCCNOT for control=[3,2,1], target=0: making exchange between(11 ↔ 14)
      After applying this gate, the reflecting state-vectors include **12, 9, 15**
  • CCCZ, multi-control z, for control=[3,2,1], target=0: making reflection on 15, the reflecting state-vectors include 12, 9, which are all we demanded.

Quantum circuit - Diffuser

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
def diffuser(nqubits):
    qc = QuantumCircuit(nqubits)

    for qubit in range(nqubits):
        qc.h(qubit)

    for qubit in range(nqubits):
        qc.x(qubit)
    
    # Do multi-controlled-Z gate
    qc.h(nqubits-1)
    qc.mct(list(range(nqubits-1)), nqubits-1) 
    qc.h(nqubits-1)

    for qubit in range(nqubits):
        qc.x(qubit)

    for qubit in range(nqubits):
        qc.h(qubit)

    U_s = qc.to_gate()
    U_s.name = "U$_s$"
    return U_s

This part is referred to the 3-qubit example Grover Algorithm of qiskit.

Final Quantum Circuit

Final Quantum Circuit 
1
2
3
4
5
6
7
8
9
n = 4
grover_circuit = QuantumCircuit(n)
grover_circuit = initialize_s(grover_circuit, [0,1,2,3])
grover_circuit.barrier()
grover_circuit.append(oracle(n), [0,1,2,3])
grover_circuit.append(diffuser(n), [0,1,2,3])

grover_circuit.measure_all()
grover_circuit.draw()
After applying the oracle and diffuser, the unrolled circuit will be shown as above.

Result

Result -1

Running jupyterLab on IBM Lab, we can finally find out the result shown as the histogram above.
As shown in the histogram, the output results with higher probabilities are | 1001 > and | 1100 >.

Bonus

Method

Different from the original problem, there are 5 remaining blanks that can be filled.
Besides, we need to find the best decisions with higher probability within two rounds.

Same as solving the original problem as above, I still make a discussion at first to find out the best decisions with higher probability within two rounds.

After discussing by brutal force, we can easily find out that there are still two solutions with the highest probabilities to win under this situation, including | 10001 >, and | 11000 >.

Similarly, I adopt the “Grover algorithm” to amplify the probabilities of our willing results by designing the oracle and diffuser of the algorithm.
Besides, same as above, there are two reasonable answers, hence, we only need to run oracle and diffuser for one time.

NOTE: If you are interested in the discussion to find the best solution, you can reference the file ‘discu\brufo’ under the same GitHub repository. However, this file is just the calculation process when I solved this problem which is not organized. It is only provided as a supplementary that the content is relatively messy.

Quantum circuit - Oracle

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
# oracle: make |10001> and |11000> reflect
def oracle (nqubits):
    qc = QuantumCircuit(nqubits)
    qc.cz(4,3) # 1, control, target 
    qc.toffoli(4,0,3) # 2, CCNOT, toffoli
    
    qc.mct([4,3,2,1], 0) # 3-1, CCCCX
    # 3-2, CCCCZ
    qc.h(0)
    qc.mct([4,3,2,1], 0)
    qc.h(0)
    
    qc.mct([4,2,1,0], 3) # 4-1, CCCCX
    # 4-2, CCCCZ
    qc.h(0)
    qc.mct([4,3,2,1], 0)
    qc.h(0)    
    
    qc.mct([4,3,1], 2) # 5, CCCX
    qc.mct([4,3,2,1], 0) # 6-1, CCCCX
    # 6-2, CCCCZ
    qc.h(0)
    qc.mct([4,3,2,1], 0)
    qc.h(0)    

    qc.mct([4,1,0], 3) # 7, CCCX
    qc.mct([4,3,1,0], 2) # 8-1, CCCCX
    # 8-2, CCCCZ
    qc.h(0)
    qc.mct([4,3,2,1], 0)
    qc.h(0) 
    
    qc.mct([4,3,2], 0) # 9, CCCX
    qc.mct([4,3,2,0], 1) # 10-1, CCCCX
    # 10-2, CCCCZ
    qc.h(0)
    qc.mct([4,3,2,1], 0)
    qc.h(0) 
    
    qc.mct([4,2,0], 1) # 11, CCCX
    qc.mct([4,2,1,0], 3) # 12-1, CCCCX
    # 12-2, CCCCZ
    qc.h(0)
    qc.mct([4,3,2,1], 0)
    qc.h(0) 

    U_w = qc.to_gate()
    U_w.name = "U$_\omega$"
    return U_w
  • For the convenience of explanation, I will represent binary as decimal representation below. For example: | 10000 > is represented by 16, | 11000 > is represented by 24. The willing states are 17 and 24.
  • In this part, I first use the CZ gate to reflect 8 state-vectors (24-31).
    • cz(4,3): At this point, only 24 of the reflected state is what we are willing to be reflected.
    • qc.toffoli(4,0,3): Next, I use the CCX gate to exchange the amplitude of (17 ↔ 25), (19 ↔ 27), (21 ↔ 29) and (23 ↔ 31).
    • At this time, there are a total of reflected state-vectors are 24, 17, 26, 19, 28, 21, 30, 23 with only 24 and 17 are the desired states needed to reflect.
  • After reflecting on those needed state-vectors, there are some state-vector that don’t need to be reflected. Hence, we need to reflect them back to be positive.
  1. The approach I took is to swap each state-vector with only three qubits are measured in | 1 > by using the CCCX gate to swap with their corresponding state-vectors with 4 qubits are measured in | 1 >.
  2. Then exchanges the state-vector with 4 qubits are measured in | 1 > with | 11111 > by using the CCCCX gate.
  3. Finally, we use the CCCCZ gate to reflect | 11111 > as a positive state-vector. Then we can successfully make the state-vector reflected back to the positive amplitude.

  • The processes in detail are shown below:

    • Ｍaking the state 30 reflected back to positive, the remaining negative state-vectors are 24, 17, 26, 19, 28, 21, 23

      1
      2
      3
      4
      qc.mct([4,3,2,1], 0) # 3-1, CCCCX
      qc.h(0) # 3-2, CCCCZ
      qc.mct([4,3,2,1], 0)
      qc.h(0)

    • Ｍaking the state 23 reflected back to positive, the remaining negative state-vectors are 24, 17, 26, 19, 28, 21

      1
      2
      3
      4
      5
      qc.mct([4,2,1,0], 3) # 4-1, CCCCX
      # 4-2, CCCCZ
      qc.h(0)
      qc.mct([4,3,2,1], 0)
      qc.h(0)

    • Ｍaking the state 26 reflected back to positive, the remaining negative state-vectors are 24, 17, 19, 28, 21

      • Making exchange between 26 ↔ 30 and 27 ↔ 31. The exchange between 27 and 31 have no impact.
        1
        qc.mct([4,3,1], 2) # 5, CCCX
        Making exchange between 30 ↔ 31.
        1
        qc.mct([4,3,2,1], 0) # 6-1, CCCCX
        Making reflection on 31. 
        1
        2
        3
        4
        # 6-2, CCCCZ
        qc.h(0)
        qc.mct([4,3,2,1], 0)
        qc.h(0)

    • Making the state 19 reflected back to positive, the remaining negative state-vectors are 24, 17, 28, 21

      • Making exchange between 19 ↔ 27 and 23 ↔ 31. The exchange between 23 and 31 have no impact.

        1
        qc.mct([4,1,0], 3) # 7, CCCX

      • Making exchange between 27 ↔ 31. 

        1
        qc.mct([4,3,1,0], 2) # 8-1, CCCCX

      • Making reflection on 31. 

        1
        2
        3
        4
        # 8-2, CCCCZ
        qc.h(0)
        qc.mct([4,3,2,1], 0)
        qc.h(0)

    • Making the state 28 reflected back to positive, the remaining negative state-vectors are 24, 17, 21

      • Making exchange between 28 ↔ 29 and 30 ↔ 31. The exchange between 30 and 31 have no impact.
        1
        qc.mct([4,3,2], 0) # 9, CCCX
      • Making exchange between 29 ↔ 31 
        1
        2
        3
        4
        5
        6
        7
        8
        9
        10
        11
        12
        qc.mct([4,3,2,0], 1) # 10-1, CCCCX
        ```   
        * Making exchange between **29 ↔ 31**.
        ```python=
        qc.mct([4,3,2,0], 1) # 10-1, CCCCX
        ```         
        * Making reflection on **31**
        ```python=
        # 10-2, CCCCZ
        qc.h(0)
        qc.mct([4,3,2,1], 0)
        qc.h(0)

    • Making the state 21 reflected back to positive, the remaining negative state-vectors are 24, 17

      • Making exchange between 21 ↔ 23 and 29 ↔ 31. The exchange between 29 and 31 have no impact.
        1
        qc.mct([4,2,0], 1) # 11, CCCX
      • Making exchange between 23 ↔ 31
        1
        qc.mct([4,2,1,0], 3) # 12-1, CCCCX
      • Making reflection on 31
        1
        2
        3
        4
        # 12-2, CCCCZ
        qc.h(0)
        qc.mct([4,3,2,1], 0)
        qc.h(0)

    • Finally, we got that only the state-vectors 24, and 17 are reflected in negative.

Quantum circuit - Diffuser

This part is referred to the 3-qubit example Grover Algorithm of qiskit.

Final Quantum Circuit

Bonus - Final Quantum Circuit 
1
2
3
4
5
6
7
8
9
n = 5
grover_circuit = QuantumCircuit(n)
grover_circuit = initialize_s(grover_circuit, [0,1,2,3,4])
grover_circuit.barrier()
grover_circuit.append(oracle(n), [0,1,2,3,4])
grover_circuit.append(diffuser(n), [0,1,2,3,4])

grover_circuit.measure_all()
grover_circuit.draw()
After applying the oracle and diffuser, the unrolled circuit will be shown as above.

Result

Bonus - Final Quantum Circuit

Running jupyterLab on IBM Lab, we can finally find out the result shown as the histogram above.
As shown in the histogram, the output results with higher probabilities are | 10001 > and | 11000 >.

Discussion by brutal force

The discussion make by brutal force for the classical situation is shown in the “discu_brufo.pdf” file.

Full code

For the full executable code, please refer to my Github Repository.

Conclusion

In this article, we introduce the solution of task3 of QC qosf Mentorship program cohort 5.

This article focuses on describing how to build quantum circuits of the oracle function of Grover’s Algorithm by describing everything that happens after applying each gate in the oracle.

Question

If there is any question or discussion, please feel free to send an email to me.