사용 지침서와 쇼어 알고리즘¶
키스킷에서는 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' 함수를 나타냄을 알 수 있다.
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]:
보여지는 바와 같이, \(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]:
마찬가지로, \(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 Software | Version |
|---|---|
| Qiskit | 0.23.0 |
| Terra | 0.16.0 |
| Aer | 0.7.0 |
| Ignis | 0.5.0 |
| Aqua | 0.8.0 |
| IBM Q Provider | 0.11.0 |
| System information | |
| Python | 3.6.1 |Continuum Analytics, Inc.| (default, May 11 2017, 13:09:58) [GCC 4.4.7 20120313 (Red Hat 4.4.7-1)] |
| OS | Linux |
| CPUs | 1 |
| 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.