<jupyter_start><jupyter_text>Challenge 02: Minimum Hamming Distance using a Quantum AlgorithmThe Hamming distance between two binary strings (with the same number of bits) is defined as the number positions where the bits differ from each other. For example, the Hamming distance between these $6$-bit strings $0$$01$$0$$0$$1$ and $1$$01$$1$$0$$0$ is $3$.A simple way to calculate the Hamming distance between two numbers is to perform a bitwise XOR between them, and count the number of ones in the resulting string:$$ 001001 \oplus 101100 = 100101 \xrightarrow[]{\; \text{count ones} \;} 011 \text{ (3 in base-2)} $$The purpose of this challenge is to develop a quantum algorithm that takes as an input an arbitrary number $m$ of $n$-bit strings, and outputs the two strings with the minimum Hamming distance between them with a resonably high probability. How high? the higher the better.For instance, for the following input of four 4-bit strings: $[0000,1001,1100,1101]$ the algorithm should return strings $[1100,1101]$ since they only differ by one bit.**Level 1:** Start by only considering the cases in which the answer is unique. In other words, assume that all inputs only have one pair of strings that gives the minimum Hamming distance. So inputs such as $[0000,0001,0010,0111]$ don't have to be considered because there are two solutions: $[0000,0001]$ and $[0000,0010]$.**Level 2:** Now consider the case where more than one solution can exist and make sure the algorithm returns each of the possible solutions with equal probability. So, for the example above, the probability of measuring $[0000,0001]$ or $[0000,0010]$ should be close to $50\%$ (inputs with repeated strings should also be considered).**Hint:** Consider looking into some of the "textbook" quantum algorithms (like Deutch-Jozsa (DJ) [1], Bernstein-Vazirani (BV) [2], Grover [3], etc.) to see if this problem can be solved with variations of these. Take for instance this pre-print [4], where a modified version of DJ was used to compute Hamming distances between two strings. Now, keep in mind that in that approach, Hamming weights were calculated using probability distributions (which require multiple runs of the algorithm), and not by amplifying states, as required by this challenge.[1] Deutsch, David, and <NAME>. "Rapid solution of problems by quantum computation." Proceedings of the Royal Society of London. Series A: Mathematical and Physical Sciences 439.1907 (1992): 553-558.[2] <NAME>, and <NAME>. "Quantum complexity theory." SIAM Journal on computing 26.5 (1997): 1411-1473.[3] Grover, <NAME>. , "A fast quantum mechanical algorithm for database search", Proceedings of the 28th Annual ACM Symposium on the Theory of Computing (1996), [arXiv:quant-ph/9605043](https://arxiv.org/abs/quant-ph/9605043)[4] Bravo, <NAME>. "Calculating Hamming distance with the IBM Q Experience." Preprints (2018).<jupyter_code>%matplotlib inline
# Importing standard Qiskit libraries
from qiskit import QuantumCircuit, execute, Aer, IBMQ , QuantumRegister , ClassicalRegister
from qiskit.compiler import transpile, assemble
from qiskit.tools.jupyter import *
from qiskit.visualization import *
from iqx import *

# Loading your IBM Q account(s)
provider = IBMQ.load_account()
import numpy as np
import os
from math import pi
import operator<jupyter_output><empty_output><jupyter_text>Example For this example the goal is to find the minimum distance between the  array=['0000','0001','0010','0111']so I will use the design of the QRAM to get all the values in one overlay, to indicate the positions of each cell in the memory is supported by X gates that through the function 'position' supports the decision of how many X gates are used per cell.<jupyter_code>array=['0000','0001','0010','0111']<jupyter_output><empty_output><jupyter_text>The function converts the cell index into a binary value to automate how many X gates are needed<jupyter_code>def position(inputs,valor):
    lista = []
    a = bin(inputs)[2:] 
    while len(a)<valor:
        a = '0'+a
    a=a[::-1]
    #print(a)
    for i in range(len(a)):
        if a[i] == '1':
            lista.append(i)
    return lista<jupyter_output><empty_output><jupyter_text>The function 'qram' uses the value obtained from the function 'position' to indicate the number of X gates, also, it reads the variable of each cell, when it finds the value 1 it generates a ccx gate on the qubits that are called 'distance_h' and that will serve to find the minimum distance of hamming.<jupyter_code>def qram(qc,address,distance_h,array):
    states = 2**len(array)
    lista =[]
    count = 0
    for i in array:
        lista = position(count,states)
        for k in lista:
            qc.x(address[k])
        for index,j in enumerate(i):
            if j == '1':
                qc.ccx(address[0],address[1],distance_h[index])
        for k in lista:
            qc.x(address[k])
        qc.barrier()
        
        count+=1<jupyter_output><empty_output><jupyter_text>For the realization of this algorithm is from the Bernstein-Vazirani algorithm to find the distances between each of the inputs as an oracle as the grover algorithm to find the minimum value of the hamming distance. Therefore it is important to make the diffuser function for the grover algorithm that aims to amplify the values that meet the conditions of the oracle.<jupyter_code>from IPython.display import Image
Image('ch2.png')
def diffuser(nqubits):
    qc = QuantumCircuit(nqubits)
    # Apply transformation |s> -> |00..0> (H-gates)
    for qubit in range(nqubits):
        qc.h(qubit)
    # Apply transformation |00..0> -> |11..1> (X-gates)
    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)  # multi-controlled-toffoli
    qc.h(nqubits-1)
    # Apply transformation |11..1> -> |00..0>
    for qubit in range(nqubits):
        qc.x(qubit)
    # Apply transformation |00..0> -> |s>
    for qubit in range(nqubits):
        qc.h(qubit)
    # We will return the diffuser as a gate
    U_s = qc.to_gate()
    U_s.name = "$U_s$"
    return U_s<jupyter_output><empty_output><jupyter_text>It generates the hamming function that develops all the process described in the previous figure and using the Bernstein-Vazirani algorithm as an oracle.<jupyter_code>def hamming2(array):
    n=2
    address_1 = QuantumRegister(n)
    address_2 = QuantumRegister(n)
    distance_h = QuantumRegister(len(array[0]))
    reg_oracle= QuantumRegister(1)
    c_1 = ClassicalRegister(n)
    c_2 = ClassicalRegister(n)
    qc = QuantumCircuit(address_1,address_2, distance_h,reg_oracle, c_1, c_2)
   
    qc.x(reg_oracle)
    qc.h(reg_oracle)
    qc.h(address_1)
    qc.h(address_2)
    qc.barrier()
    qram(qc,address_1,distance_h,array)
    qram(qc,address_2,distance_h,array)
        
    
    qc.h(distance_h)
    qc.barrier()
    for i in distance_h:
        qc.cx(i,reg_oracle)
    qc.h(distance_h)
    qc.barrier()
    

    qc.x(distance_h[3])
    qc.mct(distance_h,reg_oracle)

    qc.x(distance_h[3])    
    qc.barrier()    

    qc.x(distance_h[0])

    qc.mct(distance_h,reg_oracle)
    qc.x(distance_h[0])
   
    qc.barrier() 
    
    qc.x(distance_h[2])
    qc.mct(distance_h,reg_oracle)
    qc.x(distance_h[2])
    qc.barrier()
    
    qc.x(distance_h[1])

    qc.mct(distance_h,reg_oracle)
    qc.x(distance_h[1])
   
    qc.barrier() 
    
    qc.h(distance_h)
    qc.barrier()
    for i in distance_h:
        qc.cx(i,reg_oracle)
    qc.h(distance_h)
    qc.barrier()
    
    qram(qc,address_2,distance_h,array)
    qram(qc,address_1,distance_h,array)
    qc.barrier() 
    qc.append(diffuser(2*n),[address_1[0],address_1[1],address_2[0],address_2[1]])
    qc.barrier() 
    qc.x(address_1)
    qc.x(address_2)
    qc.measure([address_1[0], address_1[1],address_2[0], address_2[1]], [c_1[0], c_1[1],c_2[0], c_2[1]])
    qc=qc.reverse_bits()
    return qc<jupyter_output><empty_output><jupyter_text>Quantum circuit resulting<jupyter_code>array2=['0000','0001','0010','0111']
qc = hamming2(array2)
qc.draw(output='mpl')<jupyter_output><empty_output><jupyter_text>The result for level 2 will be given 2 correct solutions, but these have 2 results because the order changes although the answer remains the same, for example [0000,0001] is equal to [0001,0000]. Also, we modified the oracle where we acquire the distances that are equal to 1 as an answer, because it is the minimum distance that can be given, in case it is 0 it means that they are the same so that does not interest. Input ['0000','0001','0010','0111']Expected answers [0000,0001]=[0001,0000] or [0000,0010] = [0010,0000]   The simulation is obtained with all the values that give a distance between the different combinations of two QRAMs that have the same values highlighting the values that have a distance.<jupyter_code>simulator = Aer.get_backend('qasm_simulator')
job = execute(qc, simulator, shots=81920)
result = job.result()
# Returns counts
counts = result.get_counts(qc)
print(counts)
output = max(counts.items(), key=operator.itemgetter(1))[0]
print(output)<jupyter_output>{'00 01': 20590, '00 10': 20361, '01 00': 20491, '10 00': 20478}
00 01<jupyter_text>gives as results the expected values and with the same probability if we consider that each two values represent the same, that is, we have 50% of each of the expected responses.<jupyter_code>outputs =  dict(sorted(counts.items(), key=lambda item: item[1]))

outputs<jupyter_output><empty_output><jupyter_text>Consider:00 01 is equal to [0000,0001]00 10 is equal to [0000,0010]01 00 is equal to [0001,0000]10 00 is equal to [0010,0000]in this case 00 01 and 01 00 represent the same output as 00 10 and 10 00. Therefore, we have a 50% probability of obtaining [0000,0001] and another 50% for [0000,0010], meeting the level 2 objective<jupyter_code>plot_histogram(job.result().get_counts(qc))
result_h = output.split()
index_output = []
for i in result_h:
    index_output.append(int(i, 2))
for j in index_output:
    print(array2[j])<jupyter_output>0010
0000<jupyter_text>Other example To check the level 2 proposal, you have the following entry ['0000','1001','1100','1101']Expected answers [1001,1101]=[1101,1001] or [1100,1101] =[1101,1100]<jupyter_code>array=['0000','1001','1100','1101']
qc = hamming2(array)
qc.draw(output='mpl')
simulator = Aer.get_backend('qasm_simulator')
job = execute(qc, simulator, shots=81920)
result = job.result()
# Returns counts
counts = result.get_counts(qc)
print(counts)
output = max(counts.items(), key=operator.itemgetter(1))[0]
print(output)
outputs =  dict(sorted(counts.items(), key=lambda item: item[1]))
print(outputs)<jupyter_output>{'01 11': 20297, '10 11': 20552, '11 01': 20722, '11 10': 20349}
11 01
{'01 11': 20297, '11 10': 20349, '10 11': 20552, '11 01': 20722}<jupyter_text>Consider:01 11 is equal to [1001,1101]10 11 is equal to [1100,1101]11 01 is equal to [1101,1001]11 10 is equal to [1101,1100]in this case 01 11 and 11 01 represent the same output as 10 11 and 11 01. Therefore, we have a 50% probability of obtaining [1001,1101] and another 50% for [1100,1101].<jupyter_code>plot_histogram(job.result().get_counts(qc))
result_h = output.split()
index_output = []
for i in result_h:
    index_output.append(int(i, 2))
for j in index_output:
    print(array[j])<jupyter_output>1101
1001
{'fraction_non_alphanumeric': 0.10881784647813104, 'fraction_numerical': 0.06806604602142982, 'mean_word_length': 4.422380952380952, 'pattern_counts': {'":': 0, '<': 51, '<?xml version=': 0, '>': 62, 'https://': 1, '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': '12', 'dir': 'jupyter-structured-clean-dedup', 'id': '67884', 'license': 'Apache-2.0', 'n_tokens_mistral': 4245, 'n_tokens_neox': 3576, 'n_words': 1268, 'path': 'challenge-2020.12-dec/maldoalberto/challenge-02.ipynb', 'repo_name': 'zgreco2000/monthly-challenges', 'size': '11415'}