進捗のようなもの

やったこと書きます

IBM Quantum Challenge 2019 振り返り(第3週)

第3週の課題を振り返っていきます。

第3週 GroverアルゴリズムでMAXCUT問題

量子ゲートをグラフに応用した課題です。最終週への基礎を固める問題にもなっています。

量子コンピュータ初心者として、グラフ問題は量子アニーリングで解く印象を持っていましたが、量子ゲートでも解けました。 この問題を量子アニーリングでの実装にチャレンジするのも面白いかもしれないですね。

第3週の課題はこちら↓

github.com

今回も解答例の量子回路を参考に、コストが小さくなるように回路を実装していきました。

解答

# パッケージのインポート
from qiskit import QuantumRegister, ClassicalRegister, QuantumCircuit
from qiskit import IBMQ, Aer, execute
import numpy as np
from qiskit.tools.visualization import plot_histogram

#cutedge判定 (XORと同じ)
def ccheck(a, b, c): 
    qc.cx(q[a], q[c]) 
    qc.cx(q[b], q[c])
   
#inverse cutedge checker
def iccheck(a, b, c): 
    qc.cx(q[b], q[c])
    qc.cx(q[a], q[c]) 

# 4bitのMulti-controlled NOTゲート
# 量子コスト削減ver. mct
# aqは補助量子ビット 
def mct(cq, aq, tq):
    qc.u2(1/4*np.pi, np.pi, aq)
    qc.cx(cq[1],aq)
    qc.u1(-1/4*np.pi, aq)
    qc.cx(cq[0],aq)
    qc.u1(1/4*np.pi, aq)
    qc.cx(cq[1],aq)
    qc.u3(1/2*np.pi,0,3/4*np.pi, aq)
    qc.ccx(cq[2],aq,tq)
    qc.u2(1/4*np.pi, np.pi, aq)
    qc.cx(cq[1],aq)
    qc.u1(-1/4*np.pi, aq)
    qc.cx(cq[0],aq)
    qc.u1(1/4*np.pi, aq)
    qc.cx(cq[1],aq)
    qc.u3(1/2*np.pi,0,3/4*np.pi, aq)

# 量子回路の準備
q = QuantumRegister(11)
c = ClassicalRegister(4)
qc = QuantumCircuit(q,c)
ite = 2 #number of iteration

# 量子回路の初期化
qc.h(q[0:4])
qc.u3(3/2*np.pi, 0, 0, q[8])

# グローバーのアルゴリズム
for i in range(ite):
#oracle part
    ccheck(0,1,4)
    ccheck(0,2,5)
    ccheck(0,3,6) 
    mct([q[4],q[5],q[6]], q[7] , q[8])
    iccheck(0,3,6)
    iccheck(0,2,5)
    iccheck(0,1,4)
#diffusion part
    qc.u3(3/2*np.pi, 0, np.pi, q[0:4])
    qc.h(q[3])
    mct([q[0],q[1],q[2]], q[7] , q[3])
    qc.h(q[3])
    qc.u3(3/2*np.pi, 0, 0, q[0:4])
qc.barrier()
qc.measure(q[0:4], c[0:4])

# 量子回路の実行
backend = Aer.get_backend('qasm_simulator')
job = execute(qc, backend, shots=100000)
result = job.result()
count =result.get_counts()
qc.draw(output='mpl')

f:id:SJSY:20191110103010p:plain

# 結果の表示
print(count)
plot_histogram(count)

f:id:SJSY:20191110104259p:plain

{'1100': 392, '0011': 395, '1001': 419, '0101': 381, '1000': 407, '0010': 390, '0111': 399, '1010': 429, '1111': 379, '0100': 369, '0000': 418, '0001': 46758, '1011': 401, '0110': 385, '1101': 389, '1110': 47689}

|1000>と|0111>の確率が最大となっています。

# 量子回路のコスト計算
from qiskit.transpiler import PassManager
from qiskit.transpiler.passes import Unroller
pass_ = Unroller(['u3', 'cx'])
pm = PassManager(pass_)
new_circuit = pm.run(qc) 
print(new_circuit.count_ops())
cost = new_circuit.count_ops()['u3'] + 10 * new_circuit.count_ops()['cx']
print(cost)
OrderedDict([('u3', 93), ('cx', 72), ('measure', 4), ('barrier', 1)])
813

コストは813で、解答例846よりもコスト小さく実装できました。

IBM Quantum Challenge 2019 関連

第1週はこちら

sjsy.hatenablog.com

第2週はこちら sjsy.hatenablog.com