Quantum computing7 [양자컴퓨팅] Deutsch's Algorithm 정리 어떤 함수 f가 constant하다 라는 말은 함수 f가 f(0)=0, f(1)=0 을 만족하거나 f(0)=1, f(1)=1을 만족함을 의미하며, f(0), f(1)이 각각 0과 1의 값을 가질 때 함수 f가 balance하다 라고 말한다. 어떤함수 f가 있을 때 우리는 함수 f가 constant인지 balance인지를 파악하고 싶다. 단순히 생각해보면 먼저 f(0)이 무엇인지 찾고, f(1)이 무엇인지 찾아서 그 결과가 동일하면 constant, 다르면(큐빗이 2개임을 가정) balance하다라고 할 수 있으며, 총 2번의 확인으로 알 수 있다. 여기서 양자컴퓨팅으로 더 빠르게 알 수 있지 않을까 해서 나오게 된것이 도이치 알고리즘(Deutsch's algorithm)이다. Deutsch's Algor.. 2022. 6. 4. [양자컴퓨팅] Grover's Algorithm 정리 여러가지 데이터에서 특정한 조건을 만족하는 항목을 찾을 때 우리는 하나하나 열어보면서 열어본 항목이 우리가 원하는 답인지를 비교해야한다. 즉 순차적으로 탐색하였을 경우에 시간복잡도는 O(N)이다. 고전컴퓨터의 이러한 탐색에서 벗어나 시간복잡도를 O(√N)로 낮추면서 원하는 답을 얻어내는 알고리즘인 그로버 알고리즘이 등장한다. 그로버알고리즘이 어떤식으로 search를 하는지 알아보자. 😊그로버 알고리즘의 원리 1. Phase Inversion 큐빗이 두개일때 중첩상태를 그림으로 나타내면 다음과 같다. 00, 01, 10, 11이 나올수 있는 확률이 1/4로 동일하게 관측된다. 이 상태에서 우리가 찾고자하는 항목이 01에 있다고 한다면 우리는 01이 나오는 확률을 축에 반대로 표시한다. 이것을 Phase i.. 2022. 6. 2. [양자컴퓨팅] Eigenvectors & Eigenvalues 와 Hermition 😊Eigenvalue & Eigenvector 식 AV = cV를 만족할 때 스칼라c와 벡터V를 각각 A의 eigenvalue, eigenvector라고 한다. 행렬A의 eigenvalue와 eigenvector는 여러개가 있을 수 있다. 아래 예시와 같이 2*2행렬A가 주어졌을 때 (1,2)를 곱하게 되면 2*(1,2)가 나오므로 AV = cV의 형태를 만족하게 된다. Eigenvector 특징 서로 다른 두 벡터 V와 V'가 있을 때 두 벡터는 같은 eigenvalue c0을 가질 수 있다. 밑의 증명식들은 V대신 다른 것들을 넣었을 때 AV = cV형태로 만들어지면서 같은 c0을 가질 수 있다는 것을 증명하기 위한 것이다. c0을 eigenvalue로 갖는 모든 eigenvector들의 집합은 co.. 2022. 4. 17. [양자컴퓨팅] 내적과 직교성 정리 Inner product(내적)이란? 내적은 벡터를 마치 수처럼 곱하는 개념이다. 벡터에는 방향이 있으므로, 방향이 일치하는 만큼만 곱한다. 예를 들어 두 벡터의 방향이 같으면, 두 벡터의 크기를 그냥 곱한다. 두 벡터가 이루는 각이 90도일 땐, 일치하는 정도가 전혀 없기 때문에 내적의 값은 0이다. Inner product space(내적공간)이란 complex vector space을 확장한 개념으로, 기존의 벡터덧셈과 스칼라곱에 대해서 닫혀있던 complex vector space에서 내적연산을 포함하는 공간을 말한다. 다음 4가지 조건을 모두 만족하는 연산을 내적이라고 한다. Orthogonal & Orthonormal? 내적공간(inner product space)의 두 벡터 V1,V2가 내적.. 2022. 4. 8. [양자컴퓨팅] Complex vector spaces의 특징 정리 Words Transpose: 열과 행을 바꾼다. Conjugate: 켤레복소수(허수부의 부호를 반대로) Adjoint: Transpose와 Conjugate를 둘다 적용 Multiplication(행렬 곱) multiplication이 행렬끼리의 곱이라는 것과 이 행렬들이 모두 벡터공간에 속해있다고 할때, 다음 6가지의 공식을 모두 만족한다. Linearity(선형성) 두개의 Complex vector space V, V'가 있고, V에서 V'로 가는 함수가 있을 때 아래의 두가지 조건을 만족한다면 이 함수가 선형적이라고 할 수 있다. Linear combination(선형 합) 아래 식과 같이 벡터 V는 V0, V1,...,Vn-1의 linear combination으로 표현이 가능하다. Linear.. 2022. 4. 1. [양자컴퓨팅] Complex Vector Space(복소 벡터 공간) 개념정리 Complex Vector Space 스칼라가 복소수인 vector space를 말한다. vector space이란 어떤 집합인데, 벡터덧셈이나 스칼라곱의 연산결과가 이 집합의 원소일 때 이를 vector space라고 한다. 한마디로 덧셈이나 스칼라곱에 닫혀있는 집합을 말한다. 벡터덧셈이란 벡터의 Index가 같은 원소끼리 더하는 것. --> 결합법칙, 교환법칙, 항등원존재, 역 존재 총 4가지를 만족해야만 성립한다. 스칼라곱(scalar multiplication)? 숫자 1개를 각 벡터의 원소에 곱하는 것. 스칼라곱 -> 교환법칙, 분배법칙2개, 항등원존재 총 4가지를 만족해야만 성립한다. 예시로 벡터 v=(2,3)과 스칼라 a=4, b=3이 있다고 하자. 이 벡터은 vector space일까? 먼.. 2022. 3. 25. 이전 1 2 다음
