невелике число бітів. Елементарне перетворення в квантовому разі: тензорне твір довільного унітарного оператора, що діє на частини співмножників , де обмаль ( ), і тотожного оператора, що діє на інших множники.
Тензорне твір деякого оператора , чинного на безлічі q-бітів , та тотожного оператора, що діє на інших q-бітах , будемо позначати . (Зокрема, позначає дію на перших q-бітах.)
Приклад 5.1. Наведемо матрицю оператора , що діє в просторі . Оператор діє на другий q-біт, на інших q-бітах дію тотожне. Базисні вектори розташовані в лексикографічному порядку: від до .
В
З цього місця починається обчислювальна складність. Нехай , тоді - деяка матриця , - матриця розмірності , у якої по діагоналі стоять блоки з матриць . Ця матриця представляє один елементарний крок. Коли застосовується декілька таких операторів до різних парах q-бітів, результат буде виглядати набагато складніше. Не видно способу визначити цей результат, крім прямого перемноження матриць. Оскільки розміри матриць експоненціально великі, буде потрібно експоненціальне час для їх перемноження.
Зауважимо однак, що обчислення матричних елементів можливо на полиномиально обмеженою пам'яті. Нехай потрібно знайти матричний елемент оператора
В
Очевидно, що
(5.1)
(Тут - рядки довжиною бітів.) Для обчислення цієї суми достатньо -го регістра для зберігання поточних значень , ще одного регістра для зберігання часткової суми і деякого фіксованого кількості регістрів для обчислення проміжних творів.
Визначення 5.1. Квантова схема. Нехай - деяке безліч унітарних операторів (базис). Тоді квантова схема в базисі - це послідовність , де - безлічі q- бітів,
Оператор, реалізований квантової схемою. Це оператор , рівний .
Це визнач...
