lign="justify"> Лемма про очищення сміття показує, що можна уникнути таких втрат енергії, пов'язаних з необоротністю обчислень.
Можна також показати, що будь-яке обчислення, що вимагає пам'яті , можна реалізувати оборотним чином з використанням пам'яті, що не перевищує . Наведемо начерк докази.
Оскільки завдання TQBF PSPACE-повна, то досить обчислювати на невеликий пам'яті значення формули
(6.1)
за умови, що вичіслімих булевої схемою невеликого розміру . Покажемо, що в цьому випадку значення формули 6.1 можна обчислити на пам'яті . Обчислення буде організовано рекурсивно, починаючи з внутрішніх кванторів.
Щоб обчислити , обчислимо , занесемо результат в одну додаткову комірку, потім обчислимо і занесемо результат в іншу комірку. Після обчислимо і результат занесемо в третю клітинку. Щоб прибрати сміття, прокрутимо всі обчислення, крім останнього кроку, у зворотному напрямку.
Розібравшись аналогічним чином з формулою , приходимо до такого висновку: додавання квантора по булевої змінної збільшує необхідну пам'ять не більше ніж на константу бітів.
На закінчення сформулюємо теорему про обчислення оборотних функцій, яка є прямим узагальненням леми 6.2.
Теорема 6.1. Нехай і вичіслімих булевими схемами розмірів . Тоді реалізується оборотною схемою розміру .
Доказ. Дається наступною схемою обчислень (для простоти не вказані біти, які "беруться напрокат" при обчисленні з леми 6.2. br/>В
Розділ № 7. Базиси для квантових схем
Тема 7.1 Точна реалізація
Як вибрати базис для обчислень у квантових схемах? Унітарних операторів нескінченно багато, тому або повний базис повинен містити нескінченну кількість елементів, або ми повинні послабити умову точної реалізованості оператора схемою, замінивши його на умову наближеною реалізованості. Ми розглянемо обидві можливості. p align="justify"> Точна реалізація.
Теорема 7.1. Базис, що містить всі унітарні оператори, що діють на парах q-бітів, дозволяє реалізувати будь-який унітарний оператор в розширеному сенсі. p align="justify"> Для доказу цієї теореми введемо важливий клас операторів: оператори з квантовим управлінням.
Визначе...
