<jupyter_start><jupyter_text>prepared by <NAME> (<EMAIL>) | December 09, 2018 I have some macros here. If there is a problem with displaying mathematical formulas, please run me to load these macros.$ \newcommand{\bra}[1]{\langle 1|} $$ \newcommand{\ket}[1]{|1\rangle} $$ \newcommand{\braket}[2]{\langle 1|2\rangle} $$ \newcommand{\inner}[2]{\langle 1,2\rangle} $$ \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 } $  Homework (Rotations) Deadline: January 14, 2019Send your solutions to <EMAIL>.Feel free to ask questions by e-mail.  Decision problems on streaming inputs 1. Suppose that you read a series of symbols from an alphabet $ \Sigma $.        For example, $ \Sigma = \{a,b\} $, and your inputs can be $ aaabbbabababababab $ or $ aaaaaaa $ or $ bbbbbba $, etc.2. You may use one or more qubits for solving the given task. 3. At the beginning, each qubit is set to $ \ket{0} $.4. For each symbol, you fix certain operators and apply them to the quantum register whenever you read this symbol.     For example, for each $ a $, you may apply x-gate on each qubit; and, for each $ b $, you may apply z-gate and then h-gate on each qubit.5. After reading whole the input, you make a measurement.     You should make a decision on the given input.         There will be two possible outcomes.    So, you divide all possible outcomes into two sets, and give your decisions accordingly.  Example 1 Let $ \Sigma = \{a\} $.We decide whether the length of the given input is odd or even.We use a single qubit. For each symbol, we apply x-gate.If we observe $ 0 $ (resp., $1$) at the end, we output "even" (resp., "odd"). We test our program on randomly generated 10 strings of length less than 50.<jupyter_code>from qiskit import QuantumRegister, ClassicalRegister, QuantumCircuit, execute, Aer

def parity_check(input):
    qreg =  QuantumRegister(1)
    creg = ClassicalRegister(1)
    mycircuit = QuantumCircuit(qreg,creg)
    for i in range(len(input)):
        mycircuit.x(qreg[0])
    mycircuit.measure(qreg,creg)
    job = execute(mycircuit,Aer.get_backend('qasm_simulator'),shots=100)
    counts = job.result().get_counts(mycircuit)
    return counts

from random import randrange

for i in range(10):
    length = randrange(50)
    input = ""
    for j in range(length):
        input = input + "a"
    counts = parity_check(input)
    
    print("the input is",input)
    print("its length is",length)
    print(counts)
    for key in counts:
        if key=="0": 
            print("the output 'even' is given",counts["0"],"times")
        if key=="1": 
            print("the output 'odd' is given",counts["1"],"times")
    print()<jupyter_output>C:\ProgramData\Anaconda3\lib\site-packages\marshmallow\schema.py:364: ChangedInMarshmallow3Warning: strict=False is not recommended. In marshmallow 3.0, schemas will always be strict. See https://marshmallow.readthedocs.io/en/latest/upgrading.html#schemas-are-always-strict
  ChangedInMarshmallow3Warning<jupyter_text>Example 2 Let $ \Sigma = \{a,b\} $.We decide whether the input contains odd numbers of $a$s and odd numbers of $b$s.We use two qubits. For each $a$, we apply x-gate to the first qubit.For each $b$, we apply x-gate to the second qubit.If we observe $ 11 $ at the end, we output "yes". Otherwise, we output "no". We test our program on randomly generated 20 strings of length less than 40.<jupyter_code>from qiskit import QuantumRegister, ClassicalRegister, QuantumCircuit, execute, Aer


def double_odd(input):
    qreg =  QuantumRegister(2)
    creg = ClassicalRegister(2)
    mycircuit = QuantumCircuit(qreg,creg)
    for i in range(len(input)):
        if input[i]=="a":
            mycircuit.x(qreg[0])
        if input[i]=="b":
            mycircuit.x(qreg[1])
    mycircuit.measure(qreg,creg)
    job = execute(mycircuit,Aer.get_backend('qasm_simulator'),shots=100)
    counts = job.result().get_counts(mycircuit)
    return counts

from random import randrange

for i in range(20):
    length = randrange(40)
    input = ""
    number_of_as=0
    number_of_bs=0
    for j in range(length):
        if randrange(2)==0: 
            input = input + "a"
            number_of_as = number_of_as + 1
        else:
            input = input + "b"
            number_of_bs = number_of_bs + 1
            
    counts = double_odd(input)
    
    print("the input is",input)
    print("the number of as is",number_of_as)
    print("the number of bs is",number_of_bs)
    print(counts)
    number_of_yes = 0
    number_of_no = 0
    for key in counts:
        if key=="11": 
            number_of_yes = counts["11"]
        elif key=="00":
            number_of_no = number_of_no + counts["00"]
        elif key=="01":
            number_of_no = number_of_no + counts["01"]
        elif key=="11":
            number_of_no = number_of_no + counts["10"]
    print("number of yes is",number_of_yes,"and number of no is",number_of_no)
    print()<jupyter_output>the input is abaabbbbababbab
the number of as is 6
the number of bs is 9
{'10': 100}
number of yes is 0 and number of no is 0

the input is bbbbabaaababaababbbbbbbbb
the number of as is 8
the number of bs is 17
{'10': 100}
number of yes is 0 and number of no is 0

the input is abaaabaaaabbaaaaaabbabbaaaaabb
the number of as is 20
the number of bs is 10
{'00': 100}
number of yes is 0 and number of no is 100

the input is bbbbabaaabbbbaaabbabaaabaabaaabbbb
the number of as is 16
the number of bs is 18
{'00': 100}
number of yes is 0 and number of no is 100

the input is bbabaaaaaaabaaabbbbbababbbbbbaabbaaab
the number of as is 18
the number of bs is 19
{'10': 100}
number of yes is 0 and number of no is 0

the input is aababaabbaababaababbbba
the number of as is 12
the number of bs is 11
{'10': 100}
number of yes is 0 and number of no is 0

the input is bbabbbbaaabaabbabbbabbaaba
the number of as is 11
the number of bs is 15
{'11': 100}
number of yes is 100 and number of no is 0

the input[...]<jupyter_text>Task 1 Let $ \Sigma = \{a\} $.You will read an input of length which is a multiple of $ 8 $: $ 8i \in \{8,16,24,\ldots\} $.Use a single qubit and determine whether the multiple ($ i $) is odd or even.For each $a$, you can apply a rotation.Test your program with the inputs of lengths $ 8, 16, 24, 32, 40, 48, 56, 64, 72, 80 $.<jupyter_code>from qiskit import QuantumRegister, ClassicalRegister, QuantumCircuit, execute, Aer
from math import pi
from random import randrange

def quntum_processor(input):
    qreg =  QuantumRegister(1)
    creg = ClassicalRegister(1)
    mycircuit = QuantumCircuit(qreg,creg)
    rotation_angle=pi/16
    for i in range(len(input)):
        mycircuit.ry(2*rotation_angle,qreg[0])
    mycircuit.measure(qreg,creg)
    job = execute(mycircuit,Aer.get_backend('qasm_simulator'),shots=100)
    counts = job.result().get_counts(mycircuit)
    return counts



for i in range(1,11):
    length = 8*(i)
    input = ""
    for j in range(length):
        input = input + "a"
    counts = quntum_processor(input)
    
    print("the input is",input)
    print("its length is",length)
    print(counts)
    for key in counts:
        if key=="0": 
            print("the output 'even' is given",counts["0"],"times")
        if key=="1": 
            print("the output 'odd' is given",counts["1"],"times")
    print()<jupyter_output>the input is aaaaaaaa
its length is 8
{'1': 100}
the output 'odd' is given 100 times

the input is aaaaaaaaaaaaaaaa
its length is 16
{'0': 100}
the output 'even' is given 100 times

the input is aaaaaaaaaaaaaaaaaaaaaaaa
its length is 24
{'1': 100}
the output 'odd' is given 100 times

the input is aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa
its length is 32
{'0': 100}
the output 'even' is given 100 times

the input is aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa
its length is 40
{'1': 100}
the output 'odd' is given 100 times

the input is aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa
its length is 48
{'0': 100}
the output 'even' is given 100 times

the input is aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa
its length is 56
{'1': 100}
the output 'odd' is given 100 times

the input is aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa
its length is 64
{'0': 100}
the output 'even' is given 100 times

the input is aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa[...]<jupyter_text>Task 2 Let $ \Sigma= \{a\} $.Determine whether the length of the input is a multiple of 7 or not in the following manner:1. If it is a multiple of 7, then output "yes" with probability 1.2. If it is not a multiple of 7, then output "yes" with probability less than 1.For each $a$, you can apply a rotation.Test your program with all inputs of lengths less than 29.Determine the inputs for which you output "yes" nearly three times less than the output "no".<jupyter_code>from qiskit import QuantumRegister, ClassicalRegister, QuantumCircuit, execute, Aer
from math import pi
from random import randrange

def quntum_processor(input):
    qreg =  QuantumRegister(1)
    creg = ClassicalRegister(1)
    mycircuit = QuantumCircuit(qreg,creg)
    rotation_angle=pi/7
    for i in range(len(input)):
        mycircuit.ry(2*rotation_angle,qreg[0])
    mycircuit.measure(qreg,creg)
    job = execute(mycircuit,Aer.get_backend('qasm_simulator'),shots=100)
    counts = job.result().get_counts(mycircuit)
    return counts



for i in range(1,29):
    length = i
    input = ""
    for j in range(length):
        input = input + "a"
    counts = quntum_processor(input)
    
    print("the input is",input)
    print("its length is",length)
    print(counts)
    for key in counts:
        if key=="0": 
            print("the output 'yes' is given",counts["0"],"times")
        if key=="1": 
            print("the output 'no' is given",counts["1"],"times")
    if ("0" in counts) & ("1" in counts):
        r=counts["1"]/counts["0"]
        print("The 'no' to 'yes' ratio is ",r)
        if abs(r-3)<0.5:
            print("For this input the output 'yes' is nearly three times less frequent than the output \"no\".")
    print()<jupyter_output>the input is a
its length is 1
{'0': 84, '1': 16}
the output 'yes' is given 84 times
the output 'no' is given 16 times
The 'no' to 'yes' ratio is  0.19047619047619047

the input is aa
its length is 2
{'0': 45, '1': 55}
the output 'yes' is given 45 times
the output 'no' is given 55 times
The 'no' to 'yes' ratio is  1.2222222222222223

the input is aaa
its length is 3
{'0': 7, '1': 93}
the output 'yes' is given 7 times
the output 'no' is given 93 times
The 'no' to 'yes' ratio is  13.285714285714286

the input is aaaa
its length is 4
{'0': 4, '1': 96}
the output 'yes' is given 4 times
the output 'no' is given 96 times
The 'no' to 'yes' ratio is  24.0

the input is aaaaa
its length is 5
{'0': 36, '1': 64}
the output 'yes' is given 36 times
the output 'no' is given 64 times
The 'no' to 'yes' ratio is  1.7777777777777777

the input is aaaaaa
its length is 6
{'0': 88, '1': 12}
the output 'yes' is given 88 times
the output 'no' is given 12 times
The 'no' to 'yes' ratio is  0.13636363636363635
[...]<jupyter_text>Task 3 Write down possible six different rotation angles that would work for Task 2.  Rotations:(Double click to this cell for editing.)1. $ \frac{\pi}{7} $2. $ 8\frac{\pi}{7} $3. $ 15\frac{\pi}{7} $4. $ 22\frac{\pi}{7} $5. $ 29\frac{\pi}{7} $6. $ 36\frac{\pi}{7} $  Task 4 Experimentially test each of these rotations for Task 2.<jupyter_code>from qiskit import QuantumRegister, ClassicalRegister, QuantumCircuit, execute, Aer
from math import pi
from random import randrange

def quntum_processor(input,rotation_angle):
    qreg =  QuantumRegister(1)
    creg = ClassicalRegister(1)
    mycircuit = QuantumCircuit(qreg,creg)
    for i in range(len(input)):
        mycircuit.ry(2*rotation_angle,qreg[0])
    mycircuit.measure(qreg,creg)
    job = execute(mycircuit,Aer.get_backend('qasm_simulator'),shots=100)
    counts = job.result().get_counts(mycircuit)
    return counts

ang_ctr=-1
for ang in [pi/7,8*pi/7,15*pi/7,22*pi/7,29*pi/7,36*pi/7]:
    ang_ctr+=1
    for i in range(1,29):
        length = i
        input = ""
        for j in range(length):
            input = input + "a"
        counts = quntum_processor(input,ang)
    
        print("Roatation angle is ",7*ang_ctr+1,"* pi/7")
        print("the input is",input)
        print("its length is",length)
        print(counts)
        for key in counts:
            if key=="0": 
                print("the output 'yes' is given",counts["0"],"times")
            if key=="1": 
                print("the output 'no' is given",counts["1"],"times")
        if ("0" in counts) & ("1" in counts):
            r=counts["1"]/counts["0"]
            print("The 'no' to 'yes' ratio is ",r)
            if abs(r-3)<0.5:
                print("For this input the output 'yes' is nearly three times less frequent than the output \"no\".")
        print()
    print()
    print()<jupyter_output>Roatation angle is  1 * pi/7
the input is a
its length is 1
{'0': 84, '1': 16}
the output 'yes' is given 84 times
the output 'no' is given 16 times
The 'no' to 'yes' ratio is  0.19047619047619047

Roatation angle is  1 * pi/7
the input is aa
its length is 2
{'0': 40, '1': 60}
the output 'yes' is given 40 times
the output 'no' is given 60 times
The 'no' to 'yes' ratio is  1.5

Roatation angle is  1 * pi/7
the input is aaa
its length is 3
{'0': 5, '1': 95}
the output 'yes' is given 5 times
the output 'no' is given 95 times
The 'no' to 'yes' ratio is  19.0

Roatation angle is  1 * pi/7
the input is aaaa
its length is 4
{'0': 5, '1': 95}
the output 'yes' is given 5 times
the output 'no' is given 95 times
The 'no' to 'yes' ratio is  19.0

Roatation angle is  1 * pi/7
the input is aaaaa
its length is 5
{'0': 43, '1': 57}
the output 'yes' is given 43 times
the output 'no' is given 57 times
The 'no' to 'yes' ratio is  1.3255813953488371

Roatation angle is  1 * pi/7
the input is aaaaaa
its len[...]<jupyter_text>Task 5We can improve the algorihtm for Task 2.Let $ \Sigma= \{a\} $.Determine whether the length of input is a multiple of 91.There are 90 different rotations that you can use.Randomly pick four of these rotations and fix them.Use four qubits. In each qubit, apply one of these rotations.Test your program with all inputs of lengths less than 92.If the input length is 91, then your program should output "yes" with probability 1.If the input length is not 91, then your program should output "yes" with probability less than $ \epsilon < \frac{1}{2}$.Experimentially verify both cases, and also determine the approximate value of $\epsilon$.<jupyter_code>from qiskit import QuantumRegister, ClassicalRegister, QuantumCircuit, execute, Aer
from math import pi
from random import randrange,sample

def quntum_processor(input):
    four_rotations=sample(range(91),4)
    qreg =  QuantumRegister(4)
    creg = ClassicalRegister(4)
    mycircuit = QuantumCircuit(qreg,creg)
    rotation_angle=pi/91
    for i in range(len(input)):
        for ctr_qb in range(4):
            mycircuit.ry(2*four_rotations[ctr_qb]*rotation_angle,qreg[ctr_qb])
    mycircuit.measure(qreg,creg)
    job = execute(mycircuit,Aer.get_backend('qasm_simulator'),shots=100)
    counts = job.result().get_counts(mycircuit)
    return counts


overall_epsilon=0
for i in range(1,92):
    length = i
    input = ""
    for j in range(length):
        input = input + "a"
    counts = quntum_processor(input)
    
    print("the input is",input)
    print("its length is",length)
    print(counts)
    if ("0000" in  counts):
        e=counts["0000"]/100
    else:
        e=0    
    print("The 'yes' relative frequency, estimate of epsilon, is ",e)
    overall_epsilon+=e
        
    print()
print("Average epsilon over all the experiments except the last one is ",(overall_epsilon-1)/90)<jupyter_output>the input is a
its length is 1
{'1001': 61, '0101': 1, '1011': 3, '1101': 2, '0001': 33}
The 'yes' relative frequency, estimate of epsilon, is  0

the input is aa
its length is 2
{'0000': 19, '1010': 5, '1101': 1, '0100': 1, '1000': 53, '1001': 8, '1011': 1, '0001': 4, '1100': 7, '0011': 1}
The 'yes' relative frequency, estimate of epsilon, is  0.19

the input is aaa
its length is 3
{'1111': 19, '0101': 5, '1101': 5, '0111': 10, '1001': 6, '1011': 30, '0001': 5, '0011': 20}
The 'yes' relative frequency, estimate of epsilon, is  0

the input is aaaa
its length is 4
{'1111': 6, '1110': 31, '0110': 17, '1010': 23, '0111': 7, '0010': 10, '1011': 5, '0011': 1}
The 'yes' relative frequency, estimate of epsilon, is  0

the input is aaaaa
its length is 5
{'0101': 1, '0000': 28, '0110': 1, '1010': 7, '0111': 1, '0010': 23, '0100': 2, '1000': 6, '1001': 6, '1011': 4, '0001': 12, '0011': 9}
The 'yes' relative frequency, estimate of epsilon, is  0.28

the input is aaaaaa
its length is 6
{'1111': 1[...]<jupyter_text>Task 6 Repeat Task 5 with five and then six rotations by using five and six qubits, respectively.The value of $ \epsilon $ is expected to decrease if we use more rotations and qubits.<jupyter_code>from qiskit import QuantumRegister, ClassicalRegister, QuantumCircuit, execute, Aer
from math import pi
from random import randrange,sample

def quntum_processor(input,num_qbits):
    k_rotations=sample(range(91),num_qbits)
    qreg =  QuantumRegister(num_qbits)
    creg = ClassicalRegister(num_qbits)
    mycircuit = QuantumCircuit(qreg,creg)
    rotation_angle=pi/91
    for i in range(len(input)):
        for ctr_qb in range(num_qbits):
            mycircuit.ry(2*k_rotations[ctr_qb]*rotation_angle,qreg[ctr_qb])
    mycircuit.measure(qreg,creg)
    job = execute(mycircuit,Aer.get_backend('qasm_simulator'),shots=100)
    counts = job.result().get_counts(mycircuit)
    return counts


for num_qbits in range(5,7):
    overall_epsilon=0
    for i in range(1,92):
        length = i
        input = ""
        for j in range(length):
            input = input + "a"
        counts = quntum_processor(input,num_qbits)
        
        print("Number of qbits is",num_qbits)
        print("the input is",input)
        print("its length is",length)
        print(counts)
        yes_state=""
        for ctr_bit in range(num_qbits):yes_state+="0"
        if (yes_state in counts):
            e=counts[yes_state]/100
        else:
            e=0    
        print("The 'yes' relative frequency, estimate of epsilon, is ",e)
        overall_epsilon+=e
        
        print()
    print("Average epsilon over all the experiments except the last one is ",(overall_epsilon-1)/90)
    print()
    print()
    print()<jupyter_output>Number of qbits is 5
the input is a
its length is 1
{'01111': 1, '00101': 1, '00110': 20, '01101': 1, '00100': 6, '01000': 4, '10110': 3, '11010': 1, '00000': 1, '01100': 10, '01110': 27, '01010': 8, '00111': 3, '00010': 7, '10000': 1, '10010': 3, '11110': 3}
The 'yes' relative frequency, estimate of epsilon, is  0.01

Number of qbits is 5
the input is aa
its length is 2
{'01111': 1, '00001': 20, '00101': 7, '01101': 1, '11011': 2, '11000': 1, '00100': 1, '01000': 1, '01001': 6, '11010': 1, '00000': 1, '01100': 1, '00011': 1, '00111': 1, '10000': 2, '10001': 29, '11101': 4, '10010': 1, '10011': 1, '10101': 3, '11001': 15}
The 'yes' relative frequency, estimate of epsilon, is  0.01

Number of qbits is 5
the input is aaa
its length is 3
{'11101': 14, '01101': 3, '10000': 2, '10001': 2, '11000': 29, '01000': 11, '01001': 2, '11100': 18, '01100': 2, '11001': 17}
The 'yes' relative frequency, estimate of epsilon, is  0

Number of qbits is 5
the input is aaaa
its length is 4
{'00000': 19, '0[...]
{'fraction_non_alphanumeric': 0.1309398604073047, 'fraction_numerical': 0.06592408452050866, 'mean_word_length': 3.45369384713647, 'pattern_counts': {'":': 14, '<': 28, '<?xml version=': 0, '>': 25, 'https://': 1, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 14, 'word_list_counts': {'cursed_substrings.json': 2, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'chain_length': '7', 'dir': 'jupyter-structured-clean-dedup', 'id': '619905', 'license': 'Apache-2.0', 'n_tokens_mistral': 8099, 'n_tokens_neox': 7011, 'n_words': 2535, 'path': 'bronze/.ipynb_checkpoints/R_Dinuls_B96_Homework-checkpoint.ipynb', 'repo_name': 'dilyaraahmetshina/quantum_computings', 'size': '20939'}