<jupyter_start><jupyter_text>prepared by <NAME>                 This cell contains some macros. If there is a problem with displaying mathematical formulas, please run this cell to load these macros. $ \newcommand{\bra}[1]{\langle 1|} $$ \newcommand{\ket}[1]{|1\rangle} $$ \newcommand{\braket}[2]{\langle 1|2\rangle} $$ \newcommand{\dot}[2]{ 1 \cdot 2} $$ \newcommand{\biginner}[2]{\left\langle 1,2\right\rangle} $$ \newcommand{\mymatrix}[2]{\left( \begin{array}{1} 2\end{array} \right)} $$ \newcommand{\myvector}[1]{\mymatrix{c}{1}} $$ \newcommand{\myrvector}[1]{\mymatrix{r}{1}} $$ \newcommand{\mypar}[1]{\left( 1 \right)} $$ \newcommand{\mybigpar}[1]{ \Big( 1 \Big)} $$ \newcommand{\sqrttwo}{\frac{1}{\sqrt{2}}} $$ \newcommand{\dsqrttwo}{\dfrac{1}{\sqrt{2}}} $$ \newcommand{\onehalf}{\frac{1}{2}} $$ \newcommand{\donehalf}{\dfrac{1}{2}} $$ \newcommand{\hadamard}{ \mymatrix{rr}{ \sqrttwo & \sqrttwo \\ \sqrttwo & -\sqrttwo }} $$ \newcommand{\vzero}{\myvector{1\\0}} $$ \newcommand{\vone}{\myvector{0\\1}} $$ \newcommand{\vhadamardzero}{\myvector{ \sqrttwo \\  \sqrttwo } } $$ \newcommand{\vhadamardone}{ \myrvector{ \sqrttwo \\ -\sqrttwo } } $$ \newcommand{\myarray}[2]{ \begin{array}{1}2\end{array}} $$ \newcommand{\X}{ \mymatrix{cc}{0 & 1 \\ 1 & 0}  } $$ \newcommand{\Z}{ \mymatrix{rr}{1 & 0 \\ 0 & -1}  } $$ \newcommand{\Htwo}{ \mymatrix{rrrr}{ \frac{1}{2} & \frac{1}{2} & \frac{1}{2} & \frac{1}{2} \\ \frac{1}{2} & -\frac{1}{2} & \frac{1}{2} & -\frac{1}{2} \\ \frac{1}{2} & \frac{1}{2} & -\frac{1}{2} & -\frac{1}{2} \\ \frac{1}{2} & -\frac{1}{2} & -\frac{1}{2} & \frac{1}{2} } } $$ \newcommand{\CNOT}{ \mymatrix{cccc}{1 & 0 & 0 & 0 \\ 0 & 1 & 0 & 0 \\ 0 & 0 & 0 & 1 \\ 0 & 0 & 1 & 0} } $$ \newcommand{\norm}[1]{ \left\lVert 1 \right\rVert } $$ \newcommand{\pstate}[1]{ \lceil \mspace{-1mu} 1 \mspace{-1.5mu} \rfloor } $   Solutions for  Max-Cut Problem  Task 1    Let's implement the idea given above. We have a graph with 4 vertices, and so we have a circuit with 4 qubits. Represent the following coloring of the given graph in the quantum circuit.  Solution<jupyter_code>import cirq
from cirq import X, I

qq = cirq.LineQubit.range(4)
circuit = cirq.Circuit()

circuit.append(X(qq[1]))
circuit.append(X(qq[2]))

circuit.append(cirq.measure(*qq, key='result'))
print(circuit)

s = cirq.Simulator()
samples = s.run(circuit, repetitions=1)
result = samples.measurements["result"]

# decode the solution
for qubit in range(4):
    if result[0][qubit] == 0:
        print("Qubit",qubit, "is red")
    else:
        print("Qubit",qubit, "is blue")<jupyter_output><empty_output><jupyter_text>Task 2For the given graph below, implement the first two steps of the oracle described above. The first four qubits are used for vertices.The next three qubits are used for edges.The last qubit is used for the output.Remark that the last qubit should be in state $ \ket{1} $ (resp., $\ket{0}$) if the coloring of the vertices is correct (resp., incorrect).Test your implementation with different colorings.  Solution<jupyter_code>import cirq
from cirq import X, CX
s = cirq.Simulator()

qq = cirq.LineQubit.range(8)
circuit = cirq.Circuit()
# correct coloring
circuit.append(X(qq[0]))
circuit.append(X(qq[1]))

# incorrect coloring
# circuit.append(X(qq[0]))

# check 0-2 edge and store at 4th qubit
circuit.append(CX(qq[0], qq[4]))
circuit.append(CX(qq[2], qq[4]))
# check 0-3 edge and store at 5th qubit
circuit.append(CX(qq[0], qq[5]))
circuit.append(CX(qq[3], qq[5]))
# check 1-3 edge and store at 6th qubit
circuit.append(CX(qq[1], qq[6]))
circuit.append(CX(qq[3], qq[6]))

# check all edge qubits
circuit.append(X(qq[7]).controlled_by(*(qq[4:7])))

circuit.append(cirq.measure(*qq, key='result'))
samples = s.run(circuit, repetitions=1)
result = samples.measurements["result"]
# 0 - first (and only measurement)
# 7 - last qubit
output = result[0][7] 
print("Measurement output: ", output)
if output == 1:
    print("correct coloring (graph is bipartite)")
else:
    print("incorrect coloring")
print(circuit)<jupyter_output><empty_output><jupyter_text>Task 3 For the given graphs below, iterate Grover’s search algorithm 2 steps to find the correct colorings. (There are indeed $k=2$ possible colorings, and so the oracle should be applied $\frac{\pi}{4}\sqrt{\frac{2^4}{k}}\approx 2$ times.) You will use nine qubits: 4 for vertices, 4 for edges, and 1 for the output qubit.The diffusion operator is provided below.Observe which outcomes have the higher frequencies.  Solution<jupyter_code>import cirq
from cirq import X, H, Z, inverse, CX
s = cirq.Simulator()

qq = cirq.LineQubit.range(9)

def edge_check(a, b, c):
    yield CX(qq[a], qq[c])
    yield CX(qq[b], qq[c])

def oracle():
    # check 0-2 edge and store at 4th qubit
    yield edge_check(0, 2, 4)
    # check 0-3 edge and store at 5th qubit
    yield edge_check(0, 3, 5)
    # check 1-2 edge and store at 6th qubit
    yield edge_check(1, 2, 6)
    # check 1-3 edge and store at 7th qubit
    yield edge_check(1, 3, 7)

    # check all edge qubits
    yield X(qq[8]).controlled_by(*(qq[4:8]))
    
def oracle_computation():
    yield oracle()
    yield Z(qq[8])
    yield inverse(oracle())    

def grover_diffusion():
    yield H.on_each(*qq)
    yield X.on_each(*qq)
    yield Z(qq[3]).controlled_by(*(qq[0:3]))
    yield X.on_each(*qq)
    yield H.on_each(*qq)

circuit = cirq.Circuit()
circuit.append(H.on_each(*(qq[0:4])))
for i in range(2):
    circuit.append(oracle_computation())
    circuit.append(grover_diffusion())

# we are only intertested in outputs of first 4 qubits
circuit.append(cirq.measure(*(qq[0:4]), key='result'))

# determine the statistics of the measurements
trials_number = 1000
samples = s.run(circuit, repetitions=trials_number)
result = samples.measurements["result"]

def bitstring(bits):
    return "".join(str(int(b)) for b in bits)

counts = samples.histogram(key="result",fold_func=bitstring)
print(counts)<jupyter_output><empty_output><jupyter_text>Note that the states '0011' and '1100' are the most commonly observed states.<jupyter_code>print("Probability of measuring 0011: ", counts.get('0011')/trials_number)
print("Probability of measuring 1100: ", counts.get('1100')/trials_number)<jupyter_output><empty_output><jupyter_text>Task 4Repeat Task 3 for the following graph.Does the following graph has any correct colorings or not? If not, what would you say in advance about the frequencies of the outcomes?  Solution<jupyter_code>import cirq
from cirq import X, H, Z, inverse, CX
s = cirq.Simulator()

qq = cirq.LineQubit.range(9)

def oracle_computation():
    # check 0-1 edge and store at 4th qubit
    yield edge_check(0, 1, 4)
    # check 0-2 edge and store at 5th qubit
    yield edge_check(0, 2, 5)
    # check 0-3 edge and store at 6th qubit
    yield edge_check(0, 3, 6)
    # check 1-3 edge and store at 7th qubit
    yield edge_check(1, 3, 7)

    # check all edge qubits
    yield X(qq[8]).controlled_by(*(qq[4:8]))

def oracle():
    yield oracle_computation()
    yield Z(qq[8])
    yield inverse(oracle_computation())    
    
def grover_diffusion():
    yield H.on_each(*qq)
    yield X.on_each(*qq)
    yield Z(qq[3]).controlled_by(*(qq[0:3]))
    yield X.on_each(*qq)
    yield H.on_each(*qq)

circuit = cirq.Circuit()
circuit.append(H.on_each(*(qq[0:4])))

for i in range(2):
    circuit.append(oracle())
    circuit.append(grover_diffusion())

# we are only intertested in outputs of first 4 qubits
circuit.append(cirq.measure(*(qq[0:4]), key='result'))

# determine the statistics of the measurements
trials_number = 10000
samples = s.run(circuit, repetitions=trials_number)
result = samples.measurements["result"]

# create an histogram of the result
def bitstring(bits):
    return "".join(str(int(b)) for b in bits)

counts = samples.histogram(key="result",fold_func=bitstring)
print(counts)<jupyter_output><empty_output>
{'fraction_non_alphanumeric': 0.16590272472625414, 'fraction_numerical': 0.03437738731856379, 'mean_word_length': 4.391214824982842, 'pattern_counts': {'":': 0, '<': 22, '<?xml version=': 0, '>': 22, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'chain_length': '5', 'dir': 'jupyter-structured-clean-dedup', 'id': '281665', 'license': 'Apache-2.0', 'n_tokens_mistral': 2975, 'n_tokens_neox': 2709, 'n_words': 759, 'path': 'nickel/B02_Max_Cut_Problem_Solutions.ipynb', 'repo_name': 'asif-saad/qNickel', 'size': '7857'}