[논문번역] Quantum computations (course of lectures)

제목 : Quantum computations (course of lectures)

저자 및 관련 : Yuri I. Ozhigov Moscow State University of M.V.Lomonosov, Faculty of Computational Mathematics and Cebernetics, Moscow center of fundamental and applied mathematics, Institute of physics and technology of K.A.Valiev (RAS), e-mail: ozhigov@cs.msu.ru

2107.08047.pdf

3.42MB

 

This is just translated to korean by google translator.

Original article is attached.

페이지 1

양자 계산(강의 과정)

유리 I. 오지고프

모스크바 주립대학교 MVLomonosov, 계산 학부

수학 및 Cebernetics, 모스크바 기초 및 응용 센터

수학, KAValiev (RAS)의 물리학 및 기술 연구소,

이메일: ozhigov@cs.msu.ru

1

arXiv:2107.08047v1 [quant-ph] 2021년 7월 16일

---

2 쪽

핵심어 : 양자컴퓨터, 양자알고리즘, 결맞음, 양자모델-

ing, 양자 비국소성

주석

이 강의 과정은 Lomonosov Moscow에서 몇 년 동안 진행되었습니다.

주립대학교; 2021년 수정된 버전은 Zhejiang University(Hangzhou)에서 읽히고,

양자 컴퓨팅에 대한 여름 학교의 틀에서. 코스는

양자 역학에 기반한 새로운 유형의 계산. 양자 계산은

소위 말하는 공간에서 발생한다는 점에서 고전적인 것과 근본적으로 다릅니다.

일반적인 이진 문자열이 아닌 양자 상태. 물리적 구현

양자 컴퓨팅 - 양자 컴퓨터라고 하는 장치는 이미 부분적으로

만들어졌으며 그 기술은 계속해서 집중적으로 발전하고 있습니다. 양자 컴퓨팅은

수학적 설명이 양자와 불가분하게 연결된 실제 과정

물리학. 특히, 복잡한 시스템의 양자 역학, 그 모델은

양자 컴퓨터는 현재 만들어지고 있는 단계에 불과하기 때문에 양자 컴퓨터는 재미있습니다.

적용된 것보다 더 근본적인 방향. 따라서 과정에서 -

일반적, 수학적, 이 새로운 물리적 구현에 많은 관심을 기울입니다.

계산 유형. 다양한 형태의 양자 컴퓨팅이 고려됩니다. Feynman

게이트 모델, 페르미온 및 단열 계산. 문제의 종류는 에 설명되어 있습니다.

양자 컴퓨팅은 고전적 컴퓨팅보다 효율적일 뿐만 아니라

그들로 대체됩니다. 복잡한 프로세스를 설명하는 가장 중요한 작업입니다.

예측 수준에서. 특히 양자 비국소성 현상을 이용하여

20세기 말에 다뤘다. 양자의 궁극적 가능성에 대한 추정

컴퓨팅도 제공됩니다 - 양자 복잡성에 대한 더 낮은 추정. 코스는 드-

물리학, 수학 및 자연과학 전공의 학생들뿐만 아니라

이 주제에 관심이 있는 모든 사람. 선형 대수학의 기초 지식이 필요합니다.

대학의 처음 두 과정에서 수학적 분석.

내용

소개

6

1 강의 1. 양자역학과 자연의 모델링

10

1.1 상태의 양자 표현. . . . . . . . . . . . . . . . . . . . . . . 15

1.2 단일 진화 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19

1.3 매트릭스 역학 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21

1.4 경로 적분 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 22

2 강의 2. 복합 시스템

27

2.0.1 텐서 제품 . . . . . . . . . . . . . . . . . . . . . . . . . . . . 27

2

---

3페이지

2.1 부분 측정. 혼합 상태 . . . . . . . . . . . . . . . . . . . . . . 28

2.2 슈미트 정리 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 32

2.3 양자 엔트로피의 역설 . . . . . . . . . . . . . . . . . . . . . . . 34

3 강의 3. 양자 게이트

35

3.1 단일 큐비트 게이트, CNOT, CSign, Λ φ 및 Tofffoli . . . . . . . . . . . . . 37

3.2 양자 암호의 개념 . . . . . . . . . . . . . . . . . . . . 38

3.3 양자 순간이동 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 40

4 강의 4. Grover 검색 알고리즘

42

4.1 Grover 알고리즘의 연속 버전. . . . . . . . . . . . . . . . . . 46

4.2 고전적 계산의 양자 가속과 그 한계. . . . . . . . . . 46

5 강의 5. 함수와 연산자의 이산화

50

5.1 관측 가능한 물리량 . . . . . . . . . . . . . . . . . . . . . . . 52

5.2 좌표 관찰 . . . . . . . . . . . . . . . . . . . . . . . . . 52

5.3 양자 푸리에 연산자와 임펄스 관찰 . . . . . . . 53

5.4 양자 컴퓨터에서 양자 푸리에 변환의 구현 55

5.5 Zalka-Wiesner 알고리즘 . . . . . . . . . . . . . . . . . . . . . . . . . 57

5.6 QFT로 숨겨진 기간 공개 . . . . . . . . . . . . . . . . . . . . . . 58

5.7 정수 인수분해 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 60

5.8 이산 최적화 문제의 해결 . . . . . . . . . . . . . . . 62

6 강의 6. 단열 양자 계산

62

6.1 단열 정리 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 62

6.2 Grover 알고리즘의 단열 형식 . . . . . . . . . . . . . . . . . . . . . . 67

6.3 단열 계산을 위한 해밀턴의 구성 . . . . . . . . . . 71

7 강의 7. 양자결합에서 단순화된 제어와 페르미온 동일성

추측

74

7.1 양자 계산에서 하나의 큐비트 제어 . . . . . . . . . . . . . . . . . 75

7.1.1 하나의 큐비트 제어에서 양자 푸리에 변환의 실현 . . . 76

7.2 직업 번호의 형식주의 . . . . . . . . . . . . . . . . . . . . . . . 82

7.3 터널링에 의해 제어되는 계산 . . . . . . . . . . . . . . . . . . . . . 83

삼

---

4페이지

8 강의 8. 광공동에서의 양자 컴퓨팅 구현 86

8.1 Jaynes-Cummings 모델 . . . . . . . . . . . . . . . . . . . . . . . . . 86

8.2 Tavis-Cummings-Hubbard 모델 . . . . . . . . . . . . . . . . . . . . . 90

8.3 JCH 모델의 얽힘 게이트 . . . . . . . . . . . . . . . . . . . . . . . . . 91

8.4 위상 변이 계산 . . . . . . . . . . . . . . . . . . . . . . . . . . . 92

8.5 coCSign 구현 . . . . . . . . . . . . . . . . . . . . . . . . . . . 94

8.6 단일 큐비트 게이트의 구현 . . . . . . . . . . . . . . . . . . . . . 94

8.7 밀도 매트릭스 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 96

8.8 개방형 양자 시스템. 양자 기본 방정식 . . . . . . . . . . 97

9 강의 9. 양자 시스템의 복잡성과 그 정확성

기술

99

9.1 소개 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 99

9.2 범용 컴퓨터 . . . . . . . . . . . . . . . . . . . . . . . . . . . . 100

9.3 양자 상태의 복잡성 . . . . . . . . . . . . . . . . . . . . . . . 101

9.4 예: 상호 작용하는 고조파 발진기 시스템 . . . . . . . . . . . 104

9.5 준 입자 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 106

9.6 진폭 세분성 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 108

9.7 상수 Q의 실험적 발견. . . . . . . . . . . . . . . . . . . . . 110

9.8 측정의 원인으로서 진폭의 입자. . . . . . . 112

9.9 평형 상태 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 112

9.10 진폭 양자 및 결정론 . . . . . . . . . . . . . . . . . . . . . . 114

9.11 결론 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 120

10 강의 10. 양자 비국소성, 벨 부등식 및 분포 양자

텀 컴퓨팅

120

10.1 단방향 분산 컴퓨팅에서 양자 우월성의 예

통제 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 126

10.2 단방향 제어 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 126

10.3 양자 이중 광자 신호 . . . . . . . . . . . . . . . . . . . . . . . . . . 128

4

---

5페이지

5

---

6페이지

소개

자연 과학은 실제 시나리오가 따르는 패턴을 연구합니다. 있는 곳

법이 없으면 혼돈이 지배합니다. 중세의 혼돈 속에서 탄생한 고전역학

세계에 대한 설명이었지만, 20세기 초에 소우주의 혼돈을 만났습니다.

20세기, 양자 역학이 등장하여 우리에게 초소형 전자 공학

및 IT 기술. 추가 진행은 주로 복잡한 시나리오와 관련이 있습니다.

생물학적 것들. 그들의 설명은 현재 고전 물리학의 아이디어에 의해 지배되고 있습니다.

그리고 혼돈도 당분간 지배합니다. 생물학적 데이터베이스의 기하학적 성장

프로틴 데이터 뱅크(Protein Data Bank) 및 점점 더 강력해지는 컴퓨터에 대한 수요와 같은

축적된 정보의 외부적이고 얕은 처리는

의 발견 이후 의학이나 기초 생물학의 가시적인 발전

1953년 DNA 이중나선. 현대 생물학이 일으킨 혼돈의 장에서 질서 회복

소우주에 대한 정확한 이론의 도입이 필요합니다.

양자 방법. 양자 컴퓨터가 이러한 목적을 수행합니다.

복잡한 시스템을 포함하여 소우주의 완전한 이론을 구축하는 경로

및 프로세스는 매우 어렵고 우리는 여전히 초기 단계에 있습니다(그림 참조).

1).

그러나 양자 컴퓨터에 대한 아이디어가 등장한 1982년 이후로 취해진 모든 조치는

처음 공개된 것은 올바른 방향으로 나아가는 단계였습니다. 이 과정에서는 다음을 따르게 됩니다.

수학적 관점에서 단계.

양자 컴퓨팅은 양자 컴퓨터의 수학적 지원입니다. 아래로-

이 주제의 자리에 서려면 양자 컴퓨터 자체에 대한 아이디어를 제공해야 하며

만들 필요가 있습니다.

양자 컴퓨터의 물리학은 본질적으로 복잡한 시스템의 양자 물리학입니다.

단순계의 양자이론과 다른 점, 이른바 코펜하겐

이론. 차이점은 수학에 대한 새롭고 더 엄격한 제한에 있습니다.

무한소 장치, 그리고 또한 복잡한 시스템 계산의 경우

오래된 코펜하겐 이론에는 없었던 매우 특별한 역할을 합니다. 이것의 이름

프로젝트는 20세기 후반에 시작되었습니다.

데스크탑이나 실험실에 서 있는 일종의 컴퓨팅 머신으로서의 제품,

고전적인 슈퍼컴퓨터보다 더 빠르게 어떤 것을 계산할 수 있습니다.

지난 30년은 그러한 생각의 순진함을 보여주었습니다. 현실에서 우리는 원하지 않는다.

추상적인 것을 계산하기 위해 우리는 다음과 같은 복잡한 자연 과정을 관리하고자 합니다.

우리의 생존에 필요합니다. 그리고 이 제어는 양자 수준에서 수행되어야 합니다.

복잡한 과정의 과정은 법칙이 존재하는 소우주에서 결정되기 때문입니다.

양자 물리학이 우세합니다.

계산 자체는 생명을 제어하는 ​​데만 필요합니다. 이렇게 하려면 다음이 필요합니다.

통제권의 이 또는 그 움직임이 무엇으로 이어질지 잘 알기 위해서는, 즉,

제어 시스템(나노소자, 살아있는 세포 또는 유기체)의 행동을 예측하고,

실시간으로, 즉 제어 시스템 자체가 우리의 응답에 응답하는 것보다 더 빠르게 수행합니다.

제어. 이것이 양자 컴퓨터가 어떻게 생겼든지 간에 해야 할 역할입니다.

이 장치를 만들기 위한 첫 번째 단계는 이미 사전에 수행되었습니다.

cessors - 양자 역학의 창시자. 지식의 이 장대한 단계는

6

---

7페이지

그림 1: 양자 역학 및 복잡한 프로세스

7

---

8페이지

세상은 그러한 컴퓨터의 출현을 이끌었습니다. 물론 계산도 가능하다.

Boole 시대의 기계 산술계에서 계산의 역사; 역사적으로,

이것은 근거가 있지만 여전히 컴퓨터는 마이크로 전자 장치입니다 - 마이크로 회로 세트

실리콘-게르마늄 헤테로 구조를 기반으로 합니다. 그리고 그러한 de-의 작동 원리

악덕은 고체의 전자 상태에 대한 양자 표현에 기반합니다. 즉,

양자역학에 대해.

모든 현대 마이크로일렉트로닉스는 양자 이론의 성취입니다. 그리고 여기에서 사용되는

동일한 입자의 거대한 앙상블을 제어하기 위해 - 광자와 같은 보존 또는 페르미온과 같은

전자. 수학적 분석 방법은 이러한 앙상블에 매우 적합합니다.

이것이 거의 20세기 전체를 ​​아우르는 이 단계에서 성공할 수 있었던 이유입니다.

우리는 그러한 마이크로 전자 시스템을 잘 관리할 수 있습니다.

오늘날 우리는 생물학적 본성의 보다 복잡한 시스템을 관리하는 방법을 배워야 합니다.

여기서 우리는 개성을 가진 많은 원자에 대해 이야기하고 있습니다. 개별 DNA 링크

더 이상 동일한 입자의 앙상블로 결합될 수 없습니다(예: 헬륨-4 원자).

액체 상태, 또는 헤테로 구조의 반도체 층에 있는 전자와 유사합니다. 이 단계는

"양자 컴퓨터"라는 용어로 지정되었으며 아직 통과하지 못했습니다. 우리는 얘기하고있다

여기에서 생물의 관리에 대해 근본적으로 구별합니다.

과거 시대의 현재 시간. 오늘날 과거의 분석 방법의 역할은 지나갑니다.

컴퓨터 과학의 이데올로기가 물리학의 주요 이데올로기가 됩니다.

복잡한 프로세스의. 결과적으로 양자 컴퓨팅은 수학적 형식이 됩니다.

이러한 프로세스를 제어하는 ​​것입니다.

양자 컴퓨터는 소우주의 깊숙한 곳까지 침투하는 방법입니다.

양자 이론 자체가 변형되고 거대한

생명체의 복잡성. 그것의 창조 프로젝트는 광범위하고 다양하며,

한 강의로 다 담을 수 없다. 과거의 분석적 방법의 역할은

지금은 컴퓨터로 옮겨가고 있고, 컴퓨터과학의 이념은

복잡한 과정의 물리학에서 가장 중요한 것. 결과적으로 양자 컴퓨팅

이러한 프로세스를 제어하는 ​​수학적 형태가 됩니다.

이 강의 과정은 수학적 측면과 편향된 측면만 제시합니다.

이 주제를 다루는 저자의 관점. 청취자는 다음을 찾을 수 있습니다.

지속적으로 증가하는 문헌에서 이 프로젝트의 다른 측면에 대한 설명과

아카이브 http:arxiv.org, quant-ph 섹션 참조. 의 수학적 측면

양자 컴퓨터는 매우 중요합니다.

20세기의 물리학자들은 현실에 적합하지 않습니다. 이것은 분명히 악마였다-

소위 고속 양자 알고리즘의 예에 의해 90년대에

우리가 자세히 고려할 예.

양자 컴퓨터 프로젝트의 개발은 다음 분야에 심각한 영향을 미칠 수 있습니다.

앞으로 수십 년 동안 자연 과학의 발전, 그것에 관한 많은 연구가

출판되고 그 결과는 정보기술 분야에서 즉시 활용됩니다.

이것은 양자 암호화에 적용됩니다.

또는 2개의 큐비트 또는 정밀 양자 장치로; 이 두 영역 모두에서 널리 사용됩니다.

연습. 여기에서는 이러한 영역에 대해 아주 간략하게만 다룰 것입니다. 우리의 주제는 양자가 될 것입니다

컴퓨팅 및 가장 중요한 일반 과학 작업과의 연결.

이 주제에 대한 훌륭한 물리적 모노그래프가 있습니다.

Lev Landau와 Yevgeny Lifshitz[1]의 책과 동등하게 우수한 다른 많은 책.

8

---

9페이지

그러나 양자 컴퓨팅은 약간 다른 형식과 간결한 스타일을 요구합니다.

선형 대수학을 기반으로 한 프레젠테이션. 이 접근 방식을 사용하면 빠르게 마스터할 수 있습니다.

양자 컴퓨팅 프로세스가 설명될 공식 언어. 이것은 허용합니다

사용자 인터페이스가 있는 양자 컴퓨터의 추상 Feynman 모델을 공식화하기 위해

양자 게이트의 형태([5] 참조, 첫 번째 자세한 정의는 [6]에서 찾을 수 있음),

양자 알고리즘으로 넘어갑니다.

우리는 수학적 문제를 해결하는 세 가지 알고리즘에 대해 좀 더 자세히 설명할 것입니다.

문제: Grover 알고리즘, 빠른 양자 푸리에 변환 및 - 간단히 -

관련 Shor 정수 인수분해 알고리즘 및 Zalka - Wiesner 알고리즘.

처음 두 개는 대상에 대한 진폭의 빠른 집중 속성을 보여줍니다.

상태를 통해 고전적 계산의 소위 양자 속도 향상을 달성할 수 있습니다.

여기서 우리는 또한 외부 객체인 오라클과 그 양자를 사용한 계산에 대해 논의할 것입니다.

형태. 양자 복잡성의 하한선에도 주의를 기울일 것입니다.

양자 컴퓨팅의 기능을 제한합니다. 세 번째 알고리즘은 예측을 위해 설계되었습니다.

양자 수준에서 복잡한 시스템의 실제 진화를 모델링합니다. 의 선택

이러한 알고리즘은 양자의 본질을 완전히 드러낸다는 사실에 의해 결정됩니다.

수학적 문제 분야에서 컴퓨팅 및 가능한 응용 프로그램.

처음 두 강의에서는 양자 역학에 대한 간략한 소개가 제공됩니다.

더 많은 이해를 위해 필요합니다. 우리는 또한 양자 알고리즘에 대해 다룰 것입니다.

분산 컴퓨팅의 장점은 양자 비국소성을 사용한다는 것입니다. 그만큼

페르미온 양자 컴퓨팅의 체계와 그 제어를 분석할 것이다. 우리는 이야기 할 것입니다

양자 순간 이동에 대해 - 1 큐비트의 예에서. 아주 간단히, 우리는 만질 것입니다

양자 암호화 - BB84 프로토콜.

한 강의는 단열 양자 컴퓨팅에 전념할 것이며, 이는 특수성을 명확히 합니다.

양자 물리학의 가장 중요한 방정식의 상태 - 슈뢰딩거 방정식.

Feynman 모델의 물리적 구현에도 주의를 기울일 것입니다.

양자 컴퓨팅 - 양자 게이트. 특정 게이트 기술을 분석해 드립니다.

- QED 양자의 유한 차원 모델을 기반으로 하는 광학 공동

전기역학.

마지막으로, 우리는 한계를 결정하는 양자 컴퓨팅의 역할을 고려할 것입니다.

양자 이론 자체의 적용 가능성 및 양자의 가능한 계획

운영 체제. 양자 알고리즘 및 계산은 이 운영 체제를 다음과 같이 사용합니다.

기술적 기반이지만 그 한계는 알고리즘 자체에 직접적인 영향을 미칩니다. 양자

따라서 컴퓨팅은 양자의 형태를 결정하기 위한 실험적 플랫폼이 됩니다.

복잡한 프로세스 분야의 법률.

결론적으로, 우리는 양자를 개발하는 주요 결과와 가능한 방법을 관찰할 것입니다

컴퓨팅 및 그 응용.

9

---

10페이지

1 강의 1. 양자역학과 Na-의 모델링

사실

진실한 모든 것은 단순하고 분명하며, 안개가 있는 곳에는 항상

일종의 진흙

레프 란다우

자연 과정의 모델링은 물리학의 주요 작업입니다. 상반기까지라면

20세기 모델링은 주로 대수적 계산으로 축소되었습니다.

실험과 비교했을 때 20세기 말에 컴퓨터가 눈에 띄었습니다.

이론 물리학의 주요 장치로 모든 분석 자료를 다운로드할 수 있습니다.

계산 및 또한 이러한 계산보다 훨씬 더 멀리 갈 수 있습니다.

작업 결과의 형태로 현실과 함께 - 계산으로.

기본 용어에 대해 동의합시다. 라는 특정 장치가 있다고 가정합니다.

컴퓨터는 특정 상태 집합에 있을 수 있으며 그 집합은 c로 표시됩니다.

알고리즘 우리는 이 집합의 매핑 J를 자기 자신으로 부를 것입니다:

J : c→c.

알고리즘은 다른 상태를 얻을 수 있는 특정 규칙의 형태로 설정됩니다.

주어진 상태에 따라 컴퓨터의 이 규칙은 실제로 가장 자주 만들어집니다.

컴퓨터 프로그램의 형태로 또는 일반적으로 공식화 된 레시피의 형태로

인간의 언어 "우리는 이것과 저것을 해야 한다".

알고리즘의 고전 이론에서 컴퓨터 상태 c의 집합은 단순히 모든

a 0 ,a 1 , ..., a n−1 형식의 가능한 부울 문자열 , 여기서 n은 컴퓨터 크기

메모리, j ∈ 10,1l.

이 알고리즘에 해당하는 계산은 맵을 적용하는 순서입니다.

J를 초기 상태 c 0으로 ping :

c 0 -→ J(c 0 ) -→ J(J(c 0 )) -→ ... -→ J(...J

︸ ︷︷ ︸

티

(c 0 )...) = J {T} (c 0 ),

(1)

여기서 규칙 J는 더 이상 최종 상태에 적용할 수 없습니다. 숫자 T(c 0 )라고 합니다.

주어진 초기 단어에 대한 알고리즘 작업의 복잡성 c 0 ; T = с이면

복잡성은 무한합니다. 즉, 알고리즘은 절대 종료되지 않습니다. 이렇게 정의된 복잡성

실제로 실행 시간이며 추상 단위로 표현됩니다.

이 연산자.

연산자 J는 위에서 정의한 시간에 따라 달라질 수 있습니다. 이를 위해서는

상수 연산자 J가 있는 표준 모델과 다르지 않은 상황에서는 다음이 필요합니다.

상태 자체에 시간을 포함하는 경우 C ∈ c. 이 기술은 양자

전기역학. 그러나 실용적인 관점에서 변수 연산자 J는

특별한 접근이 필요한 경우 - 이것은 단열에 관한 강의에서 논의될 것입니다.

계산. 앞으로 기본적으로 J 연산자는 시간에 종속되지 않습니다.

10

---

11페이지

그림 2: 양자 컴퓨터에서 실제 프로세스 시뮬레이션

11

---

12페이지

그림 3: 양자 컴퓨터의 체계

12

---

13페이지

우리는 단어의 넓은 의미에서 계산을 이해합니다. 모든 실제 프로세스는

어떤 계산의 형태로 우리에게 제시됩니다. 따라서

알고리즘은 우리가 공식화할 수 있는 모든 자연법칙입니다.

정확한 용어.

이 알고리즘 개념, 구성 수학은 Andrey Markov에 의해 만들어졌습니다.

Jr.([2],[3] 참조)이며 실제 프로세스 모델링에 컴퓨터를 적용하기 위한 기초입니다.

모든 양자 알고리즘은 궁극적으로 실제 프로세스를 시뮬레이션하는 알고리즘입니다.

(그림 2 참조); 이 알고리즘에 해당하는 계산이 다음을 제공하지 않는 경우

원하는 결과를 얻으려면 이 알고리즘이 올바르지 않다고 결론을 내려야 합니다. 양자 알고리즘은

원하는 결과로 이어지는 기본 양자 연산의 고전적인 기록,

우리가 양자 물리학 자체의 법칙의 작동을 올바르게 이해한다면

우리 컴퓨터의 양자 부분과 관련하여. 직접 확인 불가

그러한 지식의 사실 - 실험을 통해서만 확인할 수 있습니다.

이것은 양자 컴퓨터의 구성이

이전에 테스트된 적이 없는 분야에서 양자 이론 자체를 테스트하는 것입니다.

복잡한 시스템. 20세기의 물리학 문제에서 우리는

단순한 시스템에서는 복잡성이 특별한 역할을 하지 않았습니다.

소위 얽힘을 제거하여 감소됩니다. 다음과 같은 복잡한 시스템의 경우

오늘날 과학의 초점, 이것은 할 수 없습니다.

큐비트 수를 늘리면 복잡성이 기하급수적으로 빠르게 증가합니다.

큐비트 메모리를 사용하면 쉽게 분석할 수 있는 단순한 시스템을 매우 빠르게 뛰어넘습니다.

지난 세기의 물리학자들에 의해 따라서 양자 컴퓨팅은 현대의 물리학입니다.

시간과 그것에 대한 우리의 아이디어는 여전히 실험적으로 테스트해야 합니다. 우리는 따를 것이다

에 대해 완벽하게 테스트된 코펜하겐 양자 이론의 표준 경로

단순한 문제, 그리고 그것이 우리를 복잡한 문제로 이끄는 곳을 보십시오.

어떻게든 컴퓨터 상태 c의 복잡성 C(c)를 결정합시다. 해 보자

모든 초기 복잡도 상태에서 시작하는 알고리즘의 최대 복잡도

주어진 자연 n보다 크지 않음:

C(J)(n) = 최대 C(C 0 )≤n T(c 0 )

그런 다음 알고리즘의 복잡성이라고 하는 자연 인수의 함수를 얻습니다.

제이.

계산을 위해 오라클이라고 하는 외부 장치가 자주 사용됩니다. 신탁

컴퓨터보다 훨씬 복잡한 개체입니다. 거의 부를 수도 없다.

객체라기 보다는 알고리즘의 관점에서 전혀 기술될 수 없는 주체이다. 에 대한

예를 들어, 오라클은 컴퓨터 사용자가 될 수 있습니다.

공식적으로 oracle은 다음 형식의 다른 기능입니다.

오 : ㄷ→ㄷ

컴퓨터 상태 c의 집합에 부분 집합 AÇc가 있다고 하자.

13

---

14페이지

쿼리 상태. 쌍(O,J)을 오라클과 함께 알고리즘이라고 합니다. 계산은

오라클을 사용하여 주어진 알고리즘에 응답하는 것은 다음 형식의 시퀀스입니다.

c 0 -→ L(c 0 ) -→ L(L(c 0 )) -→ ... -→ L(...L

︸ ︷︷ ︸

티

(c 0 )...) = J {L} (c 0 ),

(2)

여기서 매핑 L은 인수가 A에 속하지 않는 경우 J로 작동하고 다음과 같은 경우 O로 작동합니다.

그것의 인수는 A에 속한다. 여기서, 위에서와 같이 매핑 L은 마지막에 적용할 수 없다.

컴퓨터의 상태. 이러한 계산은 쿼리 상태가 발생할 때까지 J로 작동합니다.

이러한 상태가 발생하면 일반적인 함수 J 대신 Oracle O가 사용됩니다.

약간의 생각 후에 우리는 사용자의 상호 작용이

컴퓨터가 오라클의 계산 체계에 정확히 들어맞는다면, 후자가 필요하다면

사용자를 점화합니다.

오라클 = 컴퓨터 사용자

오라클을 사용한 계산의 복잡성은 응용 프로그램의 수입니다.

사슬의 신탁(2); 오라클을 사용한 알고리즘의 복잡성이 결정됩니다.

위와 같은 방법으로.

계산 (1)은

법칙 J, 즉 모든 실제 프로세스. 계산 형식은 다음 형식에 따라 다릅니다.

고려 중인 시스템의 상태에 대한 설명. 예를 들어 클래식에서

물리학에서 집합 c의 상태는 길이가 N인 이진 문자열입니다.

수학적 분석은 N → с의 극한 전환이 필요합니다. 그러나 이 요건은

데카르트 수학의 방정식은 실제 세계와 정확히 일치하지 않습니다. 예를 들어,

우리가 주어진 방의 공기에 대해 이야기한다면 엄밀히 말하면 그것을 고려할 수 없습니다.

연속: 유한한 크기의 분자로 구성됩니다. 컴퓨터 계산에서 모든 표현은

컴퓨터의 메모리는 항상 제한되어 있기 때문에 문장은 유한합니다. 이 상황

컴퓨터 모델링이 실제 물리적 프로세스를 보다 적절하게 반영할 수 있음을 의미합니다.

분석 공식과 비교합니다.

컴퓨터의 메모리를 확장하면 진화 속도를 높일 수 있습니까? 가능한가요?

공간으로 비용을 지불하여 시간을 산다고? 당신은 할 수 없습니다! 일반적으로 진화는 불가능하다.

새로운 자원을 포함함으로써 가속화됩니다. 검색(또는

무차별 대입) 문제는 병렬 처리됩니다. 양자 컴퓨터는 속도를 높일 수 없다

모든 작업의 ​​실행뿐만 아니라.

정리([4]).

길이 O(N 1/7 )의 반복이 다음 에서 임의로 선택될 확률

"블랙 박스" J의 균일한 분포는 양자에서 적어도 하나에 의해 가속화될 수 있습니다.

컴퓨터는 공간의 차원이 무한대에 가까워지면 0이 되는 경향이 있습니다.

이 정리의 의미는 양자를 허용하는 문제의 비율이

적어도 하나의 속도 향상은 가능한 모든 문제 중에서 아주 작습니다.

다시 말해:

14

---

15페이지

양자 속도 향상은 다음 문제에서만 발생하는 드문 현상입니다.

무차별 대입 유형

이것은 양자 병렬 처리를 고전 병렬 처리에 더 가깝게 만듭니다. 장