from IPython.display import Image, display
Image('lights_out_prob.png')

Image('lights_out_circuit.jpg')

from qiskit import QuantumCircuit, ClassicalRegister, QuantumRegister
tile = QuantumRegister(9)
flip = QuantumRegister(9)
oracle = QuantumRegister(1)
auxiliary = QuantumRegister(7)
result = ClassicalRegister(9)
#26 qubit
qc = QuantumCircuit(tile, flip, oracle, auxiliary, result)

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

def map_board(lights, qc, qr):
    j = 0
    for i in lights:
        if i==1:
            qc.x(qr[j])
            j+=1
        else:
            j+=1

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

    qc.h(flip[0:10])
    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])

initialize()

for i in range(17):
    # oracle
    flip_tile(qc,flip,tile)
    
    qc.x(tile[0:9])
    qc.mct(tile[0:9], oracle[0], auxiliary[0:7], mode='basic')
    qc.x(tile[0:9])
    
    flip_tile(qc,flip,tile)
    
    # diffusion
    qc.h(flip)
    qc.x(flip)
    qc.h(flip[8])
    qc.mct(flip[0:8], flip[8], auxiliary[0:7], mode='basic')
    qc.h(flip[8])
    qc.x(flip)
    qc.h(flip)

# Uncompute
qc.h(oracle[0])
qc.x(oracle[0])
# Measuremnt
qc.measure(flip,result)

# Make the Out put order the same as the input.
qc = qc.reverse_bits() 

from qiskit.transpiler import PassManager
from qiskit.transpiler.passes import Unroller

# Unroll the circuit
pass_ = Unroller(['u3', 'cx'])
pm = PassManager(pass_)
new_circuit = pm.run(qc)

# obtain gates
gates=new_circuit.count_ops()
print(gates)

%%time
from qiskit import IBMQ, execute
provider = IBMQ.load_account()
backend = provider.get_backend('ibmq_qasm_simulator')
job = execute(qc, backend=backend, shots=8000, seed_simulator=12345, backend_options={"fusion_enable":True})
result = job.result()
count = result.get_counts()

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

Image('lights_out_optimal.png')

Image('lights_out_optimal_circuit.jpg')

tile = QuantumRegister(9)
flip = QuantumRegister(9)
oracle = QuantumRegister(1)
auxiliary = QuantumRegister(1)
result = ClassicalRegister(9)
# 20 qubit
qc = QuantumCircuit(tile, flip, oracle, auxiliary, result)

# Initialize
def initialize_smart(l,qc,tile):
    map_board(l, qc, tile)
    qc.h(flip[:3])
    qc.x(oracle[0])
    qc.h(oracle[0])

def flip_1(qc,flip,tile):
    # push 0
    qc.cx(flip[0], tile[0])
    qc.cx(flip[0], tile[1])
    qc.cx(flip[0], tile[3])
    # push 1
    qc.cx(flip[1], tile[0])
    qc.cx(flip[1], tile[1])
    qc.cx(flip[1], tile[2])
    qc.cx(flip[1], tile[4])
    # push 2
    qc.cx(flip[2], tile[1])
    qc.cx(flip[2], tile[2])
    qc.cx(flip[2], tile[5]) 
    
def inv_1(qc,flip,tile):
    # copy 0,1,2
    qc.cx(tile[0], flip[3])
    qc.cx(tile[1], flip[4])
    qc.cx(tile[2], flip[5])
    
def flip_2(qc,flip,tile):
    # apply flip[3,4,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])
    
def inv_2(qc,flip,tile1):
    # copy 3,4,5
    qc.cx(tile[3], flip[6])
    qc.cx(tile[4], flip[7])
    qc.cx(tile[5], flip[8])
    
def flip_3(qc,flip,tile):
    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 lights_out_oracle(qc,tile,oracle,auxiliary):
    qc.x(tile[6:9])
    qc.mct(tile[6:9], oracle[0], auxiliary, mode='basic')
    qc.x(tile[6:9])
    
def diffusion(qc,flip):
    qc.h(flip[:3])
    qc.x(flip[:3])
    qc.h(flip[2])
    qc.ccx(flip[0],flip[1],flip[2])
    qc.h(flip[2])
    qc.x(flip[:3])
    qc.h(flip[:3])

initialize_smart(lights,qc,tile)

for i in range(2):
    flip_1(qc,flip,tile)
    inv_1(qc,flip,tile)
    flip_2(qc,flip,tile)
    inv_2(qc,flip,tile)
    flip_3(qc,flip,tile)
    
    lights_out_oracle(qc,tile,oracle,auxiliary)
    
    flip_3(qc,flip,tile)
    inv_2(qc,flip,tile)
    flip_2(qc,flip,tile)
    inv_1(qc,flip,tile)
    flip_1(qc,flip,tile)
    
    diffusion(qc,flip)
    
# Uncompute
qc.h(oracle[0])
qc.x(oracle[0])

# get the whole solution from the top row of the solution
# If you get a solution, you don't need to erase the board, so you don't need the flip_3 function.
flip_1(qc,flip,tile)
inv_1(qc,flip,tile)
flip_2(qc,flip,tile)
inv_2(qc,flip,tile)

# Measuremnt
qc.measure(flip,result)

# Make the Out put order the same as the input.
qc = qc.reverse_bits() 

# Unroll the circuit
pass_ = Unroller(['u3', 'cx'])
pm = PassManager(pass_)
new_circuit = pm.run(qc) 

# obtain gates
gates=new_circuit.count_ops()
print(gates)

%%time
backend = provider.get_backend('ibmq_qasm_simulator')
job = execute(qc, backend=backend, shots=8000, seed_simulator=12345, backend_options={"fusion_enable":True})
result = job.result()
count = result.get_counts()

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