Задача Фейнмана

Задача Фейнмана (англ. universal quantum simulator — універсальний квантовий симулятор) — проблема використання квантових комп'ютерів для моделювання квантових систем. Вперше подібні ідеї висловив Юрій Манін у 1980 році, але загальну увагу до використання квантових комп'ютерів у цьому напрямку привернув Річард Фейнман після свого виступу на Першій конференції з обчислень в МТІ у 1981 році й подальших публікацій. Фейнман показав, що моделювання найпростіших фізичних систем на класичному комп'ютері потребує неймовірних обчислювальних ресурсів, завдяки чому задача стає нерозв'язною. Наприклад, додання до молекули одного електрона ускладнює розв'язок відповідного рівняння Шредінгера більш ніж у два рази, завдяки чому моделювання систем із кількістю електронів більше 30 стає практично неможливим. Але завжди можна отримати шуканий результат, якщо поставити фізичний експеримент із відповідною квантовомеханічною системою.

Ці факти наштовхнули Фейнмана на думку, що квантовомеханічні закони можна використовувати для прискорення обчислень. Він показав, що, на відміну від гіпотетичного квантового комп'ютера, класична машина Тюрінга зазнаватиме експоненційного зменшення швидкості обчислень під час моделювання квантової системи. Пізніше Девід Дойч розвинув цю ідею Фейнмана й у 1985 році вперше дав детальний теоретичний опис універсального квантового комп'ютера. В 1996 році Сет Ллойд показав, що звичайний квантовий комп'ютер можна запрограмувати для ефективного моделювання будь-якої локальної квантової системи.

Квантова система багатьох частинок описується в гільбертовому просторі, кількість вимірів якого експоненційно зростає із збільшенням кількості частинок. Саме тому моделювання подібної системи потребує експоненційного часу на класичному комп'ютері. Але можна припустити, що квантову систему багатьох частинок можна моделювати за допомогою квантового комп'ютера, кількість кубітів у складі якого дорівнює кількості частинок у системі, що моделюється. Ллойд показав, що це виконується для класу локальних квантових систем. Пізніше цей принцип був поширений на більш широкі класи квантових систем.

Див. також

• Квантова машина Тюрінга

Виноски

1. Манин Ю. И. Вычислимое и невычислимое. — М. : Советское радио, 1980. — С. 15.
2. Feynman R. Simulating physics with computers // International Journal of Theoretical Physics. — 1982. — Т. 21, вип. 6-7. — С. 467-488. (рос. переклад: Фейнман Р. Моделирование физики на компьютерах // Квантовый компьютер и квантовые вычисления (том 2). — Ижевск : РХД, 1999. — 288 с.)
3. Deutsch D. Quantum Theory, the Church-Turing Principle and the Universal Quantum Computer // Proc. R. Soc. Lond A. — 1985. — Т. 400. — С. 97-117. (рос. переклад: Дойч Д. Квантовая теория, принцип Чёрча-Тьюринга и универсальный квантовый компьютер // Квантовый компьютер и квантовые вычисления (том 2). — Ижевск : РХД, 1999. — 288 с.)
4. Lloyd S. Universal Quantum Simulators // Science. — 1996. — Т. 273, вип. 5278. — С. 1073-1078.
5. Aharonov D., Ta-Shma A. Adiabatic Quantum State Generation and Statistical Zero Knowledge // arXiv:quant-ph/0301023v2. — 2003.
6. Berry D. W., Ahokas G., Cleve R., Sanders B. C. Efficient quantum algorithms for simulating sparse Hamiltonians // Communications in Mathematical Physics. — 2005. — Т. 270, вип. 2. — С. 359-371. (arXiv:quant-ph/0508139 [Архівовано 1 лютого 2017 у Wayback Machine.])
7. Childs A. M. On the relationship between continuous- and discrete-time quantum walk // Communications in Mathematical Physics. — 2008. — Т. 294, вип. 2. — С. 581-603. (arXiv:0810.0312v2)