๐ ๋ชฉ์ฐจ

์์ ์๊ณ ๋ฆฌ์ฆ์ ์ง์ง ๊ฐ์ ์ ์ดํดํ๋ ค๋ฉด โ๋ณต์ก๋ ๋ถ์โ์ด ๊ผญ ํ์ํด์. ๋จ์ํ ๋น ๋ฅด๋ค, ํจ์จ์ ์ด๋ค๋ผ๋ ๋ง๋ง์ผ๋ก ๋ถ์กฑํ๊ฑฐ๋ ์. ์ํ์ ์ผ๋ก ์ผ๋ง๋ ๋นจ๋ฆฌ ๋ฌธ์ ๋ฅผ ํ ์ ์๋๋๋ฅผ ์ธก์ ํ๋ ๊ธฐ์ค์ด ๋ฐ๋ก โ๋ณต์ก๋โ์์.
๋ด๊ฐ ์๊ฐํ์ ๋ ์ด ๋ถ์ผ์์ ๊ฐ์ฅ ๋งค๋ ฅ์ ์ธ ์ ์, ๊ณ ์ ์ปดํจํฐ๋ก๋ ์์ฒ ๋ ๊ฑธ๋ฆด ๋ฌธ์ ๋ ์์ ์๊ณ ๋ฆฌ์ฆ์ ๋ช ๋ถ ๋ง์ ํ ์ ์๋ค๋ ์ฌ์ค์ด์์. ์ด ์ฐจ์ด๋ฅผ ๋ช ํํ ์ค๋ช ํด์ฃผ๋ ๋๊ตฌ๊ฐ ๋ฐ๋ก ๋ณต์ก๋ ์ด๋ก ์ด์์. ์ง๊ธ๋ถํฐ ์ฝ๊ฒ ํ์ด๋ณผ๊ฒ์!
๐ ๋ณต์ก๋๋ ๋ฌด์์ธ๊ฐ์?
๋ณต์ก๋๋, ์๊ณ ๋ฆฌ์ฆ์ด ๋ฌธ์ ๋ฅผ ํด๊ฒฐํ๋ ๋ฐ ํ์ํ โ์์โ์ ์ํ์ ์ผ๋ก ์ธก์ ํ ๊ฐ๋ ์ด์์. ๋ณดํต ๊ณ์ฐ ์๊ฐ(time complexity), ๋ฉ๋ชจ๋ฆฌ ๊ณต๊ฐ(space complexity), ์ ์ถ๋ ฅ ํ์ ๋ฑ์ผ๋ก ๋๋๊ณ , ์ ๋ ฅ ํฌ๊ธฐ n์ ๋ฐ๋ผ ์ด๋ค ํจ์ ํํ๋ก ์ฆ๊ฐํ๋์ง๋ฅผ ๋ถ์ํ์ฃ .
๊ณ ์ ์๊ณ ๋ฆฌ์ฆ์์๋ ํํ O(n), O(nยฒ), O(log n) ๊ฐ์ ํ๊ธฐ๋ฒ์ ์จ์. ์๋ฅผ ๋ค์ด ์ ๋ ฌ ์๊ณ ๋ฆฌ์ฆ์ O(n log n)์ด ํ๊ท ์ ์ธ ๋ณต์ก๋๊ณ , ๋จ์ ํ์์ O(n), ์ด์ง ํ์์ O(log n)์ด์ฃ . ์ด๊ฑด โ์ ๋ ฅ n์ด ์ปค์ง์๋ก ์ฑ๋ฅ์ด ์ด๋ป๊ฒ ๋๋น ์ง๋๊ฐโ๋ฅผ ๋ณด์ฌ์ค์.
์์ ์๊ณ ๋ฆฌ์ฆ๋ ๋ง์ฐฌ๊ฐ์ง๋ก ๋ณต์ก๋๋ฅผ ๋ถ์ํด์. ํ์ง๋ง ํ๋นํธ์ ์ค์ฒฉ๊ณผ ๊ฐ์ญ, ์ฝํ ๋๋ถ์ ์ด๋ค ๋ฌธ์ ๋ ๊ณ ์ ๋ณด๋ค ํจ์ฌ ๋น ๋ฅด๊ฒ ํ ์ ์์ด์. ๋ํ์ ์ผ๋ก ๊ทธ๋ก๋ฒ ์๊ณ ๋ฆฌ์ฆ์ O(โn), ์ผ์ด ์๊ณ ๋ฆฌ์ฆ์ O((log n)ยณ) ์๊ฐ์ ๋ฌธ์ ๋ฅผ ํด๊ฒฐํ์ฃ .
๊ทธ๋ผ ์๋ ๋น๊ตํ์์ ๊ณ ์ ์๊ณ ๋ฆฌ์ฆ๊ณผ ์์ ์๊ณ ๋ฆฌ์ฆ์ด ๊ฐ์ ๋ฌธ์ ๋ฅผ ์ผ๋ง๋ ๋ค๋ฅด๊ฒ ์ฒ๋ฆฌํ๋์ง, ๋ณต์ก๋ ๊ด์ ์์ ๋น๊ตํด๋ณผ๊น์?
โ๏ธ ์๊ณ ๋ฆฌ์ฆ๋ณ ๋ณต์ก๋ ๋น๊ตํ
๋ฌธ์ | ๊ณ ์ ์๊ณ ๋ฆฌ์ฆ | ์์ ์๊ณ ๋ฆฌ์ฆ | ๋ณต์ก๋ ์ฐจ์ด |
---|---|---|---|
๋ฐ์ดํฐ ํ์ | O(n) | O(โn) (๊ทธ๋ก๋ฒ) | ์ ๊ณฑ๊ทผ ์๋ ํฅ์ |
์์ธ์ ๋ถํด | ์ง์ ์๊ฐ | O((log n)ยณ) (์ผ์ด) | ์ง์ โ ๋คํญ์ ์ ํ |
์ ํ ๋ฐฉ์ ์ ํด | O(nยณ) | O(log n) (HHL ์๊ณ ๋ฆฌ์ฆ) | ์ง์์ ํฅ์ |
์ต์ ํ ๋ฌธ์ | NP-Hard, O(2โฟ) | QAOA (๋ฌธ์ ์ ๋ฐ๋ผ ์์ด) | ์กฐ๊ฑด๋ถ ๊ฐ์ |
๋ณต์ก๋ ๊ด์ ์์ ๋ณด๋ฉด, ์์ ์๊ณ ๋ฆฌ์ฆ์ด ๋จ์ํ ๋น ๋ฅด๊ธฐ๋ง ํ ๊ฒ ์๋๋ผ โ์ง์ ์ผ๋ก ๋ค๋ฅธ ์ ๊ทผโ์ ์ ๊ณตํ๋ค๋ ๊ฑธ ์ ์ ์์ด์. ๊ณ์ํด์, ์์ ๋ณต์ก๋ ํด๋์ค๋ค์ ๋ ์์ธํ ์ดํด๋ณผ๊ฒ์!
๐ ์์ ๋ณต์ก๋ ํด๋์ค(QC, BQP ๋ฑ)
๋ณต์ก๋ ์ด๋ก ์์๋ ๋ฌธ์ ๋ฅผ โํด๋์คโ๋ก ๋ถ๋ฅํด์. ๊ณ ์ ์ปดํจํฐ์๋ P(๋คํญ์๊ฐ), NP(๋น๊ฒฐ์ ์ ๋คํญ์๊ฐ), NP-Hard ๊ฐ์ ํด๋์ค๊ฐ ์๊ณ , ์์ ์ปดํจํ ์๋ BQP(Bounded-error Quantum Polynomial time), QMA ๋ฑ์ด ์์ด์.
BQP๋ ์์ ์ปดํจํฐ๊ฐ ๋คํญ ์๊ฐ ๋ด์ ๋์ ํ๋ฅ (๋ณดํต 2/3 ์ด์)๋ก ์ ๋ต์ ์ถ๋ ฅํ ์ ์๋ ๋ฌธ์ ์งํฉ์ด์์. ์ผ์ด ์๊ณ ๋ฆฌ์ฆ๊ณผ ๊ทธ๋ก๋ฒ ์๊ณ ๋ฆฌ์ฆ ๋ชจ๋ BQP์ ์ํ์ฃ . BQP๋ ๊ณ ์ ์ P๋ณด๋ค ๋๊ณ , NP๋ณด๋ค๋ ์๋ค๊ณ ์๋ ค์ ธ ์์ด์.
QMA๋ NP์ ์์ ๋ฒ์ ์ด๋ผ ๋ณด๋ฉด ๋ผ์. ๊ฒ์ฆ์๋ ์์ ์ปดํจํฐ๊ณ , ์ฆ๊ฑฐ(์ํธ๋์ค)๋ ์์ ์ํ๋ก ์ฃผ์ด์ ธ์. ์ํธํ ๋ฌธ์ ๋ ๋ณต์กํ ๊ตฌ์กฐ ๊ฒ์ฆ์์ ์์ฃผ ๋ฑ์ฅํ๋ ํด๋์ค์์. ์ ์ ๋ ๋ง์ ๋ฌธ์ ๊ฐ ์ฌ๊ธฐ์ ํฌํจ๋๋ฉด์ ์ฐ๊ตฌ๊ฐ ํ๋ฐํด์ง๊ณ ์์ด์.
์ด ์ธ์๋ DQC1(๋ํฐ๋ฏธ๋์คํฑ ์์ ๊ณ์ฐ), QSZK(์์ ์ ๋ก ์ง์), PostBQP ๋ฑ ๋ค์ํ ํด๋์ค๊ฐ ์กด์ฌํด์. ์์ ๋ณต์ก๋๋ ๊ธฐ์กด ์ด๋ก ์ ์๋ก์ด ๊ด์ ์ ๋ํ๋ฉด์ ์ํ, ์ปดํจํฐ๊ณผํ, ๋ฌผ๋ฆฌํ์ ์ฐ๊ฒฐํด์ฃผ๊ณ ์์ด์.
๐งช ๋ํ ์๊ณ ๋ฆฌ์ฆ์ ๋ณต์ก๋ ์ฌ๋ก
์์ ์๊ณ ๋ฆฌ์ฆ์ ๋ณต์ก๋๋ฅผ ์ดํดํ๊ธฐ ๊ฐ์ฅ ์ข์ ๋ฐฉ๋ฒ์ ๋ํ ์๊ณ ๋ฆฌ์ฆ๋ค์ ์ง์ ์ดํด๋ณด๋ ๊ฑฐ์์. ๊ฐ์ฅ ์ ๋ช ํ ์๋ ์ผ์ด(Shor)์ ์๊ณ ๋ฆฌ์ฆ์ด์ฃ . ๊ณ ์ ์ปดํจํฐ๋ก๋ ์์ธ์ ๋ถํด๊ฐ ์ง์ ์๊ฐ์ด ๊ฑธ๋ฆฌ์ง๋ง, ์ผ์ด ์๊ณ ๋ฆฌ์ฆ์ O((log n)ยณ)์ ํด๊ฒฐ ๊ฐ๋ฅํด์.
๊ทธ๋ก๋ฒ(Grover)์ ์๊ณ ๋ฆฌ์ฆ๋ ๊ฐ๋ ฅํด์. n๊ฐ์ ๋ฐ์ดํฐ์์ ํน์ ํญ๋ชฉ์ ์ฐพ๋ ๋ฐ ๊ณ ์ ์ ์ผ๋ก๋ O(n)์ด์ง๋ง, ์์์์๋ O(โn)์ ํด๊ฒฐ ๊ฐ๋ฅํด์. ๋ฐ์ดํฐ๊ฐ ๋ง์์ง์๋ก ์ฐจ์ด๋ ํจ์ฌ ์ปค์ง์ฃ .
HHL ์๊ณ ๋ฆฌ์ฆ์ ์ ํ ๋ฐฉ์ ์ ๋ฌธ์ ๋ฅผ ํ ๋ ํ์ฉ๋ผ์. Ax = b ํํ์ ๋ฌธ์ ๋ฅผ ๊ณ ์ ์ ์ผ๋ก๋ O(nยณ)์ ํ์ง๋ง, ์์ ์ปดํจํฐ์์ O(log n) ์์ค์ผ๋ก ์๋๊ฐ ํ ์ค์ด๋ค ์ ์์ด์. ๋๊ท๋ชจ ํ๋ ฌ ์ฐ์ฐ์ด ํ์ํ ์ฐ์ ๋ถ์ผ์ ํฐ ์ํฅ์ ์ค ์ ์์ด์.
์ด์ฒ๋ผ ๋ฌธ์ ์ ๋ฐ๋ผ ๋ค๋ฅด๊ธด ํ์ง๋ง, ์์ ์๊ณ ๋ฆฌ์ฆ์ ํน์ ๋ถ์ผ์์ ๋ณต์ก๋ ๋ฉด์์ ๊ฒ์ ์ฒด์ธ์ ๊ฐ ๋ ์ ์์ด์. ์ค์ํ ๊ฑด '์ด๋ค ๋ฌธ์ ์ ๋ง๋ ์๊ณ ๋ฆฌ์ฆ์ ์ด๋ป๊ฒ ์ค๊ณํ๋๋'์์!
๐ก ๋ณต์ก๋ ๋ถ์์ด ๊ฐ๋ ์๋ฏธ
๋ณต์ก๋ ๋ถ์์ ๋จ์ํ โ์ด ์๊ณ ๋ฆฌ์ฆ์ด ๋น ๋ฅด๋คโ๋ ๊ฑธ ๋์ด์, ๊ธฐ์ ์ ๋ฐฉํฅ์ฑ๊ณผ ์ ๋ต์ ๊ฒฐ์ ํ๋ ํต์ฌ ์งํ์์. ์ด๋ค ๋ฌธ์ ์ ์์ ์๊ณ ๋ฆฌ์ฆ์ด ํจ๊ณผ์ ์ธ์ง, ์ด๋ค ๋ฌธ์ ๋ ์์ง ์๊ธฐ์์กฐ์ธ์ง ํ๋จํ๋ ๊ธฐ์ค์ด ๋๊ฑฐ๋ ์.
์๋ฅผ ๋ค์ด, NP-Hard ๋ฌธ์ ๋ ์์ ์ปดํจํฐ๋ก๋ ์ฝ๊ฒ ํ ์ ์๋ ๊ฒฝ์ฐ๊ฐ ๋ง์์. QAOA ๊ฐ์ ์ ๊ทผ์ ๊ทผ์ฌํด๋ฅผ ์ ๊ณตํ ์ ์์ง๋ง, ํญ์ ํด๋ต์ ์ฐพ์ ์ ์๋ ๊ฑด ์๋์์. ์ด๊ฑธ ์ดํดํด์ผ ์ค๋ฌด์์ ์ค๋งํ์ง ์์์.
๋ํ ๋ณต์ก๋๋ ์๊ณ ๋ฆฌ์ฆ ์ ํ๋ฟ ์๋๋ผ ํ๋์จ์ด ์ค๊ณ, ์์ ํ๋ก๊ทธ๋๋ฐ ์ธ์ด, ํด๋ผ์ฐ๋ ํ๋ซํผ์ ์ํคํ ์ฒ ๊ตฌ์ฑ์๋ ์ํฅ์ ์ค์. ๊ฒฐ๊ตญ ์์ ๊ธฐ์ ์ ์ฒด์ ์ฑ๋ฅ๊ณผ ํจ์จ์ ๊ฒฐ์ ์ง๋ ํ์ธ ์ ์ด์์.
๋ณต์ก๋ ๋ถ์์ ํตํด ์์ ์ปดํจํ ์ด ์ด๋๊น์ง ๊ฐ ์ ์์์ง, ๊ทธ๋ฆฌ๊ณ ํ์ค์์ ์ด๋๊น์ง ๋๋ฌํ๋์ง๋ฅผ ์ ํํ ์ ์ ์์ด์. ์ด๊ฑด ์ฐ๊ตฌ์์ ๊ฐ๋ฐ์ ๋ชจ๋์๊ฒ ํ์์ ์ธ ์ญ๋์ด์์!
โ FAQ
Q1. ๋ณต์ก๋ ๋ถ์์ ์ ์ค์ํ๊ฐ์?
A1. ์๊ณ ๋ฆฌ์ฆ์ ์ฑ๋ฅ์ ์ํ์ ์ผ๋ก ํ๊ฐํ๊ณ , ์ค์ ์ ์ฉ ๊ฐ๋ฅ์ฑ์ ํ๋จํ๋ ๊ธฐ์ค์ด์์.
Q2. BQP๋ ์ด๋ค ๋ฌธ์ ๋ฅผ ํฌํจํ๋์?
A2. ์์ ์ปดํจํฐ๋ก ๋คํญ ์๊ฐ ๋ด์ ๋์ ํ๋ฅ ๋ก ํ ์ ์๋ ๋ฌธ์ ๋ค์ด ํฌํจ๋ผ์.
Q3. ์ผ์ด ์๊ณ ๋ฆฌ์ฆ์ ์ ๋๋จํ๊ฐ์?
A3. ์ง์ ์๊ฐ์ด ๊ฑธ๋ฆฌ๋ ์์ธ์ ๋ถํด ๋ฌธ์ ๋ฅผ ๋คํญ ์๊ฐ์ผ๋ก ์ค์๊ธฐ ๋๋ฌธ์ด์์.
Q4. NP-Hard ๋ฌธ์ ๋ ์์๋ก ํ ์ ์๋์?
A4. ์๋ฒฝํ ํด๋ต์ ์ด๋ ค์ธ ์ ์์ด์. QAOA์ฒ๋ผ ๊ทผ์ฌ ์ ๊ทผ ๋ฐฉ์์ด ์ฃผ๋ก ์ฐ์ฌ์.
Q5. HHL ์๊ณ ๋ฆฌ์ฆ์ ์ด๋์ ์ฐ์ด๋์?
A5. ๋๊ท๋ชจ ์ ํ ๋ฐฉ์ ์ ๋ฌธ์ , ํนํ ๋ฌผ๋ฆฌ ์๋ฎฌ๋ ์ด์ ๊ณผ ๋จธ์ ๋ฌ๋์์ ์ฐ์ฌ์.
Q6. ๊ทธ๋ก๋ฒ ์๊ณ ๋ฆฌ์ฆ์ O(โn)์ ์ค์ฉ์ ์ธ๊ฐ์?
A6. ๋ฐ์ดํฐ๊ฐ ๋งค์ฐ ๋ง์ ๊ฒฝ์ฐ์ ํนํ ์ ๋ฆฌํด์. ํ์ ์๊ฐ์ด ํ๊ธฐ์ ์ผ๋ก ์ค์ด์.
Q7. ์์ ๋ณต์ก๋ ๋ถ์์ ์ด๋ค ์ํ์ ์ฐ๋์?
A7. ๋ก๊ทธ, ์ง์ํจ์, ํ๋ฅ , ์ ํ๋์, ๊ณ์ฐ ์ด๋ก ๋ฑ์ด ํ์์์.
Q8. ๋ณต์ก๋ ์ด๋ก ์ ์์ ํ๋์จ์ด์ ๋ฌด์จ ๊ด๋ จ์ด ์๋์?
A8. ์๊ณ ๋ฆฌ์ฆ ํจ์จ์ ๋ฐ๋ผ ํ์ํ ํ๋นํธ ์, ํ๋ก ๊ธธ์ด, ์ฐ์ฐ ์๋๋ ๋ฌ๋ผ์ง๊ธฐ ๋๋ฌธ์ด์์.