1

LỜI CẢM ƠN
Trước hết, tôi xin bày tỏ lòng biết ơn sâu sắc đến TS. Trần Thái Hoa,
người đã tận tình chỉ dạy, cung cấp cho tôi những kiến thức nền tảng, trực tiếp
để tôi hoàn thành bài luận văn này. Thầy cũng là người đã giúp tôi ngày càng
tiếp cận và có niềm say mê khoa học trong suốt thời gian được làm việc cùng
thầy.
Tôi xin bày tỏ lòng biết ơn tới các thầy, các cô ở phòng Sau Đại Học,
trong Khoa Vật Lý Trường Đại học sư phạm Hà Nội 2 và các Giáo sư, Tiến sĩ
đã trực tiếp giảng dạy, truyền đạt cho tôi những kiến thức quí báu về chuyên
môn cũng như kinh nghiệm nghiên cứu khoa học trong thời gian qua.
Cuối cùng, tôi xin chân thành gửi lời cảm ơn đến những người thân
trong gia đình, bạn bè đã luôn giúp đỡ, động viên và tạo mọi điều kiện cho tôi
trong suốt quá trình học tập và hoàn thiện luận văn này.
Hà Nội, tháng 10 năm 2010

Nguyễn Minh Vương


2

LỜI CAM ĐOAN
Tên tôi là : Nguyễn Minh Vương, học viên cao học khóa 2008 – 2010,
chuyên nghành Vật lý lý thuyết và vật lý toán – Trường Đại học Sư phạm Hà
Nội 2.
Tôi xin cam đoan đề tài: “Các thuật toán cơ bản trong thông tin lượng tử
”, là kết quả nghiên cứu, thu thập của riêng tôi. Các luận cứ, kết quả thu được
trong đề tài là trung thực, không trùng với các tác giả khác. Nếu có gì không
trung thực trong luận văn tôi xin hoàn toàn chịu trách nhiệm trước hội đồng
khoa học.

7

Chương 1: Giới thiệu và các khái niệm cơ bản về thông tin lượng tử

7

1.1. Giới thiệu
1.2. Các khái niệm cơ bản

7
13

1.2.1. Bit lượng tử

13

1.2.2. Rối lượng tử

19

1.2.3 Trạng thái kết hợp

21

1.2.4. Qubit dưới dạng chồng chập của hai trạng thái kết hợp

26

Chương 2. Các thuật toán cơ bản trong thông tin lượng tử


2.3.2. Thực thi QFT

43

2.3.3. Thuật toán Shor cho việc tính toán thời gian

44

2.4. Thuật toán Grover

46

2.5. Những thuật toán khác

48

2.5.1 Vấn đề nhóm phụ ẩn

48

2.5.2 Thuật toán nghiên cứu

50


4

2.5.3 Những thuật toán khác

51

3.4. Vấn đề 4

62

3.5. Vấn đề 5

64

3.6. Vấn đề 6

66

Kết luận

69

Tài liệu tham khảo

70


5

MỞ ĐẦU
1. Lý do chọn đề tài
Trong hơn hai thập kỉ qua, khoa học thông tin lượng tử đã trở thành một
trong những lĩnh vực thu hút được nhiều sự quan tâm nhất của các nhà khoa
học. Nó được xem là một lĩnh vực mới có khả năng tạo ra sự đột phá mạnh
mẽ trong lĩnh vực khoa học và kỹ thuật có liên quan đến sự tính toán, thông
tin liên lạc, phép đo chính xác và khoa học lượng tử cơ bản.

Chương 3. Một số vấn đề và các giải pháp về thuật toán trong thông
tin lượng tử


7

NỘI DUNG
CHƯƠNG 1.
GIỚI THIỆU VÀ CÁC KHÁI NIỆM CƠ BẢN VỀ THÔNG TIN
LƯỢNG TỬ
1.1 Giới thiệu
Trong hơn hai thập kỉ qua, khoa học thông tin lượng tử đã trở thành
một trong những lĩnh vực thu hút được nhiều sự quan tâm nhất của các nhà
khoa học. Nó được xem là một lĩnh vực mới có khả năng tạo ra sự đột phá
mạnh mẽ trong lĩnh vực khoa học và kỹ thuật có liên quan đến sự tính toán,
thông tin liên lạc, phép đo chính xác và khoa học lượng tử cơ bản. Lĩnh vực
này xuất hiện kể từ lúc một số nhà khoa học tiên phong như Charles Bennett,
Paul Benioff, Richard Feynman và những người khác bắt đầu nghĩ đến việc
áp dụng trực tiếp cơ học lượng tử trong các tính toán và xử lý thông tin.
Lý thuyết thông tin cổ điển do Claude Shanon phát minh ra cách đây
hơn 50 năm đã phát triển và trở thành một trong những nhánh sai quả và đẹp
nhất của ngành toán học. Hiện nay, nó thật sự là một lý thuyết không thể thiếu
trong lĩnh vực công nghệ thông tin, bất cứ ở đâu mà thông tin được lưu trữ và
xử lý. Mặc dù đã có những thành công không thể nào phủ nhận được song
thông tin cổ điển vẫn còn tồn tại rất nhiều hạn chế do nó chỉ bám rễ trong
phạm vi của vật lý cổ điển. Chính vì vậy, việc nghiên cứu và áp dụng lý
thuyết lượng tử vào việc xử lý thông tin luôn thôi thúc các nhà khoa học,và
gần đây, nó đã mang lại nhiều thành công đáng kinh ngạc. Kể từ năm 1990,
Khi Max Planck đề xuất giả thuyết về tính gián đoạn của bức xạ điện từ phát
ra từ các vật - giả thuyết lượng tử - để giải thích những kết quả thực nghiệm

chép lại y nguyên mà không hề để lại một dấu vết nào về sự đọc trộm và sao
chép đó. Trong khi đó, thông tin lượng tử không thể nào sao chép được
nguyên vẹn và bất cứ một sự đọc trộm nào đều có thể bị phát hiện. Đây là một
đặc điểm rất quan trọng của cơ học lượng tử mà có thể được tận dụng để trao


9

đổi thông tin một cách hoàn toàn tuyệt mật. Các trạng thái rối lượng tử còn có
thể tạo ra một mức độ song song trong tính toán cao hơn hẳn một máy tính có
kích thước bằng cả vũ trụ. Đó là các tính toán được thực hiện một cách hoàn
toàn mới, gọi là tính toán lượng tử.
Trong lý thuyết thông tin cổ điển, đại lượng cơ bản của thông tin là bit,
còn trong thông tin lượng tử thì đại lượng cơ bản của nó là bit lượng tử, còn
được gọi qubit, thuật ngữ này đã được Ben Schuhmacher đưa ra năm 1995.
Nói chung, thông tin lượng tử được xem như là sự tổng quát hoá hay sự mở
rộng của thông tin cổ điển. Bất kỳ một hệ lượng tử nào cũng có thể được xem
như là một qubit nếu nó được xác định bởi hai trạng thái độc lập tuyến tính
với nhau. Các photon phân cực, các hạt có spin 1/2, các nguyên tử hai mức,
các cấu trúc chấm lượng tử kép,…đều có thể sử dụng như các qubit. Ngoài ra
còn có thể sử dụng cả các đặc trưng ngoại như hai hướng truyền khác nhau
của một hạt như là các qubit.
Năm 1985 David Deutsch đã giới thiệu về máy tính lượng tử và cho
thấy rằng lý thuyết lượng tử có thể giúp các máy tính thực hiện công việc
nhanh hơn rất nhiều. Trong khi các máy tính số ngày nay xử lý thông tin cổ
điển được mã hoá theo các bit thì máy tính lượng tử lại xử lý thông tin lượng
tử theo các qubit. Máy tính lượng tử có thể được sử dụng để thực thi những
nhiệm vụ rất khó thực hiện đối với máy tính số thông thường. Ví dụ, các siêu
máy tính số ngày nay phải mất một thời gian dài hơn cả tuổi thọ của vũ trụ để
có thể tìm ra được các thừa số nguyên tố của một số nguyên lớn có khoảng

phân tích một số nguyên lớn ra thừa số nguyên tố [41] hay dò tìm dữ liệu
[31],… Các công nghệ thông tin liên lạc và mật mã cũng đã được khám phá
dựa trên cơ học lượng tử. Sự phân bố khoá lượng tử cho phép sự liên lạc tuyệt
mật mà điều này không bao giờ có thể thực hiện được theo các giao thức cổ
điển như hiện nay. Tính chất không định xứ của cơ học lượng tử dẫn đến một
hiện tượng vô cùng kỳ lạ đó là “Viễn thông lượng tử”. Bằng viễn chuyển


11

lượng tử, một trạng thái lượng tử chưa biết bất kỳ bị phá huỷ ở một nơi và
một bản sao hoàn hảo của nó lại xuất hiện một nơi rất xa khác. Dù đã có rất
nhiều thành công đáng kinh ngạc về lĩnh vực này trong thời gian qua nhưng
vẫn còn quá xa trước khi hiện thực hoá việc xử lý thông tin lượng tử trong các
ứng dụng thực tiễn. Đối với tính toán lượng tử, các nhà nghiên cứu phải tìm
một hệ qubit vật lý có thể đo được, một tập hợp các hoạt động cổng và các
phương pháp xuất/ nhập qubit. Hơn thế nữa, các lỗi không thể tránh khỏi xảy
ra sự phá vỡ kết hợp dòi hỏi các phương pháp sửa lỗi [12] là rất cần thiết. Đến
nay, cũng đã có nhiều nghiên cứu khác nhau về sự thực thi của một máy tính
lượng tử dựa vào cộng hưởng từ nhật nhân (NMR), bẫy ion, hệ các trạng thái
rắn và quang. Những minh hoạ gần đây nhất về tính toán lượng tử chỉ mới
giới hạn 7 qubit, có nghĩa là chúng vẫn đang ở một mức độ cơ bản. Năm
1998, Chuang đã báo cáo về sự hiện thực hoá 2 qubit của một thuật toán
lượng tử cơ bản (thuật toán Deustch - Jozsa), ông đã thu được bằng cách sử
dụng công nghệ khối NMR. Trong cùng năm đó và năm tiếp theo, cũng đã có
một số minh hoạ thực nghiệm tương tự, ví dụ như Jones và Mosca đã tạo
được một thiết bị 2 qubit dựa trên chất lỏng, trong đó 2 qubit được tích trữ
trong các spin hạt nhân của các nguyên tử Hydro; Vandersypen cùng các cộng
sự đã phát triển một số thiết bị 7 qubit bằng cách sử dụng NMR để minh hoạ
thuật toán thừa số hoá Shor trong năm 2000. Năm 2003, đã có một số nhà

nhiều. Do đầu ra của các laser ổn định được mô tả rất tốt bởi các trạng thái kết
hợp nên việc mã hoá thông tin theo sự chồng chập của các trạng thái kết hợp
là rất thuận tiện. Thay vì các qubit người ta đưa vào khái niệm qubit logic
được định nghĩa như sau
  x   y 

Trong đó   e 

2

/2




n 0

(1.1)

( ) n n / n! là hai trạng thái kết hợp cùng biên

độ phức  nhưng có pha ngược nhau và x, y là các hệ số chuẩn hoá. Khi


13

thông tin lượng tử được mã hoá theo các trạng thái biến liên tục được mô tả
bởi một không gian Hilbert có số chiều xác định thì một qubit logic (1.1) là
một vector trong khôn gigan Hilbert hai chiều nhận vector trạng thái độc lập
tuyến tính {  ,  }làm hệ vector cơ sở. Chú ý rằng, mặc dù  và


2

N 2   a1  2e

2 

2

RE  a1*a 3  a *2a 4  a1*a 2  a *3a 4   2e

4 

2

RE  a1*a 4  a *2a 3  .

i 1

1.2 Các khái niệm cơ bản
1.2.1. Bit lượng tử
Đơn vị cơ bản của thông tin cổ điển là bit. Một bit có thể nhận hai giá
trị hoặc là 0 hoặc 1 và chứa lượng thông tin nhỏ nhất. Một bit có thể được


14

hiện thực hoá trong một hệ vật lý đơn giản ví dụ như một tín hiệu điện “tắt’
hoặc “mở”. Quá trình sử lý thông tin cổ điển liên quan đến việc làm thế nào
để lập mã, giải mã, lưu trữ, truyền và bảo mật thông tin cổ điển mà trong đó

15

hạt A sẽ được tìm thấy xung quanh x1 hoặc x2 với xác suất bằn nhau và bằng
1/2.

Hình 1.1: Sơ đồ về sự chồng chập tuyến tính của hai bó sóng Gauss trong
một giếng thế kép. Một hạt cổ điển phải ở một trong hai giếng thế vào một
thời điểm nào đó nhưng một hạt lượng tử thì có thể ở trong một sự chồng
chập của hai trạng thái khác nhau giống như (c).

Một trong những điểm đáng chú ý của trạng thái chồng chập (1.2) là sự giao
thoa giữa các trạng thái x1 và x 2 có thể ảnh hưởng đến sự phân bố xác
suất của phép đo toạ độ lên trạng thái (1.2). Mức độ giao thoa thay đổi tuỳ
theo giá trị của  . Biểu thức (1.2) không có nghĩa rằng hạt A hoặc là ở xung
quanh x1 hoặc là ở xung quanh x2 và xác suất của chúng là bằng nhau như
một trường hợp của hỗn hợp thống kê: Một trạng thái tương ứng với một


16

trạng thái trộn của x1 và x 2 với các xác suất bằng nhau được mô tả bởi
một toán tử mật độ 1/2  x1 x1  x 2 x 2  , hạt A cũng không ở một nơi nào
đó giữa x1 và x2. Cũng thật nguy hiểm khi nói rằng hạt A đồng thời ở cả xung
quanh x1 và x2 tại cùng một thời điểm. Nó thật rộng bởi vì chẳng ai có thể xác
minh được nó nếu không tiến hành một phép đo trực tiếp. Đã có một số ví dụ
nghịch lý để minh hoạ tính chất kỳ lạ này. Nghịch lý con mèo của
Schrödinger cho thấy sự mô tả của cơ học lượng tử về tự nhiên kỳ lạ như thế
nào khi nó được áp dụng vào các hệ vât lý vĩ mô. Thí nghiệm hai khe hẹp giải
thích hiệu ứng giao thoa của một hạt lượng tử đơn trong một trạng thái chồng
chập. Nghịch lý của Hardy minh hoạ cách mà một sự chồng chập lượng tử tạo


là sự chồng chập tuyến tính của hai trạng thái cơ bản với các số phức a và b
bất kỳ.

Hình 1.2: Sơ đồ về các bit và bit lượng tử. Trong khi một bit chỉ chiếm
một trong hai cực tương ứng với 0 hoặc 1 thì một bit lượng tử lại có thể ở bất
kỳ điểm nào trên bề mặt quả cầu Bloch vì nó có thể ở trong trạng thái chồng
chập khác nhau. Nói chung, một bit lượng tử có thể được đặt bất cứ một điểm
nào ở bên trong quả cầu nếu như nó ở trong một trạng thái hỗn hợp.
2

2

2

2

Thoả mãn điều kiện chuẩn hoá, a  b  1 , trong đó a ( b ) tươgn ứng
với xác suất mà qubit đo được có giá trị “0” (“1”). Chú ý rằng các trạng thái cơ sở
có thể được chọn một cách tuỳ ý. Ví dụ như  0  1  / 2 và  0  1  / 2 cũng
có thể là một hệ cơ sở trực chuẩn khác. Dạng tổng quát của một ma trận mật độ
của một qubit là


18

 
1
qubit  (I  r  )
2

tìm ra một hệ qubit thích hợp cho quá trình xử lý thông tin lượng tử lại là một
chuyện khác, hệ qubit đó phải có thể nhập vào, kiểm soát, đo đạt và có thể


19

đọc được trước khi nó bị phá vỡ bởi tương tác với môi trường xung quanh. Có
hai loại qubit đó là: qubit quang học (không có khối lượng) rất tốt cho truyền
tin và qubit vật thật (có khối lượng) rất tốt cho tính toán lượng tử. Việc
chuyển hoá thông tin lượng tử từ các qubit quang học sang các qubit vật chất
và ngược lại là cần thiết và đã được nghiên cứu khá kỹ càng trong [53] và
xem các tài liệu tham khảo trong đó.

1.2.2. Rối lượng tử
Rối lượng tử là một trong những điều thú vị nhất của cơ học lượng tử.
Cái tên rối lần đầu tiên được đưa ra bởi Shrödinger bằng tiếng Đức là
“verschrankung” (tiếng Anh là “entanglement”). Khi hai hệ tương tác với
nhau và sau khoảng thời gian ảnh hưởng lẫn nhau các hệ tách riêng ra trở lại
thì lúc đó chúng không còn được mô tả theo cách như trước đây nữa. Đây là
nét đặc trưng của cơ học lượng tử. Do đã tương tác với nhau mà hai hệ trở nên
rối với nhau, dù sau đó chúng có ở cách xa nhau bao nhiêu cũng được (hình
2.3).
Gần đây, các nghịch lý đã được thảo luận trong chương trước lại xuất
hiện và đóng góp vào rối của các hệ vật lý hơn là giải thích cũ dựa trên
nguyên lý bất định Heisenberg. Như đã được giải thích bởi Shrödinger, các
trạng thái rối có thể sinh ra do tương tác giữa các hệ lượng tử, ví dụ như khi
hai hạt được tạo ra một cách đồng thời với một số yêu cầu là spin hay xung
lượng phải được bảo toàn. Tuy nhiên, một trạng thái rối có thể mất rối do
tương tác với môi trường. Rối đóng vai trò không thể thay thế như là nguồn
tài nguyên trong các quá tình xử lý thông tin lượng tử bao gồm viễn chuyển

2

(1.7)

 

1
(0 1  1 0 )
2

(1.8)

được gọi là các trạng thái Bell hay các cặp EPR. Một cách tổng quát, chúng ta
nói rằng trạng thái 

12

là rối trong

H1  H2 khi nó không thể được biểu

diễn như là một tích trực tiếp của hai trạng thái bất kỳ


với  1  '

2

12


nó là trạng thái ánh sáng được phát ra từ một nguồn laser, ký hiệu là  với
 là một số phức. Trong biểu diễn Fock n của trường điện từ thì trạng thái

kết hợp có dạng tường minh như sau:
  exp(

1 2  n
 )
n
2
n!
n 0

(1.10)


22

Trạng thái kết hợp có một tính chất rất đặc biệt. Tính chất đó thể hiện ở
chỗ nó là một trạng thái riêng của toán tử huỷ photon a, tức là
(1.11)

a   

Khác hẳn với trạng thái Fock là trạng thái chứa một số photon xác định,
trạng thái kết hợp chứa một số photon không xác định và toán tử huỷ không
thể làm thay đổi trạng thái này. Xét cho trường hợp tổng quát, hai toán tử
Hermitc A và B theo thứ tự biểu diễn cho hai đại lượng vật lý A và B. Nếu
hai đại lượng vật lý này không đo được đồng thời thì theo cơ học lượng tử
A và B không giao hoán với nhau, nghĩa là

1
p  (a   a)
2

(1.14)

   1 . Các thăng giáng của chúng lần lượt là
với hệ thức giao hoán [x,p]
2

 x  x   x  ,  p  p   p  và do đó thăng giáng trung bình của chúng bị triệt

tiêu, nghĩa là  x    p   0 . Tuy nhiên, các giá trị trung bình lượng tử của
bình phương của chúng, hay còn gọi là phương sai hoặc thăng giáng lượng tử
 2    x 2    x  2 và  ( p)
 2    p 2    p  2 lại khác không.
mà cụ thể là  ( x)

Khi tính trung bình trong các trạng thái Fock n thì


23

 n | x | n   x  n   n | p | n   p  n  0 và
 2   (  p)
 2   1 (1  2n)
 ( x)
n
n
4

kết hợp thì
 2   (  p)
 2  1
 ( x)


4

(1.17)

 2   ( p)
 2   1 | [x,p]
   |2  1
 ( x)



4
16

(1.18)

và lúc đó

luôn đúng bằng độ bất định tối thiểu suy ra từ hệ thức bất định. Từ các biểu
thức (1.16) và (1.18) chúng ta thấy trạng thái kết hợp luôn ứng với độ bất định
tối thiểu suy ra từ hệ thức bất định. Một tính chất nữa mà chúng ta có thể thấy
rõ đó là khi tính phương sai số hạt trong các trạng thái Fock
2
 (n) 2  n   n | n | n   | n |  2  0


|  |2
n!

(1.21)


25

là hàm phân bổ Poisson. Các trạng thái có hàm phân bố Poisson là các trạng
thái cổ điển [88]. Vì vậy, trạng thái kết hợp là một trạng thái cổ điển. Hình 1.4
vẽ hàm phân bố P (n) với các giá trị khác nhau của |  |2 . Chúng ta thấy rằng
với
|  |2  1 thì P (n) đạt giá trị cực đại tại n = 0, trong đó với |  |2  1thì P (n)

đạt cực đại tại n |  |2 . Bây giờ, chúng ta hãy xét tích phân sau (với
 |  | ei )

* n

 ( )

m ||2

 e

2
n  m 1 ||2

2

do đó
1
|   | d 2  I



(1.24)

Đây là biểu thức phân giải đơn vị đối với trạng thái kết hợp. Hai trạng thái kết
hợp tương ứng với hai trị riêng khác nhau  và  ' là không trực giao với nhau
1
1
 |  '   exp(  |  |2  '*  | ' |2
2
2

(1.25)

|  |  '  |2  exp( |    ' |2 )

(1.26)

và