양자 알고리즘

양자 계산에서 양자 알고리즘은 양자 계산의 실제 모델에서 실행되는 알고리즘이며 가장 일반적으로 사용되는 모델은 계산의 양자 회로 모델이다. 고전적(또는 비양자적) 알고리즘은 유한한 명령 열 또는 문제를 해결하기 위한 단계별 절차로, 각 단계 또는 명령은 기존 컴퓨터에서 수행할 수 있다. 마찬가지로 양자 알고리즘은 각 단계를 양자 컴퓨터에서 수행할 수 있는 단계별 절차이다. 모든 고전적인 알고리즘은 양자 컴퓨터에서도 실행 할 수 있지만 양자 알고리즘이라는 용어는 일반적으로 양자 중첩 또는 양자 얽힘과 같은 양자역학적 특징을 필수적으로 사용하는 알고리즘을 의미한다.

기존 컴퓨터를 사용하여 결정불가능한 문제는 양자 컴퓨터를 사용하여도 결정할 수 없다. 양자 알고리즘이 활용하는 양자 중첩 및 양자 얽힘이 고전 컴퓨터에서 효율적으로 시뮬레이션 될 수 없기 때문에, 일부 문제를 고전 알고리즘보다 더 빠르게 해결할 수 있다.(양자 우월성 참조).

가장 잘 알려진 알고리즘은 소인수분해를 위한 쇼어의 알고리즘과 구조화되지 않은 데이터베이스 또는 정렬되지 않은 목록을 검색하는 그로버 알고리즘이다. 쇼어의 알고리즘은 소인수분해를 위한 가장 잘 알려진 기존 알고리즘인 일반 수체 체보다 훨씬(거의 기하급수적으로) 빠르게 실행된다. 그로버 알고리즘은 동일한 작업에 대해 가능한 최상의 기존 알고리즘인 선형 검색보다 제곱으로 빠르게 실행된다.

 개요 
양자 알고리듬은 일반적으로 양자 계산의 일반적으로 사용되는 회로 모델에서 일부 입력 큐비트에 작용하고 측정으로 끝나는 양자 회로에 의해 설명된다. 양자 회로는 고정된 수의 큐비트에서 작동하는 간단한 양자 게이트들로 구성된다. 큐비트 수의 변화는 비유니타리 진화를 의미하기 때문에 큐비트 수는 고정되어야 한다. 양자 알고리듬은 해밀토니안 오라클 모델과 같은 다른 양자 계산 모델에서도 언급될 수 있다.

양자 알고리듬은 그 알고리듬이 사용하는 주요 기술로 분류할 수 있다. 양자 알고리듬에서 일반적으로 사용되는 기술/아이디어에는 페이즈 킥백, 페이즈 추정, 양자 푸리에 변환, 양자 걸음, 진폭 증폭 및 위상 양자장론이 포함된다. 양자 알고리듬은 해결된 문제의 유형에 따라 분류될 수도 있다. 예를 들어, 대수적 문제에 대한 양자 알고리듬에 대한 문헌을 참조하라.

 양자 푸리에 변환 기반 알고리듬 
양자 푸리에 변환은 이산 푸리에 변환과 비슷한 양자 알고리듬이며 다른 여러 양자 알고리듬에 사용된다. 아다마흐 변환은 유한체 에 대한 차원 벡터 공간에 대한 양자 푸리에 변환의 예이기도 하다. 양자 푸리에 변환은 의 다항식적으로 증가하는 양자 게이트들만을 사용하여 양자 컴퓨터에서 효율적으로 구현될 수 있다.

 도이치-조사 알고리듬 
섬네일| 도이치-조사 알고리듬
도이치-조사 알고리듬은 결정론적 고전 컴퓨터의 경우 블랙 박스에 대한 기하급수적으로 많은 쿼리가 필요하지만 양자 컴퓨터에서는 하나의 쿼리로 수행할 수 있는 블랙박스 문제를 해결한다. 유계 오류 양자 알고리듬과 고전적 알고리듬을 모두 허용하면 고전적 확률 알고리듬이 작은 오류 확률로 일정한 수의 쿼리로 문제를 해결할 수 있기 때문에 속도 향상이 없다. 이 알고리듬은 함수 f 가 상수(모든 입력에서 0 또는 모든 입력에서 1)인지 또는 균형(입력 도메인의 절반에 대해 1을 반환하고 나머지 절반에 대해 0을 반환)인지 결정한다.

 번스타인-바지라니 알고리듬 

번스타인-바지라니 알고리듬은 가장 잘 알려진 고전 알고리듬보다 더 효율적으로 문제를 해결하는 최초의 양자 알고리듬이다. 이 알고리듬은 BQP와 BPP 사이에 오라클 분리를 생성하도록 설계되었다.

 사이먼 알고리듬 

사이먼 알고리듬은 유계 오류 확률론적 알고리듬을 포함하여 어떤 고전적인 알고리듬보다 기하급수적으로 더 빠르게 블랙박스 문제를 해결한다. 우리가 효율적이라고 생각하는 모든 기존 알고리듬에 비해 기하급수적인 속도 향상을 달성한 이 알고리듬은 쇼어의 인수분해 알고리듬에 대한 동기가 되었다.

 양자 페이즈 추산 알고리듬 
양자 페이즈 추산 알고리듬은 고유 벡터에 비례하는 양자 상태와 게이트에 대한 접근이 주어진 유니터리 게이트의 고유 벡터의 고유 페이즈를 결정하는 데 사용된다. 이 알고리듬은 다른 알고리듬에서 서브루틴으로 자주 사용된다.

 쇼어 알고리듬 
쇼어 알고리듬은 이산 로그 문제와 소인수 분해 문제를 다항식 시간으로 해결하는 반면 가장 잘 알려진 고전 알고리듬은 초다항식 시간을 사용한다. 이러한 문제는 P 또는 NP-완전에 있는지 알려져 있지 않다. 또한 가장 잘 알려진 고전 알고리듬이 초다항식 시간에서 실행되는 다항식 시간 – 블랙박스가 아닌 문제를 해결하는 몇 안 되는 양자 알고리듬 중 하나이다.

 숨은 부분군 문제 
아벨 군의 숨은 부분군 문제는 사이먼의 문제, 펠 방정식, 환 R의 주 이데알 판정 및 인수 분해와 같이 양자 컴퓨터로 해결할 수 있는 많은 문제의 일반화이다. 숨은 아벨 부분군 문제로 알려진 효율적인 양자 알고리듬이 있다. 아벨이 아닌 보다 일반적인 숨겨진 부분군 문제는 이전에 언급한 문제와 그래프 동형 및 특정 격자 문제의 일반화이다. 특정 비 아벨 군에 대해 효율적인 양자 알고리듬이 알려져 있다. 그러나 그래프 동형에 대한 효율적인 알고리듬을 제공하는 대칭 군에 대해 알려진 효율적인 알고리듬은 없으며 특정 격자 문제를 해결할 이면체 군에 대해 알 수 있다.

 보손 샘플링 문제 
실험적 구성에서 보손 샘플링 문제는 적당한 수의 보손(예: 빛의 광자)의 입력이 정의된 유니타리로 제한되는 다수의 출력 모드로 무작위로 흩어지는 것으로 가정한다. 그러면 문제는 보손과 유니타리의 입력 배열에 따라 달라지는 출력 확률 분포의 공정한 샘플을 생성하는 것이다. 고전적인 컴퓨터 알고리듬으로이 문제를 해결하려면 유니터리 변환 행렬의 퍼머넌트를 계산해야 하는데, 이는 불가능하거나 엄청나게 오랜 시간이 걸릴 수 있다. 2014년에 유니터리 광자 상태를 생성하는 기존 기술 및 표준 확률 방법을 적합한 양자 계산 가능한 선형 광 네트워크에 대한 입력으로 사용할 수 있고 출력 확률 분포의 샘플링이 양자 알고리듬을 사용하여 명백히 우수할 것이라고 제안되었다 2015년에 조사에서는 샘플링 문제가 포크 상태 광자 이외 입력에 대해 유사한 복잡성을 가지며 고전적으로 시뮬레이션 할 수 있는 것에서 보손 샘플링 문제만큼 어려운 계산 복잡도의 전환을 확인했다. 이는 일관된 진폭 입력의 크기에 따라 달라진다.

 가우스 합 추산 
가우스 합은 지수 합의 한 유형이다. 이러한 합계를 추정하기 위한 가장 잘 알려진 고전적인 알고리듬은 기하급수적인 시간이 걸린다. 이산 로그 문제가 가우스 합 추정으로 축소되기 때문에 가우스 합을 추정하기 위한 효율적인 고전적 알고리듬은 이산 로그를 계산하기 위한 효율적인 고전적 알고리듬을 의미할 것이며, 이는 있을 법하지 않은 것으로 간주된다. 그러나 양자 컴퓨터는 가우스 합을 다항 시간의 다항 정밀도로 추정할 수 있다.

 푸리에 피싱 및 푸리에 검사 
우리는 n비트 문자열을 부울 값에 매핑하는 n 개의 무작위 부울 함수로 구성된 오라클을 가지고 있다. 아다마흐-푸리에 변환의 경우 문자열의 3/4 이상이 만족하는 n개의  n비트 문자열 z 1 ,..., z n 을 찾아야 한다.



1/4 이상 만족



이는 유계 오류 양자 다항식 시간 (BQP)에서 수행할 수 있다.

 진폭 증폭 기반 알고리듬 
진폭 증폭은 양자 상태의 선택된 부분 공간을 증폭할 수 있는 기술이다. 진폭 증폭의 적용은 일반적으로 해당하는 기존 알고리듬에 비해 2차 속도 향상을 가져온다. 그로버 알고리듬의 일반화라고 볼 수 있다.

 그로버 알고리듬 
그로버의 알고리듬은 개의 항목이 있는 구조화되지 않은 데이터베이스(또는 정렬되지 않은 목록)에서 표시된 항목을 검색한다.  대신 쿼리  고전적으로 필요한 쿼리. 고전적으로  제한된 오류 확률 알고리듬을 허용하는 경우에도 쿼리가 필요하다.

이론가들은 봄 역학에서 숨겨진 변수의 역사에 액세스할 수 있는 표준 양자 컴퓨터의 가상 일반화를 고려했다. (이러한 컴퓨터는 완전히 가설적이며 표준 양자 컴퓨터가 아니며 양자 역학의 표준 이론 하에서도 가능하지 않다. ) 그러한 가상의 컴퓨터는 기껏해야  항목 데이터베이스의 검색을 구현할 수 있다.  단계. 이보다 약간 빠르다.  그로버의 알고리듬이 취하는 단계. 두 검색 방법 모두 양자 컴퓨터 모델이 다항식 시간에 NP-완전 문제를 풀도록 허용하지 않는다.

 양자 집계 
양자 집계는 검색 문제의 일반화를 해결한다. 단순히 항목이 있는지 감지하는 대신 정렬되지 않은 목록에서 표시된 항목의 수를 세는 문제를 해결한다. 구체적으로, 그것은 표시된 항목의 수를 계산한다.  -원소 목록, 오류 있음  만들기만  쿼리, 여기서  목록에서 표시된 원소의 수이다. 보다 정확하게는 알고리듬이 추정치를 출력한다.  ~을 위한 , 표시된 항목 수, 정확도는 다음과 같다.  .

 양자 걸음 기반 알고리듬 
양자 걸음은 일부 상태에 대한 확률 분포로 설명할 수 있는 고전적인 무작위 걸음의 양자 아날로그이다. 양자 걸음은 상태에 대한 양자 중첩으로 설명할 수 있다. 양자 걸음은 일부 블랙박스 문제에 대해 기하급수적인 속도 향상을 제공하는 것으로 알려져 있다. 또한 많은 문제에 대해 다항식 속도 향상을 제공한다. 양자 걸음 알고리듬 생성을 위한 프레임워크가 존재하며 상당히 다재다능한 도구이다.

 원소 구별 문제 
원소 구별 문제는 목록의 모든 원소가 구별되는지 여부를 결정하는 문제이다. 일반적으로 크기가 N 인 목록에는  쿼리가 필요하다. 그러나, 양자 컴퓨터에서는  쿼리로 해결될 수 있다. 최적의 알고리듬은 안드리스 암바니이스가 제안한 알고리듬이다. Shi Yaoyun Shi는 범위의 크기가 충분히 클 때 빡빡한 하한을 먼저 증명했다.  암바니이스와 쿠틴은 독립적으로(그리고 다른 증명을 통해) 모든 함수에 대한 하한을 얻기 위해 작업을 확장했다.

 삼각형 찾기 문제 
삼각형 찾기 문제는 주어진 그래프에 삼각형(크기 3의 클릭)이 포함되어 있는지 여부를 결정하는 문제이다. 양자 알고리듬에 대해 가장 잘 알려진 하한은 이지만 알려진 최고의 알고리듬에는  쿼리가 필요하며 이전의 최상의 결과인  쿼리보다 개선되었다.

 수식 값 계산 
수식은 각 내부 노드에 게이트가 있고 각 리프 노드에 입력 비트가 있는 트리이다. 문제는 입력에 대한 오라클 액세스가 주어진 루트 노드의 출력인 공식을 계산하는 것이다.

잘 연구된 공식은 NAND 게이트만 있는 균형 이진 트리이다.이 유형의 수식에는 임의성을 사용하는  쿼리가 필요하다.  여기서 . 그러나 양자 알고리듬을 사용하면  쿼리로 해결할 수 있다.이 경우에 대한 더 나은 양자 알고리듬은 비전통적인 해밀토니안 오라클 모델에 대해 발견될 때까지 알려지지 않았다. 표준 설정에 대한 동일한 결과가 곧 이어졌다.

더 복잡한 공식을 위한 빠른 양자 알고리듬도 알려져 있다.

 군 가환성 
문제는 k개의 생성원에 의해 주어진 블랙박스 군이 가환인지 확인하는 것이다. 블랙박스 군은 군 연산(곱셈, 반전, 항등 비교)을 수행하는 데 사용해야 하는 오라클 함수가 있는 군이다. 우리는 문제를 해결하는 데 필요한 오라클 호출의 수인 쿼리 복잡성에 관심이 있다. 결정적 및 무작위 쿼리 복잡성은 각각와 이다. 양자 알고리듬에는  쿼리가 필요하다. 하지만 가장 잘 알려진 알고리듬은  쿼리를 사용한다.

 BQP-완전 문제 
BQP (Bounded-Error Quantum Polynomial Time) 복잡도 종류는 모든 인스턴스에 대해 오류 확률이 최대 1/3인 다항식 시간에 양자 컴퓨터가 해결할 수 있는 결정 문제 집합이다.Michael Nielsen and Isaac Chuang (2000). Quantum Computation and Quantum Information. Cambridge: Cambridge University Press. . 그것은 고전적인 복잡도 종류 BPP에 대한 양자버전이다.

BQP에 있는 문제는 BQP-완전이며 BQP의 모든 문제는 다항식 시간으로 줄일 수 있다. 비공식적으로 BQP-완전 문제들은 BQP에서 가장 어려운 문제만큼 어렵고 양자 컴퓨터로 효율적으로 해결할 수 있는 문제들이다(유계 오류 포함).

 매듭 불변량 계산 
위튼은 천-사이먼스 위상 양자장론 (TQFT)이 존스 다항식으로 풀릴 수 있음을 보여주었다. 양자 컴퓨터는 TQFT를 시뮬레이션할 수 있으므로 우리가 아는 한 최악의 시나리오에서 고전적으로 계산하기 어려운 존스 다항식을 근사화할 수 있다.

 양자 시뮬레이션 
양자 컴퓨터가 고전 컴퓨터보다 더 강력할 수 있다는 생각은 고전 컴퓨터가 다입자 양자 계를 시뮬레이션 하는 데 기하급수적인 시간이 필요한 것 같다는 리처드 파인만의 관찰에서 비롯되었다. 그 이후로 양자 컴퓨터가 기존 컴퓨터보다 기하급수적으로 빠르게 양자 물리 프로세스를 시뮬레이션할 수 있다는 생각이 크게 구체화되고 정교해졌다. 보손 및 페르미온 계를 모두 시뮬레이션내기 위해 효율적인(즉, 다항식 시간) 양자 알고리듬이 개발되었으며, 특히 현재의 고전적인 슈퍼컴퓨터의 기능을 넘어서는 화학 반응의 시뮬레이션에는 수백 큐비트만 필요하다. 양자 컴퓨터는 위상 양자장론을 효율적으로 시뮬레이션할 수도 있다. 위상 양자장론 자체에 대한 관심 외에도 이 결과는 존스 및 HOMFLY 다항식, 및 3차원 다양체의 투레브-비로 불변량과 같은 양자 위상 불변량을 추정하기 위한 효율적인 양자 알고리듬으로 이어졌다.

 연립 일차 방정식 해법 
2009년 아람 하로우는 연립 일차 방정식를 해결하기 위한 양자 알고리듬을 공식화했다. 이 알고리듬은 주어진 선형 방정식 계에 대한 해 벡터에 대한 스칼라 측정 결과를 추정한다.

연립 일차 방정식이 희박하고 조건수 가 낮은 경우, 사용자가 해 벡터 자체의 값 대신 해 벡터에 대한 스칼라 측정 결과에 관심이 있는 경우 알고리듬의 런타임은 과 같다. 여기서 은 연립 일차 방정식의 변수 수이다. 이것은  (또는  양의 준정부호 행렬의 경우)로 실행되는 가장 빠른 기존 알고리듬에 비해 기하급수적인 속도 향상을 제공한다.

 하이브리드 양자/고전 알고리듬 
하이브리드 양자/고전적 알고리듬은 양자 상태 준비 및 측정을 고전적 최적화와 결합한다. 이러한 알고리듬은 일반적으로 에흐미트 연산자의 바닥 상태 고유 벡터 및 고유 값을 결정하는 것을 목표로 한다.

 QAOA 
양자 근사 최적화 알고리듬은 그래프 이론의 문제를 해결하는 데 사용할 수 있는 양자 어닐링의 장난감 모델이다.이 알고리듬은 목적 함수를 최대화하기 위해 양자 연산의 고전적인 최적화를 사용한다.

 변분법적 양자 고유값 해법 
변분법적 양자 고유값 해법 알고리듬은 고전적인 최적화를 적용하여 분자의 바닥 상태 에너지를 찾기 위해 ansatz 상태의 에너지 기대치를 최소화한다. 이것은 또한 분자의 들뜬 에너지를 찾기 위해 확장될 수 있다.

 축소된 양자 고유값 해법 
CQE 알고리듬은 슈뢰딩거 방정식의 축소(또는 사영)의 residual을 두 개(또는 그 이상) 전자의 공간으로 최소화하여 바닥 상태 또는 여기 상태 에너지와 분자의 두 전자 감소 밀도 행렬을 찾는 이는 반 에흐미트 축소 슈뢰딩거 방정식에서 직접 에너지와 2전자 감소 밀도 행렬을 풀기 위한 고전적인 방법을 기반으로 한다.

 같이 보기 

 양자 기계 학습
 양자 최적화 알고리듬
 양자 정렬
 소수 판별법

 각주 

 외부 링크 
 양자 알고리듬에 대한 Andrew Childs의 강의 노트
 양자 검색 알고리듬 - 무차별 대입  .

 서베이 




분류:신기술
분류:양자 알고리즘
분류:이론 컴퓨터 과학
분류:양자 컴퓨팅
분류:양자 정보 이론