y"> - або , або . За визначенням, , а
.
Теорема 4.3. -повна.
Доказ. Побудуємо зведення будь-якої мови до задачі c TQBF. Для цього перетворимо МТ, яка обчислює результат гри (предикат ), в схему, а ходи гравців закодуємо булевими змінними. Тоді наявність виграшної стратегії у білих задається умовою
В
де позначає результат обчислення за схемою.
Щоб перетворити в бульову формулу, додамо нові змінні (значення, обчислене при -м присвоюванні в схемі) і замінимо на формулу виду
В
де - розмір схеми, - права частина -го присвоювання.
Після цієї підстановки отримаємо квантифікувати бульову формулу, яка істинна в точності для .
Розділ № 5. Квантові обчислення
Тема 5.1 Квантові обчислення
Як вже говорилося у вступі, звичайні комп'ютери не використовують усіх можливостей, що надаються природою. У них виконуються перетворення на кінцевих множинах станів (дії з 0 і 1), а в природі є можливість робити унітарні перетворення, тобто діяти на нескінченному множестве1) <# "22" src = "doc_zip1117.jpg"/> звичайно і має потужність.
Квантовий комп'ютер працює з кінцевими наборами елементарних станів, званих q-бітами. Кожен q-біт має два виділених стану (якщо вважати q-біти спинами, те це стани "спін вгору" і "спін вниз"). Вказівка ​​виділених станів для кожного q-біта системи задає не всі можливі стану системи, а тільки базисні. Можливі також будь лінійні комбінації базисних станів з комплексними коефіцієнтами. Базисні стану ми будемо позначати, де, або, де. Довільний стан системи може бути представлено у віде2) <# "47" src = "doc_zip1123.jpg"/>
Простір станів для такої системи - конечномерное (розмірності) простір над полем комплексних чисел.
Стани
Звичайного комп'ютера
квантового комп'ютера
біти
В
q-біти
базисне:
довільне:
Невелике уточнення: якщо помножити вектор на фазовий множник,, (- речовий), то вийде фізично неотличимое стан. Таким чином, стан квантового комп'ютера - це вектор одиничної довжини, заданий з точністю до фазового множника. p> Обчислення можна представляти як послідовність перетворень на множині станів системи. Опишемо, які перетворен...
