Korean
언어
English
Japanese
German
Korean
Portuguese, Brazilian
French
Table of Contents
  • Docs >
  • 사용 지침서와 쇼어 알고리즘
Shortcuts

참고

이 페이지는 tutorials/algorithms/09_textbook_algorithms.ipynb 에서 생성되었다.

IBM 퀀텀 랩 에서 대화식으로 실행하시오.

사용 지침서와 쇼어 알고리즘

키스킷에서는 Deutsch-Jozsa algorithm, Bernstein-Vazirani algorithm 및 Simon’s algorithm 과 같이 잘 알려진 양자 알고리즘들을 구현해두어 포함하고 있다.

키스킷에는 Shor’s algorithm 이 구현되어 있다.

이전 참조들은 회로들의 상세한 설명들 및 build-out of circuits를 가지는 반면, 이 노트북은 실험 및 교육 목적으로 사용할 수 있는 키스킷에서 사전에 구현된 알고리즘들을 예로 들어 설명한다.

[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) 알고리즘

입력과 같은 함수가 주어졌을때, 함수가 'balanced' 인지 'constant' 인지를 결정할 수 있는`Deutsch-Jozsa algorithm <https://qiskit.org/documentation/stubs/qiskit.aqua.algorithms.DeutschJozsa.html>`__ 알고리즘 부터 시작해 보자. 진리표에서 생성된 오라클을 사용하여 키스킷에서 실험할 수 있다. 예를 들어, 다음과 같이 TruthTableOracle 인스턴스를 만들 수 있다.

[2]:

bitstr = '11110000'
oracle = TruthTableOracle(bitstr)

보여지는 바와 같이, 진리표는 테이블의 모든 항목 값을 포함하는 bitstr 로 지정된다. 길이가 \(8\) 이므로 해당 진리표는 \(3\) 입력 비트이다. 물론 값의 절반은 \(1\) 이고 나머지 절반은 \(0\) 이므로 이 진리표가 'balanced' 함수를 나타냄을 알 수 있다.

함수 출력이 문자 그대로 트루 테이블의 값으로 나열되어 있기 때문에 진리표에 있는 도이치-조사를 실행하는 것처럼 보일 수도 있다. 그 의도는, 그 근거 정보가 우리는 쉽게 알수 있지만 oracle 회로에 작용하는 quantum Deutsch-Jozsa 알고리즘에는 명백하지 않은 oracle 회로를 생성하기 위한 것이다. 보다 현실적인 상황에서, oracle 회로는 알고리즘에 대한 블랙박스로서 제공될 것이다.

위에서는 TruthTableOracle` 인스턴스에서 인코딩된 기능에 해당하는 회로를 검사할 수 있다.

[3]:

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

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

보여지는 바와 같이, \(v_i\) 는 3 개의 입력 비트에 대응하며; \(o_0\) 는 오라클의 출력 큐비트이고, \(a_0\) 는 보조 큐비트(ancilla qubit)이다.

다음으로, 우리는 단순히 oracle을 생성하여 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.

우리는 물론 빠르게 다음과 같이 'constant' 기능에 대한 또 다른 예를 들 수 있다.

[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 algorithm 이 있다. 이 예제에서는 다시 한번 TruthTableOracle 인스턴스를 작성한다.

[6]:

bitstr = '00111100'
oracle = TruthTableOracle(bitstr)

보여지는 바와 같이, 진리표는 테이블의 모든 항목 값을 포함하는 bitstr 로 지정된다. 길이가 \(8\) 이므로 해당 진리표는 \(3\) 입력 비트이다. 진리표는 다음과 같이 함수 매핑을 나타낸다:

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

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

  • :math:` mathbf{a} cdot 010 mod 2 = 1 `

  • :math:` mathbf{a} cdot 011 mod 2 = 1 `

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

  • :math:` mathbf{a} cdot 101 mod 2 = 1 `

  • :math:` mathbf{a} cdot 110 mod 2 = 0 `

  • :math:` mathbf{a} cdot 111 mod 2 = 0 `

그리고 목표는 모든 내부 제품 방정식을 만족시키는 비트스트링 \(\mathbf{a}\) 를 찾는 것이다.

Oracle 회로를 다시 살펴보면, 이제 TruthTableOracle 인스턴스에 인코딩된 바이너리 함수에 해당한다.

[7]:

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

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

마찬가지로, \(v_i\) 는 3 개의 입력 비트에 대응하며; \(o_0\) 는 오라클의 출력 큐비트이고, \(a_0\) 는 보조 큐비트(ancilla qubit)이다.

먼저 groundtruth \(\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 인스턴스를 생성하고 이를 실행하여 groundtruth에 대한 결과를 확인할 수 있다.

[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’s algorithm 은 Simon’s problem 를 해결하는 데 사용된다. 이 예제에서는 다시 한번 TruthTableOracle 인스턴스를 작성하며, 여기서는 다른 형태의 구성을 보여준다.

[10]:

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

보여지는 대로, 진리표는 3 개의 길이-8 비트 문자열로 지정되며, 각각은 테이블에서 특정 출력 열에 대한 모든 항목의 값을 포함한다. 각 비트 문자열의 길이는 \(8\) 이므로, 진리표에는 \(3\) 입력 비트가 있으며; \(3\) 비트 문자열이 있으므로 진리표에는 \(3\) 출력 비트가 있다.

진리표로 표현되는 함수 \(f\) 는 1대1 또는 2대1로 약속된다. 우리의 목표는 주어진 함수가 둘 중 무엇인지를 결정하는 것이다. 주어진 함수가 2대1인 경우, 마스크 \(\mathbf{s}\) 도 계산해야 하는데, 이는 \(\forall \mathbf{x},\mathbf{y}\): \(\mathbf{x} \oplus \mathbf{y} = \mathbf{s}\) iff \(f(\mathbf{x}) = f(\mathbf{y})\) 를 만족한다. 명백하게도, 만약 \(f\) 가 1대1이면, 이에 해당하는 마스크는 \(\mathbf{s} = \mathbf{0}\) 이다.

먼저 groundtruth mask \(\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.

또한 다음과 같이 일대일 함수 (즉, \(\mathbf{0}\) mask에 대응하는) 를 나타내는 진리표를 빠르게 시도해볼 수 있다.

[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’s Factoring algorithm 은 가장 잘 알려진 양자 알고리즘 중 하나로 다항식 시간 내에 입력된 정수 \(N\) 의 소인수(prime factor)를 찾는다. 키스킷에서 구현된 알고리즘은 단순히 목표 정수를 입력받아 실행하는데, 다음과 같이:

[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].

참고: 쇼어의 알고리즘 구현은 \(4n + 2\) 큐비트를 사용하며 여기서 \(n\) 은 정수의 바이너리 비트 개수이다. 따라서 실제로 현재 이 구현은 크기가 작은 정수를 소인수 분해하는 것으로 제한된다. 위의 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.