양자 알고리즘 - Quantum algorithm

양자 알고리즘 - Quantum algorithm

양자 계산에서 양자 알고리즘은 양자 계산의 현실적인 모델에서 실행되는 알고리즘으로, 가장 일반적으로 사용되는 모델은 계산의 양자 회로 모델이다. 고전(또는 비 퀀텀) 알고리즘은 명령의 유한 순서 또는 문제 해결을 위한 단계별 절차로, 각 단계 또는 명령이 클래식 컴퓨터에서 수행될 수 있다. 마찬가지로 양자 알고리즘은 양자 컴퓨터에서 각각의 단계를 수행할 수 있는 단계별 절차다. 비록 모든 고전 알고리즘은 양자 컴퓨터에서도 수행될 수 있지만, 양자 알고리즘이라는 용어는 본질적으로 양자처럼 보이는 알고리즘에 사용되거나 양자 중첩이나 양자 얽힘과 같은 양자 계산의 필수적인 특징을 사용한다.

고전적인 컴퓨터를 사용한 불문율적인 문제들은 양자 컴퓨터를 사용한 불문율적인 것으로 남아있다. 양자 알고리즘을 흥미롭게 하는 것은 양자 알고리즘이 아마도 고전적인 컴퓨터에서는 양자 중첩과 양자 얽힘이 효율적으로 시뮬레이션될 수 없기 때문에 고전적인 알고리즘보다 어떤 문제를 더 빨리 해결할 수 있을지도 모른다는 것이다.

가장 잘 알려진 알고리즘은 팩토링에 대한 쇼어의 알고리즘과 비정형 데이터베이스나 정렬되지 않은 목록을 검색하는 그로버의 알고리즘이다. Shor의 알고리즘은 가장 잘 알려진 인수용 고전 알고리즘인 일반 숫자 필드 체보다 훨씬 빠르게(거의 기하급수적으로) 작동한다. 그로버의 알고리즘은 동일한 작업에 대해 가능한 최고의 고전 알고리즘인 선형 검색보다 2차적으로 빠르게 실행된다.

개요

양자 알고리즘은 일반적으로 사용되는 양자 계산의 회로 모델에서 일부 입력 쿼트에 작용하고 측정으로 끝나는 양자 회로에 의해 설명된다. 양자 회로는 기껏해야 정해진 수의 퀘빗에 작용하는 단순한 양자 게이트로 구성된다. 퀘빗의 수는 수정되어야 한다. 왜냐하면 퀘빗의 수의 변화는 비위생적인 진화를 의미하기 때문이다. 양자 알고리즘은 해밀턴 오라클 모델과 같은 다른 양자 연산 모델에서도 명시될 수 있다.

양자 알고리즘은 알고리즘이 사용하는 주요 기법으로 분류할 수 있다. 양자 알고리즘에서 일반적으로 사용되는 기법/이데아로는 위상 킥백, 위상 추정, 양자 푸리에 변환, 양자 보행, 진폭 증폭 및 위상 양자장 이론이 있다. 양자 알고리즘은 또한 해결된 문제의 유형별로 분류될 수 있다. 예를 들어 대수 문제에 대한 양자 알고리즘 조사를 참조한다.

양자 푸리에 변환에 기반한 알고리즘

양자 푸리에 변환은 이산 푸리에 변환의 양자 아날로그로, 여러 양자 알고리즘에 사용된다. 하다마드 변환은 또한 필드 F2 위에 있는 n차원 벡터 공간을 통한 양자 푸리에 변환의 예다. 양자 푸리에 변환은 다항식 양자 게이트 수만을 사용하여 양자 컴퓨터에서 효율적으로 구현될 수 있다.

독일-조즈사 양자 알고리즘

독일-조즈사 알고리즘은 블랙박스 문제를 해결하는데, 이것은 아마도 결정론적인 고전적 컴퓨터의 경우 블랙박스에 기하급수적으로 많은 쿼리를 필요로 하지만 양자컴퓨터에 의해 정확히 하나의 쿼리로 수행될 수 있다. 만약 우리가 경계 오류 양자 알고리즘과 고전적 알고리즘을 모두 허용한다면, 고전적 확률론 알고리즘은 오류 확률이 적은 일정한 수의 쿼리로 문제를 해결할 수 있기 때문에 속도 상승이 없다. 알고리즘은 함수 f가 상수(모든 입력에 0 또는 모든 입력에 1)인지 또는 균형(입력 영역의 절반에 대해 1을 반환하고 나머지 절반에 대해서는 0을 반환하는지 여부를 결정한다.

사이먼 알고리즘

사이먼의 알고리즘은 경계 오류 확률 알고리즘을 포함한 어떤 고전 알고리즘보다 블랙박스 문제를 기하급수적으로 빠르게 해결한다. 우리가 효율적이라고 생각하는 모든 고전 알고리즘에 대해 기하급수적인 속도 증가를 달성하는 이 알고리즘은 쇼르의 인수 알고리즘의 동기였다.

양자 위상 추정 알고리즘

양자 위상 추정 알고리즘은 고유 벡터에 비례하는 양자 상태를 부여하고 게이트에 접근하는 단일 게이트의 고유 벡터의 고유 위상을 결정하는 데 사용된다. 알고리즘은 다른 알고리즘에서 서브루틴으로 자주 사용된다.