GitHub Repository: quantum-kittens/platypus
Path: blob/main/translations/ko/ch-states/case-for-quantum.ipynb
³⁸⁵⁵ views

Kernel: Python 3

양자 컴퓨터의 경우

1. 추가의 복잡성

간단히 말해서 양자 컴퓨터의 경우 기존 컴퓨터가 할 수 없었던 특정 문제를 해결할 수 있다는 것입니다. 그 이유를 이해하려면 먼저 특정 문제를 해결하기 위해 얼마나 많은 계산 노력이 필요한지 고려해야 합니다.

시작하기 위해 첫 번째 섹션에서 고려한 알고리즘인 두 개의 숫자를 추가하는 방법을 다시 살펴볼 수 있습니다.

   9213
+  1854
=  ????

두 개의 $n$ 자리 숫자를 추가하는 것은 간단한 작업 세트로 수행할 수 있으며, 각 작업은 한 자리 숫자 두 개를 추가하는 것으로 구성됩니다. 절차의 복잡성을 분석하기 위해 이러한 기본 추가 사항 중 얼마나 많은 것이 필요한지, 그리고 이 숫자가 $n$ 에 어떻게 의존하는지 생각할 수 있습니다. 이 숫자를 $c(n)$ 라고 합니다.

가장 쉬운 경우에는 어떤 시점에서도 1을 수행할 필요가 없으며 $n$ 기본 추가만 필요합니다. 최악의 경우 $n$ 캐리 작업을 수행해야 하며 각 작업에는 기본적인 추가 작업이 필요합니다. 이러한 고려사항으로부터 우리는 $n \leq c(n) \leq 2n$ 이라고 결론을 내릴 수 있습니다.

2. 빅오 표기법

이 결과를 사용해 $c(n)$ 가 $n$ 와 함께 선형적으로 증가한다 고 표현할 수 있습니다. 보다 일반적으로는 $n$ 가 클 경우에 최대 $c(n)$ 을 갖는 $n$ 의 선형 함수를 찾을 수 있다고 할 수 있습니다. 이것은 말로 하면 길어지기 때문에, 대신에 이것을 빅오 표기법을 사용해 표현합니다.

기억 할 것

빅오 표기법
일례로 함수

f(x)

g(x)

및 파라미터

가 있을 때, 명제

f(x) = O(g(x))

는

f(x) \leq Mg(x) \forall x> x_0

를 충족하는 유한 수

M> 0

및

x_0 $가 존재함을 의미합니다.

빅오 표기법은 특정 플랫폼이나 알고리즘 구현에 관계없이 알고리즘에 필요한 리소스/런타임이 입력 크기에 따라 어떤 스케일로 변하는지 비교할 수 있어 편리합니다. 다음은 입력 크기 $N$ 의 함수로서의 런타임 $N$ 의 일반적인 스케일링 계수의 예를 보여 줍니다. 문제의 크기가 충분히 클 경우 $a$ 와 $b$ 가 일정할 때 $O(a^n)$ 알고리즘 실행 시간이 $O(n^b)$ 알고리즘 실행 시간을 넘어서게 되는 것을 쉽게 확인할 수 있습니다.

다른 시간 복잡도의 비교. n은 입력 비트 수이고 N은 필요한 연산 수 [5]

이 표기법으로 위에서 설명한 속성은 간단히 $c(n) = O(n)$ 로 표현됩니다. 이것은 세부 사항에 집착할 필요 없이 선형 동작을 캡처합니다. 따라서 $c(n) = n$ , $c(n) = 2n$ 또는 다른 것에 관계없이 간단히 $c(n) = O(n)$ 라고 말할 수 있습니다.

우리가 지금까지 고려한 것에는 숨겨진 가정이 있습니다. 자릿수에 대해 이야기함으로써 우리는 특정 숫자 체계의 사용을 가정했습니다. 그러나 자릿수는 10진수, 2진수 또는 기타 등 우리가 사용하는 숫자 체계에 따라 다릅니다. 예를 들어, 숫자를 표현하는 데 필요한 비트 $n_2$ 는 동일한 숫자를 표현하는 데 필요한 십진수 $n_{10}$ 와 관련이 있습니다.

$n_2 = \left\lceil \frac{\log 10}{ \log 2}, n_{10} \right\rceil \approx 3.3, n_{10}.$

이것도 선형적인 관계이기 때문에 빅오 표기법을 사용해서 복잡함을 표현하는 방법은 변하지 않습니다. $c(n_2)=O(n_2)$ , $c(n_{10})=O(n_{10})$ , 심지어 $c(n_{10})=O(n_{2})$ 는 동등하다고 할 수 있습니다. 우리가 사용하는 지수법을 지정하지 않고도 흔히 단순히 자릿수 $n$ 라고 이야기할 수 있는 것은 이 때문입니다.

3. 복잡성 이론

복잡성 이론은 알고리즘을 실행하는 데 필요한 계산 노력에 대한 연구입니다. 주어진 문제를 해결하기 위한 최상의 알고리즘을 고려함으로써 우리는 이 문제를 해결하는 데 내재된 계산 노력도 연구할 수 있습니다. 추가로 우리는 이미 최적의 알고리즘을 알고 있으므로 $O(n)$ 복잡성의 문제임을 알고 있습니다.

곱셈은 그렇게 간단하지 않습니다. 두 개의 $n$ 자리 수를 곱하기 위해 학교에서 배운 알고리즘에는 한 자리 덧셈 및 곱셈과 같은 $O(n^2)$ 기본 연산이 필요합니다. 점근적 복잡성이 더 낮은 알고리즘이 발견되었지만 $O(n)$ 복잡성으로 곱셈을 수행하는 것은 불가능하다고 널리 간주됩니다.

그래도 곱셈은 가장 복잡한 문제가 아닙니다. 훨씬 복잡한 문제의 예는 인수 분해입니다: $n$ 자리 수를 취하고 그 소인수를 찾는 것입니다. 이 소인수분해의 가장 잘 알려진 알고리즘의 계산량은 ParseError: KaTeX parse error: Expected '}', got '\right' at position 18: …left(e^{n^{1/3}\̲r̲i̲g̲h̲t̲) 보다 더 나쁩니다. 여기서 지수가 포함되어 있음은 매우 빠르게 복잡성이 증폭되고 해결하기 어려운 문제가 된다는 것을 나타냅니다.

실제 계산 시간을 사용하여 이 점을 설명하기 위해 최근 예를 살펴 보겠습니다. $^{1}$ 다음의 829자리 숫자를 생각해봅시다.

In [1]:

rsa_250 = 2140324650240744961264423072839333563008614715144755017797754920881418023447140136643345519095804679610992851872470914587687396261921557363047454770520805119056493106687691590019759405693457452230589325976697471681738069364894699871578494975937497937

컴퓨터를 사용하여 이 크기의 숫자를 더하거나 곱하면 이러한 문제를 매우 빠르게 해결할 수 있다는 것을 알게 될 것입니다. 컴퓨터의 프로세서 수와 코어 초 수를 구하는 데 걸리는 시간을 곱하면 1 코어 초보다 훨씬 적은 시간이 필요하다는 것을 알게 될 것입니다.

그러나 이 숫자에 대해 인수분해를 수행하려면 슈퍼컴퓨터와 약 2700년 코어년이 필요하며 결국 다음 두 가지 요소를 산출합니다.

In [2]:

p = 64135289477071580278790190170577389084825014742943447208116859632024532344630238623598752668347708737661925585694639798853367
q = 33372027594978156556226010605355114227940760344767554666784520987023841729210037080257448673296881877565718986258036932062711
p*q

Out[2]:

2140324650240744961264423072839333563008614715144755017797754920881418023447140136643345519095804679610992851872470914587687396261921557363047454770520805119056493106687691590019759405693457452230589325976697471681738069364894699871578494975937497937

더 큰 수의 인수분해를 위해 우리는 행성 크기의 슈퍼컴퓨터가 우주의 나이 동안 실행되어야 하는 지점에 쉽게 도달합니다. 분명히 그러한 문제는 실제로 불가능합니다.

지금까지는 $n$ 자리 숫자에 대해 복잡함은 간단한 한 자리 연산의 수로 나타나는 수학적 연산만을 생각해 왔습니다. 러나 복잡성 이론은 데이터베이스 검색, 그래픽 렌더링, 역학 시뮬레이션 또는 Zelda의 전설 에서 던전 횡단 등 모든 종류의 문제에 대한 모든 계산 방법을 분석하는 데 사용할 수 있습니다. 각각의 경우에 입력 크기 역할을 하는 매개변수 또는 매개변수 세트를 찾을 수 있으며 빅오 표기법을 사용하여 이 입력 크기의 관점에서 복잡성을 표현할 수 있습니다. 예를 들어 $N$ 항목의 데이터베이스를 검색하는 경우 복잡성은 $O(N)$ 입니다.

공식적으로 알고리즘의 복잡성은 우리가 사용하는 계산을 위한 정확한 이론적 모델에 달려 있습니다. 각 모델에는 기본 연산이라고 하는 원시(primitive) 연산 집합이 있으며 이를 사용하여 모든 알고리즘을 표현할 수 있습니다. 부울 회로의 경우 첫 번째 섹션에서 고려했듯이 원시 연산은 논리 게이트입니다. 앨런 튜링이 제안한 가상의 컴퓨터인 튜링 기계의 경우 테이프에 저장된 정보를 처리하고 조작하는 장치를 상상해볼 수 있습니다. RAM 모델은 보다 복잡한 원시 작업 집합을 가지고 있으며 우리가 매일 사용하는 컴퓨터의 이상적인 형태로 작동합니다. 이 모든 것은 이산 값(discrete value)의 이산화된(discretized) 작동을 기반으로 하는 디지털 계산 모델입니다. 서로 다르게 보일 수 있지만 각자가 상대방의 것을 시뮬레이션하는 것은 매우 쉽습니다. 이는 대부분의 경우 계산의 복잡성은 이들 모델에서 어떤 모델을 사용하느냐에 크게 의존하지 않는다는 것을 의미합니다. 따라서 RAM 모델이나 튜링머신에 특화하여 계산량을 말하는 것이 아니라 디지털 컴퓨터의 계산량을 간단하게 말할 수 있습니다.

4. 디지털 컴퓨팅 너머

비록 디지털 컴퓨터가 현재 지배적이지만, 이것이 유일한 형태의 계산은 아닙니다. 아날로그 컴퓨터도 과거에 널리 연구되고 사용되었습니다. 디지털 컴퓨터의 이산 값과 달리 이들은 지속적으로 변화하는 매개변수의 정밀한 조작을 기반으로 합니다. 때때로 그러한 장치가 디지털 컴퓨터에서 다루기 힘든 문제를 신속하게 해결할 수 있다고 주장되어 왔습니다. 그러나 그러한 주장은 실현된 적이 없습니다. 아날로그 컴퓨터의 주요 걸림돌은 임의로 높은 정밀도로 장치를 구축할 수 없다는 것입니다. 디지털 컴퓨터에서 이산화는 오류가 눈에 띄기 위해서는 상대적으로 커야 하며 이러한 오류를 감지하고 수정하는 방법을 구현할 수 있음을 의미합니다. 그러나 아날로그 컴퓨터에서 오류는 임의로 작고 감지하기 불가능할 수 있지만 여전히 그 영향이 누적되어 계산을 망칠 수 있습니다.

이상적인 계산 모델을 제안한다면 디지털 컴퓨터의 확실성과 아날로그 컴퓨터의 섬세한 조작을 결합하는 방법을 모색할 수 있습니다. 이를 달성하기 위해 우리는 양자 역학을 고려해 볼 수있습니다. 큐비트는 이산 출력 0 과 1 을 가진 시스템이지만 연속 매개변수로만 설명할 수 있는 상태로 존재할 수 있음을 이미 살펴보았습니다. 큐비트는 이산적이거나 연속적인 어느 하나로는 완전히 표현할 수 없고 오히려 그 두 가지 조합으로 표현할 수 있습니다. 아인슈타인은 아래의 말을 남겼습니다, $^{2}$

'때로는 하나의 이론을 사용하고 때로는 다른 이론을 사용해야 하는 것처럼 보이지만 때로는 둘 중 하나를 사용할 수도 있습니다. 우리는 새로운 종류의 어려움에 직면해 있습니다. 우리는 현실에 대해 두 가지 상반된 그림을 가지고 있습니다. 따로따로 그들 중 어느 것도 현상을 완전히 설명하지 못하고…'

따라서 큐비트에 게이트를 적용하는 것이 원시적인 작업인 양자 컴퓨터는 아날로그도 디지털도 아닌 고유한 것입니다. 다음 장에서 우리는 이 독특한 특성의 결과를 탐구할 것입니다. 우리는 양자 컴퓨터가 디지털 컴퓨터와 근본적으로 다른 복잡성으로 문제를 해결할 수 있음을 알게 될 것입니다. 사실, 양자 컴퓨팅은 특정 작업에 대해 기존 컴퓨터보다 기하급수적으로 빨라질 수 있는 유일한 알려진 기술로, 잠재적으로 계산 시간을 몇 년에서 몇 분으로 단축할 수 있습니다. 또한 양자 오류 수정이 결함의 영향을 제거할 수 있는 방법을 탐구할 것입니다.

5. 양자 컴퓨터를 사용하는 경우

큐비트와 양자 게이트를 사용하면 디지털 및 아날로그 고전 알고리즘과 근본적으로 다른 새로운 알고리즘을 설계할 수 있습니다. 이러한 방식으로 우리는 기존 컴퓨터에서 다루기 힘든 문제에 대한 솔루션을 찾기를 희망합니다.

이 작업을 수행할 수 있는 한 가지 방법은 전역 속성을 결정하려는 함수가 있는 경우입니다. 예를 들어 어떤 함수 $f(x)$ 가 최소값인 매개변수 $x$ 의 값을 찾고자 하거나 $f(x)$ 가 주기적이면 함수의 주기를 찾고자 합니다. 디지털 컴퓨터의 알고리즘은 전역 속성에 대한 충분한 정보를 얻기 위해 다양한 입력에 대해 $f(x)$ 를 계산하는 프로세스를 사용할 수 있습니다. 그러나 양자 컴퓨터를 사용하여 중첩 상태를 생성할 수 있다는 사실은 함수가 가능한 많은 입력에 동시에 적용될 수 있음을 의미합니다. 이것은 그러한 상태의 측정이 단순히 단일 결과를 제공하기 때문에 가능한 모든 출력에 액세스할 수 있다는 것을 의미하지는 않습니다. 그러나 대신 양자 간섭 효과를 유도하여 우리가 필요로 하는 전체 속성을 나타낼 수 있습니다.

이 일반적인 설명은 이미 발견된 많은 양자 알고리즘의 작동을 설명합니다. 한 가지 눈에 띄는 예는 $N$ 항목을 $O(N)$ 에서 $O(N^{1/2})$ 로 검색하는 복잡성을 줄이는 Grover 알고리즘입니다. 이 2차 속도 향상은 최적화 문제 및 기계 학습과 같이 구조화되지 않은 검색으로 표현할 수 있는 작업이 있는 많은 응용 프로그램에서 유용할 수 있습니다.

In [ ]:

# This code is to create the interactive figure
from bokeh.layouts import column
from bokeh.models import ColumnDataSource, CustomJS, Slider
from bokeh.plotting import figure, show
from bokeh.embed import file_html
from bokeh.resources import CDN
import numpy as np
import IPython

x = np.arange(0,500)
y_linear = x
y_sqrt = 7.5*np.sqrt(x)

linear_source = ColumnDataSource(data=dict(x=x, y=y_linear))
sqrt_source = ColumnDataSource(data=dict(x=x, y=y_sqrt))

plot = figure(
              plot_height=400, 
              plot_width=800,
              sizing_mode="scale_width",
              tools="reset,save",
              x_range=[0, 500], y_range=[0, 500], 
              x_axis_label="Size of Problem",
              y_axis_label="Time Taken to Find Solution")
plot.line('x', 'y', source=linear_source, line_width=3, line_alpha=0.6, color="blue", legend_label="Classical Search O(N)")
plot.line('x', 'y', source=sqrt_source, line_width=3, line_alpha=0.6, color="red", legend_label="Quantum Search O(√N)")
plot.legend.location = "top_left"

callback = CustomJS(args=dict(source=sqrt_source), code="""
        var data = source.data;
        var f = (10-cb_obj.value)*2 + 3
        var x = data['x']
        var y = data['y']
        for (var i = 0; i < x.length; i++) {
            y[i] = f*Math.sqrt(x[i])
        }
        source.change.emit();
    """)

speed_slider = Slider(title="Relative Speed of Quantum Computer", value=7.5, start=1.0, end=10.0, step=0.1, show_value=False)
speed_slider.js_on_change('value', callback)

layout = column(plot, speed_slider)

caption = """
Comparing performance of algorithms across different platforms is difficult. What we can tell (through big-O-notation) is 
despite the difference in speeds between our classical and quantum computers, for a large enough problem, the quantum search 
algorithm will always out-perform the classical search algorithm."""

html_repr = file_html(layout, CDN)
html_fig = "<figure>{0}<figcaption>{1}</figcaption></figure>".format(html_repr, caption)
IPython.display.HTML(html_fig)

인수분해 문제의 핵심에서 주기적 함수를 분석하는 Shor의 알고리즘을 사용하면 훨씬 더 인상적인 속도 향상을 얻을 수 있습니다. 이것은 복잡성이 $O(n^3)$ 인 $n$ 자리 숫자를 인수분해하는 양자 솔루션을 허용합니다. 이것은 $O\left(e^{n^{1/3}}\right)$ 보다 나쁜 디지털 컴퓨터의 복잡성에 비해 초다항식 속도 향상입니다.

양자 알고리즘에 대한 또 다른 접근 방식은 양자 컴퓨터를 사용하여 양자 문제를 해결하는 것입니다. 다음 장에서 살펴보겠지만 양자 상태를 표현하려면 큐비트 수에 따라 기하급수적으로 확장되는 정보의 양이 필요합니다. 따라서 $n$ 큐비트의 상태를 기록하는 것은 $n$ 이 증가함에 따라 디지털 컴퓨터에서 다루기 힘든 작업이 됩니다. 그러나 양자 컴퓨터의 경우 동일한 작업을 수행하는 데 $n$ 큐비트만 있으면 됩니다. 양자 상태를 표현하고 조작하는 이 자연적인 능력을 통해 분자 및 기본 입자와 같은 관심 있는 양자 시스템을 연구하고 더 잘 이해할 수 있습니다.

따라서 다양한 산업에서 양자 알고리즘을 적용하고 적용하면 비즈니스 및 과학에서 파괴적인 사용 사례를 가능하게 할 수 있습니다. 여기에는 약물 발견, 기계 학습, 재료 발견, 옵션 가격 책정, 단백질 접힘 및 공급망의 혁신이 포함됩니다. $^{3}$ 특히 유망한 문제는 기존 알고리즘이 고유한 확장 제한에 직면하고 큰 클래식을 필요로 하지 않는 문제입니다. 로드할 데이터세트입니다. 양자 이점을 위해 주어진 문제의 답은 양자 역학이 모든 경로를 거치지 않고도 솔루션으로 발전할 수 있도록 구조와 함께 기하급수적으로 많은 얽힌 자유도에 크게 의존해야 합니다. 그러나 양자 컴퓨터에서 '쉬운' 문제(다항식 시간으로 풀 수 있음)와 기타 복잡성 이론 클래스 간의 정확한 관계는 여전히 미해결 문제입니다. $^{4}$

이것은 양자 알고리즘이 고유한 방식으로 계산을 수행할 수 있는 방법의 맛보기일 뿐입니다. 이러한 접근 방식에 대한 자세한 내용은 이후 장에서 찾을 수 있습니다. 그러나 먼저 단일 큐비트를 넘어 우리가 필요로 하는 전체 양자 게이트 세트를 이해하는 데 시간을 투자해야 합니다. 이것이 다음 장의 초점입니다.

6. 참고문헌

https://lists.gforge.inria.fr/pipermail/cado-nfs-discuss/2020-February/001166.html
알버트 아인슈타인, 레오폴드 인펠트(1938). 물리학의 진화: 초기 개념에서 상대성 이론과 양자에 대한 아이디어의 성장. 캠브리지 대학 출판부.
https://www.ibm.com/think-leadership/institute-business-value/report/quantumstrategy
https://www.cs.virginia.edu/~robins/The_Limits_of_Quantum_Computers.pdf
이미지: Cmglee / CC BY-SA (https://creativecommons.org/licenses/by-sa/4.0)

In [17]:

import qiskit.tools.jupyter
%qiskit_version_table

Out[17]: