Đề tài Sơ đồ mạch lượng tử

1 Sơ đồ mạch lượng tử Tóm tắt công trình Vấn đề nghiên cứu các phương pháp tính toán lượng tử dựa trên các sơ đồ mạch lượng tử đóng vai trò ngày càng tăng khi trong tương lai gần, khả năng xây dựng được máy tính lượng tử công nghiệp trở thành hiện thực. Hiện nay các nước có nền kinh tế phát triển đã và đang hình thành nhiều trung tâm nghiên cứu phát triển các dự án về máy tính lượng tử, các thuật toán lượng tử dựa trên các mạch lượng tử,… Các ngành khoa học tính toán, đặc biệt là công nghệ thông tin sẽ có những bước chuyển nhảy vọt một khi ra đời các thế hệ máy tính lượng tử công nghiệp. Ở các nước không có tiềm lực kinh tế cao, thích hợp hơn cả để bắt kịp với các nghiên cứu cơ bản trong lĩnh vực này là phát triển các công cụ mô phỏng dựa trên hệ máy tính truyền thống để tìm hiểu, kiểm chứng và nghiên cứu các thuật toán, mạch lượng tử. Để đóng góp cho việc dây dựng bộ công cụ hỗ trợ của một trung tâm nghiên cứu khoa học về các thuật toán và mạch lượng tử, trong công trình này chúng tôi trình bày việc xây dựng một chương trình khép kín hỗ trợ việc thiết kế mạch lượng tử và thực thi chúng trên máy ảo là môi trường SQL Server. Về logic, chương trình được chia thành hai hệ thống nhỏ là hệ thống thiết kế mạch và hệ thống thực thi (mô phỏng) các mạch đó trên máy ảo. Hệ thống thiết kế mạch cung cấp những chức năng tiện lợi, dễ dàng cho người sử dụng trong việc thiết kế các mạch lượng tử như kéo, thả đồ họa trực quan, ... Hệ thống mô phỏng sử dụng môi trường SQL Server nhằm tận dụng khả năng tuyệt vời của nó về lưu trữ, xử lí dữ liệu, đặc biệt là khả năng xử lí thông tin theo nhóm rất phù hợp với bản chất của các cổng lượng tử. Hai hệ thống này giao tiếp với nhau thông qua ngôn ngữ được nhóm thiết kế dựa theo chuẩn XML. được gọi là QuML (Quantum Marked up Language). Ngôn ngữ này có tính cấu trúc cao, dễ hiểu đối với người sử dụng, dễ dàng mở rộng và đặc biệt là khả năng mô tả những mạch có cấu trúc phức tạp. Do tính độc lập logic cao giữa các thành phần trong thiết kế, chương trình có khả năng dễ dàng mở rộng để phát triển cho các môi trường tính toán song song, dữ liệu phân tán, hoặc có thể sử dụng hệ quản trị dữ liệu khác phù hợp cho các môi trường tính toán với khối lượng dữ liệu rất lớn như Oracle…,và các hệ thống tính toán chuyên dụng như: grid computing, PC – Cluster, …để tăng khả năng về tốc độ và qui mô mô phỏng. Bên cạnh đó tính đúng đắn của các thuật toán mô phỏng cũng được chứng minh chặt chẽ về mặt toán học trong công trình này. 2 Mục lục Tóm tắt công trình ..................................................................................................................... 1 Mục lục ...................................................................................................................................... 2 Chương 1. Tính toán lượng tử và vấn đề mô phỏng trên máy tính truyền thống .................. 3 1.1. Sơ bộ ............................................................................................................................................. 3 1.2. Hướng giải quyết ......................................................................................................................... 4 1.3. Các khái niệm cơ bản về mạch lượng tử và tính toán lượng tử .............................................. 5 1.4. Lựa chọn giải pháp cho Visual Quantum Studio (VQS) ......................................................... 8 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ử .................... 10 2.1. Ngôn ngữ SQL ........................................................................................................................... 10 2.2. Sự tương thích chặt chẽ giữa SQL và tính toán lượng tử...................................................... 10 2.3. Mô phỏng tính toán lượng tử bởi SQL Server ....................................................................... 11 2.4. Định lý cơ bản về tính đúng đắn của phép mô phỏng ........................................................... 12 2.5. Mô phỏng một số cổng lượng tử phổ dụng ............................................................................. 19 Chương 3. Ngôn ngữ QuML và kiến trúc hệ thống Visual Quantum Studio (VQS) ........... 21 3.1. Kiến trúc hệ thống Visual Quantum Studio ........................................................................... 21 3.2. Hệ thống giao diện đồ họa ........................................................................................................ 21 3.3. Ngôn ngữ mô tả mạch lượng tử QuML (Quantum Marked up Language) ........................ 22 3.4. Máy ảo thực hịên tính toán lượng tử bởi SQL Server ........................................................... 29 Kết luận chung ......................................................................................................................... 30 Tài liệu tham khảo ................................................................................................................... 31 Phụ lục. GIỚI THIỆU CHƯƠNG TRÌNH ............................................................................ 32 3 Chương 1. Tính toán lượng tử và vấn đề mô phỏng trên máy tính truyền thống 1.1. Sơ bộ Sự ra đời của máy tính điện tử giữa thế kỉ XX đã đánh dấu một bước ngoặt lớn trong sự phát triển của xã hội nói chung cũng như của khoa học tính toán nói riêng. Thế nhưng đã xuất hiện những vấn đề mà máy tính điện tử không thể giải quyết được với thời gian thực. Sự ra đời của vật lí lượng tử đầu thế kỉ XX đã tạo nên một cuộc cách mạng trong lĩnh vực vật lí. Từ những quan niệm về vật chất theo cơ học cổ điển Newton, chúng ta phải suy nghĩ theo những quan niệm hoàn toàn mới theo cơ học lượng tử. Khác với quan niệm một hạt tại một thời điểm bất kì luôn ở trong một trạng thái xác định, trong cơ học lượng tử, có những hạt mà tại một thời điểm có thể tồn tại ở hai hay nhiều trạng thái khác nhau, hứa hẹn khả năng biểu diễn thông tin khổng lồ. Hai nhà bác học, Benioff và Feynman, đã nhìn thấy trước qua vật lý lượng tử một mô hình tính toán mới, mà nền tảng của nó dựa hoàn toàn vào sự bí ẩn của cơ học lượng tử [5]. Mô hình đó gắn liền với một mô hình máy tính mới, đó là máy tính lượng tử. Mặc dầu cần phải trải qua thời gian nữa những chiếc máy tính lượng tử công nghiệp mới có thể ra đời, nhưng khả năng to lớn của nó đã được khẳng định. Với nền tảng của vật lý lượng tử, khả năng truyền thông tin trên cơ sở bit lượng tử, tốc độ tính toán nhanh kỳ lạ để phá các hệ mật nổi tiếng hiện đại như RSA, logarit rời rạc [13], tìm kiếm cơ sở dữ liệu không sắp xếp trước [6], khả năng chứa đựng thông tin cực lớn của cả một thư viện hiện đại trong một đĩa CD,... khiến nhiều chuyên gia dự báo sự ra đời của máy tính lượng tử công nghiệp trong vòng 20 năm tới sẽ như quả bom hạt nhân không chỉ trong lĩnh vực công nghệ thông tin mà trong toàn bộ các lĩnh vực của xã hội, mà hệ quả đầu tiên sẽ là sự sụp đổ của các hệ thống bảo mật hiện đại trên thế giới dùng hệ mã RSA như: hệ thống bảo mật thương mại điện tử, thư tín điện tử, các hệ thống bảo mật quốc gia,…Như vậy vấn đề lý thuyết bảo mật lượng tử cần được xúc tiến nghiên cứu ngay từ bây giờ. Chính vì tiềm năng to lớn của máy tính lượng tử, lý thuyết về tính toán lượng tử hiện nay đang được phát triển rộng khắp trên thế giới. Nhiều quốc gia phát triển đang ráo riết đầu tư cho dự án nghiên cứu chế tạo máy tính lượng tử và phát triển các thuật toán, mô hình tính toán (otomat lượng tử, máy Turing lượng tử..). Nhiều trung tâm nghiên cứu trên thế giới đã xuất hiện những labo nghiên cứu về lĩnh vực này với sự đầu tư lên tới hàng tỉ USD như tại IBM. Tháng 11 năm 2001, IBM đã công bố thí nghiệm thành công việc chế tạo máy tính lượng tử 7-qubit, điều đó chỉ ra rằng, việc chế tạo những chiếc máy tính lượng tử công nghiệp chỉ còn là vấn đề thời gian. Đối với nước ta, đứng trước một lĩnh vực đầy tiềm năng nhưng cũng đầy thách thức này, câu hỏi đặt ra là: chúng ta phải làm gì để bắt kịp với sự phát triển của thế giới? Rõ ràng chúng ta không thể chờ cho đến khi máy tính lượng tử công nghiệp ra đời bởi điều gì sẽ xảy ra khi những hệ thống bảo mật của quốc gia bị phá? Chính vì vậy việc đầu tư nhân lực và tiền của vào nghiên cứu máy tính lượng tử là không thể tránh khỏi, và công việc này diễn ra càng sớm càng tốt. Tuy nhiên việc đầu tư cho một dự án nghiên cứu chế tạo máy tính lượng là không thực tế trong hoàn cảnh nước ta bởi nó đòi hỏi rất nhiều tiền của, hơn nữa nền công nghệ và vật lý của nước ta còn nhiều hạn chế. Do đó hướng nghiên cứu chiến lược với nước ta sẽ là tập trung nghiên cứu các thuật toán lượng tử và các mô hình tính toán lượng tử. Để thực hiện được điều đó, việc xây dựng một chương trình mô phỏng tính toán lượng tử trên hệ máy tính truyền thống như là một bộ công cụ trợ giúp việc nghiên cứu các thuật toán lượng tử là điều thiết yếu. Với thực tế đó, nhóm chúng tôi đề xuất xây dựng một bộ công cụ mô phỏng làm hạt nhân cho việc hình thành một labo nghiên cứu về máy tính lượng tử ở Việt Nam theo một tiếp cận hoàn toàn mới. 4 1.2. Hướng giải quyết Hiện nay trên thế giới xuất hiện rất nhiều chương trình mô phỏng tính toán lượng tử như: labo của Kieu Tien Dung( Centre for atom optics and ultrafast spectroscopy, Swinburne University of Technology, Howthorn 3122, Australia), Gregory David Baker( Computer science at Macquaie University) với hướng tiếp cận dùng lập trình thủ tục, Bernhard Oemer( Department of Theoretical Physics Technical University of Vienna) với hướng tiếp cận dùng C/C++, chương trình jaQuzzi( www.physics.bufalo.edu/~phygons/jaQuzzi) với hướng tiếp cận dùng Java,… Trong nghiên cứu mô phỏng tính toán lượng tử có hai xu hướng chính: thứ nhất là viết các chương trình mô phỏng cho từng thuật toán cụ thể, thứ hai là nghiên cứu xây dựng một bộ công cụ cho phép thực thi một mạch bất kỳ. Rõ ràng hướng thứ nhất khó có thể phát triển được với qui mô lớn và tự động. Theo hướng thứ hai, mặc dầu có khả năng phát triển thành một bộ công cụ mạnh nhưng cần phải giải quyết một số vấn đề đặt ra mà những chương trình hiện nay trên thế giới chưa giải quyết được, đó là vấn đề bùng nổ dữ liệu theo hàm luỹ thừa với số qubit đầu vào - một bản chất của mô hình tính toán lượng tử, kèm theo đó là vấn đề kiểm soát và xử lý dữ liệu. Với C/C++, chúng ta sẽ mất nhiều công sức vào vấn đề tổ chức lưu trữ dữ liệu lớn và xây dựng một bộ công cụ với giao diện thân thiện hỗ trợ người dùng vì ngôn ngữ không hỗ trợ nhiều module đồ hoạ. Với Java, chúng ta không thể tối ưu được về mặt tốc độ, đặc biệt là khi phải xử lý với dữ liệu lớn. Với một số chương trình dùng Mathemetica hay Mathlab, việc kiểm soát dữ liệu là không chủ động vì nó phụ thuộc vào các nhà thiết kế Mathemetica, Mathlab và chưa có tương tác trợ giúp thiết kế ở mức giao diện đơn giản. Đứng trước thực tế đó, trong thời gian đầu nghiên cứu, câu hỏi lớn nhất mà nhóm cần trả lời được là: lựa chọn hướng tiếp cận nào cho phù hợp, khắc phục được những hạn chế của các chương trình đã có đồng thời hướng đến mục tiêu phát triển dài lâu cùng sự phát triển của máy tính lượng tử? Xuất phát từ thuật toán của Deutsch-Jozsa, đặc biệt là sau thuật toán nổi tiếng của Peter Shor [13] năm 1994, lý thuyết về thuật toán lượng tử phát triển ngày càng sâu và rộng, các hướng nghiên cứu mới liên tục xuất hiện. Ban đầu là mô hình tính toán lượng tử dựa trên các cổng và mạch lượng tử, sau đó xuất hiện các mô hình tính toán lượng tử mới như: Adiabetic Evolution, Quantum Radom Walks, hướng của Kieu Tien Dung nghiên cứu mô hình trên không gian Hilbert vô hạn chiều và phát triển các chương trình mô phỏng trên máy tính truyền thống. Tuy nhiên mô hình tính toán lượng tử trên các cổng và mạch lượng tử vẫn là mô hình tổng quát được nghiên cứu nhiều nhất và gần với hướng thiết kế máy tính lượng tử. Chính vì vậy, lựa chọn đầu tiên của nhóm là thực hiện mô phỏng tính toán lượng tử trên các cổng và mạch lượng tử mô phỏng cho phép người dùng dễ dàng thiết kế một mạch lượng tử bất kì một cách trực quan dựa trên máy tính truyền thống. Về tương lai lâu dài, chương trình sẽ phát triển mở rộng cho các tiếp cận tổng quát. Để giải quyết vấn đề tăng dữ liệu theo hàm luỹ thừa với số qubit đầu vào, nhóm đề xuất giải pháp tính toán bằng SQL trên các hệ quản trị cơ sở dữ liệu (tập trung hoặc phân tán). Ở công trình này chúng tôi lựa chọn SQL Server vì nó phù hợp với một labo nghiên cứu về tính toán lượng tử ở quy mô trung bình. Khi có nhu cầu mở rộng quy mô tính toán chương trình có thể dễ dàng chuyển đổi sang sử dụng các hệ quản trị dữ liệu khác như Oracle…. Đây là một giải pháp hoàn toàn mới, lí do của sự lựa chọn này là: + Thuận tiện cho việc lưu trữ và quản lý dữ liệu tăng theo hàm luỹ thừa với số qubit bởi việc lưu trữ bằng cơ sở dữ liệu đã được các hãng phần mềm lớn trên thế giới tối ưu. + Tạo khả năng áp dụng tính toán song song cổ điển vào mô phỏng nguyên lý song song lượng tử, bởi việc thực hiện tính toán trên môi trường song song là rất phù hợp khi dùng cơ sở dữ liệu. 5 + Giảm thiểu cho người lập trình khỏi vấn đề quản lý và kiểm soát dữ liệu. Cùng với giải pháp trên là một chương trình được xây dựng dựa vào các công nghệ hiện đại với kiến trúc 3 tầng: + Hệ thống giao diện đồ hoạ thân thiện hỗ trợ tối đa việc thiết kế mạch lượng tử bằng các thao tác kéo, thả quen thuộc. Nhờ đó có thể kiểm chứng và phát kiến các thuật toán lượng tử trong một thời gian kỉ lục nhờ phương pháp giao diện đồ hoạ kéo thả tương tự như các chương trình hỗ trợ thiết kế mạch điện tử cổ điển như Circuit Maker, Work Bend..., thay cho phương pháp tiếp cận truyền thống cho tới nay là mỗi lần muốn thử nghiệm một thuật toán mô phỏng, người ta phải viết lại chương trình từ đầu. + Hỗ trợ cho việc hiểu và thực thi cần có một ngôn ngữ trung gian. Ở đây chúng tôi xây dựng mới một ngôn ngữ mô tả mạch, đặt tên là QuML, đặc tả toàn bộ cấu trúc mạch lượng tử được thể hiện trên tầng giao diện, mọi sự thay đổi trên mạch hiển thị đều kèm theo sự thay đổi trong kịch bản tạo bởi QuML. + Mọi thao tác kéo thả từ tầng giao diện thông qua ngôn ngữ trung gian được truyền đạt tới tầng thực thi. Tầng chạy: thực thi các câu lệnh truy vấn SQL để mô phỏng các toán tử lượng tử cơ bản, trên môi trường SQL Server thông qua sự giao tiếp với kịch bản có trong tầng QuML. Nhờ kiến trúc 3 tầng, chương trình có thể phát triển được với qui mô rất lớn, sử dụng tổng hợp những công nghệ hiện đại nhất như: C#, XML, tính toán khoa học bằng phương pháp truy vấn SQL cùng những thuật toán mới hữu hiệu. Do nhu cầu và đặc điểm của nhóm nghiên cứu nên chương trình này thực hiện mô phỏng tính toán trên môi trường cụ thể là SQL Server. Với hướng tiếp cận trên, chúng tôi đã thực hiện được các công việc sau: + Tiếp cận được các khái niệm cơ bản của tính toán lượng tử và một số thuật toán quan trọng như: Deutsch-Josza, Peter Shor, Grover,…. + Cụ thể hoá các kiến thức thu được, từng bước thiết kế, hoàn thiện chương trình. Đến nay, nhóm đã xây dựng thành công phiên bản đầu tiên mô phỏng tính toán với các cổng cơ bản bằng các thao tác kéo, thả quen thuộc với những người dùng Window, cho phép nhanh chóng kiểm thử các thuật toán đã nêu với giao diện tạo mạch lượng tử thuận tiện. Từ những kết quả ban đầu cho thấy, mô phỏng thiết kế cho phép dễ dàng mở rộng và phát triển lâu dài phù hợp với yêu cầu của lĩnh vực tính toán lượng tử, đồng thời sản phẩm của nhóm hoàn toàn có thể đóng vai trò là bộ công cụ hỗ trợ tính toán mô phỏng cho một trung tâm khoa học nghiên cứu các thuật toán trên máy tính lượng tử với quy mô vừa và lớn. 1.3. Các khái niệm cơ bản về mạch lượng tử và tính toán lượng tử Dưới đây xin nhắc lại một số kiến thức cơ bản về tính toán lượng tử, về chi tiết người đọc có thể xem [1,3,4,5,8]. 1.3.1. Qubit Hạn chế của bit cổ điển: một bit có thể biểu diễn một trong hai trạng thái: 0 hoặc 1 (tại một thời điểm xác định). Do đó, n bit có thể biểu diễn 2n trạng thái khác nhau. Tuy nhiên, theo cách quan niệm cổ điển, nếu một thanh ghi được tạo nên từ n bit cổ điển, tại một thời điểm, nó chỉ có thể biểu diễn đúng một giá trị nguyên trong khoảng 0 → 2 1n − Theo quan niệm mới về qubit lượng tử dựa trên vật lý lượng tử, một thanh ghi có thể chứa được tổ hợp nhiều giá trị tại một thời điểm. Trước hết ta xét quan niệm mới về qubit - đơn vị biểu diễn thông tin cơ bản trong tính toán lượng tử. Xét không gian Hilbert 2 (trường cơ sở là ). Nó có cơ sở trực giao là (1, 0) và (0, 1), được ký hiệu tương ứng là 0 & 1 . 6 Định nghĩa 1.1: Một siêu trạng thái (trạng thái chồng chất – Superposition) trên 1-qubit được biểu diễn bởi một vectơ bất kì trong không gian Hilbert 2 có dạng 0 1α β+ với ,α β ∈ và thoả mãn luật phân bố xác suất 2 2 1α β+ = . Mô hình vật lý: 1-qubit có thể được biểu diễn bởi một hạt hai trạng thái, nó có thể là: spin hạt nhân trong phân tử, ion bị bẫy (trapped ions),... Như vậy sử dụng kí hiệu 0 và 1 ta có thể biểu diễn trạng thái của qubit, cũng giống như 0 và 1 biểu diễn trạng thái của bit cổ điển. Tuy nhiên, để có thể thực hiện tính toán phức tạp ta cần phải kết hợp những qubit ấy lại với nhau, tạo thành thanh ghi n-qubit (n-qubit register). 1.3.2. Thanh ghi n-qubit Một n-qubit biểu diễn 1 vectơ trong không gian Hilbert H là tích tenxơ của n lần 2 , vectơ này có dạng 0 100...0 00...1 ... 11...1 , 2 1 n NC C C N+ + + = - thoả mãn điều kiện: Ci ∈ 2 , Σ1≤ i ≤N | Ci|2 = 1, ở đó | i1i2..in 〉 = | i1 〉 ⊗ | i2 〉 ⊗..⊗ | in 〉, | ij 〉 ∈ 2 , j=1..,n. Định nghĩa 1.2: Thanh ghi lượng tử n-qubit là hình thức vật lý biểu diễn khả năng của n- qubit, cho phép đồng thời lưu một siêu trạng thái là tổ hợp tuyến tính của 2n véc tơ cơ sở dạng | i1i2..in 〉 thuộc H. 1.3.3. Nguyên lý rối lượng tử (entanglement) Ta xét ví dụ sau đây: ( ) ( )1 10 3 00 11 2 2 X = + = + Khi tiến hành đo một qubit, tùy theo kết quả của phép đo mà ta có ngay trạng thái của qubit còn lại. Tức là phép đo đã ảnh hưởng đến toàn bộ hệ thống: Nếu kết quả là 0 , trạng thái hệ thống còn lại là 0 Nếu kết quả là 1 , trạng thái hệ thống còn lại là 1 Suy ra: giữa hai hệ thống có mối quan hệ nào đó. Người ta gọi những trạng thái như vậy là trạng thái rối lượng tử (entanglement). Trạng thái này của qubit không thể phân tích thành tích tenxơ của hai hệ thống con. 1.3.4. Nguyên lý song song lượng tử Thanh ghi lượng tử cùng một lúc có thể lưu trữ rất nhiều trạng thái đơn lẻ khác nhau, nhưng có một đặc điểm đáng chú ý đó là: bất kì một phép tác động nào lên một thanh ghi lượng tử cũng sẽ tác động đồng bộ lên các trạng thái mà thanh ghi đó lưu trữ (ta không thể tách rời các trạng thái để thao tác trên chúng một cách riêng lẻ). 1.3.5. Mạch và cổng lượng tử, cổng lượng tử phổ dụng Tính toán cổ điển được tạo nên bởi quá trình xử lý, biến đổi bit cổ điển. Đơn vị xử lý bit được gọi là cổng logic. Bộ vi xử lý được tạo nên từ hàng triệu các cổng như vậy. Ta không cần đi vào thiết kế bên trong của cổng mà chỉ cần biết sự tương ứng của các đầu ra với các đầu vào. 7 Trong trường hợp lượng tử, đơn vị xử lý qubit được gọi là cổng lượng tử. Tác động của chúng lên qubit cũng giống như tác động của cổng logic thông thường lên bit. Trong vật lý lượng tử, các phép biến đổi đều phải là các toán tử Unita. Do đó trong mô hình toán học, chúng ta cũng phải dùng những toán tử Unita. Định nghĩa 1.3: Một cổng logic lượng tử n-qubit biến đổi n-qubit được biểu diễn về mặt toán học bởi một phép biến đổi Unita tác động lên vectơ siêu trạng thái của n-qubit đó. Ví dụ: Cổng HADAMARD: Dạng ma trận: ( ) ( ) 1 1/ 2 1/ 2 2 11/ 2 1/ 2 2 H α βα α β β α β ⎛ ⎞+⎜ ⎟⎛ ⎞⎛ ⎞ ⎛ ⎞ ⎜ ⎟⎯⎯→ =⎜ ⎟⎜ ⎟ ⎜ ⎟⎜ ⎟ ⎜ ⎟−⎝ ⎠ ⎝ ⎠⎝ ⎠ −⎜ ⎟⎝ ⎠ Dạng vectơ: ( ) ( )1 10 1 0 1 2 2 + ⎯⎯→ + + − +Hα β α β α β Ta thấy rằng, khi tác động cổng Hadamard lên thanh ghi 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 k ni i i i i i k k k n i i i i i i k k k n c i i i i i i c i i i i i i− + − +− + − +→ − nếu ti =1 1 2 1 1 1 2 1 1... ... 1 2 1 1 ... ... 1 2 1 1 ... ... ... ... k k k n k k k ni i i i i i k k k n i i i i i i k k k n c i i i i i i c i i i i i i− + − +− + − +→ nếu ti =0 Mô phỏng bằng SQL: Update @table set qk=1-qk where qt=1 Nhận xét: Vai trò của định lý cơ bản có ý nghĩa thực tiễn lớn vì các cổng phổ dụng cơ bản được biểu diễn sang câu lệnh SQL đưa vào dưới dạng biên dịch sẵn (Stored Procedure) giúp tăng tốc quá trình tính toán mô phỏng trên môi trường dữ liệu lớn hướng mạng, song song, phân tán. 21 Chương 3. Ngôn ngữ QuML và kiến trúc hệ thống Visual Quantum Studio (VQS) Phần này dành cho việc trình bày về kiến trúc 3 tầng của sản phẩm, trong đó sẽ tập trung vào ngôn ngữ mô tả mạch lượng tử dựa trên chuẩn XML do chúng tôi thiết kế, được đặt tên là QuML. 3.1. Kiến trúc hệ thống Visual Quantum Studio Hệ thống VQS được chia thành 2 hệ thống con và gồm 3 tầng: + Hệ thống giao diện đồ hoạ thân thiện hỗ trợ tối đa việc thiết kế mạch lượng tử + Hệ thống máy ảo thực thi các câu lệnh lượng tử cơ bản: máy ảo cục bộ và máy ảo trên SQL Server, ... Hai hệ thống này trao đổi thông tin về mạch lượng tử thông qua một ngôn ngữ có cấu trúc là QuML. Kiến trúc này sẽ tạo ra sự thuận lợi trong việc phát triển độc lập các thành phần trong hệ thống. Việc tối ưu hoá từng thành phần có thể thực hiện độc lập mà không liên quan tới các thành phần khác. Với các giao diện được chuẩn hoá giữa các thành phần trong hệ thống giúp cho việc bảo trì, phát triển được dễ dàng. 3.2. Hệ thống giao diện đồ họa 3.2.1. Những đối tượng cơ bản của giao diện đồ họa trong hệ thống VQS Sơ đồ quản lý các đối tượng đồ họa: QuCircuit (mạch) QuRegister (thanh ghi) QuBit (bit) Operator Observer QuGate Implement Oracle 22 3.2.2. Qubit Thuộc tính : - Name - Text - Alpha - Beta - Status observer Phương thức : - Đổi tên, đổi text - Thiết lập giá trị Alpha, Beta. - Chọn, xoá 3.2.3. QuRegister Thuộc tính : - Name - Text - Danh sách QuBit - Circuit chứa nó - Inside / Outside Phương thức : - Đổi tên, đổi text - Đổi kiểu Inside Outside - Xoá, thêm bit 3.2.4. Operator Thuộc tính : - Name - Text - Danh sách QuBit - Linkbits - State Phương thức: - Đổi tên, đổi text. - Đổi kiểu nội dung Linkbit. - Xoá, sửa. 3.3. Ngôn ngữ mô tả mạch lượng tử QuML (Quantum Marked up Language) 3.3.1. Giới thiệu về XML XML là một đề xuất của tổ chức World Wide Web Consortium (W3C), một nhóm đa công ty đã định nghĩa XHTML và tiền thân của ngôn ngữ này là HTML. XML là một phương tiện mang các dữ liệu khả dụng tới máy tính cá nhân và là một định dạng dữ liệu tổng quát – nó cung cấp những thẻ đánh dấu cần thiết. Vì mã nguồn của các ngôn ngữ được định dạng trong XML giống như HTML, nên so sánh hai ngôn ngữ này là rất hữu ích. XML bao gồm các trường được lồng nhau theo kiểu phả hệ giống như HTML, nó cũng rất dễ đọc, và dễ chuyển đổi. Tuy nhiên, nếu HTML chứa các tiêu đề, đầu đề, và các định dạng hiển thị kí tự, ... thì XML có thể chứa khách hàng, số hoá đơn, giá cả, hay bất kì một yếu tố thông tin nào mà ta cần. XML là hoàn toàn mở do đó ta có thể bổ sung những thẻ mới và những yếu tố mới để hỗ trợ cho ứng dụng… (xem thêm [15]). Hạt nhân của XML 23 Thông tin có cấu trúc bao gồm cả nội dung (từ ngữ, hình ảnh, ...) và một gợi ý về chức năng của nội dung đó. Ví dụ, nội dung trong một phần tiêu đề có một ý nghĩa khác với nội dung trong một chú thích, và cũng khác với nội dung trong một ghi chú hình vẽ hay một bảng trong cơ sở dữ liệu. Đặc tả XML định nghĩa một phương thức chuẩn để cấu trúc các phần đánh dấu của các tài liệu. Lý do sử dụng XML Các lập trình viên tạo ra XML để những tài liệu có cấu trúc chặt chẽ có thể được sử dụng trên Web. Những ngôn ngữ có thể làm được điều này, HTML và SGML (Standard Generalized Markup Language), lại không thực tế cho mục đích này. HTML thì bị giới hạn bởi một tập các ngữ nghĩa và không cung cấp một cấu trúc bất kì. SGML thì cung cấp một cấu trúc bất kì, nhưng việc cài đặt SGML lại quá khó đối với một trình duyệt Web. XML không định nghĩa các ngữ nghĩa cũng như không định nghĩa một tập các thẻ. Nó là một siêu ngôn ngữ (metalanguage) để mô tả các ngôn ngữ đánh dấu và cung cấp một cơ sở cho việc định nghĩa các thẻ và quan hệ cấu trúc giữa chúng. Vì vậy không có một tập các thẻ định nghĩa sẵn, cũng không có một ngữ nghĩa tiền định nào trong XML. Ngữ nghĩa của một tài liệu XML sẽ được định nghĩa hoặc bởi các chương trình xử lí chúng hoặc bởi các kiểu dạng mẫu (style sheet). Do vậy chúng tôi lựa chọn XML làm ngôn ngữ để xây dựng nên QuML. 3.3.2. Những yêu cầu đối với ngôn ngữ QuML. + Ngôn ngữ này phải mô tả được cấu trúc của các mạch tuần tự nhiều qubit. + Mô tả các cổng phức hợp và mô tả được sự lắp các cổng đó vào mạch nhiều qubit. + Có khả năng mô tả việc bổ sung thêm các qubit vào mạch. + Mô tả các phép đo. + Mô tả các qubit theo tập hợp các thanh ghi. + Mô tả giao diện riêng của từng loại cổng phức hợp. + Có khả năng cho phép khai báo những kiểu cổng phức hợp mới dựa trên các cổng có sẵn (built in) và các cổng phức hợp tự tạo khác. + Tất cả các tài liệu đều bắt đầu bằng thẻ 3.3.3 Những đối tượng cần mô tả của ngôn ngữ QuCircuit, QuRegister, QuBit, QuGate, QuObserver, ... 3.3.4 Các khai báo cho các đối tượng này a. QuSpace Không gian tên lượng tử, trong không gian tên lượng tử ta có thể định nghĩa các cổng hoặc các không gian tên lượng tử cấp thấp của nó. Cấu trúc của các không gian tên: NameSpace1.NameSpace2.... Khai báo không gian tên lượng tử có thể là khai báo tuyệt đối hoặc khai báo tuần tự. VD: b. QuCircuit Tạo ra một mạch lượng tử để tính toán Lệnh: 24 Mặc định là các qubit trong một mạch lượng tử là Outside. Nhưng vẫn cho phép là có các giá trị khởi đầu. Trong phần giao diện thì các thanh ghi Outside sẽ được đặt ở thứ tự đứng trước. Sau đó là tới các thanh ghi Inside. Không nên đặt xen kẽ. Có thể là thanh ghi Outside để sau nhưng khi biên dịch thì trình dịch sẽ tự động chuyển chúng lên đầu. Tất nhiên là không ảnh hưởng gì vì ta tham chiếu cục bộ thông qua tên và ID của qubit. c. GateType Tạo một cổng phức, là tổ hợp của các cổng khác, có thể là cổng cơ bản hoặc các cổng phức khác. d. QuRegister Tạo ra một thanh ghi lượng tử để đưa vào hệ thống Lệnh: Các lệnh tạo thanh ghi chỉ được phép xuất hiện trong phần giao diện (để đơn giản cho việc xử lí). e. QuBit Tạo ra một qubit để đưa vào hệ thống trong bối cảnh một thanh ghi, tức là những lệnh này chỉ được chấp nhận khi nó nằm trong một cấu trúc thanh ghi. Lệnh: <QuBit Text=”Tên của qubit” Name=”Tên tham chiếu thanh ghi (nên để ở dạng số)” Alpha=”complex” Beta=”complex” /> Tên của QuBit phải viết liền. f. QuGate Tạo ra một cổng theo kiểu đã được định danh Lệnh tổng quát để tạo một cổng phức danh sách các bit cục bộ của thanh ghi đó Tên thanh ghi trong LinkedBits là tên thanh ghi trong bối cảnh cục bộ của hệ thống hoặc component. Sự nối này theo thứ tự nào? Theo thứ tự được khai báo trong phần interface. Bit nào được khai báo trước thì có thứ tự cục bộ ở trước. Khi kết nối thì SystemID của mapped bit sẽ được chuyển vào các lệnh thực hiện. g. Observer Tạo ra một quan sát một qubit hoặc nhiều qubit trong hệ thống. Lệnh để tạo một phép đo: danh sách các bit cục bộ của thanh ghi đó Tên của mỗi phép đo yêu cầu phải là duy nhất trong bối cảnh cục bộ. Mô tả cấu trúc một câu lệnh khai báo kiểu cổng phức hợp với các kiểu cổng cơ bản được chấp nhận là: NOT, CNOT, HADAMAR, TOFFOLI, CPSHIFT (controlled phase shift),… dựa trên kết quả nghiên cứu tập cổng phổ dụng và các cổng hay sử dụng trong các thuật toán lượng tử. 25 Các thông số cho những cổng cơ bản: được khai báo kèm với thẻ QuGate như một thuộc tính của thẻ. Ví dụ: Cổng CPSHIFT cần thêm thông số về góc quay Phase Những ví dụ mạch cơ bản. Ví dụ 1: Mạch không có các component phức, không có QuReg cục bộ Mạch cộng hai số hai bit: AB + CD = EFG 1, 3 1 1, 3 3 2 1, 3 0, 2 0 A B C D 0 0 0 A B C D E F G : TOFFOLI : CNOT 26 0, 2 2 1, 0 2 1 0, 2 0, 1, 2, 3 0, 1, 2 Ví dụ 2: Mạch có sử dụng oracle ( )fx y x y f x⎯⎯→ ⊕ Mạch có sử dụng oracle đóng vai trò quan trọng trong các thuật toán lượng tử, nó làm cho các thuật toán lượng tử trở lên uyển truyển hơn rất nhiều. Để xây dựng các cổng oracle thuận tiện cho người dùng, chương trình có sử dụng bộ phân tích biểu thức số học được biểu diễn dưới dạng cấu trúc dữ liệu cây nhị phân. Ví dụ mạch mô tả thuật toán Deutch-Joza: x x y y⊕ f(x) f 27 0 1 0, 1 0 1 0 0, 1 Các bước phân tích mạch: Đầu tiên xây dựng cấu trúc các không gian tên và các định nghĩa cổng tương ứng. Với các file .quml, ta cung cấp các thẻ <UsingQuSpace Name=”Tên của QuSpace sử dụng”>. Sau đó khi biên dịch ta sẽ chuyển các thẻ cục bộ đó sang các tên của không gian tên tuyệt đối của nó. Khi đặt các đối tượng đồ hoạ trực quan vào hệ thống thì ta sử dụng không gian tên tuyệt đối để mô tả nó. Trong các file .quml chỉ cho phép một thẻ mà thôi và đó điểm khởi đầu của mạch. Trong các file chứa component ta có thể cho resource là ảnh bitmap. Ngoài ra việc dụng thêm các thẻ bổ trợ giúp thuận tiện cho ứng dụng. Như cấu trúc của file project nhằm lưu trữ thông tin về một project. <Referrence Name=’ Tên component” AssemblyName=” tên file chứa component đó” HintPath=” đường dẫn mặc định” /> //Sau này có thể cho phép include cả những file resource Xử lí các file .quproj: + Phân tích các thông tin để liên kết các file ref và các file mạch nguồn. 28 + Xây dựng cấu trúc không gian tên trong bộ nhớ kèm theo các đối tượng cổng (là các lá trong cây đó). Mỗi lá nên có kiểu của nó. Trong mỗi lá là một đối tượng cổng sẽ chứa thông tin về giao diện bên ngoài của đối tượng đó, những thuộc tính bên ngoài của nó, nhằm tạo thuận lợi cho việc tạo giao diện. + Những kiến trúc bên trong chỉ cho phép thể hiện khi mô phỏng (debug khi mô phỏng). Cấu trúc của file .qugate nên chứa các thông tin thuận lợi cho quá trình biên dịch sao cho tận dụng được tính chất là đã biên dịch một lần rồi. Chẳng hạn các thông tin về không gian tên chẳng hạn. 29 Cấu trúc của file qugate a. Phần thông tin thu được sau quá trình biên dịch. Thông tin về các file tham chiếu: đặt trong thẻ Khi biên dịch, hoặc ngay khi bổ sung(add) một referrence vào project thì hệ thống sẽ phải tìm tới các file này trước. Tìm trong local hoặc tìm trong HintPath. Chứa trong thẻ: Gồm các thông tin về các loại cổng được phép hiển thị trong toolbox (những cổng dạng public) đi kèm là không gian tên của nó. Giao diện Outside của nó. (Phần này bắt buộc phải có, nếu không có thì phải báo lỗi) b. Nội dung đã biên dịch. Các thông tin đầy đủ về một cổng. Giao diện trong, ngoài; Kiến trúc... Chứa các thẻ đầy đủ, Kiểu phải là kiểu có tham chiếu không gian tên tuyệt đối (chứ không phải là không gian tên tương đối). Khi ta import một file .qugate vào hệ thống toolbox, nó sẽ cho phép ta tham chiếu được tất cả các loại cổng khai báo trong file đó. Tất nhiên là nếu ta check vào đó. Còn nếu không thì ta loại bỏ. Các thông tin đó cần được lưu trữ trong một file cấu hình của chương trình. Chẳng hạn là file Toolbox.config.xml --> Phải có hộp thoại cho phép cấu hình Toolbox. Nhận xét: Những tính năng về không gian tên lượng tử, project mạch lượng tử là những tính năng có tính mở rất cao của hệ thống. Nó cho phép mô tả những hệ thống lớn, phức tạp và uyển chuyển. 3.4. Máy ảo thực hịên tính toán lượng tử bởi SQL Server Được xây dựng trên Stored Procedure, máy ảo này cung cấp tất cả các thủ tục cho phép hệ thống dùng để thực hiên các cổng lượng tử cơ bản và phéo đo. Nhờ sử dụng môi trường cơ sở dữ liệu và những điểm mạnh của SQL Server nên các Stored Procedure thực hiện các tính toán với tốc độ rất nhanh và có khả năng thực hiện với dữ liệu lớn. Nhờ sử dụng phương pháp này, chúng tôi đã giải quyết được vấn đề rất cơ bản trong lập trình là kiểm soát dữ liệu lớn với độ an toàn cao. 30 Kết luận chung + Với những mục tiêu đã đặt ra, VQS thực sự trở thành một bộ công cụ hữu ích phục vụ cho việc nghiên cứu, giảng dạy và học tập về lĩnh vực tính toán lượng tử, đóng vai trò là công cụ đắc lực để trợ giúp cho việc hoạt động một labo nghiên cứu về máy tính lượng tử trong các viện khoa học, các trường đại học ở Việt Nam. + Do được thiết kế mở, VQS sẽ được hoàn thiện từng bước trong tương lai để thích hợp cho việc nghiên cứu nhiều hướng khác nhau của tính toán lượng tử. + Thời gian tới, nhóm sẽ tiếp tục hoàn thiện chương trình với nhiều tính năng mới, thực hiện khả tính toán trên môi trường song song cho VQS (chỉ cần thay đổi hệ quản trị CSDL thích hợp chẳng hạn Oracle,…), đồng thời tiếp tục nghiên cứu lý thuyết, sử dụng VQS để tìm tòi các thuật toán mới. + Tài liệu kỹ thuật này cũng sẽ hữu ích cho những nhóm khoa học, đặc biệt là sinh viên ngành toán tin khi quan tâm đến các ứng dụng công nghệ của SQL trong những lĩnh vực hoàn toàn mới của tính toán khoa học ngoài những mục đích quản lý cơ sở dữ liệu truyền thống, gợi ý khả năng tăng cường sức mạnh của SQL cho các mục tiêu mới của khoa học tính toán. 31 31 Tài liệu tham khảo 1. D.Aharonov, Quantum Computation, arXiv: quant-Ph/9810237, 12/1998. 2. Phan Hoàng Anh, Ứng dụng phương pháp truy vấn dữ liệu trong tính toán khoa học, công trình nghiên cứu khoa học khoa Toán Tin ứng dụng, trường ĐHBKHN, 2001 (giải nhì bộ, nhì VIFOTEC). 3. A.Barenco, C.H.Bennett, R.Cleve, D.P.D.Divicenzo, N.Margolus, P.W.Shor, T.Sleator, J.Smolin, H.Weinffurter, Elementary Gates For Quantum Computation, arXiv: quant-Ph/950316, 3/1995. 4. A. Ekert, P. Hayden, H. Inamori, Basic Concepts In Quantum Computation, 11/2000, arXiv: quant-ph/0011013. 5. R. Feynman, Quantum Mechanical Computers, Foundations of Physics, 16, No.6. March 1985. 6. L. Grover, A Fast Quantum Mechanical Algorithm For Database Search, Proceedings, STOC 1996. 7. Phạm Hữu Khang, Kỹ thuật lập trình ứng dụng C#. Net toàn tập, tập 1, 2, 3, NXB Lao Động - Xã Hội, 2000. 8. A. Yu. Kitaev, A.H. Shen, M.N. Vyalyi, Classical And Quantum Computation, Graduate Studies in Mathematics volume 47. 9. Damian P. Menscher, Modeling The Quantum Computer On The Classical Computer, 8/1997, PhD program in physics. Univ. Illinois. Honor Thesis. 10. K.Obenland, A. Despain, Simulation Of Factoring On a Quantum Computer Architecture, Proc. of physics of Compitation 1996. 11. Dương Thế Quang, Ngôn ngữ của các hệ quản trị cơ sở dữ liệu- S.Q.L.-Structred Query Language, NXB Thống Kê, Hà Nội 1995. 12. B.V.Sabat, Giải tích phức, NXB Đại Học Và Trung Học Chuyên Nghiệp, 1974. 13. Peter W. Shor, Polynomial-Time Algorithms For Prime Dacotrization And Disrete Logarithms On a Quantum Computer, arXiv: quant-ph/ 050802 v2 25 Jan 1996. 14. Lại Đức Thịnh, Bài giảng số học, NXB Giáo Dục, 1970. 15. R.Allen Wyke, Sultan Renman, Brad Leupen, XML Programming, Microsoft Press, 2002. 32 32 Phụ lục. GIỚI THIỆU CHƯƠNG TRÌNH 4.1. Tổng quan + Phần mềm được xây dựng nhằm mô phỏng mạch lượng tử có khả năng thực thi nhằm trợ giúp nghiên cứu các thuật toán lượng tử trên nền máy tính truyền thống hiện có. Bước đầu phần mềm này cung cấp những đối tượng cơ bản của lý thuyết tính toán lượng tử như : thanh ghi lượng tử, qubit, các cổng cơ bản ... Đồng thời, chương trình với giao diện thân thiện cho phép người dùng dễ dàng thiết kế một mạch bất kỳ với những thao tác kéo thả rất quen thuộc. + Phần mềm được thiết kế dưới sự phân tích kỹ lưỡng về sự tương thích giữa những khái niệm lý thuyết và sức mạnh của những công cụ hiện có như : ngôn ngữ lập trình Visual C#, hệ quản trị cơ sở dữ liệu SQL Server 2000, ngôn ngữ định dạng mở rộng XML . + Phần mềm là một nỗ lực của nhóm nhằm phục vụ mục đích lâu dài nên chúng tôi thực hiện thiết kế theo hướng mở, do đó sẽ dễ dàng được mở rộng cho các công cụ mới sau này. + Chúng tôi đang và sẽ tiếp tục nâng cấp để ở những phiên bản sau, sản phẩm có khả năng trợ giúp nhiều tính năng như: đóng gói một cổng phức hợp do người dùng xây dựng, thiết kế một mạch mới từ những mạch đã có. + Xây dựng tài liệu đóng gói để có thể bàn giao, tạo cơ sở cho ứng dụng tính toán của một labo về tính toán lượng tử có qui mô. 4.2. Chức năng chính + Người dùng có thể sử dụng những công cụ đã được cung cấp sẵn trên ToolBox để xây dựng mạch theo ý muốn bằng những thao tác kéo, thả quen thuộc và điền thông tin đầu vào thông qua những DialogBox. + Toàn bộ quá trình làm việc trên một mạch được quản lý bởi một đối tượng mạch. Trên nền đối tượng đó ta mới đi xây dựng những thành phần cơ bản như: thanh ghi, qubit, cổng ... + Song song với quá trình xây dựng mạch qua các đối tượng đồ hoạ chương trình có 2 chức năng: - Người dùng có thể ghi lại nội dung cấu trúc mạch dưới định dạng file *.xml sau khi xây dựng mạch xong mà sau này chính chương trình có thể sử dụng những file này để dựng lại mạch, theo nội dung file. - Những thông tin về khởi tạo mạch sẽ được đọc từ file *.xml để truyền vào CSDL. Sau đó những thủ tục được xây dựng trong SQL sẽ đảm nhận vai trò xử lý tính toán, biến đổi và cập nhật trạng thái. + Quá trình thực thi mô phỏng trên máy ảo có thể được thực hiện ở 2 chế độ: - Thực thi bởi bộ nhớ trong Tools -> Options -> Memory Virtual Machine - Thực thi trên SQL Serverr : Tools -> Options -> SQL Server Virtual Machine. + Theo dõi kết quả thực hiện: Sau khi thực hiện mô phỏng ta có thể xem các kết quả bằng cách đọc dữ liệu từ cơ sở dữ liệu để thấy được tác động và hiệu quả của mạch mà ta đã xây dựng thông qua các phép đo qubit. + Có chức năng cho phép người dùng tạo, sử dụng và sử dụng lại các cổng Oracle: sử dụng các cổng Oracle là một phương pháp mang lại nhiều sức mạnh cho các thuật toán lượng tử. Chính vì vậy để tận dụng được điểm mạnh này vào trong các mạnh lượng tử, công trình tập trung xây dựng nhìêu tính năng hỗ trợ các 33 33 cổng Oracle. VQS cho phép người dùng tự tạo một Oracle bất kì ứng với một hàm xác đinh, hỗ trợ phương pháp nhập hàm theo biểu thức nhờ bộ phân tích biểu thức số học được biểu diễn dưới dạng cấu trúc dữ liệu cây nhị phân. 4.3. Tương tác giao diện + Muốn mở một Project mới để thực hiện : Chọn File->New->Project ->Nhập tên Project mới. Nhấn Tab BasicGate, nó sẽ cho ta thấy những công cụ đã được cung cấp. Từ đây ta có thể tuỳ chọn: thanh ghi, qubit, các cổng cơ bản... theo yêu cầu của mình bằng thao tác kéo và thả quen thuộc từ ToolBox xuống vùng Client của ta. Kết thúc thiết kế, nếu ta muốn ghi lại nội dung: chọn File -> Save All thì toàn bộ cấu trúc mạch đó sẽ được lưu lại dưới file cùng tên với Project của ta. + Muốn dựng lại một mạch từ file đã có sẵn (chẳng hạn file ta vừa tạo ra và ghi lại ở trên ), thực hiện: Chọn File->Open->Project. Sau đó chọn tên file mà ta muốn mở. Nhấn GateType trong cửa sổ Project Explorer. Nhấn vào dấu “+” trong cửa sổ Project Explorer đến tên file cuối cùng thì nhấp đúp vào biểu tượng ấy ta sẽ có mạch mô phỏng lại. 4.4. Sau đây là một số hình ảnh về chương trình (xem trang bên) 34 34 a. Giao diện chính của chương trình: (hình 1) Hình 1 b. Tạo một mạch mới:( hình 2) Hình 2 Kéo thả các cổng cơ bản vào mạch, thiết lập các thông số cho các cổng đó (hình 3) 35 35 Hình 3 c. Mở một mạch đã có (Mạch cộng 2 qubit) (hình 4) Hình 4 d. Mô phỏng với máy ảo SQL Server: thiết lập cấu hình máy ảo SQL Server Chọn menu Simulation/Simulate (Ctrl F5) (hình 5) 36 36 Hình 5 Kết quả mô phỏng (hình 6) Hình 6