Japanese
言語
English
Japanese
German
Korean
Portuguese, Brazilian
French
Table of Contents
  • Docs >
  • 教科書的なアルゴリズムと Shor のアルゴリズム
Shortcuts

注釈

このページは `tutorials/algorithms/09_textbook_algorithms.ipynb`__ から生成されました。

IBM Quantum lab でインタラクティブに実行します。

教科書的なアルゴリズムと Shor のアルゴリズム

Qiskit には Deutsch-Jozsa のアルゴリズム, Bernstein-Vazirani のアルゴリズム, Simon のアルゴリズム などの、よく知られている教科書的な量子アルゴリズムの実装が含まれています。

Qiskit には Shor のアルゴリズム の実装があります。

上記の参照先では回路の配置と詳細な説明を行っていますが、このノートブックでは Qiskit であらかじめ構築されたアルゴリズムの例を示しているので、実験や教育の目的で用いることができます。

[1]:

import math
import numpy as np
from qiskit import BasicAer
from qiskit.aqua import QuantumInstance
from qiskit.aqua.algorithms import BernsteinVazirani, DeutschJozsa, Simon, Shor
from qiskit.aqua.components.oracles import TruthTableOracle

Deutsch-Jozsa のアルゴリズム

まず Deutsch-Jozsa のアルゴリズム から始めてみましょう。これは関数が入力として与えられたときに、その関数が balanced なのか constant なのかの判定ができるものとなっています。 Qiskit では、真理値表から作成したオラクルを用いてその実験を行うことが可能です。例えば以下のように、 TruthTableOracle インスタンスを作成することができます。

[2]:

bitstr = '11110000'
oracle = TruthTableOracle(bitstr)

このように、真理値表は表内の全てのエントリーの値を含む bitstr で指定されます。長さは \(8\) となっているので、対応する真理値表は \(3\) ビットの入力から構成されています。もちろんこの真理値表は、値の半分が \(1\) 、 残りの半分は \(0\) であることから、 balanced 関数を表していることがわかります。

It might seem like a moot point running Deutsch-Jozsa on a truthtable as the function outputs are literally listed as the truthtable’s values. The intention is to create an oracle circuit whose groundtruth information is readily available to us but obviously not to the quantum Deutsch-Jozsa algorithm that is to act upon the oracle circuit. In more realistic situations, the oracle circuit would be provided as a blackbox to the algorithm.

TruthTableOracle インスタンスでエンコードされた関数に対応する回路を調べることができます。

[3]:

oracle.circuit.draw(output='mpl')

[3]:
../../_images/tutorials_algorithms_09_textbook_algorithms_5_0.png

見ての通り、 \(v_i\) は三つの入力ビットに、 \(o_0\) はオラクルの出力ビットに、 \(a_0\) は補助ビットにそれぞれ対応しています。

次に、オラクルを用いて DeutschJozsa インスタンスを作成し、実行して結果を確認します。

[4]:

dj = DeutschJozsa(oracle)
backend = BasicAer.get_backend('qasm_simulator')
result = dj.run(QuantumInstance(backend, shots=1024))
print(f'The truth table {bitstr} represents a \'{result["result"]}\' function.')

The truth table 11110000 represents a 'balanced' function.

もちろん、以下のように定数関数の例を用意することもできます。

[5]:

bitstr = '1' * 16
oracle = TruthTableOracle(bitstr)
dj = DeutschJozsa(oracle)
backend = BasicAer.get_backend('qasm_simulator')
result = dj.run(QuantumInstance(backend, shots=1024))
print(f'The truth table {bitstr} represents a \'{result["result"]}\' function.')

The truth table 1111111111111111 represents a 'constant' function.

Bernstein-Vazirani のアルゴリズム

次に `Bernstein-Vazirani のアルゴリズム<https://qiskit.org/documentation/stubs/qiskit.aqua.algorithms.BernsteinVazirani.html>`__ を用いて、隠された文字列の発見を試みます。ここでも例のために TruthTableOracle インスタンスを作成します。

[6]:

bitstr = '00111100'
oracle = TruthTableOracle(bitstr)

このように、真理値表は表内の全てのエントリーの値を含む bitstr で指定されます。長さは \(8\) となっているので、対応する真理値表は \(3\) ビットの入力から構成されています。真理値表は以下のように関数のマッピングを表しています。

  • \(\mathbf{a} \cdot 000 \mod 2 = 0\)

  • \(\mathbf{a} \cdot 001 \mod 2 = 0\)

  • \(\mathbf{a} \cdot 010 \mod 2 = 1\)

  • \(\mathbf{a} \cdot 011 \mod 2 = 1\)

  • \(\mathbf{a} \cdot 100 \mod 2 = 1\)

  • \(\mathbf{a} \cdot 101 \mod 2 = 1\)

  • \(\mathbf{a} \cdot 110 \mod 2 = 0\)

  • \(\mathbf{a} \cdot 111 \mod 2 = 0\)

目標は、全ての内積方程式を満たすビット列 \(\mathbf{a}\) を見つけることです。

もう一度 TruthTableOracle インスタンスでエンコードされたバイナリ関数に対応するオラクル回路を見てみましょう。

[7]:

oracle.circuit.draw(output='mpl')

[7]:
../../_images/tutorials_algorithms_09_textbook_algorithms_13_0.png

ここでも \(v_i\) は三つの入力ビットに、 \(o_0\) はオラクルの出力ビットに、 \(a_0\) は補助ビットにそれぞれ対応しています。

まず 正解 \(\mathbf{a}\) を古典的に計算してみましょう。

[8]:

a_bitstr = ""
num_bits = math.log2(len(bitstr))
for i in reversed(range(3)):
    bit = bitstr[2 ** i]
    a_bitstr += bit
print(f'The groundtruth result bitstring is {a_bitstr}.')

The groundtruth result bitstring is 110.

次に、オラクルを使って BernsteinVazirani インスタンスを作成し、それを実行して結果を正解と照合します。

[9]:

bv = BernsteinVazirani(oracle)
backend = BasicAer.get_backend('qasm_simulator')
result = bv.run(QuantumInstance(backend, shots=1024))
print(f'The result bitstring computed using Bernstein-Vazirani is {result["result"]}.')
assert(result['result'] == a_bitstr)

The result bitstring computed using Bernstein-Vazirani is 110.

Simon のアルゴリズム

Simon のアルゴリズム によって、 Simon の問題 を解いてみましょう。改めて例のために TruthTableOracle インスタンスを作成していますが、ここでの構造は異なる形式を取っています。

[10]:

bitmaps = [
    '01101001',
    '10011001',
    '01100110'
]
oracle = TruthTableOracle(bitmaps)

このように、真理値表は長さ 8 のビット列 3 つによって指定されており、それぞれが表の出力列に対する全てのエントリーの値を含んでいます。各ビット列の長さは \(8\) なので、真理値表は \(3\) ビットの入力をもちます。また \(3\) つのビット列があるので、真理値表は \(3\) ビットの出力をもちます。

真理値で表される関数 \(f\) は、1 対 1 か 2 対 1 のどちらかであることが保証されています。我々の目的は、そのどちらであるかを決定することです。 2 対 1 の場合には、 \(\forall \mathbf{x},\mathbf{y}\): \(\mathbf{x} \oplus \mathbf{y} = \mathbf{s}\) iff \(f(\mathbf{x}) = f(\mathbf{y})\) を満たすマスク \(\mathbf{s}\) を計算する必要があります。 \(f\) が 1 対 1 ならば、明らかに対応するマスクは \(\mathbf{s} = \mathbf{0}\) となります。

まず 正解のマスク \(\mathbf{s}\) を古典的に計算してみましょう。

[11]:

def compute_mask(input_bitmaps):
    vals = list(zip(*input_bitmaps))[::-1]
    def find_pair():
        for i in range(len(vals)):
            for j in range(i + 1, len(vals)):
                if vals[i] == vals[j]:
                    return i, j
        return 0, 0

    k1, k2 = find_pair()
    return np.binary_repr(k1 ^ k2, int(np.log2(len(input_bitmaps[0]))))

mask = compute_mask(bitmaps)
print(f'The groundtruth mask is {mask}.')

The groundtruth mask is 011.

[12]:

simon = Simon(oracle)
backend = BasicAer.get_backend('qasm_simulator')
result = simon.run(QuantumInstance(backend, shots=1024))
print(f'The mask computed using Simon is {result["result"]}.')
assert(result['result'] == mask)

The mask computed using Simon is 011.

また 1 対 1 関数を表す真理値表 (対応するマスクは \(\mathbf{0}\) ) は、以下のように手軽に試すこともできます。

[13]:

bitmaps = [
    '00011110',
    '01100110',
    '10101010'
]
mask = compute_mask(bitmaps)
print(f'The groundtruth mask is {mask}.')

oracle = TruthTableOracle(bitmaps)
simon = Simon(oracle)
result = simon.run(QuantumInstance(backend, shots=1024))
print(f'The mask computed using Simon is {result["result"]}.')
assert(result['result'] == mask)

The groundtruth mask is 000.
The mask computed using Simon is 000.

Shor の素因数分解アルゴリズム

Shor の素因数分解アルゴリズム は最もよく知られた量子アルゴリズムの一つであり、入力された整数 \(N\) の素因数を多項式時間で求めます。 Qiskit でのアルゴリズムの実装では、以下のように素因数分解する整数を与えるだけで実行できます。

[14]:

N = 15
shor = Shor(N)
backend = BasicAer.get_backend('qasm_simulator')
quantum_instance = QuantumInstance(backend, shots=1024)
result = shor.run(quantum_instance)
print(f"The list of factors of {N} as computed by the Shor's algorithm is {result['factors'][0]}.")

The list of factors of 15 as computed by the Shor's algorithm is [3, 5].

注: Shor のアルゴリズムのこの実装は、\(n\) を二進表示された入力整数のビット数として、 \(4n + 2\) 量子ビット用いています。したがって実際には今のところ、小さな整数の素因数分解に限定されています。上記の N の値があたえられているので、以下に \(4n +2\) を計算し、実際の回路サイズを確認します。

[15]:

print(f'Computed of qubits for circuit: {4 * math.ceil(math.log(N, 2)) + 2}')
print(f'Actual number of qubits of circuit: {shor.construct_circuit().num_qubits}')

Computed of qubits for circuit: 18
Actual number of qubits of circuit: 18

[16]:

import qiskit.tools.jupyter
%qiskit_version_table
%qiskit_copyright

Version Information

Qiskit SoftwareVersion
Qiskit0.23.0
Terra0.16.0
Aer0.7.0
Ignis0.5.0
Aqua0.8.0
IBM Q Provider0.11.0
System information
Python3.6.1 |Continuum Analytics, Inc.| (default, May 11 2017, 13:09:58) [GCC 4.4.7 20120313 (Red Hat 4.4.7-1)]
OSLinux
CPUs1
Memory (Gb)5.827335357666016
Sun Nov 08 16:49:50 2020 EST

This code is a part of Qiskit

© Copyright IBM 2017, 2020.

This code is licensed under the Apache License, Version 2.0. You may
obtain a copy of this license in the LICENSE.txt file in the root directory
of this source tree or at http://www.apache.org/licenses/LICENSE-2.0.

Any modifications or derivative works of this code must retain this
copyright notice, and modified files need to carry a notice indicating
that they have been altered from the originals.

© Copyright 2021, Qiskit Development Team. 最終更新: 2021/06/04

Built with Sphinx using a theme provided by Read the Docs.