CHƯƠNG 1 - TỐNG QUAN ó thể xem khác biệt cơ bản của máy tính lượng tử so với máy tính cổ điển năm ö 9 diém chinh: qubit so với bït, và cổng lượng bử so với phép toán logic. Trong lúc bịt chỉ lưu một giá trí 0 hoặc 1, thì qubit lưu đồng thai hai giá trị này ở đang chồng chất trạng thái mà khi kết hợp lại thành rnộp thanh ghỉ, thanh ghỉ cổ điển vẫn chỉ lưu một giá trị còn thanh ghi lượng tử có khả năng lưu tất cả các giá trị quan tâm, cũng dưới dạng chồng chất trạng thái. Ngoài ra trong lúc các phép toán logic nhận các bit đần vào và trả kết quả cho bit dan ra, thi các cổng lượng tử tác đồng lên quhit làm thay đổi chính nó, nghĩa là xử lý đồng thài các giá trị nằm trong thạng thái chồng chất. Nhĩ vậy máy tính lượng tử tu việt hơn máy tính cổ điển ở chỗ nó có khả năng lưn trữ và xử lý đồng thời các giá trị quan tâm.
Một thuật toán lượng tử bản chất, là một phép biến đổi unita, cài đất một thuật Loán lượng tử là phân tích phản tích các phép biển đổi uniLa thành các cổng lượng Lử (là các phép biến đổi unita cho trước). Dal sé Lie sa(z) và su(ø) là các dại gỗ các phép biến đổi tuyến tính đặc biết cá vai trò rất quan trong trong việc cài đặt cáo Lhuật toán lượng tử. Trong chương này chúng tôi giới thiên tổng quan về 8 thuật toán lượng tử và một số kiến thức cơ bản về đại số Lic so() và su(n). 1 Tổng quan về thuật toán lượng tử 1-1 Các khái niệm cơ bản của tính toán lượng tử Jác khái niệm cø bản của tính toán lượng tử bao gồm: thanh ghí lượng tử, đo lượng tứ, công lượng tử.
Trong mục này chứng tôi cũng giỏi thiệu một số phép biến đối unita quan trong thường được đừng trong xây dìịmg các thuật toan litdng tit.14 Thanh ghi lgng tt Tai mat thời điểm, trong lúc bít cổ điển nhận một trong hai giá trị Ú hoặc 1, thi bit lượng rử (được gọi là qubit) lại nhận đồng thời cà hai giá trị này. TĐ-ng ký hiện bra-kel (Paul Dirao, 1002-1984), một, qubil Bà niột hệ vật lý gồm các Lrạng thái lø — «ao |8) + ai|D với œụ,œ là các số phức thỏa man |og|Ÿ + |an|Š — 1 và {I0).|I)} là một cơ sở chính tắc của ŒẺ, Thanh ghi lượng tử lưu trữ đồng thời các giá trị tính toán hình thành một phân bố xác suất xác định. Một thanh ghi n qubit là một hệ vật lý gồm các trang thai 2" 1 ht) — SO ag [ed aa) &=Ũ aril với các số phức a, théa man 3` |ơ; 1 và {|#}} Ta: là một cơ sở chính k0 tác trong (C?}#", Trạng thái Lồng quát (1.1) được gọi là trưng thái chẳng chất 9 gì? —1 với phân bố xác suất bằng {la}, E Hai trang thái |j) và |¿s) được xem là một nếu |) = e'” |ús) 0 € R.,2" — 1 được gọi là frạng thái thuần., 2"— 1, được gọi là các trạng thái tính toán.1 Trạng thái chồng chất của một thanh ghi 2 qubit.1 Trạng thái chồng chất của một thanh ghỉ 2 qubit 1.2 Đo lượng tử Tinh toán lượng tử làm việc trên nhiều qubit, trong đó một số qubit được nhóm lại thành các thanh ghỉ để thuận tiện trong việc mô tả. Muốn xác định kết quả chúng ta phải thực hiện một phép đo trên một hoặc nhiều thanh ghi này.
Kết quả đo thu được một trang thái thuần trên các thanh ghỉ được do trong lúc thay đổi trạng thái trên hệ con các thanh ghi còn lại. 10 Trong cơ học lượng tử, trạng thái của hạt (vi mô) được mô tả bởi hàm sóng, là một véc tơ đơn vị trong khéng gian Hilbert phite, được gợi là không gian Hilbert liên kết với hạt. Một đại lượng vật lý được mô tả bồi một toán tit Hermite là toán tử tuyến tính tự liên hợp với các trị riêng là cáe giá trị đo được của đại lượng này. Kết quả đo sẽ làm sny sụp hàm sóng, đưa trạng thai của, hại.
về trạng thái riêng là véc bở riêng đơn vị ứng với Lrị riêng vừa được đó. Ký hiệu |ớ) là trạng thái của bạu và |a} là véeLd riêng đơn vị ứng với trị riêng a, khi ấy xáo suất đo dược a là Pa = {tal [| Xét dại lượng vật lý có hai giá trị, toán tử mö tả nó có 2 trị riêng ứng với 2 yée tơ riêng được chọn làm cơ sở chính tắc của không gian Hilbert liên kết biểu diễn tất cả các trạng thái của hạt. Hai véc tở riêng này được ký hiệu là |U) và |1). Để mã hóa dữ liệu cho tính Loán lượng tử, chúng ta quy ước trị riêng do dược ứng với chúng là Ö và 1 tương ứng, Nhà đó chúng tá không, quan tầm dến hạt nào dược chọn Iam qubit va dại lượng nào dược chọn dể đo.
Kết quả ta có mô hình toán học thuần túy. Xác suất đo được một trạng thái thuần được tính như sau. Trước hết, nếu do trên tất cả các qubit của hệ, ở trạng thái (1.1), như đã đề cập ở trên, ta cổ PhD =r = kel? a2) Nếu hệ phân tích thành 2 thanh ghi m va n qubit thi (1.1) được viết lại: 211 18} — SOY ery le} ly}, 2=0 yo kết quả đo trên thanh thứ nhất nhận được giá trị j: mt a1 Prox = 9) — 3 boyy? by — SO (1.2 Xét hé 3 gubil, phần Lích thành 2 thánh ghỉ, thách ghỉ thứ nhất gầm 1 qubit dầu, thanh ghi thứ 2 gồm 2 qubit cồn lại. 1 1 1 lap = 9/911) gl) — ali) Ké&t qua do trén thanh ghi thit nhat: Gia tri do duge 0 1 Xác suất 1 1 "Trạng thái san đo | 2 |0) J1) | |1) (22) — Js ) 1.
Cổng lượng tử Trong tính toán lượng tử trạng thái hệ được thay đổi bằng các phép biên đổi unita. Các phép biến đổi unita được phân tích thành tích của các phép biến đổi tác động lên không quá 2 qubit, gợi là cổng lượng tử. Cổng Iladamard, ký hiệu là II 1, 5 Hk) ~ (I0 v3 +(—U"[P) (1. Gác công chuyển pha 1 và 2 qubit, ky hiệu là P„ Tạ |k) — e* [ky Pe |) [yy — oF? |e} |y) 3.
Các cổng Pauli, ký hiệu là ø„,ø¿, ơ;, trong đó ơ„ còn được gọi là cổng XOR, ole) =| &) =|LOR)=|1 +8), ay |) = (-1) [1 — ay, (1. Céng SWAP SWAP lee) lạ) = lạ ke) (13) 6. Céng Toffoli, k¥ higu la T fey Ly) Le) = Le) ly) Le & ey) (19) >———_ = « 1000 700 0010 =}070 0100 00 a, 0001 Một số phép biến đổi quan trọng Một số phép biển đổi unita déng vai tro quan trong trong tính toán lưgng tử: 1. Phếp biến đổi Hadarmard, kỹ hiệu /Ÿ“, hoặc H (nếu kuông sợ nhằm lân) amd H |x) — 1" ip (119) w=0 acl - - trong đó x.
Phép biến đổi tách pha, ký hiệu Ứ„ md Up |b) — — 7 eM [ny (1. Phép biến đổi điều khiển, ký hiệu A¿;. |#) lự},#Z —1 Xe le lộ Qo (1. Phép biến đổi lượng giá hàm, cồn gọi là hộp đen, ký hiệu Uy Usleply) — [sgk f2) (LH) Ö đây, hép biến đổi điều khiển đóng vai trò như cấu trúc rẽ nhánh trong tính toán cổ điển, còn hộp đen thường đùng để biểu diễn dữ liệu bài toán.
“Trong hầu hết tài liệu phép toán cộng ở (1.14) là phép XOR. theo từng bịt; 144 cũng có tài liệu coi day 1A phép cong mod 2”, véi m là số qubit của thanh ghỉ thứ 3.2 'Thuật toán lượng tử Có thể xem sự khác biệt cơ bản giữa thuật toán lượng tử và thuật toán ich quan lý và sử dụng biến để lí trữ và xử lý dit | - Qua đó lập trình viên cũng thay đổi cách tư duy lập trình của họ. 'Irong thuật toán gỗ điển lập kình viền khoẩi mái sử dụng các biến mà khả năng lưu trữ và xử lý đữ liệu của chúng được xác định qua các kiểu dữ liệu khác nhau được xây dựng sẵn hoặc do họ tự định nghĩa lấy. Với phép gán và các cấu trúc điều khiển tnần tự, lắp và rõ nhánh, lập trình viên kiểm soát các biến của chương trình mang ít nhiều tre giác.
Ngược lại, trong thuật toán lượng, tử lập trình viên chỉ dùng đuy nhất một biến, là kết hợi của nhiều qubit lưu trữ đồng thời các giá trị thuộc lĩnh vực bài toán cần giải, và xử lý nó bằng, cách ái dụng các cổng lượng Lử hoặc các phép biển đổi tuáta dược chấp nhận lên các qubit hich hợp. Không có phép gắn, chỉ cá phép do. Biến dược khởi tạo, dược xử lý bởi các phép biến dối unita, và được do để rất ra giá tìm lời giải của bài toán. Cấu trúc rẽ nhánh cũng kháe, dưới tác dụng của cáo phép biến đổi được điều khiến, chỉ các giá trị của biến thuộc một không, gian con nào đó bị thay đổi, Để xãy dựng thành công một thuật toán lượng, tứ, lấp trình viên Hic nay cầu có kiến thức về Loán học và vật lý học hiện dại.
Như vậy thuật toán lượng Lử chí ưu việt hơn thuật toán cỗ diễn khi nó được hiện thực trên một máy tính lượng tử thặt sự. Trong mục này chúng tới gidi thiệu thuật toán lượng tử ở mức tổng quát, đơn giản nhất; giới thiệu m6 hình đây và minh họa một số thuật toán, 1.1 Thuật toán lượng tử mức tổng quát Trong tính toán lượng tử bài toán chính là tìm một phép biến đổi unita, đứa hệ từ trạng thái l¿n) về trạng th ủ} , chứa nhiền théng tin cho phép giải quyết một bài toán nào đó. San đó, chúng ta sẽ thực hiện một phép đo trên trạng thái |} để có thông tin vẻ lời giải. Kết quả đo sẽ nhận được một: giá trị nguyên và để lại hệ với trạng khái lương ứng; giá trì Lhu được là ngẫu nhiên với phan bé xác suất xác định theo công thức đã biết (1.3 Xét hệ #qubit với trạng thái ban đầu là một trạng thái tính toán lựa) = |IT1).
Táo động phép biến đổi Hadamard lên 2 qnbit đầu: „1 1 vs Tu ¬ he = yall +[1}} yal JD)ID— s0 + I7) Do trên 2 qubit cuỗi thu được các giá trị 1 hoặc 3 với xác suất bằng nhau và để lại trạng thái của hệ tương ứng như sau Giá trị do dược 1 3 Xác suất 0 0.5 Trang thai sau đo. -L (J0 —|D)|1) | 54 (0) + |)I8) Như vậy một Lhuật toán lượng tử xẽ gồm ba bước chính: 1. Chuẩn bị trạng thái đầu của Llaánh ghi |jp) 2. Thực hiện phép biến dối unita |#} — (|).