Shor의 질량 인수 분해 알고리즘

Shor의 질량인수분해 알고리즘은 질량인수분해를 빠르게 해소하는 양자 알고리즘이다.
비디오 해설
Qiskit Textbook 일본어 해설 3.9장
수학 팬 양자 카페
이번에는 알고리즘의 상세한 내용을 배우기 전에 프로그램 라이브러리를 사용해 블랙박스로서의 동작을 시험해 봤다.

qiskit.아쿠아 기반 Shor의 질인수 분해 알고리즘

15를 질인수로 분해하는 경우다.

import math
import numpy as np
from qiskit import BasicAer
from qiskit.aqua import QuantumInstance
from qiskit.aqua.algorithms import Shor

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]}.")
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}')

실행하려면 상당한 시간이 필요하다.(몇 십 초)
고전 컴퓨터에서 양자 계산을 시뮬레이션했기 때문이다.
결과:The list of factors of 15 as computed by the Shor's algorithm is [3, 5].
Computed of qubits for circuit: 18
Actual number of qubits of circuit: 18나오다
-15의 질인수 분해는 3x5→맞다
- 18개의 양자 비트가 사용되는 양자 비트
그러니까18개의 숫자가 N달러의 질량 인수로 분해되면 $4**lceil\log{2}(N)\rcelil+2달러가 나온 것 같습니다.

회로를 보다

회로를 봐라.

circ_shor = shor.construct_circuit()
circ_shor.draw('mpl', scale=0.7, fold=50)

전혀 몰라요.
설명 좀 할게요.Shor의 질량인수분해 알고리즘의 근본은 양자상위추정(QPE) 알고리즘이다.
질인수 분해 문제를 단일 행렬의 고유값에 귀결시키는 상위 추정은 고속성의 원인으로 여겨진다.
QPE가 해명한다고 생각하면

이렇게 돼서
위의 8비트는 단일 행렬 $U$U의 특징 값으로 사용되기 시작합니다.
단일 행렬 $U$U의 고유 벡터가 아래 10bit에 중첩되어 있습니다.
여기서 왜 첫 번째 비트에 $X$만 붙이면 고유 벡터의 중첩을 잘 할 수 있을까요
Qiskit Textbook 일본어 해설 3.9장
구문을 사용합니다.
비트를 배분한 뒤 QPE만 하고 있다.
QPE의 단계는 다음과 같습니다.
- 모든 보조 양자 위치에 H 게이트 설정
- 각 보조 양자 비트를 $2^k 달러 제어로 설정하고 $U$U 제어 그리드를 설정합니다.
- 마지막으로 보조 양자에 대해 역QFT(QFT는 단일 연산이므로 역QFT=QFT)를 적용한다.
나는 그림이 그것에 따라 쓴 것임을 확실히 깨달았다고 생각한다.

현재 하질인수 분해의 경계는?

실기가 대규모 회로를 집행할 수 없기 때문에 상술한 15개의 질인수 분해도 매우 어렵다.
시뮬레이터의 상황을 고려해 봅시다.IBM에서 제공하는 QASM 에뮬레이터의 최대 하위 비트 수를 조사합니다.
참고 사항:
Maximum number of qubits suppoted by the Qasm simulator
네.

from qiskit import Aer
Aer.get_backend('qasm_simulator').configuration().to_dict()

실행 결과'n_qubits': 29찾을 수 있습니다.최대 29개의 양자 비트수를 시뮬레이션할 수 있다.
인수 분해 $N$N*lceil\log$에 필요한 양자 비트는{2}(N)\rcelil+2달러, 대략적으로
$N ≤64달러입니다.
혈구질수 57의 질인수 분해
수학 팬 양자 카페 　
상당히 경계에 가까운 곳이다.
물론 상술한 숫자는 qskit이다.아쿠아의 라이브러리를 우직적으로 사용했을 때
문제의 답안과 후보 범위를 알고 이를 사전 지식으로 사용하면 양자 비트의 수를 줄일 수 있다.
이 일대

Shor의 질인수 분해 알고리즘을 더 많이 이해

qiskit.aqua의 설치 확인

둘 다 필요하죠?

결론

우선 프로그램 라이브러리만 호출하면 질인수 분해를 빨리 측정할 수 있다.