ення не дуже добре, тому що не враховує можливість використання додаткової пам'яті в процесі обчислення. Тому дамо ще одне визначення. p align="justify"> Оператор , реалізований схемою в розширеному сенсі. Це такий оператор, що твір
В
чинне на q-бітів, , для будь-якого вектора задовольняє умові .
Таким чином, ми "беремо напрокат" додаткову пам'ять, заповнену нулями, і повинні повернути її в колишньому стані. Який сенс має таке визначення? Навіщо потрібно вимагати, щоб додаткові q-біти повернулися в стан ? Насправді це умова чисто технічне, проте важливо, щоб вектор стану в кінці обчислення був розкладемо, тобто мав вигляд (з довільним ). Якщо це так, то перша підсистема знаходиться в певному стані , тому про другу підсистему (додаткову пам'ять) можна забути. В іншому випадку, спільне стан двох підсистем виявляється "заплутаним" (entangled), тому першу підсистему не можна відокремити від другої.
Розділ № 6. Співвідношення між класичним і квантовим обчисленням
Тема 6.1 Співвідношення між класичним і квантовим обчисленням
Класичний об'єкт, відповідний унітарному оператору, - перестановка. Будь перестановці природно зіставляється унітарний оператор в просторі , що діє за правилом .
Аналогічно визначенню 5.1, можна визначити оборотні класичні схеми, що реалізують перестановки.
Визначення 6.1. Оборотна класична схема. Нехай - деяке безліч перестановок виду (базис). Оборотна класична схема в базисі - це послідовність перестановок , де - безлічі бітів , .
Перестановка, реалізована оборотною схемою. Це твір перестановок .
Перестановка , реалізована схемою в розширеному сенсі. Це така перестановка, що твір перестановок
В
(діюча на бітів, ) для будь-якого задовольняє умові .
У яких випадках функцію, задану булевої схемою, можна реалізувати оборотною схемою? Оборотні схеми реалізують тільки перестановки. Подолати ці труднощі можна так. Замість обчислення функції...
