Help us understand the problem. What is going on with this article?

量子コンピュータの量子ゲートで組合せ最適、2020年2月まとめ(QAOA/VQE使い方もフォロー)

はじめに

量子コンピュータで何かしらアプリケーションを作ってみたいという要望がありますが、それには組合せ最適化問題をお勧めしています。教科書に載っている理論はあまり現場で使うことはありません。現実的にはビジネス現場では、行列固有値を求めるアルゴリズムが主流になっていますが、多くの人に馴染みがある問題としては組合せ最適化問題が最適です。

研究用と実用は違う

研究のアルゴリズムと実用のアルゴリズムは違いますので、単純に企業の将来的な活用を把握したい場合には、実用的なアルゴリズムを使わなくてはいけません。

「量子コンピュータ何から手をつけていいのか疑惑に軽く答える(VQEを想定)」
https://qiita.com/YuichiroMinato/items/43d10ceb2c3faf21212a

上記ではVQEというアルゴリズムを使っていますが、VQEを使うかQAOAを使うのがいいと思います。

定式化は01で

定式化とは、上記の記事でもちょっと触れていますが、組合せ最適化問題を+1と-1の値の組合せで表される式に落とし込みます。ただ、課題があります。物理学で使われるイジングモデルは-1,+1を利用しますが、通常の産業用では0と1を計算として利用します(計算基底)。幸い-1と+1は自動的に変換ができますので、01を使っても組合せ最適化問題としては問題がありません。それがこの8年ほど発達してきました。

01で定式化をするのをQUBOと呼びます。QUBOは量子ビットの01を利用できます。係数はまだ名前が確定していませんが、「バイアス」と「ウェイト(結合荷重)」でいいでしょう。定式化で作るのは「コスト関数」と呼びたいと思います。

定式化は社会問題をQUBO形式で、コスト関数を作ることで実現でき、コスト関数は01の値をとる量子ビットに設定するバイアスとウェイトを設定することで実現できます。

この手法は量子コンピュータに限ったことではないので普通の計算に慣れている人でも受け入れられやすいでしょう。

早速プログラミング

今回は前回から少し進んで、

from strangeworks.blueqat import StrangeworksBackend #quantumcomputing.comを利用する時に必要
import numpy as np
from blueqat import Circuit
from blueqat.pauli import X, Y, Z, I
from blueqat.pauli import qubo_bit as q
from blueqat.vqe import AnsatzBase, Vqe

class QubitAnsatz(AnsatzBase):
    def __init__(self, hamiltonian):
        super().__init__(hamiltonian, 4)
        self.step = 1

    def get_circuit(self, params):
        a, b, c, d = params
        return Circuit().ry(a)[0].rz(b)[0].ry(c)[1].rz(d)[1]

cost = -3*q(0)-3*q(1)-2*q(0)*q(1)
cost = cost.to_expr().simplify()
runner = Vqe(QubitAnsatz(cost))
result = runner.run()

print('Result by VQE')
print(runner.ansatz.get_energy(result.circuit, runner.sampler))

# Hamiltonian to matrix
mat = cost.to_matrix()

# Calculate by numpy
print('Result by numpy')
print(np.linalg.eigh(mat)[0][0])

print('Matrix is')
print(mat)

quantumcomputing.comのリンクは、
https://app.quantumcomputing.com/public/projects/gxUVVo

今回のと期待コスト関数は、

cost = -3*q(0)-3*q(1)-2*q(0)*q(1)

明らかにq(0)=1,q(1)=1の時に最小値-3-3-2=-8を取りますね。上記のコスト関数は以前のように-1と+1ではなく、0と1で考えることができるので簡単です。

設定するのは、q(0)とq(1)に-3のバイアスを設定し、q(0)*q(1)に-2のウェイトを設定します。

これをVQEで解くことで、最小値-8が得られます。

ポイントは、

class QubitAnsatz(AnsatzBase):
    def __init__(self, hamiltonian):
        super().__init__(hamiltonian, 4)
        self.step = 1

    def get_circuit(self, params):
        a, b, c, d = params
        return Circuit().ry(a)[0].rz(b)[0].ry(c)[1].rz(d)[1]

となっていて、パラメータをa,b,c,dの4つを用意し、回路も2量子ビットに対応しています。この状態ですと、最適化するパラメータはN量子ビットに対して、2N必要になりそうです。

Result by VQE
-7.981654210576551
Result by numpy
-8.0
Matrix is
[[ 0.+0.j  0.+0.j  0.+0.j  0.+0.j]
 [ 0.+0.j -3.+0.j  0.+0.j  0.+0.j]
 [ 0.+0.j  0.+0.j -3.+0.j  0.+0.j]
 [ 0.+0.j  0.+0.j  0.+0.j -8.+0.j]]

あとは、定式化の方法を工夫して覚えることになります。

QAOA

上記のVQEは行列の固有値を求めるだけです。組合せ最適化問題では定式化にpauli-Zしか使わないので、QAOAというアルゴリズムでも解くことができます。

class QaoaAnsatz(AnsatzBase):
    def __init__(self, hamiltonian, step=1, init_circuit=None):
        super().__init__(hamiltonian, step * 2)
        self.hamiltonian = hamiltonian.to_expr().simplify()
        if not self.check_hamiltonian():
            raise ValueError("Hamiltonian terms are not commutable")

        self.step = step
        self.n_qubits = self.hamiltonian.max_n() + 1
        if init_circuit:
            self.init_circuit = init_circuit
            if init_circuit.n_qubits > self.n_qubits:
                self.n_qubits = init_circuit.n_qubits
        else:
            self.init_circuit = Circuit(self.n_qubits).h[:]
        self.init_circuit.make_cache()
        self.time_evolutions = [term.get_time_evolution() for term in self.hamiltonian]

    def check_hamiltonian(self):
        """Check hamiltonian is commutable. This condition is required for QaoaAnsatz"""
        return self.hamiltonian.is_all_terms_commutable()

    def get_circuit(self, params):
        c = self.init_circuit.copy()
        betas = params[:self.step]
        gammas = params[self.step:]
        for beta, gamma in zip(betas, gammas):
            beta *= np.pi
            gamma *= 2 * np.pi
            for evo in self.time_evolutions:
                evo(c, gamma)
            c.rx(beta)[:]
        return c

中身のコードを見てみると、時間発展+変分パラメータ設定を組み合わせており、ちょっと複雑なことをしているのが分かります。QAOAを詳しく知りたい方は是非その辺りのキーワードで検索をしてみてください。

最後にほぼSDK側で処理されたQAOAを使った計算をしてみます。
設定するのはcostです。

from strangeworks.blueqat import StrangeworksBackend #quantumcomputing.comの時だけ必要
from blueqat import vqe
from blueqat.pauli import qubo_bit as q

cost = -3*q(0)-3*q(1)-2*q(0)*q(1)
step = 2

result = vqe.Vqe(vqe.QaoaAnsatz(cost, step)).run()
print(result.most_common(12))

回路はちょっと複雑になりました。

スクリーンショット 2020-02-15 16.56.23.png

答えは、

(((1, 1), 0.9922852962030535), ((0, 0), 0.0047331664261775755), ((1, 0), 0.0014907686853841205), ((0, 1), 0.0014907686853841168))

https://app.quantumcomputing.com/public/projects/XMtzWE

最初の数字が答えの候補で、次の数字はそれが現れる確率です。11が最大確率になっているのでOKでした。

組合せ最適化問題は難しくない

ということで、01の量子ビットでの定式化をして、あとはツールに任せればいいというのが分かりました。最初はツールに任せて定式化を頑張りましょう!

Why not register and get more from Qiita?
  1. We will deliver articles that match you
    By following users and tags, you can catch up information on technical fields that you are interested in as a whole
  2. you can read useful information later efficiently
    By "stocking" the articles you like, you can search right away
Comments
No comments
Sign up for free and join this conversation.
If you already have a Qiita account
Why do not you register as a user and use Qiita more conveniently?
You need to log in to use this function. Qiita can be used more conveniently after logging in.
You seem to be reading articles frequently this month. Qiita can be used more conveniently after logging in.
  1. We will deliver articles that match you
    By following users and tags, you can catch up information on technical fields that you are interested in as a whole
  2. you can read useful information later efficiently
    By "stocking" the articles you like, you can search right away
ユーザーは見つかりませんでした