Transcript
КАЗАНСКИЙ (ПРИВОЛЖСКИЙ) ФЕДЕРАЛЬНЫЙ УНИВЕРСИТЕТ СБОРНИК ЗАДАЧ И УПРАЖНЕНИЙ по курсу ОСНОВЫ КВАНТОВЫХ ВЫЧИСЛЕНИЙ составитель Гайнутдинова А.Ф. Казанский федеральный университет 01 Составитель А.Ф. Гайнутдинова СБОРНИК ЗАДАЧ И УПРАЖНЕНИЙ по курсу ОСНОВЫ КВАНТО- ВЫХ ВЫЧИСЛЕНИЙ : Методические пособие / А. Ф. Гайнутдинова. - Казань:КФУ, 01. Данный сборник содержит задачи и упражнения по основам квантовых вычислений. Сборник дополняет учебное пособие ОСНОВЫ КВАНТО- ВЫХ ВЫЧИСЛЕНИЙ (А. Ф. Гайнутдинова. - Казань:КГУ, с.) и предназначен для проведения практических и лабораторных занятий по курсу Квантовые вычисления. Сборник содержит задачи и упражнения по основным разделам квантовой информатики. Решение задач и упражнений из данного сборника способствует более глубокому и адекватному пониманию базовых понятий квантовой информатики: квантового бита, квантовой суперпозиции, квантовых преобразований, квантового измерения, запутанных состояний, квантовых схем, алгоритмов и т.д. Предназначено для студентов, слушающих курс лекций по квантовым вычислениям, магистров и аспирантов, ведущих исследования в области квантовой информатики. Глава 1 Гильбертово пространство Определение 1 Гильбертово пространство обобщение евклидова пространства, допускающее бесконечную размерность. Для комплексного числа x = a + ib через x обозначается комплексно сопряженное число x = a ib. Определение Пусть x, y элементы комплекснозначного гильбертова пространства. Скалярное произведение x y - это число, удовлетворяющее аксиомам: 1. x y = y x. x λy 1 + µy = λ x y 1 + µ x y 3. x x 0, x x = 0 тогда и только тогда, когда x = 0 (нулевой элемент). Пусть H d d-мерное комплекснозначное гильбертово пространство с нормой.. Определение 3 Для x, y H d x y = d i=1 x i y i Определение 4 Для z H d, z = (z 1,..., z d ), z = z z = d i=1 z i. Определение 5 Расстояние между двумя элементами z, z H d определяется как ρ(z, z ) = z z. Определение 6 Базис множество таких векторов в векторном пространстве, что любой другой вектор пространства может быть единственным образом представлен в виде линейной комбинации базисных векторов. Каждый линейный оператор U, действующий в пространстве H d с базисом i, i = 1,..., d может быть представлен d d матрицей (будем также обозначать ее через U), строки и столбцы которой помечены i, i = 1,..., d, и на пересечении i-ой строки и j-го столбца стоит элемент i U j. 1 Определение 7 Оператор U называется унитарным, если UU = U U = I (I единичная матрица). Определение 8 a b, A B тензорное (правое кронекерово) произведение векторов a, b и матриц A, B, соответственно, определенные следующим образом. Для a = (a 1,..., a d ) и b = (b 1,..., b l ) a b = (a 1 b 1, a 1 b,..., a 1 b l, a b 1,..., a d b l ). a 11 a 1n Для A =..... a m1 a mn a 11 B a 1n B A B =..... a m1 B a mn B 1.1 Упражнения. и B = b 11 b 1k..... b l1 b lk 1. Показать, что если U унитарная матрица, то u i u j = δ i,j. Здесь u i i-ая строка матрицы U, δ i,j символ Кронекера (δ i,j = 1, если i = j, δ i,j = 0, если i j).. Доказать следующие свойства Гильбертова пространства (a) ψ 0 ψ H d ; (b) ψ = 0 ψ = 0; (c) ψ = Uψ, если U унитарно; (d) ρ(ψ, ϕ) = ρ(uψ, Uϕ), если U унитарно; (e) ρ(ψ, ϕ) = 0 ψ = ϕ. 3. ψ, φ H d называются ортонормальными, если ψ = 1, φ = 1 и ψ φ = 0. Пусть ψ, φ H d ортонормальны. Чему равно ρ(ψ, φ)? 4. Является ли система {( 6, 1 6, 1 6 ); (0, 1, 1 ); ( 1 3, 1 3, 1 3 )} ортонормированным базисом в H 3? 5. Доказать cψ = c ψ. 6. Доказать, что ψ + φ + ψ φ = ψ + φ (правило параллелограмма). 7. Для ψ = (z 1,..., z d ) и φ = (u 1,..., u d ) выписать, чему равно ψ ϕ ; ψ ϕ. 8. Доказать, что если ψ и φ ортогональны, то ψ + φ = ψ + φ. 9. Проверить унитарность матриц: 1/ 1/ 1/ 1/ A = 1/ 1/ 1/ 1/ 1/ 1/ 1/ 1/ 1/ 1/ 1/ 1/ B = Глава Квантовый бит, квантовое состояние, проективное измерение Определение 9 Мы будем обозначать состояние каждого кубита символом, внутри которого будем помещать значение 0 или 1, представляемое данным состоянием. В отличие от классического бита, который в каждый момент времени может находиться в одном из двух состояний в состоянии 0 или в состоянии 1, квантовый бит, или кубит q, кроме двух устойчивых состояний ( 0 и 1, соответственно), может находиться одновременно в суперпозиции этих двух состояний: q = α 0 + β 1, где α, β комплексные числа, α + β = 1. Таким образом, квантовый бит может принимать бесконечно много значений, но, как результат измерения, мы получим либо состояние 0 с вероятностью α, либо состояние 1 с вероятностью β Определение 10 Состояние квантовой системы из n кубитов q 1,..., q n описывается как q 1... q n = (α β 1 1 ) (α n 0 + β n 1 ) = z 0 ( ) + z 1 ( ) + + z n 1( ) = z z z n = z z z n 1 n 1, где в последнем выражении используются целые числа 0, 1,... n 1 для обозначения битовых строк , ,..., Состояния , ,..., устойчивые состояния квантовой системы, z i (i = 0,..., n 1) комплексные числа, n 1 i=0 z i = 1. 4 Определение 11 Матрица M называется унитарной (описывающей унитарные преобразования), если MM = I. Определение 1 Измерение квантовой системы это вероятностный процесс, который осуществляется следующим образом: 1. Пусть ψ = (z 0, z 1,..., z n 1) квантовое состояние и B = { 0,..., n 1 } стандартный базис пространства состояний квантовой системы из n кубитов (элементы базиса B соответствуют устойчивым состояниям квантовой системы).. Если производится измерение состояния ψ по отношению к стандартному базису B, то с вероятностью z i результатом измерения является устойчивое состояние i. 3. После измерения состояние квантовой системы становится ψ = i. Определение 13 Квантовый регистр это упорядоченное множество конечного числа кубитов. Определение 14 Стандартный базис B n-кубитного квантового регистра это B = { i i есть n битная бинарная строка.}.1 Упражнения. 1. Выписать состояние ψ квантовой системы в виде вектор-столбца. Нижний индекс обозначает число кубит квантовой системы. (a) ψ = 5 3 ; (b) ψ = 11 4 ; (c) ψ = 1 3 ( ).. Выписать состояние ψ квантовой системы в виде вектор-столбца. (a) ψ = 110 ; (b) ψ = 101 ; (c) ψ = Пусть квантовая система находится в базисном состоянии, соответствующем вектору ψ. Сколько кубитов участвует в данном состоянии? Выписать состояние каждого кубита. 5 (a) ψ = (0, 0, 0, 1, 0, 0, 0, 0) T ; (b) ψ = (0, 0, 0, 0, 0, 0, 1, 0) T ; (c) ψ = 1 (0, 0, 0, 1, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0) T. 4. Представьте базисные состояния 0, 1, в терминах состояний двоичного базиса { 0, 1 }, где 0 = 1 ( ); 1 = 1 ( 0 1 ). 5. Пусть дан кубит в состоянии ψ = α 0 +β 1. Определить вероятность исхода измерения кубита по отношению к базису (a) {1/ ( ), 1/ ( 0 1 )}; (b) {1/ ( 0 + i 1 ), 1/ (i )}; (c) {1/ 0 + 3/ 1 ), 3/( 0 1/ 1 )}. 6. Докажите, что любое квантовое состояние ψ = α 0 + β 1 кубита может быть представлено в виде где α = cosθ и β = e iϕ sinθ. ψ = α 0 + β 1, 7. Для данного квантового состояния ψ найти состояние ϕ (a) ψ = 11, ϕ = ψ ; (b) ψ = 1/ ( 0 + i 1 ), ϕ = ψ ; (c) ψ = 1 ( ), ϕ = ψ 3. Здесь ψ k = ψ ψ (k сомножителей). 8. Представьте базисные состояния 00, 01, 10, 11, в терминах состояний базиса Белла B = { 0 0, 0 1, 1 0, 1 1 } и наоборот, где 6 0 0 = 1 ( ), 0 1 = 1 ( ), 1 0 = 1 ( ), 1 1 = 1 ( ). 9. Для данного состояния ψ = α 0 + β 1 и для данного p 0 определить базис, по отношению к которому результат измерения кубита состояние 0 с вероятностью p. 7 Глава 3 Квантовые преобразования Эволюция квантовой системы, не подвергающейся измерению, переводит состояние квантовой системы в другое состояние с сохранением нормы. Для Гильбертова пространства преобразование, сохраняющее расстояние, является унитарным преобразованием, определяемым следующим образом. Любое преобразование на d-мерном комплексном векторном пространстве может быть описано при помощи d d-матрицы. Пусть M обозначает транспонированную комплексносопряженную матрицу для матрицы M. Матрица M называется унитарной (описывающей унитарные преобразования), если MM = I. 3.1 Упражнения. 1. (a) Выпишите унитарную матрицу, которая преобразует стандартный базис в двоичный; (b) Выпишите унитарную матрицу, которая преобразует двоичный базис в стандартный.. (a) Выпишите унитарную матрицу, которая преобразует стандартный базис в базис Белла; (b) Выпишите унитарную матрицу, которая преобразует базис Белла в стандартный. 3. Нарисовать схему для копирования классического бита. 4. Показать, что если бы возможно было копировать кубит, создавая столько его копий, сколько хотим, то мы могли бы определить состояние кубита с любой наперед заданной точностью. 8 5. Рассмотрим состояние двухкубитного квантового регистра ψ = 1/ / / / Показать, что если произвести произвольное унитарное преобразование над первым кубитом регистра, а затем измерить второй кубит регистра в стандартном базисе, то результат измерения B не будет зависеть от преобразования над первым кубитом. 6. Рассмотрим произвольное квантовое состояние регистра ψ H A H B. Показать, что если A производит произвольное унитарное преобразование над своей частью состояния, а затем B производит измерение второй части регистра в стандартном базисе, то результат измерения B не зависит от воздействия A. 9 Глава 4 Квантовые преобразования, квантовые гейты, квантовые схемы Определение 15 Эволюция квантовой системы (изменение состояния QS за определенный промежуток времени) задается унитарным оператором и описывается следующим образом. Если ψ конфигурация системы QS на текущем шаге, то на следующем шаге конфигурация QS будет ψ, где ψ = U ψ и U (d d) унитарная матрица. Определение 16 Квантовый гейт с n входами и n выходами это преобразование, заданное на n кубитах и определяемое унитарной матрицей U размерности n n. Простейшие однокубитные квантовые гейты. I: X: Y: Z: ( ( ( ( ) ) ) ) Определение 17 Квантовая схема это квантовая вычислительная модель, построенная из квантовых логических гейтов, в которых вычислительные шаги синхронизированы по времени. Входы квантовых гейтов связаны с входами схемы или с выходами других гейтов. Выходы некоторых гейтов связаны со входами других гейтов. Сложная унитарная операция может быть представлена в виде схемы, состоящей из нескольких квантовых гейтов. 10 4.1 Упражнения. 1. Пусть даны унитарные матрицы ( a00 a A = 01 a 10 a 11 ) ( b00 b B = 01 b 10 b 11 Написать унитарную матрицу, задающую преобразование, реализуемое следующей схемой: ) a) b) c) ( ) u00 u. Пусть U = 01. Опишите структуру следующих унитарных u 10 u 11 матриц: a) U I I; b) U I n 1 i=1 I; c) CNOT I I. 3. Разработайте квантовую схему, которая преобразует квантовое состояние a 0 + b 1 в состояние (a) b 0 + a 1 ; (b) b 0 a 1 ; (c) a 0 b 1 ; (d) a 0 + b Рассмотрите гейт CNOT со вторым, контролируемым кубитом в состоянии 1 ( 0 1 ). Опишите действие этого гейта на первый, контролирующий кубит. 5. Разработайте квантовую схему, состоящую из однокубитных гейтов и гейта CNOT, воздействующий на второй кубит, которая осуществляет преобразование: 00 1 ( ); 11 1 ( ). 11 Каково воздействие этой схемы на состояния 01 и 10? 6. Разработайте квантовую схему, которая из состояния 00 получает запутанное состояние 1 ( ); из состояния 00 }{{... 0} на l кубитах получает запутанное состояние 1 ( ). l 7. Пусть q 0 = a 0 + b 1, ψ 0 = 1 ( ). Пусть ψ = q 0 ψ 0. Выписать, чему равно состояние ψ и указать, является оно запутанным или нет. Если состояние является запутанным, то какие кубиты запутаны с какими. (a) ψ = (CNOT I) ψ, (b) ψ = (I CNOT ) ψ. 8. Представить состояние Бэлла ψ = 1 ( ) в базисе B. Является ли оно разложимым в новом базисе? (a) B = { 1 ( ), 1 ( 0 1 )}, (b) B = { 1 ( 0 + i 1 ), 1 ( 0 i 1 )}. 9. Опишите унитарную матрицу для гейта Фредкина. 10. Опишите унитарную матрицу для гейта Тоффоли. 11. Покажите, что для тензорного произведения матрицы и векторов состояний выполняется: (A B)( ψ 1 ψ = (A ψ 1 B ψ ). 1 1. Покажите, что преобразование (x 1, x,..., x n, b) (x 1, x,..., x n, b x 1 x n ) может быть осуществлено квантовой схемой глубины с O(log n), содержащей только гейты CNOT. 13. Дана квантовая схема Найти результат воздействия этой схемы на состояние Пусть даны унитарные матрицы ( ) ( a00 a A = 01 b00 b ; B = 01 a 10 a 11 b 10 b 11 ) ( c00 c ; C = 01 c 10 c 11 ) Написать унитарную матрицу, задающую преобразование, реализуемое: (a) последовательной композицией схем a), b), c); (b) последовательной композицией схем a), b); (c) последовательной композицией схем a), c); a) b) c) 15. Двухкубитная операция сумма, перенос (a, b) (a b, a b) не является взаимнооднозначной. Однако она может быть модифицирована во взаимнооднозначную (a, b, 0) (a, a b, a b), которая может быть реализована при помощи квантовых гейтов CNOT, CCNOT следующим образом: 13 Нарисовать схему для трехбитного сложения. 16. Покажите, что если гейт CNOT применяется к Адамаровскому базису (то есть с использованием преобразования Адамара до и после применения гейта CNOT), то контролируемый и контролирующий кубиты меняются местами. Можно привести такую аналогию принтер вдруг становится сканером и наоборот. 17. Пусть дано произвольное состояние a x n +b y n. Как получить состояние ψ = a x n x n + b y n y n. Какое состояние будет после измерения первого регистра состояния ψ? Какое состояние будет после измерения второго регистра состояния ψ? Как это можно трактовать, если регистр, который измеряется, считать измеряющим устройством для второго, целевого регистра. 18. Покажите, что состояние кубита q = 1/ 0 + 1/ 1 нельзя трактовать таким образом, что значение кубита с вероятностью 1/ равно 0 и с вероятностью 1/ равно 1. Подсказка: провести измерение кубита в Адамаровском базисе (с применением гейта Адамара до измерения) и подсчитать вероятности результата измерения. 19. Доказать эквивалентность следующих схем: 14 Напомним, что четыре состояния Белла это 1 ( 00 ± 11 ), 1 ( 01 ± 10 ). Последовательность каких унитарных преобразований на первом кубите (с тождественным преобразованием на втором кубите) осуществляют перестановку этих базисных состояний. 1. Предположим, что Алиса и Боб осуществляют плотное кодирование. Злоумышленник Ева перехватывает передаваемый Алисой кубит и затем пересылает его Бобу. Может ли Ева сохранить факт своего вмешательства в тайне от Боба? Может ли она узнать закодированное Алисой сообщение? Если да почему? Если нет почему? 15 16 Глава 5 Квантовые алгоритмы 1. Пусть дан квантовый гейт U y, который преобразует квантовое состояние ψ в состояние ( 1) y ψ для фиксированного y {0, 1}. Разработать квантовую схему, содержащую два гейта Адамара и условный гейт U y для определения значения y.. Дано квантовое состояние S(N, x) = 1 q q 1 a=0 a xa mod N. Пусть x = 6, N = 91, q = 51. Пусть S квантовое состояние, полученное после измерения второго кубита состояния S(N, x). Выписать состояние S, если исход измерения a = Литература 1. Гайнутдинова А.Ф. Основы квантовых вычислений. Учебное пособие. // Казань:Изд-во КГУ г с. 18
