Máy Tính Dưới Góc Nhìn Của Những Viên Bi Kì 1: Cổ Điển

Nguồn: Internet
Cũng đã vài tháng rồi tôi mới quay lại Động nhện để viết, một phần vì lịch học trên trường hơi dày, một phần vì tôi thực sự hơi ... bí ý tưởng cho chủ đề về máy tính lượng tử và mật mã của mình. 
Chuỗi ngày dài học môn kiến trúc máy tính trên trường khiến cái đầu kém hiểu biết của tôi về phần cứng máy tính được thông thoáng hơn hẳn. Tuy nhiên, vẫn còn có nhiều câu hỏi về mang tính lý thuyết nặng hơn mà tôi chưa trả lời được, đại khái là những câu dạng như "máy tính từ đâu sinh ra? Cơ sở khoa học của phần cứng máy tinh là gì". Mà phạm vi môn học chỉ có chừng đó nên tôi đành tự tìm hiểu vậy. 

Một trong những câu trả lời dễ hiểu và thú vị nhất cho câu hỏi trên được tôi may mắn tìm thấy trong một cuốn sách cho Computer Scientists sau vài ngày vọc trên mạng: 
nền tảng ban đầu của máy tính không khác gì một dạng máy lưu trữ là bao, mỗi khi tính toán (sử dụng) trên máy tính, công việc quan trọng nhất là cập nhật lại bộ nhớ cho lần tính toán tiếp theo. Bất kì hệ thống nào có tính năng này đều có thể được coi là máy tính.
Tôi sẽ lấy ý tưởng cơ bản này và khái quát nó như một hệ thống. Có lẽ sẽ thoải mái hơn khi chúng ta được tiếp xúc với đồ thị và ma trận. Vì vậy, tôi sẽ truyền đạt các ý tưởng dựa trên kiến thức về lý thuyết đồ thị và lý thuyết ma trận.
Chuỗi bài viết chia làm 3 phần, phần 1 trình bày về các đồ thị không có trọng số - mô hình hóa của hệ thống xác định cổ điển. Phần 2 sẽ nói về các đồ thị sẽ có trọng số là số thực (hệ thống xác suất cổ điển). Và trong phần 3 sẽ nói về các đồ thị có trọng số là các số phức - mô hình hóa cho hệ thống lượng tử. Ai đã học qua một lớp về cấu trúc rời rạc đều có thể sẽ biết cách biểu diễn một đồ thị có trọng số dưới dạng ma trận kề.
Tôi sẽ trình bày ý tưởng dưới dạng một mô hình đồ chơi bao gồm các viên bi, sau đó khái quát hóa nó thành một mô hình trừu tượng và chuyển sang ý tưởng tiếp theo.
HỆ THỐNG XÁC ĐỊNH CỔ ĐIỂN
Chúng ta bắt đầu với một hệ thống đơn giản được mô tả bởi một đồ thị cùng dưới góc nhìn của một số viên bi. Hãy tưởng tượng vị trí của các viên bi là các đỉnh của một đồ thị. Trạng thái của một hệ thống được mô tả bằng số viên bi trên mỗi đỉnh.
Ví dụ: Có 6 đỉnh trong đồ thị và có tổng số 27 bi. Chúng ta có thể đặt 6 viên bi trên đỉnh 0, 2 viên bi trên đỉnh 1 và phần còn lại như mô tả bởi hình ảnh này.

Chúng ta sẽ biểu diễn trạng thái này là X = [6, 2, 1, 5, 3, 10]^T
Hãy quan tâm đến việc các viên bi di chuyển. Cách chúng thay đổi vị trí - được xem như là dynamics (động lực) của hệ thống - có thể được biểu diễn bởi một đồ thị với các cạnh có trọng số xác định và mọi đỉnh trong đồ thị luôn có chính xác một cạnh đi ra/ vào. Do đó hệ thống luôn được xác định. Nói cách khác, mỗi viên bi phải di chuyển đến chính xác một nơi chứ không bất động mãi.
Ví dụ về dynamics của hệ thống có thể được mô tả bởi đồ thị sau

Ý tưởng là nếu một mũi tên đi từ đỉnh i đến đỉnh j, thì trong một lần, tất cả các viên bi trên đỉnh i sẽ dịch chuyển đến đỉnh j.
Đồ thị này dễ dàng lưu trữ trong bộ nhớ dưới dạng ma trận kề Boolean (M kí hiệu cho “marble”):

trong đó M [i, j] = 1 khi và chỉ khi có một mũi tên từ đỉnh i đến đỉnh j. Yêu cầu rằng mỗi đỉnh có chính xác một cạnh đi tương ứng với thực tế là mỗi cột của ma trận kề Boolean chứa chính xác một số 1.
Nhân M với một trạng thái như hệ X = [6,2,1,5,3,10]^T . Chúng ta có:

Phép tính này tương ứng với điều gì? Nếu X mô tả trạng thái của hệ thống tại thời điểm t, thì Y sẽ là trạng thái của hệ thống tại thời điểm t+1, tức là sau một operator (hoạt động). Chúng ta có thể thấy điều này rõ ràng bằng cách nhìn vào công thức nhân ma trận:
 

Phương trình này nói rằng số lượng viên bi sẽ tới đỉnh i sau một thời gian là tổng của tất cả các viên bi trên đỉnh với các cạnh nối với đỉnh j.
Lưu ý rằng hai dòng trên cùng của ma trận Y là 0. Có nghĩa là không có mũi tên nào tới đỉnh 0 hoặc đỉnh 1, nói cách khác đỉnh 0 và 1 không có cạnh tới.
Nói chung, bất kỳ đồ thị có hướng đơn giản nào với n đỉnh đều có thể được biểu diễn bằng ma trận n x n với quy tắc sau:
M[i, j] = 1 khi và chỉ khi có một cạnh từ đỉnh i đến đỉnh j.
            = 1 khi và chỉ khi có một con đường có độ dài 1 từ đỉnh i đến đỉnh j.
Nếu X [x0, x1, x2, ... x(n-1)]^T là một vectơ cột tương ứng với việc đặt các viên bi xi trên đỉnh i, và nếu MX = Y trong đó Y [y0, y1, y2, ...y(n-1)]^T, thì có nghĩa là chúng ta sẽ có các viên bi yj trên đỉnh j sau một operator. M là cách mô tả trạng thái của các viên bi có thể thay đổi từ thời gian t đến thời gian t+1. 
Các operator tiếp theo có thể là các ma trận khác. Để thuận lợi cho tính toán toán chúng ta sẽ lấy tất cả các operator và nhân chúng với nhau cùng lúc cho đến khi đạt được operator mong muốn và nhân nó với ma trận trạng thái hiện tại. 
Tóm lại, hệ thống xác định cổ điển bao gồm những điều sau đây:
  • Trạng thái của một hệ thống tương ứng với các vectơ cột (vectơ trạng thái).
  • Operator của một hệ thống tương ứng với ma trận.
  • Để chuyển từ trạng thái này sang trạng thái khác trong một operator, ta phải nhân vector trạng thái với một ma trận.
  • Ma trận operator nhiều bước thu được thông qua phép nhân nhiều ma trận liên tiếp.
Tài liệu tham khảo: Quantum Computing for Computer Scientists (Noson S. Yanofsky, Mirco A Mannucci) & Lý thuyết đồ thị (Wikipedia).
To be countinued ...
24
1821 lượt xem
24
5
5 bình luận