Введення
Всі комп'ютери, починаючи від так і не побудованої "аналітичної машини" Чарльза Беббіджа1) <# "16" src = "doc_zip109.jpg"/> або), а програма - це послідовність операцій, кожна з яких використовує невелику число бітів. Звичайно, нові комп'ютери працюють швидше старих, але прогрес у цьому напрямку має межу. Важко припустити, що розмір транзистора або аналогічного елемента буде менше см (діаметр атома водню), а робоча частота - більше ~ Гц (частота атомних переходів). Так що навіть суперкомп'ютери майбутнього не зможуть вирішувати обчислювальні завдання, що мають експонентну складність. Розглянемо, наприклад, задачу про розкладання цілого числа на прості множники. Очевидний спосіб - це спробувати розділити на числа від до. Якщо число має знаків у двійковій запису, то доведеться перебрати варіантів. Існує хитромудрий алгоритм, вирішальний ту ж задачу приблизно за кроків (). Навіть у цьому випадку, щоб розкласти на множники число з мільйона знаків, не вистачить часу життя Всесвіту. (Можливо, є й більш ефективні алгоритми, але від експоненти, мабуть, позбутися не вдасться.) p> Існує, однак, інший спосіб прискорити процес обчислення для деяких спеціальних класів задач. Справа в тому, що звичайні комп'ютери не використовують усіх можливостей, що надаються природою. Це твердження може здатися занадто очевидним: у природі є безліч процесів, абсолютно несхожих на операції з нулями і одиницями. Можна спробувати використовувати ці процеси для створення аналогової обчислювальної машини. Наприклад, інтерференція світла може використовуватися для обчислення перетворення Фур'є. Однак у більшості випадків виграш в швидкості не є принциповим, тобто слабо залежить від розміру пристрою. Причина полягає в тому, що рівняння класичної фізики (наприклад, рівняння Максвелла) ефективно вирішуються на звичайному цифровому комп'ютері. Що означає ефективно? Обчислення інтерференційної картини може зайняти в мільйони разів більше часу, ніж реальний експеримент, тому що швидкість світла велика, а довжина хвилі мала. Проте зі збільшенням розміру модельованої фізичної системи кількість необхідних обчислювальних операцій росте не занадто швидко - статечним, або, як прийнято говорити в теорії складності, поліноміальним чином. (Як правило, число операцій пропорційно величині, де - обсяг, а - час.) Таким чином, класична фізика занадто "проста" з обчислювальної точки зору. p> Квантова механіка влаштована в цьому сенсі набагато цікавіше. Розглянемо, наприклад, систему з спинив. Кожен спін володіє двома базисними станами (і), а вся система має базисних станів (кожна з змінних приймає значення або). Відповідно до загальних принципів квантової механіки, можливими станами системи є також суперпозиції виду, де - комплексні числа, звані амплітудами. Знак суми тут потрібно розуміти чисто формально. Суперпозиція є новим математичним об'єктом - вектором в-вимірному комплексному просторі. Квадрат модуля амплітуди,, ...
