“Tôi nghĩ tôi có thể nói một cách an toàn rằng không ai hiểu được cơ học lượng tử.” - Richard Feynman
Chủ đề về điện toán lượng tử luôn thu hút các nhà văn và nhà báo công nghệ. Tiềm năng tính toán và độ phức tạp của nó đã mang lại cho nó một hào quang thần bí nhất định. Thông thường, các bài báo chuyên đề và đồ họa thông tin mô tả chi tiết các triển vọng khác nhau của ngành này trong khi hầu như không đề cập đến ứng dụng thực tế của nó: điều này có thể đánh lừa người đọc ít chú ý hơn.
Các bài báo khoa học phổ biến bỏ qua các mô tả về hệ lượng tử và đưa ra những tuyên bố như:
Một bit thông thường có thể là 1 hoặc 0, nhưng một qubit có thể đồng thời là 1 và 0.
Nếu bạn rất may mắn (điều mà tôi không chắc chắn), bạn sẽ được thông báo rằng:
Qubit nằm ở trạng thái chồng chất giữa "1" và "0".
Không có lời giải thích nào trong số này có vẻ hợp lý, vì chúng ta đang cố gắng hình thành một hiện tượng cơ học lượng tử bằng cách sử dụng ngôn ngữ được phát triển trong một thế giới rất truyền thống. Để giải thích rõ ràng các nguyên tắc của điện toán lượng tử, cần phải sử dụng một ngôn ngữ khác - ngôn ngữ toán học.
Trong hướng dẫn này, tôi sẽ đề cập đến các công cụ toán học cần thiết để mô hình hóa và hiểu các hệ thống điện toán lượng tử, cũng như cách minh họa và áp dụng logic của điện toán lượng tử. Hơn nữa, tôi sẽ đưa ra một ví dụ về thuật toán lượng tử và cho bạn biết lợi thế của nó so với máy tính truyền thống là gì.
Tôi sẽ cố gắng hết sức để giải thích tất cả điều này bằng ngôn ngữ rõ ràng, nhưng tôi vẫn hy vọng rằng độc giả của bài viết này có hiểu biết cơ bản về đại số tuyến tính và logic số (đại số tuyến tính được đề cập ở đây). , về logic kỹ thuật số - ).
Đầu tiên, chúng ta hãy điểm qua các nguyên tắc của logic kỹ thuật số. Nó dựa trên việc sử dụng các mạch điện để thực hiện tính toán. Để làm cho mô tả của chúng tôi trừu tượng hơn, chúng ta hãy đơn giản hóa trạng thái của dây điện thành “1” hoặc “0”, tương ứng với trạng thái “bật” hoặc “tắt”. Bằng cách sắp xếp các bóng bán dẫn theo một trình tự nhất định, chúng ta sẽ tạo ra cái gọi là phần tử logic lấy một hoặc nhiều giá trị tín hiệu đầu vào và chuyển đổi chúng thành tín hiệu đầu ra dựa trên các quy tắc nhất định của logic Boolean.
Các cổng logic chung và bảng trạng thái của chúng
Dựa trên chuỗi các phần tử cơ bản như vậy, các phần tử phức tạp hơn có thể được tạo ra và dựa trên chuỗi các phần tử phức tạp hơn, cuối cùng, với mức độ trừu tượng cao, chúng ta có thể mong đợi có được một bộ xử lý trung tâm tương tự.
Như tôi đã đề cập trước đó, chúng ta cần một cách để biểu diễn logic số về mặt toán học. Đầu tiên, hãy giới thiệu logic toán học truyền thống. Sử dụng đại số tuyến tính, các bit cổ điển có giá trị “1” và “0” có thể được biểu diễn dưới dạng hai vectơ cột:
các số bên trái ở đâu vectơ. Bằng cách biểu diễn các bit theo cách này, chúng ta có thể mô hình hóa các hoạt động logic trên các bit bằng cách sử dụng các phép biến đổi vectơ. Xin lưu ý: mặc dù sử dụng hai bit trong cổng logic có thể thực hiện nhiều thao tác (AND, NOT, XOR, v.v.), nhưng khi sử dụng một bit, chỉ có thể thực hiện bốn thao tác: chuyển đổi nhận dạng, phủ định, tính hằng số “0” và tính hằng số “1”. Với chuyển đổi nhận dạng, bit không thay đổi, với số âm, giá trị bit thay đổi ngược lại (từ “0” thành “1” hoặc từ “1” thành “0”) và tính toán hằng số “1” hoặc “0” đặt bit thành “1” hoặc “0” bất kể giá trị trước đó của nó là bao nhiêu.
| Bản sắc | Chuyển đổi danh tính |
| Phủ định | Từ chối |
| Hằng-0 | Tính hằng số "0" |
| Hằng-1 | Tính hằng số "1" |
Dựa trên cách biểu diễn bit mới được đề xuất của chúng tôi, việc thực hiện các thao tác trên bit tương ứng bằng cách sử dụng phép biến đổi vectơ là khá dễ dàng:
Trước khi đi xa hơn, chúng ta hãy nhìn vào khái niệm , ngụ ý đơn giản rằng để đảm bảo khả năng đảo ngược của một thao tác hoặc phần tử logic, cần xác định danh sách các giá trị tín hiệu đầu vào dựa trên tín hiệu đầu ra và tên của các thao tác được sử dụng. Vì vậy, chúng ta có thể kết luận rằng phép biến đổi đồng nhất và phủ định là có thể đảo ngược, nhưng các phép toán tính các hằng số “1” và “0” thì không. Nhờ vào cơ học lượng tử, máy tính lượng tử chỉ sử dụng các phép toán thuận nghịch nên đó là điều chúng ta sẽ tập trung vào. Tiếp theo, chúng tôi chuyển đổi các phần tử không thể đảo ngược thành các phần tử có thể đảo ngược để cho phép máy tính lượng tử sử dụng chúng.
Với các bit riêng lẻ có thể được biểu diễn bằng nhiều bit:
Bây giờ chúng ta đã có gần như tất cả các khái niệm toán học cần thiết, hãy chuyển sang cổng logic lượng tử đầu tiên. Đây là người điều hành hoặc Không được kiểm soát (KHÔNG), điều này có tầm quan trọng lớn trong điện toán lượng tử và đảo ngược. Phần tử CNOT áp dụng cho hai bit và trả về hai bit. Bit đầu tiên được chỉ định là bit “điều khiển” và bit thứ hai là bit “điều khiển”. Nếu bit điều khiển được đặt thành "1", bit điều khiển sẽ thay đổi giá trị của nó; Nếu bit điều khiển được đặt thành "0", bit điều khiển sẽ không thay đổi.
Toán tử này có thể được biểu diễn dưới dạng vectơ biến đổi sau:
Để trình bày mọi thứ chúng ta đã trình bày cho đến nay, tôi sẽ chỉ cho bạn cách sử dụng phần tử CNOT trên nhiều bit:
Để tóm tắt những gì đã nói: trong ví dụ đầu tiên, chúng ta phân tách |10⟩ thành các phần của tích tensor của nó và sử dụng ma trận CNOT để thu được trạng thái tương ứng mới của tích; sau đó chúng tôi phân tích nó thành |11⟩ theo bảng giá trị CNOT đã đưa ra trước đó.
Vì vậy, chúng ta đã ghi nhớ tất cả các quy tắc toán học sẽ giúp chúng ta hiểu về điện toán truyền thống và các bit thông thường, và cuối cùng chúng ta có thể chuyển sang điện toán lượng tử và qubit hiện đại.
Nếu bạn đã đọc đến đây thì tôi có tin tốt cho bạn: qubit có thể dễ dàng biểu diễn bằng toán học. Nói chung, nếu một bit cổ điển (cbit) có thể được đặt thành |1⟩ hoặc |0⟩, thì qubit chỉ đơn giản ở trạng thái chồng chất và có thể là cả |0⟩ và |1⟩ trước khi đo. Sau khi đo, nó thu gọn thành |0⟩ hoặc |1⟩. Nói cách khác, một qubit có thể được biểu diễn dưới dạng kết hợp tuyến tính của |0⟩ và |1⟩ theo công thức dưới đây:
đâu a₀ и một₁ lần lượt biểu thị các biên độ |0⟩ và |1⟩. Đây có thể được coi là "xác suất lượng tử", biểu thị xác suất một qubit sụp đổ thành một trong các trạng thái sau khi nó được đo, vì trong cơ học lượng tử, một vật thể ở trạng thái chồng chất sẽ sụp đổ thành một trong các trạng thái sau khi được cố định. Hãy mở rộng biểu thức này và nhận được những điều sau:
Để đơn giản hóa lời giải thích của tôi, đây là cách trình bày tôi sẽ sử dụng trong bài viết này.
Đối với qubit này, khả năng sụp đổ về giá trị a₀ sau khi đo bằng |a₀|² và khả năng giảm về giá trị a₁ bằng |a₁|². Ví dụ: đối với qubit sau:
khả năng rơi vào “1” bằng |1/ √2|², hoặc ½, tức là 50/50.
Vì trong hệ thống cổ điển, tất cả các xác suất phải cộng lại bằng một (để phân bố xác suất hoàn chỉnh), chúng ta có thể kết luận rằng bình phương các giá trị tuyệt đối của biên độ |0⟩ và |1⟩ phải cộng lại bằng một. Dựa trên thông tin này, chúng ta có thể xây dựng phương trình sau:
Nếu bạn quen thuộc với lượng giác, bạn sẽ nhận thấy rằng phương trình này tương ứng với định lý Pythagore (aXNUMX+bXNUMX=cXNUMX), nghĩa là chúng ta có thể biểu diễn bằng đồ họa các trạng thái có thể có của qubit dưới dạng các điểm trên vòng tròn đơn vị, cụ thể là:
Các toán tử và phần tử logic được áp dụng cho qubit theo cách tương tự như trong trường hợp với các bit cổ điển - dựa trên phép biến đổi ma trận. Tất cả các toán tử ma trận khả nghịch mà chúng tôi đã gọi lại cho đến nay, đặc biệt là CNOT, đều có thể được sử dụng để hoạt động với qubit. Các toán tử ma trận như vậy cho phép bạn sử dụng từng biên độ của qubit mà không cần đo và thu gọn nó. Hãy để tôi cho bạn một ví dụ về việc sử dụng toán tử phủ định trên qubit:
Trước khi chúng ta tiếp tục, hãy để tôi nhắc bạn rằng các giá trị biên độ a₀ và a₁ thực sự là , do đó trạng thái của qubit có thể được ánh xạ chính xác nhất lên một hình cầu đơn vị ba chiều, còn được gọi là :
Tuy nhiên, để đơn giản hóa việc giải thích, ở đây chúng ta sẽ giới hạn ở số thực.
Có vẻ như đã đến lúc thảo luận về một số yếu tố logic chỉ có ý nghĩa trong bối cảnh điện toán lượng tử.
Một trong những toán tử quan trọng nhất là "Phần tử Hadamard": nó lấy một bit ở trạng thái "0" hoặc "1" và đặt nó ở vị trí chồng chất thích hợp với 50% khả năng sụp đổ thành "1" hoặc "0" sau khi đo.
Lưu ý rằng có một số âm ở phía dưới bên phải của toán tử Hadamard. Điều này là do kết quả của việc áp dụng toán tử phụ thuộc vào giá trị của tín hiệu đầu vào: - |1⟩ hoặc |0⟩, và do đó phép tính có thể đảo ngược.
Một điểm quan trọng khác về nguyên tố Hadamard là tính khả nghịch của nó, nghĩa là nó có thể lấy một qubit ở trạng thái chồng chất thích hợp và biến nó thành |0⟩ hoặc |1⟩.
Điều này rất quan trọng vì nó cho chúng ta khả năng chuyển đổi từ trạng thái lượng tử mà không cần xác định trạng thái của qubit - và theo đó, không làm nó bị sập. Do đó, chúng ta có thể cấu trúc điện toán lượng tử dựa trên nguyên tắc xác định thay vì xác suất.
Các toán tử lượng tử chỉ chứa số thực là đối lập của chúng, vì vậy chúng ta có thể biểu thị kết quả của việc áp dụng toán tử cho qubit dưới dạng một phép biến đổi trong vòng tròn đơn vị dưới dạng máy trạng thái:
Do đó, qubit, trạng thái được trình bày trong sơ đồ trên, sau khi áp dụng thao tác Hadamard, sẽ được chuyển sang trạng thái được biểu thị bằng mũi tên tương ứng. Tương tự như vậy, chúng ta có thể xây dựng một máy trạng thái khác sẽ minh họa quá trình biến đổi một qubit bằng cách sử dụng toán tử phủ định như được hiển thị ở trên (còn được gọi là toán tử phủ định Pauli hoặc đảo ngược bit), như hiển thị bên dưới:
Để thực hiện các thao tác phức tạp hơn trên qubit, chúng ta có thể xâu chuỗi nhiều toán tử hoặc áp dụng các phần tử nhiều lần. Ví dụ về chuyển đổi nối tiếp dựa trên như sau:
Nghĩa là, nếu chúng ta bắt đầu với bit |0⟩, áp dụng phép đảo ngược bit, sau đó là phép toán Hadamard, sau đó là phép đảo ngược bit khác và lại là phép toán Hadamard, tiếp theo là phép đảo ngược bit cuối cùng, chúng ta sẽ thu được vectơ cho bởi trên bên phải của chuỗi. Bằng cách xếp các máy trạng thái khác nhau lên nhau, chúng ta có thể bắt đầu từ |0⟩ và theo dõi các mũi tên màu tương ứng với từng phép biến đổi để hiểu cách hoạt động của tất cả.
Vì chúng ta đã đi xa đến mức này nên đã đến lúc xem xét một trong các loại thuật toán lượng tử, cụ thể là - và thể hiện ưu điểm của nó so với máy tính cổ điển. Điều đáng chú ý là thuật toán Deutsch-Jozsa hoàn toàn mang tính xác định, tức là nó trả về câu trả lời đúng 100% thời gian (không giống như nhiều thuật toán lượng tử khác dựa trên định nghĩa xác suất của qubit).
Hãy tưởng tượng rằng bạn có một hộp đen chứa hàm/toán tử trên một bit (hãy nhớ - với một bit, chỉ có thể thực hiện bốn thao tác: chuyển đổi nhận dạng, phủ định, đánh giá hằng số "0" và đánh giá hằng số "1 "). Chính xác thì chức năng được thực hiện trong hộp là gì? Bạn không biết cái nào, nhưng bạn có thể xem qua bao nhiêu biến thể của giá trị đầu vào tùy thích và đánh giá kết quả đầu ra.
Bạn sẽ phải chạy bao nhiêu đầu vào và đầu ra qua hộp đen để tìm ra chức năng nào đang được sử dụng? Hãy nghĩ về điều này trong một giây.
Trong trường hợp máy tính cổ điển, bạn sẽ cần thực hiện 2 truy vấn để xác định chức năng sẽ sử dụng. Ví dụ: nếu đầu vào "1" tạo ra đầu ra "0", thì rõ ràng là hàm tính hằng số "0" hoặc hàm phủ định được sử dụng, sau đó bạn sẽ phải thay đổi giá trị của tín hiệu đầu vào về "0" và xem điều gì xảy ra ở lối ra.
Trong trường hợp máy tính lượng tử, cũng sẽ cần có hai truy vấn, vì bạn vẫn cần hai giá trị đầu ra khác nhau để xác định chính xác hàm áp dụng cho giá trị đầu vào. Tuy nhiên, nếu bạn đặt lại câu hỏi một chút, thì hóa ra máy tính lượng tử vẫn có một lợi thế lớn: nếu bạn muốn biết hàm đang được sử dụng là hằng số hay biến đổi thì máy tính lượng tử sẽ có lợi thế hơn.
Hàm được sử dụng trong hộp có thể thay đổi nếu các giá trị khác nhau của tín hiệu đầu vào tạo ra các kết quả khác nhau ở đầu ra (ví dụ: chuyển đổi nhận dạng và đảo ngược bit) và nếu giá trị đầu ra không thay đổi bất kể giá trị đầu vào thì hàm hàm là hằng số (ví dụ: tính hằng số "1" hoặc tính hằng số "0").
Bằng cách sử dụng thuật toán lượng tử, bạn có thể xác định xem một hàm trong hộp đen là hằng số hay biến chỉ dựa trên một truy vấn. Nhưng trước khi xem cách thực hiện điều này một cách chi tiết, chúng ta cần tìm cách cấu trúc từng chức năng này trên máy tính lượng tử. Vì bất kỳ toán tử lượng tử nào cũng phải khả nghịch, nên chúng ta ngay lập tức gặp phải một vấn đề: các hàm tính các hằng số “1” và “0” không khả nghịch.
Một giải pháp phổ biến được sử dụng trong điện toán lượng tử là thêm một qubit đầu ra bổ sung để trả về bất kỳ giá trị đầu vào nào mà hàm nhận được.
| Trước: | Sau: |
|
|
|
Bằng cách này, chúng ta có thể xác định các giá trị đầu vào chỉ dựa trên giá trị đầu ra và hàm trở nên khả nghịch. Cấu trúc của mạch lượng tử tạo ra nhu cầu về một bit đầu vào bổ sung. Để phát triển các toán tử tương ứng, chúng tôi sẽ giả sử rằng qubit đầu vào bổ sung được đặt thành |0⟩.
Sử dụng cùng cách biểu diễn mạch lượng tử mà chúng ta đã sử dụng trước đó, chúng ta hãy xem cách thực hiện từng phần tử trong số bốn phần tử (biến đổi nhận dạng, phủ định, đánh giá hằng số "0" và đánh giá hằng số "1") có thể được thực hiện bằng cách sử dụng toán tử lượng tử.
Ví dụ: đây là cách bạn có thể triển khai hàm tính hằng số “0”:
Tính hằng số "0":
Ở đây chúng tôi không cần người vận hành chút nào. Qubit đầu vào đầu tiên (mà chúng tôi giả định là |0⟩) trả về có cùng giá trị và giá trị đầu vào thứ hai trả về chính nó - như thường lệ.
Với hàm tính hằng số “1”, tình huống hơi khác một chút:
Tính hằng số "1":
Vì chúng ta đã giả định rằng qubit đầu vào đầu tiên luôn được đặt thành |0⟩, nên kết quả của việc áp dụng toán tử đảo ngược bit là nó luôn tạo ra một qubit ở đầu ra. Và như thường lệ, qubit thứ hai cho giá trị riêng ở đầu ra.
Khi hiển thị toán tử chuyển đổi danh tính, tác vụ bắt đầu trở nên phức tạp hơn. Đây là cách thực hiện:
Phép biến đổi giống nhau:
Ký hiệu được sử dụng ở đây biểu thị phần tử CNOT: dòng trên cùng biểu thị bit điều khiển và dòng dưới cùng biểu thị bit điều khiển. Hãy để tôi nhắc bạn rằng khi sử dụng toán tử CNOT, giá trị của bit điều khiển sẽ thay đổi nếu bit điều khiển bằng |1⟩, nhưng không thay đổi nếu bit điều khiển bằng |0⟩. Vì chúng ta giả định rằng giá trị của dòng trên cùng luôn bằng |0⟩ nên giá trị của nó luôn được gán cho dòng dưới cùng.
Chúng ta tiến hành theo cách tương tự với toán tử phủ định:
Phủ định:
Chúng ta chỉ cần đảo ngược bit ở cuối dòng đầu ra.
Bây giờ chúng ta đã hiểu sơ bộ về điều đó, hãy xem xét những ưu điểm cụ thể của máy tính lượng tử so với máy tính truyền thống khi xác định tính không đổi hoặc tính biến đổi của hàm ẩn trong hộp đen chỉ bằng một truy vấn.
Để giải quyết vấn đề này bằng cách sử dụng điện toán lượng tử trong một yêu cầu duy nhất, cần phải đặt các qubit đầu vào vào trạng thái chồng chất trước khi chuyển chúng đến hàm, như minh họa bên dưới:
Phần tử Hadamard được áp dụng lại cho kết quả của hàm để phá vỡ các qubit ra khỏi trạng thái chồng chất và làm cho thuật toán có tính xác định. Chúng ta khởi động hệ thống ở trạng thái |00⟩ và, vì những lý do tôi sẽ giải thích ngắn gọn, sẽ nhận được kết quả |11⟩ nếu hàm được áp dụng là hằng số. Nếu hàm bên trong hộp đen có thể thay đổi thì sau khi đo hệ thống trả về kết quả |01⟩.
Để hiểu phần còn lại của bài viết, chúng ta hãy nhìn vào hình minh họa tôi đã trình bày trước đó:
Bằng cách sử dụng toán tử đảo ngược bit và sau đó áp dụng phần tử Hadamard cho cả hai giá trị đầu vào bằng |0⟩, chúng tôi đảm bảo rằng chúng được dịch sang cùng một vị trí xếp chồng của |0⟩ và |1⟩, như sau:
Sử dụng ví dụ về chuyển giá trị này cho hàm hộp đen, có thể dễ dàng chứng minh rằng cả hai hàm giá trị không đổi đều xuất ra |11⟩.
Tính hằng số "0":
Tương tự, chúng ta thấy rằng hàm tính hằng số “1” cũng tạo ra |11⟩ làm đầu ra, đó là:
Tính hằng số "1":
Lưu ý rằng đầu ra sẽ là |1⟩, vì -1² = 1.
Theo cùng một nguyên tắc, chúng ta có thể chứng minh rằng khi sử dụng cả hai hàm biến, chúng ta sẽ luôn nhận được |01⟩ ở đầu ra (với điều kiện chúng ta sử dụng cùng một phương pháp), mặc dù mọi thứ phức tạp hơn một chút.
Phép biến đổi giống nhau:
Vì CNOT là toán tử hai qubit nên nó không thể được biểu diễn dưới dạng máy trạng thái đơn giản và do đó cần xác định hai tín hiệu đầu ra dựa trên tích tensor của cả qubit đầu vào và phép nhân với ma trận CNOT như được mô tả trước đó:
Với phương pháp này, chúng ta cũng có thể xác nhận rằng giá trị đầu ra |01⟩ được nhận nếu hàm phủ định bị ẩn trong hộp đen:
Phủ định:
Vì vậy, chúng tôi vừa chứng minh một tình huống trong đó máy tính lượng tử rõ ràng hiệu quả hơn máy tính thông thường.
Điều gì tiếp theo?
Tôi đề nghị chúng ta kết thúc ở đây. Chúng tôi đã làm rất tốt rồi. Nếu bạn đã hiểu mọi thứ tôi trình bày thì tôi nghĩ bây giờ bạn đã hiểu rõ về những điều cơ bản của điện toán lượng tử và logic lượng tử cũng như lý do tại sao thuật toán lượng tử có thể hiệu quả hơn điện toán truyền thống trong một số trường hợp nhất định.
Mô tả của tôi khó có thể được gọi là hướng dẫn đầy đủ về tính toán lượng tử và thuật toán - đúng hơn, nó là phần giới thiệu ngắn gọn về toán học và ký hiệu, được thiết kế để xua tan ý tưởng của người đọc về chủ đề do các nguồn khoa học phổ biến áp đặt (nghiêm túc mà nói, nhiều người thực sự không thể hiểu được). tình huống!). Tôi không có thời gian để đề cập đến nhiều chủ đề quan trọng, chẳng hạn như , độ phức tạp của các giá trị biên độ |0⟩ và |1⟩ và hoạt động của các phần tử logic lượng tử khác nhau trong quá trình biến đổi bởi quả cầu Bloch.
Nếu bạn muốn hệ thống hóa và cấu trúc kiến thức của mình về máy tính lượng tử, mạnh mẽ Tôi khuyên bạn nên đọc Emma Strubel: mặc dù có rất nhiều công thức toán học, cuốn sách này thảo luận về các thuật toán lượng tử chi tiết hơn nhiều.
Nguồn: www.habr.com