Grover's Algorithm: Difference between revisions

Revision as of 14:42, 27 November 2020

Introduction

Theory

Oracle Function

Amplitude Amplification

The uniform superposition: $|u\rangle =H^{\otimes n}|0\rangle ^{n}$ , where $H$ is the Hadamard gate.

Apply the oracle reflection $U_{w}|u\rangle =|u'\rangle$ .

Apply an other reflection about the state $|u\rangle$ , also $U_{u}=2|u\rangle \langle u|-1$ . Thus we are at state $U_{u}U_{w}|u>$ . This amplifies by two the amplitude of state $|w\rangle$ .

Repeat $t$ times, where $t\approx {\sqrt {N}}$ .

Application: Lights Out

We solve the $3\times 3$ tiling game using superposition (instead of Gaussian elimination). The algorithm finds the N-qubit for which the initial state becomes zero.

First, the numbering system is shown below:

0	1	2
3	4	5
6	7	8

Second, we need a function that flips the lights: By pressing 0 the light in cells {1,3} will toggle. Thus the toggle mapping is:

0 -> {0, 1, 3}
1 -> {0, 1, 2, 4}
2 -> {1, 2, 5}
3 -> {0, 3, 4, 6}
4 -> {1, 3, 4, 5, 7}
5 -> {2, 4, 5, 8}
6 -> {3, 6, 7}
7 -> {4, 6, 7, 8}
8 -> {5, 7, 8}

The diffusion (Amplification) part is the most difficult.

Solution space is $2^{9}=512$ , the optimal number of iteration is about <math>\frac{\pi}{4} \sqrt{2^9} - \frac{1}{2} \approx 17.3 \approx 17<math>.

lights = [0, 0, 0, 
          0, 1, 1, 
          0, 1, 0]

def map_board(lights, qc, qr):
    j = 0
    for i in lights:
        if i==1:
            qc.x(qr[j])
            j+=1
        else:
            j+=1
            
            
from qiskit import QuantumCircuit, ClassicalRegister, QuantumRegister
tile = QuantumRegister(9)
flip = QuantumRegister(9)
oracle = QuantumRegister(1)
result = ClassicalRegister(9)
#19=9+9+1 qubit + 4bit
qc = QuantumCircuit(oracle, tile, flip, result)

def initialize():
    map_board(lights, qc, tile)

    qc.h(flip[:])
    
    qc.x(oracle[0])
    qc.h(oracle[0])
    
    

# Subroutine for oracle
# Calculate what the light state will be after pressing each solution candidate. 
def flip_tile(qc,flip,tile):
    qc.cx(flip[0], tile[0])
    qc.cx(flip[0], tile[1])
    qc.cx(flip[0], tile[3])
    
    qc.cx(flip[1], tile[0])
    qc.cx(flip[1], tile[1])
    qc.cx(flip[1], tile[2])
    qc.cx(flip[1], tile[4])
    
    qc.cx(flip[2], tile[1])
    qc.cx(flip[2], tile[2])
    qc.cx(flip[2], tile[5])
    
    qc.cx(flip[3], tile[0])
    qc.cx(flip[3], tile[3])
    qc.cx(flip[3], tile[4])
    qc.cx(flip[3], tile[6])
    
    qc.cx(flip[4], tile[1])
    qc.cx(flip[4], tile[3])
    qc.cx(flip[4], tile[4])
    qc.cx(flip[4], tile[5])
    qc.cx(flip[4], tile[7])
    
    qc.cx(flip[5], tile[2])
    qc.cx(flip[5], tile[4])
    qc.cx(flip[5], tile[5])
    qc.cx(flip[5], tile[8])
    
    qc.cx(flip[6], tile[3])
    qc.cx(flip[6], tile[6])
    qc.cx(flip[6], tile[7])
    
    qc.cx(flip[7], tile[4])
    qc.cx(flip[7], tile[6])
    qc.cx(flip[7], tile[7])
    qc.cx(flip[7], tile[8])
    
    qc.cx(flip[8], tile[5])
    qc.cx(flip[8], tile[7])
    qc.cx(flip[8], tile[8])
    
    
def all_zero(qc, tile):
    qc.x(tile[0:9])
    qc.mct(tile[0:9], oracle[0])
    qc.x(tile[0:9])
    
    
# create the circuit
initialize()
qc.barrier()

#Solution space is 2^9=512, the optimal number of iteration is about $\frac{\pi}{4} \sqrt{2^9} - \frac{1}{2} \risingdotseq 17.3$, so try it $3$ times.

# the number of iteration is 3
for i in range(17):
    # oracle
    flip_tile(qc,flip,tile)
    
    qc.barrier()
    
    all_zero(qc, tile)
    
    qc.barrier()
    
    # U^dagger of flip_tile function is flip_tile itself.
    flip_tile(qc,flip,tile)
    
    qc.barrier()
    
    # diffusion
    qc.h(flip)
    qc.x(flip)
    qc.h(flip[8])
    qc.mct(flip[0:8], flip[8])
    qc.h(flip[8])
    qc.x(flip)
    qc.h(flip)
    qc.barrier()



# Uncompute
qc.h(oracle[0])
qc.x(oracle[0])
qc.barrier()

# Measurement
qc.measure(flip,result)
qc.barrier()
# Make the Out put order the same as the input.
qc = qc.reverse_bits()


from qiskit import execute, Aer

backend = Aer.get_backend('statevector_simulator')

job = execute(qc,backend)

result = job.result()

count = result.get_counts()
score_sorted = sorted(count.items(), key=lambda x:x[1], reverse=True)
final_score = score_sorted[0:20]
print( final_score )