양자 최적화 알고리즘

양자 최적화 알고리즘은 최적화 문제를 해결하는 데 사용되는 양자 알고리즘이다.^[1]수학적 최적화는 가능한 해결책 집합에서 문제에 대한 최선의 해결책(일부 기준에 따름)을 찾는 것을 다룬다.대부분, 최적화 문제는 최소화된 문제로 공식화되는데, 이 문제에서는 솔루션에 의존하는 오류를 최소화하려고 한다: 최적의 솔루션은 최소의 오류를 가지고 있다.역학, 경제, 공학 등 다양한 분야에 서로 다른 최적화 기법이 적용되고 있으며, 관련 데이터의 복잡성과 양이 증가함에 따라 최적화 문제를 해결하는 보다 효율적인 방법이 필요하다.양자컴퓨팅의 힘은 고전적인 컴퓨터에서 실질적으로 실현 가능하지 않은 문제들이 해결되도록 하거나, 가장 잘 알려진 고전 알고리즘과 관련하여 상당한 속도를 낼 수 있도록 할 수 있다.

양자 데이터 적합

데이터 적합은 데이터 점 집합에 가장 적합한 수학적 함수를 구성하는 과정이다.적합치의 품질은 일반적으로 함수와 데이터 지점 사이의 거리 등 일부 기준에 의해 측정된다.

양자 최소 제곱 피팅

가장 일반적인 데이터 적합 유형 중 하나는 최소 제곱 문제를 해결하는 것으로, 데이터 점과 적합함수의 차이의 제곱 합을 최소화하는 것이다.

The algorithm is given as input ${\displaystyle N}$ data points ${\displaystyle (x_{1},y_{1}),(x_{2},y_{2}),...,(x_{N},y_{N})}$ and ${\displaystyle M}$ continuous functions ${\displaystyle f_{1},f_{2},...,f_{M$$\}\}\}\}.$ 알고리즘이 $f{\displaystyle {}_{}}$ ${\displaystyle {j\stackrel{}{}}_{}}$ ${\$을(를) 찾아 출력으로 부여하며, 이는$$ f ${\displaystyle j_{}}$ ${\$의 선형 조합이다$.$

${\displaystyle f_{\vec{\lambda }}}}}=\sum _{j=1}^{M}f_{j}(x)\lambda _{j}}}}}$

즉, 알고리즘은 복합 계수 ${\displaystyle {\lambda }_{}}$ j ${\$를 찾아내어 벡터${\displaystyle \stackrel{}{}}\lambda {\displaystyle \stackrel{}{}}$ →${\displaystyle }$= (${\displaystyle {}_{}}$ ${\displaystyle {1\mathrm{}}_{}}$,${\displaystyle {}_{}{}_{}}$ ${\displaystyle {2\mathrm{}}_{}}$,${\displaystyle }$. .${\displaystyle {\lambda }_{}}$ M${\displaystyle {}_{}}$) ${\displaystyle {\vec {\lambda }}}=(\lambda _{1}, ...,\lambda$ _$\{$$M}).$

알고리즘은 오류를 최소화하는 것을 목표로 하며, 이 오류는 다음과 같이 정의된다.

${\displaystyle E=\sum _{i=1}^{N}\left\vert f_{\vec {\lambda }}(x_{i})-y_{i}\right\vert ^{2}=\sum _{i=1}^{N}\left\vert \sum _{j=1}^{M}f_{j}(x_{i})\lambda _{j}-y_{i}\right\vert ^{2}=\left\vert F{\vec {\lambda }}-{\vec {y}}\right\vert ^{2}}$

$여기$서 F ${\displaystyle F}$을(를) 다음 행렬로 정의하십시오$$.

${\displaystyle {F}={\begin{pmatrix}f_{1}(x_{1})&\cdots &f_{M}(x_{1})\\f_{1}(x_{2})&\cdots &f_{M}(x_{2})\\\vdots &\ddots &\vdots \\f_{1}(x_{N})&\cdots &f_{M}(x_{N})\\\end{pmatrix}}}$

그 양자 최소 이승 algorithm[2]를 설치하고는 계수λ j{\displaystyle \lambda_{j}출력하}과 맞춤 등급 평가 E{E\displaystyle}3서브 루틴으로:perfo에 대한 알고리즘으로 구성되어 있Harrow, Hassidim, 로이드의 양자 알고리즘의 버전의 방정식의(HHL)선형 시스템에 사용한다.rming 의사-수정 연산, 적합성 품질 추정을 위한 하나의 루틴 및 적합성 매개변수를 학습하기 위한 알고리즘.

왜냐하면 그 양자 알고리즘은 주로 HHL 알고리즘입니다, 그것은 경우에 F{F\displaystyle}는 것은 희박하다 지수 improvement[3]고 둘 다 FF({\displaystyle FF^{\dagger}}와 F† F{\displaystyle의 조건 번호(즉, 그 비율 사이의에서 가장 크고 가장 작은 eigenvalues)을 제안합니다.F^$F}$은(는) 작다.

양자 세미데마파인 프로그래밍

Semidefinite Programming(SDP)은 양극 세미드핀 행렬의 원뿔과 아핀 공간과의 교차점에 걸쳐 선형 목표함수(최소화 또는 최대화하는 사용자 지정함수)의 최적화를 다루는 최적화 하위 분야다.목적 함수는 $X{\displaystyle }$ ${\displaystyle X}$ 변수가 있는 행렬 $C{\displaystyle }$ ${\displaystyle$ C$}($입력으로 제공됨)의 내부 제품이다$.$ $모든{\displaystyle }$ ${\displaystyle n}$ ${\displaystyle \times }$ ${\displaystyle$ $\mathb${$S$$}{$$n}}}}}}$ 대칭$$ 행렬의 공간을$$ $나타낸다{\displaystyle {\mathbb{}}^{}}$.변수 $X{\displaystyle }$ ${\displaystyle X}$은(는) 양의 세미데핀 대칭 $행렬{\displaystyle {\mathbb{}}_{}^{}}$ S${\displaystyle {}_{}^{}}$+ ${\displaystyle {}_{}^{}}$ ${\$의 (폐쇄 볼록) 원뿔 안에 있어야 한다$$$.$두 행렬의 내부 생산물은 다음과 같이 정의된다.

${\displaystyle \langle A,B\rangle _{\mathb {S}^{n}={\rm {tr}(A^{T}B)=\sum _{i=1,j=1}^{n}A_{ij}B_{ij}.}$

문제에는 추가 제약 조건(입력 자료로 제공)이 있을 수 있으며, 일반적으로 내부 제품으로도 공식화된다.각 제약조건은 최적화 $변수{\displaystyle }$ X ${\displaystyle X}$을(를) 가진 ${\displaystyle {행렬}_{}}$ $A{\displaystyle {}_{}}$ k ${\$입력으로 제공)의 내부 산출물을 지정된 값 $b{\displaystyle {}_{}}$ ${\displaystyle k_{}}$ ${\$입력으로 제공)보다 작게 강제한다$$.마지막으로, SDP 문제는 다음과 같이 쓸 수 있다.

${\displaystyle {\begin{array}{rl}{\displaystyle \min _{X\in \mathbb {S} ^{n}}}&\langle C,X\rangle _{\mathbb {S} ^{n}}\\{\text{subject to}}&\langle A_{k},X\rangle _{\mathbb {S} ^{n}}\leq b_{k},\quad k=1,\ldots ,m\\&X\succeq 0\end{array}}}$

최고의 고전 알고리즘은 무조건 다항식 시간에 실행되는 것으로 알려져 있지 않다.해당 타당성 문제는 복잡도 등급 NP와 co-NP의 조합 밖에 있거나 NP와 co-NP의 교차점에 있는 것으로 알려져 있다.^[4]

양자 알고리즘

${\displaystyle {알고리즘\mathrm{}}_{}}$ 입력은 ${\displaystyle A}$ ${\displaystyle 1_{}}$.${\displaystyle }$.${\displaystyle {}_{}}$. . . . .${\displaystyle }$. . .${\displaystyle }$. . . . . . . . b m $displaystyle A_{$$1}...$$A_{m},C,b_{1}...$$b_{m}}$ 및$$ 솔루션의 추적, 정밀도 및 최적값(최적 지점에서 목표함수의 값)에 관한 파라미터.

양자 알고리즘은^[5] 몇 번의 반복으로 구성된다.각 반복에서 타당성 문제를 해결한다. 즉, 다음과 같은 조건을 만족하는 해결책을 찾는다($임계값{\displaystyle }$ t ${\displaystyle t}).$

${\displaystyle {\begin{array}{lr}\langle C,X\rangle _{\mathbb {S} ^{n}}\leq t\\\langle A_{k},X\rangle _{\mathbb {S} ^{n}}\leq b_{k},\quad k=1,\ldots ,m\\X\succeq 0\end{array}}}$

In each iteration, a different threshold ${\displaystyle t}$ is chosen, and the algorithm outputs either a solution ${\displaystyle X}$ such that ${\displaystyle \langle C,X\rangle _{\mathbb {S} ^{n}}\leq t}$ (and the other constraints are satisfied, too) or an indication that no such solution exists. 알고리즘은 솔루션 $X{\displaystyle }$ ${\displaystyle X}$이(가) 여전히$$ 존재하는 최소 임계값 t {\$displaystyle$ t$}$을(를$)$ 찾기 위해 이진 검색을 수행하며, 이는 SDP 문제에 대한 최소 솔루션을 제공한다.

양자 알고리즘은 일반 사례에서 가장 우수한 고전 알고리즘에 비해 2차적인 개선과 입력 행렬이 낮은 등급일 때 지수적인 개선을 제공한다.

양자 결합 최적화

결합 최적화 문제는 유한한 객체 집합에서 최적의 객체를 찾는 것을 목표로 한다.문제는 부울 함수의 합인 객관적 함수의 최대화로 표현될 수 있다.Each boolean function ${\displaystyle \,C_{\alpha }\colon \lbrace {0,1\rbrace }^{n}\rightarrow \lbrace {0,1}\rbrace }$ gets as input the ${\displaystyle n}$-bit string ${\displaystyle z=z_{1}z_{2}\ldots z_{n}}$ and gives as output one bit (0 or 1).$n{\displaystyle }$ ${\displaystyle n}$ 비트와$$ m ${\displaystyle m}$ 절의$$ 조합 최적화 문제는 기능을 최대화하는$$ $n{\displaystyle }$ ${\displaystyle n}$ -bit$$ string $z{\displaystyle }$ ${\displaysty z}$을(를) 찾고 있다.

${\displaystyle C(z)=\sum _{\alpha =1}^{m}}C_{\alpha }(z)}$

근사적 최적화는 최적화 문제에 대한 근사적 해결책을 찾는 방법이며, NP-hard인 경우가 많다.조합 최적화 문제의 근사 솔루션은 $C{\displaystyle }$(${\displaystyle }$z )${\displaystyle C(z)}$ 최대화에 가까운$$ 문자열 $z{\displaystyle }$ ${\displaystyle z}$이다$.$

양자 근사 최적화 알고리즘

조합 최적화의 경우, 보다 효과적인 고전 알고리즘이 제안될 때까지 양자 근사 최적화 알고리즘(QAOA)^[6]은 알려진 어떤 다항 시간 고전 알고리즘(특정 문제의 경우)보다 짧은 근사 비율을 가지고 있었다.^[7][8]양자 알고리즘의 상대적 속도 상승은 공개 연구 질문이다.

QAOA의 심장은 2 ${\displaystyle p}$ ${\displaystyle 2p}$ 각도에 의존하는 단일 연산자의 사용에 의존하며$,$ 여기서 > ${\displaystyle p>1$}은 입력 정수다.이러한 연산자는 계산 기준에서 가능한 모든 상태의 동일한 가중치 양자 중첩인 상태에 반복적으로 적용된다.각 반복에서 상태는 계산 기준으로 측정되며 $C{\displaystyle (}$ ${\displaystyle z}$) ${\displaystyle C(z)}$이(가) 계산된다$$.충분한 반복을 반복한 후 C (${\displaystyle z}$ )${\displaystyle C(z)}$의 값이 거의 최적이며$$, 측정되는 상태도 최적화에 가깝다.

2020년 QAOA는 해당 목적 함수를 최소화하기 위해 알고리즘의 용량 제한을 두는 변수(문제 농도)에 대한 문제의 제약 비율에 대한 의존도가 높은 것으로 나타났다.^[9]

QAOA 프로세스의 일반화는 본질적으로 기초 그래프에 연속 시간 양자 보행을 교대로 적용한 후 각 솔루션 상태에 적용되는 품질 의존적 위상 편이 뒤따른다는 것을 곧 알게 되었다.이 일반화된 QAOA는 QWOA(Quantum Walk-based Optimization Algorithm)라고 불렸다.^[10]

이 논문에서 얼마나 많은 qubits 양자 계산의 패권 arXiv,[11]은 저자들은 420qubits과 500명의 제약 조건과 QAOA 회로가 고전 시뮬레이션 알고리즘 최첨단 슈퍼 컴퓨터에 보내서 양자에 충분할 것이다 달리기를 사용해 모의 실험하는 데는 적어도 1세기가 필요할 것을 맺다에 제출한 필요하다. 상태우위적 우위

참고 항목

• 단열 양자 계산
• 양자 어닐링

참조