Đồ án Nghiên cứu các phương pháp tính toán lượng tử

i một qubit, nó sẽ tác động đồng bộ lên cả 2 trạng thái cơ sở 0 , 1 , đó chính là do nguyên lý song song lượng tử. Định nghĩa 1.4: Mạch lôgic lượng tử là một tập các cổng lôgic lượng tử liên kết theo một đồ thị có hướng không chu trình, trong đó đầu ra của cổng này có thể là đầu vào của cổng kia. Định nghĩa 1.5: Một tập cổng lượng tử G được gọi là phổ dụng nếu với mọi 0ε > và mọi ma trận Unita U tác động trên số qubit bất kì, U có thể được xấp xỉ với độ chính xác ε bằng một dãy cổng của G. Nói cách khác nhóm con tạo nên bởi G là trù mật trong nhóm các toán tử Unita. Tức là , 0, 'U Uε∀ ∀ > ∃ được tạo nên bằng tích các cổng của G sao cho: 'U U ε− ≤ , với một chuẩn được lựa chọn cụ thể trong không gian Hilbert. 1.3.6. Phép đo Việc đo một qubit của siêu trạng thái S về mặt toán học được biểu diễn bởi một phép chiếu vectơ s lên một trong hai không gian con S0, S1 với Sa là không gian con sinh bởi tất vả các trạng thái cơ sở mà qubit được đo là a. Nếu 2 1 1 2 0 n i n i S C i i i − = = ∑ K thì phép đo trên qubit đầu sẽ cho ra kết quả 0 với xác suất 2 3 2 3 2 0 , , , Pr (0) n n i i i i i i ob C= ∑ K K , kết quả 1 với xác suất H 8 2 3 2 3 2 1 , , , Pr (1) n n i i i i i i ob C= ∑ K K và siêu trạng thái S sẽ sụp đổ tương ứng về một trong hai trạng thái sau: ( ) 22 0 1 2, , 1 0 Pr 0 n n i i n i i C i i i ob ∑ KK K ( ) 22 1 1 2, , 1 1 Pr 1 n n i i n i i C i i i ob ∑ KK K Sự sụp đổ của hệ thống sau phép đo chính là sự thể hiện của nguyên lý nổi tiếng về sụp đổ của hàm sóng. Ví dụ: xét siêu trạng thái 2-qubit : ( )1 00 01 11 3 + − . Phép đo trên qubit đầu tiên cho kết quả 0 với xác suất 2/3, kết quả 1 với xác suất 1/3. Như vậy sau khi đo, siêu trạng thái sụp đổ thành ( )1 00 01 2 + với xác suất 2/3 và thành trạng thái 11− với xác suất 1/3. 1.3.7. Thuật toán lượng tử Có thể xây dựng khái niệm thuật toán lượng tử dựa trên cơ sở mô hình máy Turing lượng tử. Tuy nhiên về bản chất, để ngắn gọn, ta có thể xem thuật toán lượng tử được thực hiện bởi một số bước cơ bản, mỗi bước cơ bản bao gồm một dãy các thao tác Unita kèm theo một phép đo. Điểm đáng chú ý là nó sử dụng những ưu điểm, đặc điểm riêng của máy tính lượng tử. Nhờ đó mà thuật toán lượng tử thật sự đã làm được những việc tưởng như không thể đối với những thuật toán cổ điển. Ưu điểm chủ yếu của thuật toán lượng tử là tính chất xử lý song song: việc cổng lượng tử tác động lên một siêu trạng thái n-qubit có nghĩa là nó đã tác động đồng thời lên 2n trạng thái riêng lẻ. Nhận xét: + Thanh ghi lượng tử có khả năng lưu trữ rất lớn. Cùng với nguyên lý song song lượng tử, máy tính lượng tử sẽ thực hiện được những tính toán khổng lồ chỉ sau vài bước tính toán. + Sức mạnh của máy tính lượng tử cho phép ta hi vọng khám phá những thuật toán hiệu quả giải quyết những vấn đề khó như những bài toán thuộc lớp NP-Hard, … + Với những đặc trưng riêng, mô hình máy tính lượng tử hứa hẹn cho phép chúng ta thực hiện nhiều ứng dụng trong thực tế như: truyền tin lượng tử, mã và thám mã lượng tử,... 1.4. Lựa chọn giải pháp cho Visual Quantum Studio (VQS) Việc xây dựng một bộ công cụ (Visual Quantum Studio) thân thiện nhằm mục đích giúp người dùng dễ dàng thực hiện các thao tác đòi hỏi nhiều thiết kế phức tạp, sử dụng những công cụ hiện đại. Trước hết, để thực hịên những tính toán trên khối lượng dữ liệu rất lớn có bản chất song song, môi trường cơ sở dữ liệu là phù hợp hơn cả để phục vụ cho việc tổ chức, lưu trữ và kiểm soát dữ liệu hiệu quả, an toàn và ổn định. Bên cạnh đó, chúng tôi cũng cần phải lựa chọn một ngôn ngữ thích hợp để xử lý trên môi trường cơ sở dữ liệu. Giải pháp mà chúng tôi đã chọn là SQL Server. Đó là vì (xem thêm [11]) + SQL đã trở thành một chuẩn quốc tế về xử lý cơ sở dữ liệu. + SQL trên mô hình cơ sở dữ liệu quan hệ quản lý các bản ghi một cách bình đẳng, không phụ thuộc vào trật tự các bản ghi được lưu trữ. Điều này rất phù hợp với nguyên lý song song lượng tử. 9 + SQL hỗ trợ khả năng tính toán trên môi trường phân tán. + SQL Server hỗ trợ nhiều tính năng phong phú bên cạnh các truy vấn chuẩn. + Giảm thiểu thời gian của nhóm lập trình trong vấn đề tổ chức, quản lý bộ nhớ, do đó nhóm đã viết chương trình trong thời gian kỷ lục. + Giải pháp mà chúng tôi đã chọn cũng là một sự phát triển tiếp cận trong [2]. Tuy nhiên để thực hiện được điều này, vấn đề đặt ra mà công trình cần giải quyết là chứng minh tính đúng đắn của thuật toán mô phỏng tính toán lượng tử trên mô hình đại số quan hệ và sử dụng ngôn ngữ SQL. Bên cạnh việc xử lý tính toán trên cơ sở dữ liệu, để tạo ra một bộ công cụ thân thiện giúp người dùng sử dụng VQS một cách dễ dàng, chúng tôi đã sử dụng: + Công nghệ .NET - là công nghệ hiện đại hỗ trợ khả năng đồ hoạ, đặc biệt là hỗ trợ khả năng tính toán trên môi trường mạng. + Ngôn ngữ XML: là môi trường trung gian giữa giao diện người dùng và môi trường tính toán trên cơ sở dữ liệu. Kết luận: • Trong hoàn cảnh kinh tế còn nhiều hạn chế của nước ta hiện nay, việc lựa chọn giải pháp mô phỏng để nghiên cứu tính toán lượng tử mang nhiều ý nghĩa: ƒ Về kinh tế: không phải đầu tư nhiều tiền của nhưng ta vẫn có một bộ công cụ “giả lập máy tính lượng tử” cho phép nghiên cứu mô phỏng các thuật toán lượng tử. Việc áp dụng các công nghệ hiện đại làm giảm rất nhiều thời gian cho nhóm lập trình. ƒ Về mặt khoa học: sự ra đời của VQS sẽ hỗ trợ đắc lực cho các nhà khoa học trong việc nghiên cứu, kiểm định các thuật toán lượng tử và khám phá các thuật toán mới. ƒ Tính thực tiễn: với những chức năng đã có, VQS hoàn toàn có thể đóng vai trò làm công cụ đắc lực cho một trung tâm nghiên cứu mô phỏng tính toán lượng tử như ở nước ta. Đồng thời VQS cũng có thể là một bộ công cụ hữu ích hỗ trợ cho các nhóm nghiên cứu về lĩnh vực này. ƒ Tính chiến lược: việc hình thành một trung tâm nghiên cứu mô phỏng tính toán lượng tử sẽ giúp chúng ta có cơ hội bắt kịp với thế giới trong lĩnh vực mới này, giúp chúng ta chủ động đối mặt với cuộc cách mạng về khoa học tính toán do máy tính lượng tử tạo ra trong tương lai gần. • Với việc lựa chọn 3 công nghệ hiện đại trên, bộ công cụ VQS có khả năng cung cấp cho các nhà nghiên cứu tính toán lượng tử nhiều tính năng hữu ích với tốc độ xử lý nhanh, khả năng kiểm soát dữ liệu cỡ lớn hiệu quả và an toàn, giao diện trực quan thân thiện dễ dùng mà so với các phần mềm như Mathemetica, Mathlab thì đặc điểm này của sản phẩm là nổi bật. • Với kiến trúc 3 tầng, VQS có tính mở và tính độc lập rất cao. Việc bảo trì và nâng cấp hệ thống có thể tiến hành ở từng tầng mà không đòi hỏi sự thay đổi trong phần còn lại của hệ thống. Điều đó cho phép ta dễ dàng chuyển đổi thiết kế sang các môi trường tính toán mạnh như: môi trường song song trên Windows hoặc Linux, Cluster Computing, Grid Computing,… • Đề tài đòi hỏi các tác giả tổng hợp nhiều kiến thức kết hợp cả toán học và tin học cùng với sự nỗ lực về công nghệ: số học, giải tích phức, đại số, xác suất, độ phức tạp thuật toán, cơ sở dữ liệu, phân tích thiết kế hệ thống,… để hiểu các thuật toán lượng tử, từ đó chuyển sang thiết kế được chương trình mô phỏng tính toán trên SQL. 10 Chương 2. Ngôn ngữ SQL và sự tương thích với mô hình tính toán lượng tử 2.1. Ngôn ngữ SQL Như đã nêu sơ bộ ở phần trên, lý do lựa chọn SQL được thể hiện qua những đặc điểm quan trọng của SQL, về tổng quan có thể xem chẳng hạn [11]. Ở đây ta đề cập thêm những lý do được mọi người quan tâm. a) SQL là ngôn ngữ chuẩn mực, đã được ANSI và ISO thừa nhận như là một ngôn ngữ chuẩn về xử lý dữ liệu, vì vậy dữ liệu có thể được truy xuất theo nhiều phương thức khác nhau, cho cả máy PC, các máy tính mini, và các mainframe . Một ưu điểm khác của SQL là có thể cung cấp dữ liệu cho những phần mềm khác không phải là DBMS, như các hệ xử lý văn bản và các bảng tính điện tử ... b) SQL thuộc loại ngôn ngữ thế hệ thứ 4, hướng phi thủ tục, đã được nghiên cứu nhiều năm qua, và đang nhanh chóng trở thành tiêu chuẩn trên thế giới về xử lý dữ liệu theo mô hình quan hệ . Ngày nay, trong môi trường của ngôn ngữ thế hệ 4, SQL đã xâm nhập vào mọi CSDL (Cơ sở dữ liệu) theo mô hình quan hệ trên thị trường, thích ứng với hầu hết các loại phần cứng và hệ điều hành . c) SQL là ngôn ngữ truy vấn dữ liệu có cấu trúc, tuân theo những qui tắc nhất định. Có 4 loại lệnh trong SQL: + Loại thứ nhất là những Querry , dùng để truy vấn dữ liệu . + Loại thứ hai là những lệnh ngôn ngữ định nghĩa dữ liệu ( DDL ) , cho phép khởi tạo các bảng dữ liệu quản lý đối tượng chẳng hạn như các TABLE , các VIEW . + Loại thứ ba là những lệnh ngôn ngữ xử lý dữ liệu ( DML ), dùng để đọc lại, xoá đi hoặc thêm vào CSDL . + Những lệnh ngôn ngữ kiểm soát dữ liệu ( DLC ) dùng để "giao quyền" hoặc " thu hồi quyền" xếp loại dữ liệu . Người sử dụng có thể gõ vào một cách trực tiếp những lệnh SQL, hoặc là thông qua các giao diện. Lệnh của SQL không nhiều, gần giống với tiếng Anh, do đó người sử dụng có thể truy xuất nhanh những CSDL lớn mà không cần lập trình. SQL là ngôn ngữ truy cập và xử lý dữ liệu mà đối tác của nó là những CSDL theo mô hình quan hệ. Do vậy, những tiếp cận tính toán lớn mà có thể ứng dụng phương pháp biểu diễn theo đại số quan hệ có thể dựa vào SQL để thực hiện các thao tác tính toán cơ bản. d) Các chức năng SQL Thông qua những đặc điểm của SQL, và tuỳ theo môi trường, người sử dụng có thể thường xuyên thực hiện các yêu cầu về dữ liệu như : + Định nghĩa dữ liệu. + Truy vấn, gọi xem, bảo trì dữ liệu. + Tính toán cập nhật dữ liệu. + Kiểm soát việc truy xuất dữ liệu. + Bảo đảm sự an toàn, phân chia quyền sử dụng dữ liệu. + Bảo vệ sự toàn vẹn dữ liệu .. . 2.2. Sự tương thích chặt chẽ giữa SQL và tính toán lượng tử + SQL đối xử với các bản ghi một cách bình đẳng. Nếu coi mỗi truy vấn SQL là một đơn vị tính độ phức tạp thì với mỗi truy vấn ta có thể tác động lên tất cả các bản ghi. Do vậy, nếu sử dụng một bản ghi của bảng để lưu một cơ sở thì ta có thể tác động đồng thời vào toàn bộ superposition, không phân biệt giữa các cơ sở. Như vậy giữa truy vấn CSDL và những phép biến đổi lượng tử có sự giống nhau về mặt bản chất là tác động đồng thời lên tất cả các đối tượng. + Phép JOIN cho phép kết nối hai bảng, làm tăng số cột. Ta có thể sử dụng truy vấn này để mô phỏng phép lấy tích tensơ của hai thanh ghi - một thao tác không thể thiếu trong các thuật toán lượng tử. + Sử dụng truy vấn có kết hợp GROUP BY ta có thể phân lớp các bản ghi. Điều này tạo ra hai ưu điểm sau đây khi mô phỏng tính toán lượng tử: Thứ nhất, các phép biến đổi lượng tử nhiều khi tác động làm cho một vectơr cơ sở bị biến đổi, sinh ra một số vectơ cơ sở khác. Chẳng hạn phép Hadamard : 11 1 1 11 1 12 2 20 0 1 1 1 1 2 20 2 2 2 H æ ö æ ö÷ ÷ç çæ ö÷ ÷ç ç÷ç÷ ÷ç ç÷ç÷ ÷÷ç ç÷ ÷ç ÷= = = +ç ç÷ ÷ç ÷ç ç÷ ÷ç ÷ç ç÷ ÷ç ÷÷ ÷ç ç÷ç- ÷ ÷è øç ç÷ ÷ç çè ø è ø Vậy 1 10 0 1 2 2 H¾ ¾® + 1 1 10 1 12 2 21 0 1 1 1 1 2 21 2 2 2 H æ ö æ ö÷ ÷ç çæ ö÷ ÷ç ç÷ç÷ ÷ç ç÷ç÷ ÷÷ç ç÷ ÷ç ÷= = = -ç ç÷ ÷ç ÷ç ç÷ ÷ç ÷ç ç÷ ÷ç ÷÷ ÷ç ç÷ç- -÷ ÷è øç ç÷ ÷ç çè ø è ø Vậy 1 11 0 1 2 2 H¾ ¾® - Thứ hai, nhờ sử dụng GROUP BY, sau khi tác động lên hệ thống ta có thể gộp các cơ sở giống nhau. Chẳng hạn: H¾ ¾® 1 (Im), (Re) group by q Sum Sum ⎯⎯⎯⎯⎯⎯→ 2.3. Mô phỏng tính toán lượng tử bởi SQL Tính chất (về mối quan hệ giữa mô hình cơ sở dữ liệu với mô hình siêu trạng thái lượng tử): Mô hình cơ sở dữ liệu quan hệ có thể mô phỏng trạng thái của một thanh ghi lượng tử bất kì. Chứng minh: Siêu trạng thái của thanh ghi gồm n qubit có dạng tổng quát như sau: 0 100...0 00...1 ... 11...1 , 2 1 n NC C C N+ + + = − Ta sẽ mô phỏng trạng thái trên bằng bảng quan hệ Superposition sau đây: Trong đó : q1 Im Re 0 0ImC 0ReC 1 1ImC 1ReC q1 Im Re 0 0Im 2C 0Re 2C 1 0Im 2C 0Re 2C 0 1Im 2C 1Re 2C% 1 - 1Im 2C 1Re 2C q1 Im Re 0 1 0(Im Im ) 2C C+ 1 0(Re Re ) 2C C+ 1 0 1(Im Im ) 2C C− 0 1(Re Re ) 2C C− q1 q2 … qn Im Re 0 0 … 0 0ImC 0ReC … … … ... … … 1 1 … 1 Im N C Re NC 12 U Im Rek k kC C i C= + Như vậy, ta có tương ứng 1 1« : Siêu trạng thái « Bảng quan hệ trạng thái. Các phép biến đổi trên siêu trạng thái trở thành các phép biến đổi trên quan hệ mà ta có thể sử dụng các câu lệnh SQL (xem phần sau). Nhận xét: + Nếu siêu trạng thái có dạng: 0 1 0 0 1 10 1 ... (Im Re ) 0 (Im Re ) 1 ... (Im Re ) N N N C C C N C i C C C C C N + + + = + + + + + + (trong đó 2 1nN = - ) thì mỗi véc tơ cơ sở j dược biểu diễn nhị phân bằng một hàng gồm n cột đầu của bảng. Phần thực, ảo của toạ độ tương ứng với j được biểu diễn bằng cột Im, Re tương ứng. + Không thể hiện những vectơ cơ sở j mà jC =0. Điều này giúp cho việc tính toán, lưu trữ được thuận lợi và không dư thừa. Sau đây là định lý cơ bản đóng vai trò cơ sở cho việc xây dựng các ứng dụng mô phỏng tính toán lượng tử bằng SQL. 2.4. Định lý cơ bản về tính đúng đắn của phép mô phỏng Định lý: Sử dụng truy vấn SQL trên cơ sở dữ liệu quan hệ có thể biểu diễn mọi tính toán lượng tử cơ bản (bao gồm các biến đổi Unita và phép đo). Chứng minh. Trước hết ta có nhận xét: có hai loại phép biến đổi cơ bản được thực hiện trong tính toán lượng tử, đó là phép biến đổi Unita và phép biến đổi không Unita, trong đó lớp phép biến đổi không Unita chỉ có phép đo. Hơn nữa trong lớp các phép biến đổi Unita, G= { },3 3U W là tập cổng phổ dụng (trong đó ,3 3U W được xác định ở dưới, xem thêm [4,5,6,8]). Như vậy ta sẽ chứng minh: sử dụng ngôn ngữ SQL trên cơ sở dữ liệu quan hệ có thể mô phỏng được hai cổng ,3 3U W và phép đo. i) Cổng 3U control1 control2 target Trong đó: cos(2 ) sin(2 ) sin(2 ) cos(2 ) U πα πα πα πα ⎛ ⎞= ⎜ ⎟−⎝ ⎠ Tác động cuả 3U : 13 W 3 0 0 0 5 6 7 7 7 6 7 1 0 1 0 cos(2 ) sin(2 ) cos(2 ) sin(2 ) sin(2 ) cos(2 ) cos(2 ) sin(2 ) U C C C C C C C C C C πα πα πα πα πα πα πα πα ⎛ ⎞⎛ ⎞⎛ ⎞ ⎛ ⎞ ⎜ ⎟⎜ ⎟⎜ ⎟ ⎜ ⎟ ⎜ ⎟⎜ ⎟⎜ ⎟ ⎜ ⎟ ⎜ ⎟⎜ ⎟⎯⎯→ =⎜ ⎟ ⎜ ⎟ ⎜ ⎟⎜ ⎟ +⎜ ⎟ ⎜ ⎟ ⎜ ⎟⎜ ⎟⎝ ⎠ ⎝ ⎠⎜ ⎟ ⎜ ⎟− − +⎝ ⎠ ⎝ ⎠ MOM M M M Giả sử một siêu trạng thái đã được cho dưới dạng bảng quan hệ Superposition: SQL¾ ¾ ¾® Thực hiện bằng truy vấn SQL: Select * into Tam from Superposition Update Superposition set q@target=1- q@target where q@control1=1, q@control2=1 Update Superposition set Im=Im. cos(2 )πα ,Re=Re. cos(2 )πα where q@control1=1, q@control2=1 Update Tam set Re=-Re. sin(2 )πα , Im=-Im. sin(2 )πα where q@control1=1,q@control2=1,q@target=1 Update Tam set Re=Re. sin(2 )πα , Im=Im. sin(2 )πα where q@control1=1,q@control2=1,q@target=0 Insert into Tam select * from Superposition Drop table Superposition Select q1,q2,...,qn, sum(Re) as Re, sum(Im) as Im into Superposition from Tam group by q1,q2,...,qn Drop table Tam ii) Cổng 3W control1 cotrol2 target q1 q2 q3 Im Re 0 0 0 0ImC 0ReC ... ... ... ... ... 1 1 0 6ImC 6ReC 1 1 1 7ImC 7ReC q1 q2 q3 Im Re 0 0 0 0ImC 0ReC ... ... ... ... ... 1 1 0 6 7Im cos(2 ) Im sin(2 )C Cπα πα+ 6 7Re cos(2 ) Re sin(2 )C Cπα πα+ 1 1 1 6 7Im sin(2 ) Im (2 )C C cosπα πα− + 6 7Re sin(2 ) Re (2 )C C cosπα πα− + 14 Trong đó: 2 1 0 0 i W e πα ⎛ ⎞= ⎜ ⎟⎝ ⎠ Tác động cuả 3W : 3 1 00 00 0 1 2.7 72 7 W ieie CC C C C C παπα ⎛ ⎞ ⎛ ⎞⎛ ⎞ ⎛ ⎞⎜ ⎟ ⎜ ⎟⎜ ⎟ ⎜ ⎟⎜ ⎟ ⎜ ⎟⎜ ⎟ ⎜ ⎟⎜ ⎟⎯⎯⎯→ = ⎜ ⎟⎜ ⎟ ⎜ ⎟⎜ ⎟ ⎜ ⎟⎜ ⎟ ⎜ ⎟⎜ ⎟ ⎜ ⎟⎜ ⎟ ⎜ ⎟ ⎜ ⎟⎜ ⎟⎝ ⎠ ⎝ ⎠ ⎝ ⎠⎝ ⎠ O MM MO MM M Nhận xét: Chỉ những cơ sở mà q@control1 = q@control2 = q@target = 1 mới bị nhân thêm 2ie πα Dưới dạng bảng : SQL¾ ¾ ¾® Thực hiện bằng truy vấn SQL: Alter table Superposition add tam Update Superposition set tam=Im Update Superposition set Im= Im cos(2 ) Resin(2 )πα πα+ Re= Re os(2 ) Im sin(2 )c πα πα− where q@control1=1,q@control2=1,q@target=1 Alter table Superposition drop tam Như vậy, ta đã thực hiện được các cổng ,3 3U W . Tập { },3 3U W là trù mật trong nhóm các ma trận unita 8x8. { },U Wn n là tập trù mật trong nhóm các ma trận unita 2 2n n´ . Để tạo ra ,U Wn n từ ,3 3U W ta dùng phương pháp qui nạp: sử dụng thêm phép And của 2 bit đầu tiên bằng TOFFOLI( CCNOT), ghi kết quả lên bit phụ. Sau đó áp dụng ,1 1U Wn n- - ta sẽ thu được ,U Wn n . iii) Phép And a a b b q1 q2 q3 Im Re 0 0 0 0ImC 0ReC ... ... ... ... ... 1 1 0 6ImC 6ReC 1 1 1 7ImC 7ReC q1 q2 q3 Im Re 0 0 0 0ImC 0ReC ... ... ... ... ... 1 1 0 6ImC 6ReC 1 1 1 7 7Im cos(2 ) Re sin(2 )C Cπα πα+ 6 7Re cos(2 ) Im sin(2 )C Cπα πα− 15 c cÅ ab Dạng bảng: SQL¾ ¾ ¾® Nhận xét: Bit c bị lật trạng thái khi và chỉ khi a = b = 1. Thực hiện bằng truy vấn SQL: Update Superposition set q@target=1-q@target where q@control1=1,qa@control2=1 . Nhận xét rằng, để thực hiện tính toán, nhiều khi phải sử dụng 2 thanh ghi có tương tác (correlation) với nhau. Do vậy cần phải mô phỏng phép lấy tích tensor 2 thanh ghi. iv) Mô phỏng phép lấy tích tensơ hai thanh ghi Xét phép lấy tích tensơ hai thanh ghi có trạng thái sau đây: Reg1: 0 100...0 00...1 ... 11...1 , 2 1 n NC C C N+ + + = − . Hệ thống gồm n qubit. Reg2: 0 100...0 00...1 ... 11...1 , 2 1 m MC C C M+ + + = − . Hệ thống gồm m qubit. Sau khi lấy tích tensor phải thu được: Reg1⊗Reg2= 0 1( 00...0 00...1 ... 11...1 )NC C C+ + + ⊗ 0 1( 00...0 00...1 ... 11...1 )MC C C+ + + = 0 0 0 1 000...0 00...0 00...0 00...1 ... 00...0 11...1MC C C C C C⊗ + ⊗ + + ⊗ +... + 0 111...1 00...0 11...1 00...1 ... 11...1 11...1N N N MC C C C C C⊗ + ⊗ + + ⊗ Dưới dạng bảng, Reg1 là Reg2 là a b c Im Re 0 0 0 0ImC 0ReC ... ... ... ... ... 1 1 0 6ImC 6ReC 1 1 1 7ImC 7ReC a b c Im Re 0 0 0 0ImC 0ReC ... ... ... ... ... 1 1 1 6ImC 6ReC 1 1 0 7ImC 7ReC q11 q12 … q1n Im1 Re1 0 0 … 0 0Im1C 0Re1C … … … ... … … 1 1 … 1 Im1 N C Re1 NC 16 Reg1⊗ Reg2 là Thực hiện bằng truy vấn SQL: Select * into Tensor from Reg1cross join Reg2 Alter table Tensor add Im,Re Update Tensor set Im=Im1.Re2+Im2.Re1 Re=Im1.Im2-Re1.Re2 Alter table Tensor drop Im1,Im2,Re1,Re2. Đến đây ta đã chứng minh được mọi phép biến đổi Unita trong tính toán lượng tử đều có thể mô phỏng đúng đắn bởi ngôn ngữ SQL trên cơ sở dữ liệu. Để hoàn thiện chứng minh, ta cần chứng minh sự đúng đắn với phép đo. v) Phép đo Phép đo là phép tác động lên một tập các qubit của một thanh ghi lượng tử. Nếu gọi i1,i2,...,ik là tập các chỉ số của các qubit trong một thanh ghi n qubit cần đo, khi đó phép đo sẽ thực hiện phép chiếu trạng thái của thanh ghi lên một không gian con bất kì trong 2k không gian con được sinh bởi sự tổ hợp của k qubit trên, trong đó ứng với mỗi không gian con, xác suất để trạng thái thanh ghi rơi vào phụ thuộc vào biên độ của các trạng thái trong thanh ghi ban đầu. Thuật toán thực hiện phép đo như sau: b1: tạo bảng CollectingTable gồm có (k+1) cột, với tên cột lần lượt là: 1 2 Pr , , ,..., ki i i ob q q q b2: điền toàn bộ 2k cơ sở vào bảng CollectingTable b3: giá trị của trường Prob sẽ được tính bằng tổng xác suất của các cơ sở trong bảng Superposition mà có gía trị của các qubit ứng với 1 2 , ,..., ki i i q q q bằng giá trị tương ứng trong bảng CollectingTable (bảng Superposition biểu diễn trạng thái của thanh ghi hiện hành). b4: đo toàn bộ thanh ghi CollectingTable. Trạng thái mới sau khi đo sụp đổ theo qui luật của hàm sóng sẽ được lưu trữ trong bảng tblMaxRow. b5: đối chiếu cơ sở duy nhất trong tblMaxRow với thanh ghi Superposition để lọc ra những cơ sở có các giá trị của các qubit 1 2 , ,..., ki i i q q q trùng nhau trong 2 bảng. Thuật toán được thể hiện dưới dạng truy vấn như sau: Trước hết tạo thủ tục CreateCollectingTable để hiện bước 1: Create Table CollectingTable ( prob float ) j = 1 While (j <= k) q21 q22 … q2m Im2 Re2 0 0 … 0 0Im 2C 0Re 2C … … … ... … … 1 1 … 1 Im 2 M C Re 2 MC q11 … q1n q21 ... q2m Im Re 0 … 0 0 ... 0 0 0 0 0Im1 Re 2 Im 2 Re1C C C C+ 0 0 0 0Im1 Im 2 Re1 Re 2C C C C- … … ... ... ... … … 1 … 1 1 ... 1 Im1 Re 2 Im 2 Re1N M M NC C C C+ Im1 Im 2 Re1 Re 2N M N MC C C C- 17 Begin Alter Table CollectingTable Add ji q int j := j + 1 End Tiếp theo ta thực hiện điền 2k cơ sở vào bảng CollectingTable bằng thủ tục InsertBases: Set n = 0 While(n < power(2,k)) Begin exec BiGenerate n,k,valuestr output IinsertIinto CollectingTable Values valuestr n: = n + 1 End (Thủ tục BiGenerate sẽ sinh ra số nhị phân k chữ số từ số n đồng thời biến số nhị phân đó thành dạng xâu chuẩn để đưa vào câu lệnh Insert.) Để thực hiện bước 3 điền giá trị vào trường Prob, ta thực hiện thủ tục InsertCollectingTable: Alter table superposition Add prob As square(re) + square(im) Update collectingtable Set Prob = (Select sum(s.Prob) From Superposition s Where 1 1 . .i icollectingtable q s q= and 2 2 . .i icollectingtable q s q= ... and . . k ki i collectingtable q s q= ) Sau khi tạo được bảng Collectingtable, ta dùng thủ tục CreateTblMaxRow thực hiện bước 4: Select maxprob = max(Prob) From collectingtable Select * Into tblmaxrow From collectingtable Where Prob = maxprob Thủ tục EditMaxrow được dùng để kiểm tra bảng tblmaxrow trong trường hợp bảng có nhiều hơn một hàng, xảy ra khi siêu trạng thái của ta có nhiều cơ sở cùng đạt xác suất cao nhất, ta sẽ giữ lại ngẫu nhiên một cơ sở bất kì. Select n = count(Prob) From tblmaxrow if( n > 1) Begin Alter Ttable tblmaxrow Adđ ind As 1 2 1 2.2 .2 k k k i i iq q q − −+ + +L Declare curInd Scroll Cursor For Select ind From tblmaxrow Open curInd Select row = count(Prob) From tblmaxrow exec RandId = random row F etch Absolute RandId From curInd Into i Delete From tblmaxrow Where ind i End 18 (Hàm random(n) sẽ sinh một số nguyên ngẫu nhiên nằm trong khoảng [1,n]) Cuối cùng ta thực hiện thủ tục Measure để thực hiện bước 5: Delete From superposition s From tblmaxrow t Where ( 1 1 . .i is q t q or 2 2. .i is q t q or ... or . .k ki is q t q ) Phép chứng minh định lý được hoàn thành. 19 2.5. Mô phỏng một số cổng lượng tử phổ dụng Sau đây là một số ví dụ áp dụng SQL cho các cổng lượng tử cơ bản khác i) Cổng HADAMARD Dạng mạch Dạng ma trận: 1/ 2 1/ 2 1/ 2 1/ 2 H ⎛ ⎞= ⎜ ⎟⎜ ⎟−⎝ ⎠ Thực hiện: Xét superposition tổng quát: { } 1 2 1 1 1 2 1 1 1( ... ... ) 0,11 2 1 1 ... 0 ... 1 2 1 1 ... 1 ... 1 2 1 1( ... 0 ... ... 1 ... )k k n k k n ni i i i ik k n i i i i i k k n i i i i i k k nc i i i i i c i i i i i− + − + −∈− + − + − ++∑ Cổng HADAMARD tác động trên qubit thứ k của hệ thống n qubit gây nên sự biến đổi như sau: 1 2 1 1 1 2 1 1... 0 ... 1 2 1 1 ... 1 ... 1 2 1 1 ... 0 ... ... 1 ... k k n k k ni i i i i k k n i i i i i k k n c i i i i i c i i i i i− + − +− + − ++ → 1 2 1 1 1 2 1 1 1 2 1 1 1 2 1 1... 0 ... ... 1 ... 1 2 1 1 ... 0 ... ... 1 ... 1 2 1 1 1 1( ) ... 0 ... ( ) ... 1 ... 2 2k k n k k n k k n k k ni i i i i i i i i i k k n i i i i i i i i i i k k n c c i i i i i c c i i i i i− + − + − + − +− + − ++ + − Với mọi bộ 1 2 1 1( , ,..., , ,...., )k k ni i i i i− + trong đó { }0,1 1, ,ji j n j k∈ ∀ = ≠ . Thực hiện bằng SQL: Select * into Tam from Superposition Update Superposition set q@target=1- q@target Update Superposition set Im=Im / 2 ,Re=Re / 2 Update Tam set Re=-Re / 2 , Im=-Im / 2 where q@target=1 Update Tam set Re=Re/ / 2 , Im=Im / 2 where q@target=0 Insert into Tam select * from Superposition Drop tabl e Superposition Select q1,q2,...,qn, sum(Re) as Re, sum(Im) as Im into Superposition from Tam group by q1,q2,...,qn Drop table Tam ii) Cổng NOT Dạng ma trận: 0 1 1 0 ⎛ ⎞⎜ ⎟⎝ ⎠ Hoạt động: Xét superposition tổng quát: { } 1 2 1 1 1 2 1 1 1( ... ... ) 0,11 2 1 1 ... 0 ... 1 2 1 1 ... 1 ... 1 2 1 1( ... 0 ... ... 1 ... )k k n k k n ni i i i ik k n i i i i i k k n i i i i i k k nc i i i i i c i i i i i− + − + −∈− + − + − ++∑ Thực hiện cổng NOT trên qubit thứ k ta thu được: no H 20 1 2 1 1 1 2 1 1... 0 ... 1 2 1 1 ... 0 ... 1 2 1 1 ... 0 ... ... 1 ...− + − +− + − +→k k n k k ni i i i i k k n i i i i i k k nc i i i i i c i i i i i 1 2 1 1 1 2 1 1... 1 ... 1 2 1 1 ... 1 ... 1 2 1 1 ... 1 ... ... 0 ...− + − +− + − +→k k n k k ni i i i i k k n i i i i i k k nc i i i i i c i i i i i Mô phỏng bằng SQL: Update @table set qk=1-qk iii) Cổng CNOT Dạng ma trận: 1 1 0 1 1 0 ⎛ ⎞⎜ ⎟⎜ ⎟⎜ ⎟⎜ ⎟⎝ ⎠ Hoạt động: Xét superposition tổng quát: { } 1 2 1 1 1 2 1 1 1( ... ... ) 0,11 2 1 1 ... 0 ... 1 2 1 1 ... 1 ... 1 2 1 1( ... 0 ... ... 1 ... )k k n k k n ni i i i ik k n i i i i i k k n i i i i i k k nc i i i i i c i i i i i− + − + −∈− + − + − ++∑ Thực hiện cổng NOT với qubit thứ t là bit control, qubit thứ k là bit target ta thu được: 1 2 1 1 1 2 1 1... ... 1 2 1 1 ... ... 1 2 1 1 ... ... ... (1 ) ... k k k n k k