1
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ư
2
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ả

cơ sở dữ liệu.

3
+ 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


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
.

4
Đị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
01
α β
+
với
,
α β
∈

N
CC C N+++ =-

thoả mãn điều kiện: C
i
∈
2

,
Σ
1≤ i ≤N
| C
i
|
2
= 1,
ở đó | i
1
i
2
..i
n
〉 = | i
1
〉 ⊗ | i
2
〉 ⊗..⊗ | i
n
〉, | i
j

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.

5
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

α β
⎛⎞
+
⎜⎟
⎛⎞
⎛⎞ ⎛⎞
⎜⎟
⎯⎯→ =
⎜⎟
⎜⎟ ⎜⎟
⎜⎟
⎜⎟
−
⎝⎠ ⎝⎠
⎝⎠
−
⎜⎟
⎝⎠Dạng vectơ:

() ()
11
01 0 1
22
+⎯⎯→ + +−+
H
α β αβ αβ



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 S
0
, S
1
với S
a
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
21
12
0
n
in
i
SCiii
−
=
=
∑
K
thì phép đo trên qubit đầu sẽ cho ra kết quả 0 với xác suất
23
23
2
0
,, ,

()
2
2
012
,,
1
0
Pr 0
n
n
ii n
ii
Ciii
ob
∑
K
K
K()
2
2
112
,,
1
1
Pr 1
n
n

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
2
n
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

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.

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.

0
22 2
H
æöæö
÷÷
çç
æö
÷÷
çç
÷
ç
÷÷
çç
÷
ç
÷÷
÷
çç
÷÷
ç
÷
===+
çç
÷÷
ç
÷
çç
÷÷
ç
÷

11 1
22
1
22 2
H
æöæö
÷÷
çç
æö
÷÷
çç
÷
ç
÷÷
çç
÷
ç
÷÷
÷
çç
÷÷
ç
÷
===-
çç
÷÷
ç
÷
çç
÷÷

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:

01
00...0 00...1 ... 11...1 , 2 1
n
N
CC C N+++ =−

Ta sẽ mô phỏng trạng thái trên bằng bảng quan hệ
Superposition

0
1
Im 2C
1
Re 2C
%

1
-
1
Im 2C
1
Re 2C

q1 Im Re
0
10
(Im Im ) 2CC+

10
(Re Re ) 2CC+
1
01
(Im Im ) 2CC−

01
(Re Re ) 2CC−

q1 q2 … qn Im Re
0 0 … 0

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:
01 0 0 11
0 1 ... (Im Re ) 0 (Im Re ) 1
... (Im Re )
N
NN
CC CN CiC CC
CCN
+++ = + + + +
++(trong đó
21
n
N =-

)
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.

đượ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 ,
33
UW

và phép đo
.

i)
Cổng
3
U control1

control2 target

Trong đó:
cos(2 ) sin(2 )
sin(2 ) cos(2 )
U
παπα
παπα
⎛⎞
=

CC
CC
CC
πα πα
πα πα
πα πα
παπα
⎛⎞
⎛⎞
⎛⎞ ⎛⎞
⎜⎟
⎜⎟
⎜⎟ ⎜⎟
⎜⎟
⎜⎟
⎜⎟ ⎜⎟
⎜⎟
⎜⎟
⎯⎯→=
⎜⎟ ⎜⎟
⎜⎟
⎜⎟
+
⎜⎟ ⎜⎟
⎜⎟
⎜⎟
⎝⎠ ⎝⎠
⎜⎟
⎜⎟
−

πα
,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
3
W


ReC

q1 q2 q3 Im Re
0 0 0
0
Im C
0
ReC
... ... ... ... ...
1 1 0
67
Im cos(2 ) Im sin(2 )CC
παπα
+

67
Re cos(2 ) Re sin(2 )CC
παπα
+
1 1 1
67
Im sin(2 ) Im (2 )CCcos
παπα
−+

67
Re sin(2 ) Re (2 )CCcos
παπα
− +


i
e
i
e
C
CC
CC
C
πα
πα
⎛⎞
⎛⎞
⎛⎞ ⎛⎞
⎜⎟
⎜⎟
⎜⎟ ⎜⎟
⎜⎟
⎜⎟
⎜⎟ ⎜⎟
⎜⎟
⎯⎯⎯→=
⎜⎟
⎜⎟ ⎜⎟
⎜⎟
⎜⎟
⎜⎟ ⎜⎟
⎜⎟
⎜⎟
⎜⎟ ⎜⎟
⎜⎟


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 ) Imsin(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 ,
33
UW . Tập
{}
,
33
UW
là trù mật trong nhóm các
ma trận unita 8x8.
{}
,UW

Im C

0
ReC

... ... ... ... ...
1 1 0
6
Im C
6
ReC
1 1 1
7
Im C

7
ReC

q1 q2 q3 Im Re
0 0 0
0
Im C
0
ReC
... ... ... ... ...
1 1 0
6
Im C

6

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:
01
00...0 00...1 ... 11...1 , 2 1
n
N
CC C N+++ =−
.
Hệ thống gồm n qubit.
Reg2:


Dưới dạng bảng, Reg1 là

Reg2 là
a b c Im Re
0 0 0
0
Im C
0
ReC
... ... ... ... ...
1 1 0
6
Im C
6
ReC
1 1 1
7
Im C
7
ReC
a b c Im Re
0 0 0
0
Im C
0
ReC
... ... ... ... ...
1 1 1
6