맨위로가기 타임라인 바로가기

양자 알고리즘

"오늘의AI위키"는 AI 기술로 일관성 있고 체계적인 최신 지식을 제공하는 혁신 플랫폼입니다.
"오늘의AI위키"의 AI를 통해 더욱 풍부하고 폭넓은 지식 경험을 누리세요.
타임라인 바로가기
목차

1. 개요

양자 알고리즘은 양자 컴퓨터를 사용하여 문제를 해결하는 알고리즘이다. 역사적으로 발전해왔으며, 양자 푸리에 변환, 진폭 증폭, 양자 걸음과 같은 다양한 기법을 기반으로 하는 알고리즘이 개발되었다. 쇼어 알고리즘과 같은 특정 알고리즘은 소인수분해와 이산 로그 문제를 다항 시간 내에 해결하여 고전적인 알고리즘보다 효율적이며, 하이브리드 양자/고전 알고리즘은 양자 상태 준비와 측정을 고전적인 최적화와 결합한다.

더 읽어볼만한 페이지

  • 양자 알고리즘 - 쇼어 알고리즘
    쇼어 알고리즘은 소인수분해 및 이산 로그 문제를 해결하는 양자 알고리즘으로, 양자 위상 추정 알고리즘과 연분수 알고리즘을 활용하며, 공개 키 암호화 방식을 깨뜨릴 수 있다.
  • 양자 알고리즘 - 도이치–조사 알고리듬
    도이치–조사 알고리듬은 양자역학적 현상을 이용하여 주어진 함수가 상수 함수인지 균형 함수인지 판별하는 알고리듬으로, 단일 함수 호출만으로 함수 유형을 결정할 수 있어 양자 컴퓨터 연구 개발에 영감을 주었다.
  • 양자 정보 이론 - 슈뢰딩거-HJW 정리
    슈뢰딩거-HJW 정리는 섞인 양자 상태의 서로 다른 순수 상태 앙상블 표현들이 보조 공간에 작용하는 유니터리 변환으로 연결됨을 보여주는 정리이며, 동일한 섞인 상태에 대한 서로 다른 순화는 보조 공간에서의 유니터리 연산자에 의해서만 달라진다.
  • 양자 정보 이론 - 양자정보
    양자정보는 양자역학 원리를 활용해 정보를 표현하고 처리하는 학문으로, 큐비트를 기본 단위로 사용하며 중첩, 얽힘 등의 특성을 이용하여 양자 통신, 양자 암호, 양자 컴퓨팅 등 다양한 분야에 응용된다.
  • 양자 컴퓨팅 - 위상 양자 컴퓨터
    위상 양자 컴퓨터는 애니온의 꼬임 상태를 이용하여 양자 정보를 저장하고 처리하는 양자 컴퓨터로, 2차원 공간에서 준입자인 애니온의 특성을 활용하며, 양자 회로 모델 등과 계산 능력이 동일하지만 특정 알고리즘에 유리하고 실험적 확인은 논쟁 중에 있다.
  • 양자 컴퓨팅 - 양자 프로그래밍
    양자 프로그래밍은 양자 컴퓨터 제어 및 양자 알고리즘 구현을 위한 프로그래밍 방식으로, 양자 명령어 집합과 양자 소프트웨어 개발 키트 및 프로그래밍 언어를 통해 양자 컴퓨팅 연구 및 개발을 지원한다.
양자 알고리즘
양자 알고리즘 개요
유형양자 컴퓨터에서 실행되는 알고리즘
기반중첩 및/또는 양자 얽힘
세부 정보
관련 연구 분야양자 정보 과학
컴퓨터 과학

2. 역사적 배경

양자 알고리듬은 일반적으로 양자 계산의 회로 모델에서 일부 입력 큐비트에 작용하고 측정으로 종료되는 양자 회로로 설명된다. 양자 회로는 각각 유한 수의 큐비트에 작용하는 간단한 양자 게이트로 구성된다. 큐비트 수의 변화는 비유니타리 진화를 의미하기 때문에 큐비트 수는 고정되어야 한다. 양자 알고리듬은 해밀턴 오라클 모델과 같은 다른 양자 계산 모델에서도 설명될 수 있다.[60][7]

양자 알고리듬은 알고리듬에 관련된 주요 기술에 따라 분류할 수 있다. 양자 알고리듬에 일반적으로 사용되는 기술에는 위상 반전, 위상 추정, 양자 푸리에 변환, 양자 보행, 진폭 증폭, 위상 양자장론 등이 있다. 양자 알고리듬은 해결된 문제 유형별로 그룹화될 수도 있다. (예: 대수적 문제에 대한 양자 알고리듬 조사)[8][61]

2. 1. 양자 알고리듬의 초기 발전

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

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

2. 2. 주요 양자 알고리듬의 등장

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

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

2. 3. 21세기 양자 알고리듬 연구의 확장

양자 알고리듬은 일반적으로 널리 사용되는 양자 계산의 회로 모델에서 일부 입력 큐비트에 작용하고 측정으로 종료되는 양자 회로로 설명된다. 양자 회로는 각각 유한 수의 큐비트에 작용하는 간단한 양자 게이트로 구성된다. 양자 알고리듬은 해밀턴 오라클 모델과 같은 다른 양자 계산 모델에서도 설명될 수 있다.[7]

양자 알고리듬은 알고리듬에 관련된 주요 기술에 따라 분류할 수 있다. 양자 알고리듬에 일반적으로 사용되는 기술에는 위상 반전, 위상 추정, 양자 푸리에 변환, 양자 보행, 진폭 증폭, 위상 양자장론 등이 있다. 양자 알고리듬은 해결된 문제 유형별로 그룹화될 수도 있다. (예: 대수적 문제에 대한 양자 알고리즘 조사)[8]

3. 양자 푸리에 변환 기반 알고리듬

양자 푸리에 변환은 이산 푸리에 변환과 유사한 양자 알고리듬이며, 여러 양자 알고리듬에 사용된다. 아다마르 변환은 유한체 \mathbb F_2 에 대한 n 차원 벡터 공간에서의 양자 푸리에 변환의 한 예시이다. 양자 푸리에 변환은 다항식적으로 증가하는 양자 게이트들만을 사용하여 양자 컴퓨터에서 효율적으로 구현할 수 있다.

양자 푸리에 변환은 다음과 같은 알고리듬들의 기반이 된다.


  • 도이치-조사 알고리듬: 함수가 상수인지 균형인지 판별한다.
  • 번스타인-바지라니 알고리듬: 고전 알고리듬보다 효율적으로 특정 문제를 해결한다.
  • 사이먼 알고리듬: 특정 블랙박스 문제를 고전 알고리듬보다 기하급수적으로 빠르게 해결한다.
  • 양자 위상 추정 알고리듬: 유니터리 게이트의 고유 벡터의 고유 위상을 추정한다.
  • 쇼어 알고리듬: 소인수분해와 이산 로그 문제를 다항식 시간에 해결한다.
  • 숨은 부분군 문제: 여러 문제들의 일반화된 형태로, 효율적인 양자 알고리듬이 알려져 있다.
  • 가우스 합 추정: 가우스 합을 다항식 시간에 다항식 정밀도로 추정할 수 있다.
  • 푸리에 피싱 및 푸리에 검사: 특정 조건을 만족하는 문자열을 찾는 문제로, 유계 오류 양자 다항식 시간 내에서 수행 가능하다.

3. 1. 도이치-조사 알고리듬

도이치-조사 알고리듬


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

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

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

3. 3. 사이먼 알고리듬

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

3. 4. 양자 위상 추정 알고리듬

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

3. 5. 쇼어 알고리듬

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

3. 6. 숨은 부분군 문제

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

3. 7. 가우스 합 추정

가우스 합은 지수 합의 한 유형이다. 이러한 합을 추정하기 위한 가장 잘 알려진 고전적인 알고리듬은 기하급수적인 시간이 걸린다. 이산 로그 문제가 가우스 합 추정으로 환원되므로, 가우스 합을 추정하는 효율적인 고전적 알고리듬은 이산 로그를 계산하는 효율적인 고전적 알고리듬을 의미하며, 이는 가능성이 낮다고 여겨진다.[13] 그러나 양자 컴퓨터는 다항식 시간에 다항식 정밀도로 가우스 합을 추정할 수 있다.[13]

3. 8. 푸리에 피싱 및 푸리에 검사

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

:| \tilde{f}(z_i)| \geqslant 1

또한, 1/4 이상은 다음을 만족한다.

:| \tilde{f}(z_i) | \geqslant 2.

이는 유계 오류 양자 다항식 시간 (BQP) 내에서 수행될 수 있다.[14]

4. 진폭 증폭 기반 알고리듬

진폭 증폭은 양자 상태에서 선택된 부분 공간을 증폭하는 기술이다. 진폭 증폭을 적용하면 일반적으로 해당하는 기존 알고리듬보다 이차적인 속도 향상을 얻을 수 있다. 이는 그로버 알고리듬의 일반화된 형태로 볼 수 있다.[15]

4. 1. 그로버 알고리듬

그로버 알고리듬(Grover algorithm영어)은 구조화되지 않은 데이터베이스(또는 정렬되지 않은 목록)에서 N개의 항목 중 표시된 항목을 검색한다. 고전적으로는 O({N}) 쿼리가 필요하지만, 그로버 알고리듬은 O(\sqrt{N}) 쿼리만 사용한다.[15] 제한된 오류 확률을 허용하는 알고리듬을 허용하는 경우에도 고전적으로는 O({N}) 쿼리가 필요하다.

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

4. 2. 양자 계수

양자 계수는 탐색 문제의 일반화를 해결한다. 이는 단순히 존재 여부를 감지하는 대신 정렬되지 않은 목록에서 표시된 항목의 수를 세는 문제를 해결한다. 구체적으로, 이 알고리즘은 N개의 요소로 이루어진 목록에서 최대 \varepsilon의 오차로 표시된 항목의 수를 센다. 이 때 알고리즘은 \Theta\left(\varepsilon^{-1} \sqrt{N/k}\right)개의 쿼리를 수행하며, 여기서 k는 목록에서 표시된 요소의 수이다.[17][18] 보다 정확하게는, 이 알고리즘은 표시된 항목의 수인 k에 대한 추정치 k'을 출력하며, 정확도는 |k-k'| \leq \varepsilon k이다.

양자 집계는 양자 계수와 마찬가지로 검색 문제의 일반화를 해결하며, 정렬되지 않은 목록에서 표시된 항목의 수를 계산한다.[68][69] N개의 원소 목록에서 오류 \varepsilon 범위 내에서, \Theta\left(\frac{1}{\varepsilon} \sqrt{\frac{N}{k}}\right) 쿼리만으로 계산하며, 여기서 k는 목록에서 표시된 원소의 수이다. 알고리즘은 k에 대한 추정치 k'를 출력하며, 정확도는 |k-k'| \leq \varepsilon k이다.

5. 양자 걸음 기반 알고리듬

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

5. 1. 원소 구별 문제

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

5. 2. 삼각형 찾기 문제

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

5. 3. 수식 값 계산

수식은 각 내부 노드에 게이트가 있고 각 리프 노드에 입력 비트가 있는 트리이다. 문제는 입력에 대한 오라클 접근 권한이 주어졌을 때 루트 노드의 출력인 수식을 계산하는 것이다.

잘 연구된 수식은 NAND 게이트만 있는 균형 이진 트리이다.[74] 이 유형의 수식은 임의성을 사용하는 \Theta(N^{c}) 쿼리가 필요하며, 여기서 c = \log_2(1+\sqrt{33})/4 \approx 0.754이다. 그러나 양자 알고리듬을 사용하면 \Theta(N^{0.5}) 쿼리로 해결할 수 있다. 이 경우에 대한 더 나은 양자 알고리듬은 비전통적인 해밀토니안 오라클 모델에 대해 발견될 때까지 알려지지 않았다.[60] 표준 설정에 대한 동일한 결과가 곧 이어졌다.

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

5. 4. 군 가환성

''k''개의 생성원으로 주어진 블랙 박스 군이 가환인지 확인하는 문제이다. 블랙 박스 군은 군 연산(곱셈, 역원, 항등원과의 비교)을 수행하는 데 사용해야 하는 오라클 함수를 가진 군이다. 이 문제에서는 문제 해결에 필요한 오라클 호출 횟수인 질의 복잡도가 중요하다. 결정적 질의 복잡도와 확률적 질의 복잡도는 각각 \Theta(k^2)과 \Theta(k)이다.[37] 양자 알고리즘은 \Omega(k^{2/3})의 질의를 필요로 하는 반면, 가장 잘 알려진 고전 알고리즘은 O(k^{2/3} \log k)의 질의를 사용한다.[38]

6. BQP-완전 문제

BQP-완전 문제는 BQP에서 가장 어려운 문제만큼 어렵고, 양자 컴퓨터로 효율적으로 해결할 수 있는 문제들이다(유계 오류 포함). 어떤 문제가 BQP-완전 문제이려면, 그 문제가 BQP에 속해야 하고, BQP에 속하는 모든 문제는 다항 시간 내에 그 문제로 환원될 수 있어야 한다.[77][39]

BQP-완전 문제의 예시로는 매듭 불변량 계산, 양자 시뮬레이션, 연립 일차 방정식 해법 등이 있다.

6. 1. 매듭 불변량 계산

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

6. 2. 양자 시뮬레이션

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

6. 3. 연립 일차 방정식 해법

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

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

2009년, 아람 해로우, 아비나탄 하씨딤, 그리고 세스 로이드는 선형 연립 방정식을 풀기 위한 양자 알고리즘을 공식화했다.[48] 이 알고리즘은 주어진 선형 연립 방정식의 해 벡터에 대한 스칼라 측정 결과를 추정한다.

선형 시스템이 희소 행렬이고 낮은 조건수 \kappa를 가지며, 사용자가 해 벡터 자체의 값 대신 해 벡터에 대한 스칼라 측정 결과에 관심이 있는 경우, 알고리즘의 실행 시간은 O(\log(N)\kappa^2)이며, 여기서 N은 선형 시스템의 변수 수이다. 이는 가장 빠른 고전적 알고리즘인 O(N\kappa) (또는 양의 반정부호 행렬의 경우 O(N\sqrt{\kappa}))보다 지수적 속도 향상을 제공한다.

7. 하이브리드 양자/고전 알고리듬

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

7. 1. QAOA (Quantum Approximate Optimization Algorithm)

양자 근사 최적화 알고리듬(QAOA, Quantum Approximate Optimization Algorithm)은 양자 어닐링에서 영감을 받아 양자 회로를 사용하여 양자 어닐링의 이산화된 근사를 수행한다. 이는 그래프 이론의 문제를 해결하는 데 사용될 수 있다.[50] 이 알고리듬은 "목적 함수"를 최대화하기 위해 양자 연산의 고전적 최적화를 사용한다.

7. 2. 변분법적 양자 고유값 해법 (VQE)

변분 양자 고유값 풀이(VQE) 알고리즘은 ansatz 상태의 에너지 기댓값을 최소화하기 위해 고전적 최적화를 적용하여 분자의 해밀토니안과 같은 에르미트 연산자의 바닥 상태를 찾는다.[51] 이 알고리즘은 분자의 바닥 상태 에너지 뿐만 아니라, 들뜬 에너지 상태를 찾는 데에도 확장될 수 있다.[87][52]

7. 3. 축소된 양자 고유값 해법 (CQE)

CQE 알고리듬은 분자의 바닥 상태 또는 들뜬 상태 에너지와 2전자 축소 밀도 행렬을 찾기 위해, 슈뢰딩거 방정식을 두 개(또는 그 이상)의 전자의 공간으로 축약(또는 투영)한 잔차를 최소화한다.[89][53] 이는 반-에르미트 축약된 슈뢰딩거 방정식으로부터 에너지와 2전자 축소 밀도 행렬을 직접 풀기 위한 고전적 방법에 기반한다.[90][54]

참조

[1] 서적 Quantum Computation and Quantum Information Cambridge University Press
[2] arXiv Quantum Algorithms 2008
[3] 서적 Quantum Computer Science https://books.google[...] Morgan & Claypool Publishers 2009-01-01
[4] 서적 Quantum Computation and Quantum Information https://books.google[...] Cambridge University Press
[5] 웹사이트 Shor's algorithm https://quantum-comp[...]
[6] 웹인용 IBM quantum composer user guide: Grover's algorithm https://quantum-comp[...] 2022-06-07
[7] 간행물 A Quantum Algorithm for the Hamiltonian NAND Tree 2008
[8] 간행물 Quantum algorithms for algebraic problems
[9] 간행물 Polynomial-Time Algorithms for Prime Factorization and Discrete Logarithms on a Quantum Computer
[10] conference Quantum cryptoanalysis of hidden linear functions Springer-Verlag
[11] arXiv The Symmetric Group Defies Strong Fourier Sampling: Part I
[12] arXiv Quantum Computation and Lattice Problems 2003
[13] arXiv Efficient Quantum Algorithms for Estimating Gauss Sums
[14] arXiv BQP and the Polynomial Hierarchy
[15] arXiv A fast quantum mechanical algorithm for database search 1996
[16] 웹사이트 Quantum Computing and Hidden Variables https://www.scottaar[...]
[17] 서적 Automata, Languages and Programming 1998
[18] 서적 Quantum Computation and Quantum Information
[19] conference Exponential algorithmic speedup by quantum walk Association for Computing Machinery
[20] conference Quantum Algorithms for Hidden Nonlinear Structures IEEE
[21] 간행물 Figure 1: The boson-sampling problem http://www.nature.co[...] Nature 2014-09-12
[22] 간행물 Quantum Walks of Correlated Photons https://www.science.[...] 2010-09-17
[23] 간행물 Boson Sampling from Gaussian States 2014-09-05
[24] 웹사이트 The quantum revolution is a step closer http://phys.org/news[...] Omicron Technology Limited 2014-09-12
[25] 간행물 Boson sampling with displaced single-photon Fock states versus single-photon-added coherent states: The quantum-classical divide and computational-complexity transitions in linear optics
[26] 간행물 Quantum Walk Algorithm for Element Distinctness
[27] conference The 43rd Annual IEEE Symposium on Foundations of Computer Science, 2002. Proceedings.
[28] 간행물 Polynomial Degree and Lower Bounds in Quantum Complexity: Collision and Element Distinctness with Small Range
[29] 간행물 Quantum Lower Bound for the Collision Problem with Small Range
[30] arXiv Span Programs for Functions with Constant-Sized 1-certificates
[31] conference Search via quantum walk Association for Computing Machinery
[32] 간행물 Quantum Algorithms for the Triangle Problem
[33] 웹사이트 NAND now for something completely different http://scottaaronson[...] 2009-12-17
[34] conference Probabilistic Boolean Decision Trees and the Complexity of Evaluating Game Trees http://www.math.ias.[...] IEEE
[35] arXiv A nearly optimal discrete query quantum algorithm for evaluating NAND formulas
[36] 학회인용 Span-program-based quantum algorithm for evaluating formulas Association for Computing Machinery
[37] 저널 Testing commutativity of a group and the power of randomization
[38] 저널 Quantum Complexity of Testing Group Commutativity
[39] 서적 Quantum Computation and Quantum Information Cambridge University Press
[40] 학회인용 A polynomial quantum algorithm for approximating the Jones polynomial Association for Computing Machinery
[41] 저널 Simulating physics with computers
[42] 저널 Simulation of many-body Fermi systems on a universal quantum computer
[43] 저널 Polynomial-time quantum algorithm for the simulation of chemical dynamics
[44] 저널 Simulation of Topological Field Theories by Quantum Computers
[45] 저널 A polynomial quantum algorithm for approximating the Jones polynomial
[46] 저널 The Jones polynomial: quantum algorithms and applications in quantum complexity theory
[47] 저널 Approximating Turaev-Viro 3-manifold invariants is universal for quantum computation
[48] 저널 Quantum algorithm for solving linear systems of equations
[49] 저널 Quantum optimization using variational algorithms on near-term quantum devices 2018
[50] arXiv A Quantum Approximate Optimization Algorithm 2014-11-14
[51] 저널 A variational eigenvalue solver on a photonic quantum processor 2014-07-23
[52] 저널 Variational Quantum Computation of Excited States
[53] 저널 Quantum Solver of Contracted Eigenvalue Equations for Scalable Molecular Simulations on Quantum Computing Devices 2021-02-18
[54] 저널 Anti-Hermitian Contracted Schrödinger Equation: Direct Determination of the Two-Electron Reduced Density Matrices of Many-Electron Molecules 2006-10-06
[55] 서적 Quantum Computation and Quantum Information https://archive.org/[...] Cambridge University Press
[56] 서적 Quantum Computer Science https://books.google[...] Morgan & Claypool Publishers 2009-01-01
[57] 서적 Quantum Computation and Quantum Information https://books.google[...] Cambridge University Press
[58] 웹인용 Shor's algorithm https://quantum-comp[...] 2023-02-12
[59] 웹인용 IBM quantum composer user guide: Grover's algorithm https://quantum-comp[...] 2022-06-07
[60] 저널 A Quantum Algorithm for the Hamiltonian NAND Tree 2008
[61] 저널 Quantum algorithms for algebraic problems
[62] 저널 Polynomial-Time Algorithms for Prime Factorization and Discrete Logarithms on a Quantum Computer
[63] 저널 Figure 1: The boson-sampling problem http://www.nature.co[...] Nature 2014-09-12
[64] 저널 Boson Sampling from Gaussian States 2014-09-05
[65] 웹인용 The quantum revolution is a step closer http://phys.org/news[...] Omicron Technology Limited 2014-09-12
[66] 저널 Boson sampling with displaced single-photon Fock states versus single-photon-added coherent states: The quantum-classical divide and computational-complexity transitions in linear optics
[67] 웹인용 Quantum Computing and Hidden Variables https://www.scottaar[...]
[68] 서적 Quantum Counting 1998
[69] 서적 Quantum Computation and Quantum Information
[70] 저널 Quantum Walk Algorithm for Element Distinctness
[71] 논문 Polynomial Degree and Lower Bounds in Quantum Complexity: Collision and Element Distinctness with Small Range
[72] 논문 Quantum Lower Bound for the Collision Problem with Small Range
[73] 논문 Quantum Algorithms for the Triangle Problem
[74] 웹인용 NAND now for something completely different 2007-02-03
[75] 논문 Testing commutativity of a group and the power of randomization
[76] 논문 Quantum Complexity of Testing Group Commutativity
[77] 서적 Quantum Computation and Quantum Information Cambridge University Press
[78] 논문 Simulating physics with computers
[79] 논문 Simulation of many-body Fermi systems on a universal quantum computer
[80] 논문 Polynomial-time quantum algorithm for the simulation of chemical dynamics
[81] 논문 Simulation of Topological Field Theories by Quantum Computers
[82] 논문 A polynomial quantum algorithm for approximating the Jones polynomial
[83] 논문 The Jones polynomial: quantum algorithms and applications in quantum complexity theory
[84] 논문 Approximating Turaev-Viro 3-manifold invariants is universal for quantum computation
[85] 논문 Quantum algorithm for solving linear systems of equations
[86] 논문 Quantum optimization using variational algorithms on near-term quantum devices 2018
[87] 논문 A variational eigenvalue solver on a photonic quantum processor 2014-07-23
[88] 논문 Variational Quantum Computation of Excited States
[89] 논문 Quantum Solver of Contracted Eigenvalue Equations for Scalable Molecular Simulations on Quantum Computing Devices 2021-02-18
[90] 논문 Anti-Hermitian Contracted Schrödinger Equation: Direct Determination of the Two-Electron Reduced Density Matrices of Many-Electron Molecules 2006-10-06

관련 사건 타임라인

( 최근 20개의 뉴스만 표기 됩니다. )


본 사이트는 AI가 위키백과와 뉴스 기사,정부 간행물,학술 논문등을 바탕으로 정보를 가공하여 제공하는 백과사전형 서비스입니다.
모든 문서는 AI에 의해 자동 생성되며, CC BY-SA 4.0 라이선스에 따라 이용할 수 있습니다.
하지만, 위키백과나 뉴스 기사 자체에 오류, 부정확한 정보, 또는 가짜 뉴스가 포함될 수 있으며, AI는 이러한 내용을 완벽하게 걸러내지 못할 수 있습니다.
따라서 제공되는 정보에 일부 오류나 편향이 있을 수 있으므로, 중요한 정보는 반드시 다른 출처를 통해 교차 검증하시기 바랍니다.

문의하기 : help@durumis.com