[논문]양자컴퓨터 계산성능의 정량적 비교분석

김진규; 장아름; 최병수

문제 정의

본 연구에서는 양자컴퓨팅의 성능향상효과를 정교하게 분석하기 위해서 어셈블리 코드 수준에서 분석하였다. 분석 결과 알고리즘 구동 과정에서 소요되는 큐비트 수와 게이트 수 그리고 실행시간 모든 측면에서 양자컴퓨팅의 성능향상 효과가 확인되었다.
하지만, 실질적인 상황에서 양자컴퓨터의 계산성에 대한 엄격한 평가는 아직 미진한 편이다. 본 연구에서는 이러한 알고리즘 수준 분석의 한계를 넘기 위해 조금 더 정교한 어셈블리 코드 수준에서 분석하였다. 이를 위해 양자컴퓨터 실행과정에서 중요한 메모리 및 실행시간 요구량에 대한 정량적 분석을 진행하였다.
본 연구에서는 이러한 양자컴퓨팅의 계산능력과 관련하여 현재까지 진행되었던 다양한 이론적 연구를 넘어서, 실용적 차원에서 양자컴퓨터의 성능향상효과에 대해서 다룬다. 양자컴퓨터의 계산성은 이론적 수준에서는 지수적 혹은 다항적 성능 향상 효과가 있음이 많은 문제들에서 입증되었다[5].

가설 설정

본 연구에서는 평가의 용이성을 위하여 모든 게이트의 동작시간은 동일하며, 이 때 게이트의 동작시간은 1μs로 가정하였다.

제안 방법

이 과정에서 현재 사용가능한 양자 컴파일러인 Quipper와 Scaffold를 사용하였다(본문에서 자세한 설명). 또한 양자컴퓨터에서 지수적 성능향상이 나타나는 두 개의 양자 알고리즘인 BWT와 GSE를 선정하였다(본문에서 자세한 설명). 이에 따라서 다음과 같은 두 가지 특성을 확인하였다.
부가적으로 본 연구에서는 컴파일 과정에서 소요되는시간을 분석하였다. 알고리즘에서의 실행시간에는 영향을 끼치지 않지만 양자 어셈블리 코드를 생성하는 시간이 오래 걸리는 것은 바람직하지 않기 때문이다.
양자알고리즘의 어셈블리수준에서의 실행시간을 분석하기 위해서 우선 먼저 어셈블리수준에서 필요한 게이트 수를 분석하고 이를 기준으로 하여 실행시간을 다음과 같이 평가하였다. 실행시간 T_run은 다음과 같이 정의된다.
양자컴퓨팅의 성능향상 효과를 확인하기 위하여 입력 크기에 따른 메모리 요구량과 알고리즘 실행시간을 평가하였다. 만약 어셈블리 코드 수준에서도 입력 크기에 따라서 양자컴퓨팅이 요구하는 자원요구량(메모리와 실행시간)이 고전컴퓨팅에 비해서 작다면 어셈블리 코드 수준에서도 성능향상효과가 나타난다고 할 수 있다.
기저상태란 원자나 분자 등에 있어 양자 역학계의 정상상태 중 가장 에너지가 낮은 상태를 뜻한다. 이 알고리즘에서 에너지는 b비트의 정확도를 가지며, 본 연구에서는 기저상태를 나타내는 파동함수 M에 의한 큐비트와 게이트 수를 평가한다. GSE 알고리즘의 고전계산복잡도는 지수적이지만, 양자계산복잡도는 다항적이다.
본 연구에서는 이러한 알고리즘 수준 분석의 한계를 넘기 위해 조금 더 정교한 어셈블리 코드 수준에서 분석하였다. 이를 위해 양자컴퓨터 실행과정에서 중요한 메모리 및 실행시간 요구량에 대한 정량적 분석을 진행하였다. 이 과정에서 현재 사용가능한 양자 컴파일러인 Quipper와 Scaffold를 사용하였다(본문에서 자세한 설명).

이론/모형

이를 위해 양자컴퓨터 실행과정에서 중요한 메모리 및 실행시간 요구량에 대한 정량적 분석을 진행하였다. 이 과정에서 현재 사용가능한 양자 컴파일러인 Quipper와 Scaffold를 사용하였다(본문에서 자세한 설명). 또한 양자컴퓨터에서 지수적 성능향상이 나타나는 두 개의 양자 알고리즘인 BWT와 GSE를 선정하였다(본문에서 자세한 설명).
현재까지 개발된 양자 컴파일러는 다수가 존재하지만 본 연구에서는 Quipper[11]과 Scaffold[12]를 사용하였다. Quipper는 내장형, 함수형 언어이다.

성능/효과

BWT알고리즘의 목표는 그래프를 탐색하여 한 트리의 루트부터 다른 트리의 루트를 찾는 것이다. BWT 알고리즘의 고전계산복잡도는 지수적이지만, 양자계산복잡도는 다항적이다. 이론적으로 트리의 높이(height)가 300 이상부터 양자컴퓨터가 효율적인 것으로 예상된다[7].
이 알고리즘에서 에너지는 b비트의 정확도를 가지며, 본 연구에서는 기저상태를 나타내는 파동함수 M에 의한 큐비트와 게이트 수를 평가한다. GSE 알고리즘의 고전계산복잡도는 지수적이지만, 양자계산복잡도는 다항적이다. 이론적으로 M이 208 이상부터 양자컴퓨터가 효율적인 것으로 예상된다[9].
BWT의 경우 고전적으로 수행할 수 있는 최대 입력크기가 n=300 에 대해서 양자컴퓨터에서는 10초정도 소요되는 것을 확인하였다. GSE의 경우 고전적으로 수행할 수 있는 최대 입력크기를 가정할 때 양자 컴퓨터에서는 12일 정도면 충분함을 확인하였다.
이 경우 최대 입력 크기를 고려하면 BWT와 GSE 각각 10초와 203초 이내임을 확인하였다. 고전 컴퓨터가 수행할 수 있는 최대 입력크기에서는 각각 10초 이내와 12일 이내에 연산 완료함을 알 수 있었다. 이에 따라 어셈블리 수준에서도 양자컴퓨터 실행시간 측면에서의 성능향상 효과를 확인하였다.
우선 입력 크기에 따른 어셈블리 수준에서의 게이트 수를 분석하였다(그림 3 참조). 두 개의 알고리즘 모두 입력 크기에 따라서 요구되는 게이트 수는 다항적으로 증가하는 것을 확인 할 수 있었다. 다음으로 입력크기에 따른 수행시간은 수식(1)과 (2)를 참조하여 분석하였다(그림 4 참조).
두 번째로 고전컴파일러와 달리 양자컴파일러의 실행시간은 입력 값에 의존함을 확인하였다. 분석 결과 BWT와 GSE의 경우는 평가 구간에서 다항적 혹은 지수적으로 컴파일 수행시간이 증가하는 것을 확인하였다.
분석결과 큐비트 수 혹은 요구되는 메모리 량의 증가는 입력 크기에 비례하는 것을 확인할 수 있었다(그림2 참조). 따라서 양자컴퓨터에서 요구되는 양자 메모리의 양은 입력크기에 다항적 관계를 갖는 반면에 고전컴퓨터에서 요구되는 메모리 크기가 지수적으로 증가하는 것을 고려하면 메모리 요구량 측면에서 양자컴퓨팅의 성능향상이 가능함이 입증되었다.
본 연구를 통해서 어셈블리 코드 수준에서의 양자컴퓨터 성능향상 효과를 확인하였으나 아직도 확장 및 해결해야 할 문제점이 많음을 파악하였다. 확장의 측면에서는 본연구에서 다루지 못했던 다수의 양자알고리즘들을 추가적으로 분석할 필요가 있다.
두 번째로 고전컴파일러와 달리 양자컴파일러의 실행시간은 입력 값에 의존함을 확인하였다. 분석 결과 BWT와 GSE의 경우는 평가 구간에서 다항적 혹은 지수적으로 컴파일 수행시간이 증가하는 것을 확인하였다.
본 연구에서는 양자컴퓨팅의 성능향상효과를 정교하게 분석하기 위해서 어셈블리 코드 수준에서 분석하였다. 분석 결과 알고리즘 구동 과정에서 소요되는 큐비트 수와 게이트 수 그리고 실행시간 모든 측면에서 양자컴퓨팅의 성능향상 효과가 확인되었다. 특히 고전컴퓨터로 불가능한 입력 크기를 대상으로 양자컴퓨터에서는 현실적인 수준에서 구동이 가능함을 확인하였다.
4.1 메모리 요구량 분석

분석결과 큐비트 수 혹은 요구되는 메모리 량의 증가는 입력 크기에 비례하는 것을 확인할 수 있었다(그림2 참조). 따라서 양자컴퓨터에서 요구되는 양자 메모리의 양은 입력크기에 다항적 관계를 갖는 반면에 고전컴퓨터에서 요구되는 메모리 크기가 지수적으로 증가하는 것을 고려하면 메모리 요구량 측면에서 양자컴퓨팅의 성능향상이 가능함이 입증되었다.
메모리 요구량의 경우에는 어셈블리 코드 수준에서 입력 크기에 비례함을 확인할 수 있었다. 실행시간의 경우에는 알고리즘 수준에서처럼 어셈블리 코드 수준에서도 지수적인 성능향상 효과를 확인하였다. BWT의 경우 고전적으로 수행할 수 있는 최대 입력크기가 n=300 에 대해서 양자컴퓨터에서는 10초정도 소요되는 것을 확인하였다.
알고리즘의 입력 크기가 커지면 컴파일 시간도 증가하는 것을 확인하였다(그림 5 참조). 예로써 GSE에서 #orbital 이 32인 경우 Quipper는 1000초 정도를 요구하였다.
첫 번째로 양자컴퓨터는 어셈블리 코드 수준에서도 충분한 성능향상 효과가 있음을 확인하였다. 메모리 요구량의 경우에는 어셈블리 코드 수준에서 입력 크기에 비례함을 확인할 수 있었다.
추가적으로 BWT에서는 두 개의 컴파일러 사이에서 입력 크기에 무관하게 고정적 차이가 나타나지만 GSE에서는 점진적으로 그 차이가 커지는 것을 확인하였다. 이는GSE의 경우 Scaffold 프로그래밍 과정에서 입력크기에 따라 내부적으로 추가되는 큐비트가 있음에 기인한다.
분석 결과 알고리즘 구동 과정에서 소요되는 큐비트 수와 게이트 수 그리고 실행시간 모든 측면에서 양자컴퓨팅의 성능향상 효과가 확인되었다. 특히 고전컴퓨터로 불가능한 입력 크기를 대상으로 양자컴퓨터에서는 현실적인 수준에서 구동이 가능함을 확인하였다.
해결해야 할 문제점으로는 컴파일러의 성능을 개선해야 하는데, 컴파일 알고리즘 자체와 컴파일러의 수행시간을 단축시켜야 하는 것이 향후 연구주제이다. 특히 본 연구에서 확인한 결과 평가 구간에서는 컴파일러의 수행시간이 지수적인 문제점이 발견되었다. 이러한 문제점이 일반적인 것인지 여부를 확인할 필요가 있다.

후속연구

확장의 측면에서는 본연구에서 다루지 못했던 다수의 양자알고리즘들을 추가적으로 분석할 필요가 있다. 해결해야 할 문제점으로는 컴파일러의 성능을 개선해야 하는데, 컴파일 알고리즘 자체와 컴파일러의 수행시간을 단축시켜야 하는 것이 향후 연구주제이다. 특히 본 연구에서 확인한 결과 평가 구간에서는 컴파일러의 수행시간이 지수적인 문제점이 발견되었다.
본 연구를 통해서 어셈블리 코드 수준에서의 양자컴퓨터 성능향상 효과를 확인하였으나 아직도 확장 및 해결해야 할 문제점이 많음을 파악하였다. 확장의 측면에서는 본연구에서 다루지 못했던 다수의 양자알고리즘들을 추가적으로 분석할 필요가 있다. 해결해야 할 문제점으로는 컴파일러의 성능을 개선해야 하는데, 컴파일 알고리즘 자체와 컴파일러의 수행시간을 단축시켜야 하는 것이 향후 연구주제이다.

핵심어	질문	논문에서 추출한 답변
	정보소자의 극소화에 물리적 한계가 존재하는 이유는 무엇인가?	이러한 정보소자의 극소화는 최근까지 무어의 법칙형태로 매년 집적 용량을 두 배 정도씩 향상시켰다[1]. 하지만, 이러한 정보소자의 극소화도 궁극적으로는 물리적 한계가 있는데, 이는 고전정보인 비트를 표현하는 것이 매우 작은 크기의 정보소자에서는 어렵기 때문이다. 이로 인해서 최근에는 무어의 법칙을 공식적으로 폐기하고 다른 형태의 접근법에 대한 연구가 진행되고 있다[2].
	양자정보에 기반한 정보기술은 어떤 측면에서 성능향상효과를 보여주는가?	양자정보에 기반한 정보기술은 크게 보안성과 계산성 측면에서 성능향상 효과를 보여준다. 보안성의 측면에서는 양자적으로 비밀키를 전송하는 방법의 절대보안성이 알려져 있다[3].
	Binary Welded Tree알고리즘의 목표는 무엇인가?	Binary Welded Tree(BWT)는 리프들이 연결되어 있는 두 개의 동일한 이진 트리이며, 트리의 루트를 제외하고는 모든 노드들의 차수는 3이다[6]. BWT알고리즘의 목표는 그래프를 탐색하여 한 트리의 루트부터 다른 트리의 루트를 찾는 것이다. BWT 알고리즘의 고전계산복잡도는 지수적이지만, 양자계산복잡도는 다항적이다.

내보내기 구분	파일저장 인쇄 메일전송
구성항목	기본정보 상세정보 관리번호, 논문명, 저널/프로시딩명, 저자 , 발행년, 권, 호, 시작페이지, 끝페이지, 발행기관 관리번호, 논문명, 대등논문명, 저자 , 저널/프로시딩명, 발행기관, 발행년, 발행언어, 권, 호, 시작페이지, 끝페이지, ISBN, ISSN, 주제분야, 키워드, 초록(한글), 초록(영문), 저자(소속기관)
저장형식	Text(ASCII format) Excel format RefWorks Direct Export RIS format (for Reference Manager, ProCite, EndNote), Scholar's Aids, Mendeley
메일정보	받는사람 (필수) @ 보내는사람 (선택) @ 제목 내용 KISTI 검색결과 이메일 서비스
안내	총 건의 자료가 검색되었습니다. 다운받으실 자료의 인덱스를 입력하세요. (1-10,000) 검색결과의 순서대로 최대 10,000건 까지 다운로드가 가능합니다. 데이타가 많을 경우 속도가 느려질 수 있습니다.(최대 2~3분 소요) 다운로드 파일은 UTF-8 형태로 저장됩니다. 파일의 내용이 제대로 보이지 않을실 때는 웹브라우저 상단의 보기 -> 인코딩 -> 자동선택 여부를 확인하십시오. ~ Text(ASCII format) Excel format

연합인증

양자컴퓨터 계산성능의 정량적 비교분석
Quantitative Analysis of Quantum Computing Power 원문보기

초록
AI-Helper

AI 본문요약
AI-Helper

문제 정의

가설 설정

제안 방법

이론/모형

성능/효과

4.1 메모리 요구량 분석

후속연구

질의응답

이 논문을 인용한 문헌

관련 콘텐츠

원문 보기

이 논문과 함께 이용한 콘텐츠

AI-Helper ※ AI-Helper는 오픈소스 모델을 사용합니다.

선택된 텍스트

연합인증

양자컴퓨터 계산성능의 정량적 비교분석 Quantitative Analysis of Quantum Computing Power 원문보기

초록 용어보기논문에서 용어와 풀이말을 자동 추출한 결과로, 시범 서비스 중입니다. AI-Helper

AI 본문요약 엑셀 다운로드 AI-Helper

문제 정의

가설 설정

제안 방법

이론/모형

성능/효과

4.1 메모리 요구량 분석

후속연구

질의응답

이 논문을 인용한 문헌

관련 콘텐츠

원문 보기

이 논문과 함께 이용한 콘텐츠

AI-Helper ※ AI-Helper는 오픈소스 모델을 사용합니다.

선택된 텍스트

양자컴퓨터 계산성능의 정량적 비교분석
Quantitative Analysis of Quantum Computing Power 원문보기

초록
AI-Helper

AI 본문요약
AI-Helper