Giới thiệu

Trong những năm gần đây, sự ra đời của máy tính lượng tử đã mang lại sự phấn khích lớn cho nhiều cộng đồng nghiên cứu (ví dụ: vật lý, khoa học máy tính, toán học, v.v.). Sự quan tâm đến chủ đề tính toán lượng tử đã dẫn đến nhiều đóng góp lý thuyết trong không gian, thúc đẩy sự phát triển của các thuật toán có ảnh hưởng như tìm kiếm của Grover , thuật toán Shor , tối ưu hóa đoạn nhiệt , và nhiều hơn nữa. Bất chấp những minh chứng lý thuyết về tính tối cao và tính hữu dụng của lượng tử, các thuật toán như vậy vượt ra ngoài thực tế hiện tại của phần cứng lượng tử, sử dụng độ sâu mạch và số lượng qubit quá mức. Hiện tại, các yêu cầu như vậy là không thể thực hiện được trong một hệ thống vật lý.

Hiện tại, tính toán lượng tử được cho là tồn tại trong kỷ nguyên Lượng tử quy mô trung gian ồn ào (NISQ), trong đó phần cứng bị giới hạn về số lượng qubit có sẵn và độ sâu mạch bị hạn chế do tiếng ồn ngày càng tăng phát sinh trong một hệ thống lượng tử. Do đó, nhiều thuật toán lượng tử ưu việt nhất (chẳng hạn như những thuật toán đã đề cập ở trên) có ứng dụng thực tế hạn chế, khiến các nhà nghiên cứu tập trung vào việc phát triển các thuật toán lượng tử thân thiện với NISQ. Hai trong số các thuật toán được nghiên cứu rộng rãi nhất trong không gian này là bộ phân tích lượng tử biến thiên (VQE) và thuật toán tối ưu hóa gần đúng lượng tử (QAOA), cả hai đều là thuật toán lượng tử biến thiên (VQA) sử dụng các mạch lượng tử tham số (với các tham số được tối ưu hóa theo kiểu cổ điển) để tối ưu hóa các chức năng (ví dụ: cặp eigenvalue / eigenvector tối thiểu, cắt tối đa trên biểu đồ,độ phủ đỉnh tối đa trên đồ thị, v.v.). Trong bài đăng này, tôi muốn giải thích sâu hơn về QAOA, chỉ giả sử hiểu biết cơ bản về tính toán lượng tử (ví dụ: qubit, trạng thái lượng tử và đại số tuyến tính cơ bản); xembài đăng trên blog này nếu bạn quan tâm để tìm hiểu thêm về VQE.

Tôi sẽ bắt đầu bằng cách giải thích QAOA ở cấp độ cao, bao gồm các thành phần của thuật toán và cách nó có thể được sử dụng để giải quyết các vấn đề quan tâm. Sau mô tả ban đầu về QAOA, tôi sẽ tổng quan về nhiều khái niệm trong cơ học lượng tử và toán học có liên quan đến việc phát triển sự hiểu biết sâu sắc về QAOA. Một khi nền tảng như vậy rõ ràng, tôi sẽ giải thích chi tiết của thuật toán đoạn nhiệt cho tính toán lượng tử, có liên quan phức tạp đến QAOA, nhằm cố gắng hiểu QAOA có liên quan như thế nào với các thuật toán trước nó. Ở cuối bài viết, tôi sẽ quay lại thảo luận về QAOA, nhằm mục đích thúc đẩy các thành phần của thuật toán bằng cách vẽ các kết nối với thuật toán đoạn nhiệt cho tính toán lượng tử.

Thuật toán tối ưu hóa gần đúng lượng tử

QAOA là một thuật toán lượng tử biến thiên (tức là một thuật toán lượng tử-cổ điển lai liên quan đến các mạch lượng tử tham số được tối ưu hóa theo kiểu cổ điển) được đề xuất để tìm kiếm các giải pháp gần đúng cho các vấn đề tối ưu hóa tổ hợp (ví dụ: MaxCut, Maximum Vertex Cover, MaxSAT, v.v.). Ở mức cao, QAOA áp dụng một loạt các cổng lượng tử tham số cho một số trạng thái ban đầu và tối ưu hóa các thông số của các cổng này sao cho trạng thái cuối cùng (sau khi các cổng lượng tử đã được áp dụng) mã hóa một giải pháp gần đúng cho một số vấn đề quan tâm (tức là , nếu bạn thực hiện phép đo trạng thái cuối cùng dựa trên cơ sở tính toánnó sẽ tạo ra một giải pháp chất lượng cao). Khung QAOA bao gồm một số thành phần. Ở đây, tôi chỉ đơn giản là xác định các thành phần có liên quan và minh họa cách chúng được kết hợp với nhau mà không xem xét sâu về động cơ của chúng, do đó cung cấp hiểu biết cơ bản về QAOA nói chung.

Chi phí và Máy trộn Hamiltonians

Giả sử chúng ta đang nghiên cứu một hệ lượng tử với ntổng số qubit . Trong QAOA, có hai Hamilton được quan tâm - Hamilton trộn và Hamilton chi phí. Mỗi Hamiltonians này là ma trận thứ nguyên có giá trị phức tạp 2^n x 2^n. Tuy nhiên, để hiểu mục đích của chúng, trước tiên chúng ta phải hiểu vai trò của Hamilton trong một hệ lượng tử. Trong cơ học lượng tử, Hamilton là một ma trận hermitian mã hóa năng lượng của một hệ lượng tử. Đặc biệt, các giá trị riêng của Hamilton, có giá trị thực vì ma trận là hermitian, đại diện cho các mức năng lượng có thể có của hệ thống (tức là tập hợp các kết quả có thể xảy ra khi đo tổng năng lượng của hệ thống).

Một mô hình phổ biến trong các thuật toán lượng tử là mã hóa một vấn đề quan tâm (ví dụ: tối thiểu hóa / tối đa hóa một số chức năng) trong ma trận Hamilton và tìm cách tạo ra một trạng thái lượng tử, khi được đo bằng Hamilton đó, tạo ra / năng lượng cao nhất có thể. Trong QAOA, chi phí Hamilton, mà chúng tôi sẽ biểu thị là H_Cđược xây dựng theo cách này, mã hóa giải pháp cho một số vấn đề quan tâm (ví dụ: một phiên bản MaxCut hoặc MaxSAT) trong trạng thái năng lượng thấp nhất của nó. Đối với QAOA, chi phí Hamilton thường được xây dựng bằng cách sử dụng mô hình Ising , có thể được sử dụng để mã hóa các vấn đề tối ưu hóa tổ hợp dưới dạng Hamiltonians với Pauli-Z đơn qubitđiều kiện. Mặc dù chúng tôi sẽ không trình bày chi tiết việc xây dựng chi phí Hamiltonians với các mô hình Ising trong bài đăng này , nhưng bài báo này bao gồm chủ đề khá rộng rãi. Không giống như Hamilton chi phí, bộ trộn Hamilton không liên quan đến định nghĩa vấn đề và được định nghĩa như sau.

Trong phương trình trên, tất cả các sigmabiến tương ứng với ma trận Pauli-X qubit đơn trên iqubit -th. Một đặc tính quan trọng của máy trộn Hamilton là nó không nên đi chung với hamiltonian giá thành. Nếu các ma trận này không đi lại, thì chúng không thể chia sẻ bất kỳ eigenvectors nào, điều này ngăn cản QAOA ansatz (xem bên dưới) bị mắc kẹt ở trạng thái không tối ưu với năng lượng cao hơn.

Trạng thái ban đầu

Từ đây, chúng ta cũng phải xác định trạng thái lượng tử ban đầu được sử dụng trong QAOA, được đưa ra bên dưới.

Ở đây, zđược sử dụng để biểu thị cơ sở tính toán cho hệ thống lượng tử của chúng ta. Trạng thái ban đầu này cũng có thể được viết như sau (nghĩa là hai định nghĩa giống hệt nhau).

Như có thể thấy ở trên, trạng thái ban đầu trong QAOA chỉ đơn giản là sản phẩm của các trạng thái chồng chất cực đại trên mỗi qubit. Điều thú vị là trạng thái ban đầu này là giá trị đặc trưng tối đa của bộ trộn Hamilton - sẽ trở nên rõ ràng tại sao điều này lại quan trọng ở phần sau của bài viết. Ngoài ra, trạng thái này cực kỳ dễ xây dựng - chỉ cần áp dụng cổng Hadamard riêng biệt cho từng qubit trong hệ thống - điều này làm cho nó trở thành một lựa chọn mong muốn nếu QAOA nên được triển khai trên phần cứng lượng tử thực tế.

QAOA Ansatz

Bây giờ, chúng tôi đã xác định tất cả các thành phần liên quan của QAOA, nhưng vẫn chưa rõ làm thế nào các thành phần này có thể được kết hợp với nhau để giải quyết một vấn đề tối ưu hóa. Như đã đề cập trước đây, QAOA phát triển trạng thái ban đầu bằng cách sử dụng một loạt các cổng lượng tử tham số, trong đó mỗi cổng lượng tử được mô tả là phép nhân trạng thái lượng tử với một ma trận đơn nhất . Các cổng lượng tử luôn đơn nhất để đảm bảo rằng sự tiến hóa của trạng thái lượng tử là đoạn nhiệt và đặc tính chuẩn hóa của trạng thái lượng tử được bảo toàn. Sự phát triển của trạng thái ban đầu trong QAOA được mô tả bởi ansatz sau đây , nó tạo ra trạng thái cuối cùng (hy vọng) mã hóa một giải pháp gần như tối ưu cho vấn đề quan tâm.

Đây, betavà gammalà các tham số vô hướng, có giá trị thực. QAOA ansatz, chứa 2ptổng cộng các tham số, bao gồm một loạt các cổng đơn nhất xen kẽ với các tham số vô hướng khác nhau. Như có thể thấy, "độ sâu" của ansatz này là p, vì cấu trúc cổng xoay chiều được áp dụng pliên tục vào các thời điểm trạng thái ban đầu . Các ma trận đơn nhất phát triển trạng thái nội nguyên được xây dựng bằng cách lấy cấp số nhân của ma trậncủa chi phí và bộ trộn Hamiltonians (tức là, hàm mũ của ma trận hermitian luôn là đơn nhất). Do đó, QAOA, sử dụng ansatz ở trên, tạo ra một trạng thái lượng tử mới bằng cách áp dụng một loạt các cổng đơn nguyên tham số, dựa trên chi phí và bộ trộn hamiltonians, về trạng thái ban đầu. Nếu chúng ta muốn trạng thái cuối cùng này mã hóa một giải pháp cho vấn đề chúng ta quan tâm, tất cả những gì chúng ta phải làm là thiết lập betavà gammatham số sao cho đầu ra của QAOA là trạng thái năng lượng thấp của Hamilton. Nhưng… làm thế nào để chúng tôi tìm thấy các tham số chính xác?

Tối ưu hóa các tham số QAOA

Năng lượng kỳ vọng của trạng thái cuối cùng của chúng ta đối với giá trị Hamilton có thể được biểu thị như sau, trong đó Tr()biểu thị dấu vết của ma trận.

Giá trị kỳ vọng này có thể được tính toán trong thực tế bằng cách thực hiện các phép đo lặp lại, giống hệt nhau về trạng thái do QAOA ansatz tạo ra. Sau đó, sử dụng một máy tính cổ điển, gradient của hàm này có thể được tính toán (ví dụ: sử dụng quy tắc dịch chuyển tham số ), cho phép betavàgammacác tham số được cập nhật theo hướng giảm thiểu sự mong đợi đối với chi phí Hamilton. Bằng cách lặp đi lặp lại quá trình này, các tham số của ansatz QAOA được cập nhật sao cho năng lượng của trạng thái cuối cùng được giảm thiểu. Kết quả là, một giải pháp gần như tối ưu có thể được tạo ra bằng cách tạo ra trạng thái cuối cùng này và thực hiện phép đo liên quan đến cơ sở tính toán (nghĩa là, điều này có thể được thực hiện nhiều lần để đảm bảo tìm ra giải pháp tốt, do thực tế là các phép đo trong hệ lượng tử là ngẫu nhiên). Lưu ý rằng giải pháp do QAOA cung cấp là gần đúng và không được đảm bảo là tối ưu trên toàn cầu.

Thông tin cơ bản để hiểu QAOA

Bây giờ, chúng tôi hiểu QAOA là gì, nhưng động cơ đằng sau các thành phần của nó là không rõ ràng. Nếu bạn giống tôi, các cấu trúc trong QAOA có vẻ tùy ý, khiến bạn tự hỏi tại sao nó hoạt động và làm thế nào mà ai đó thậm chí đã nghĩ ra một thuật toán như vậy. Để làm rõ một số nhầm lẫn này, có một số thông tin cơ bản phải được hiểu, mà tôi muốn phác thảo trong phần này.

Ma trận lũy thừa

Mặc dù cấp số nhân ma trận đã được phác thảo ngắn gọn trong mô tả của QAOA, nhưng cũng đáng để phác thảo thêm một số thuộc tính chính của chúng, do mức độ liên quan của chúng với QAOA ansatz. Như đã nêu trước đây, hàm mũ của ma trận Hermitian luôn là đơn nhất. Trong thực tế, bất kỳ ma trận đơn nhất nào cũng có thể được viết dưới dạng sau.

đâu Hlà ma trận hermitian tùy ý, ilà đơn vị ảo và gammalà một tham số vô hướng tùy ý. Thông thường, các cổng lượng tử được xây dựng bằng cách thực hiện sự tiến hóa thời gian của một trạng thái lượng tử đối với một số Hamilton quan tâm. Sự tiến hóa thời gian như vậy có dạng một ma trận đơn nhất như hình dưới đây, trong đó hbiểu thị hằng số Planck.

Như được chứng minh bởi biểu thức trên, một mối liên hệ phức tạp tồn tại giữa sự tiến hóa của một trạng thái lượng tử và ma trận Hamilton (lũy thừa). Các cấp số nhân ma trận của Hamiltonians thường phát sinh như một cách để thực hiện sự tiến hóa thời gian của một trạng thái lượng tử trong một số hệ thống quan tâm. Ngoài ra, tham số vô hướng được sử dụng trong số mũ ma trận có thể được hiểu là tổng thời gian mà quá trình tiến hóa đó được thực hiện. Trong trường hợp QAOA, sự tiến hóa xảy ra đối với chi phí và bộ trộn Hamiltonians theo kiểu xen kẽ và chúng tôi thực hiện tối ưu hóa cổ điển để xác định thời điểm tối ưu mà mỗi cổng đơn nhất xen kẽ của chúng tôi được áp dụng.

Bên cạnh sự hình thành của chúng đối với sự phát triển của trạng thái lượng tử, có một tính chất nữa của hàm mũ ma trận sẽ hữu ích. Nếu hai ma trận giao hoán với nhau, thì thuộc tính sau của cấp số nhân ma trận là đúng.

Thuộc tính này trở nên phù hợp khi chúng ta thảo luận về Trotterization ở phần sau của bài đăng. Ngoài ra, dựa trên thuộc tính này, người ta có thể nhận thấy rằng thứ tự của các ma trận đơn nhất trong QAOA ansatz sẽ không liên quan nếu chi phí và bộ trộn Hamiltonians đi lại, do đó cung cấp thêm lý do về yêu cầu hai Hamiltonians không được đi lại.

Phương trình Schrödinger

Nó có vẻ giống như biểu thức trên cho sự tiến hóa thời gian đối với một số Hamilton, nhưng nó thực sự bắt nguồn từ phương trình Schrödinger - một phương trình vi phân riêng cực kỳ nổi tiếng để biểu thị các trạng thái lượng tử và cách chúng thay đổi theo thời gian. Có nhiều cách để viết phương trình này, nhưng với mục đích của bài đăng trên blog này, tôi sẽ trình bày nó như sau.

Ở đây, phương trình Schrödinger mô tả động lực học của một trạng thái lượng tử tại một thời điểm tđối với một số Hamilton H. Điều thú vị là, nếu không phụ Hthuộc thời gian (tức là Hamilton không thay đổi theo thời gian t), phương trình trên có thể được giải để mang lại kết quả sau.

Như có thể thấy, ma trận đơn nhất được đưa ra bởi phương trình Schrödinger để phát triển trạng thái lượng tử ban đầu theo thời gian tgiống với biểu thức được đưa ra trong phần trước.

Tại thời điểm này, có vẻ như việc xác định động lực học của một trạng thái lượng tử là khá dễ dàng - vấn đề là gì? Chà, vấn đề nảy sinh khi Hamilton được đề cập không độc lập về thời gian. Cụ thể, nếu Hamilton thay đổi theo thời gian tthì phương trình Schrödinger trở nên cực kỳ khó giải (đôi khi là không thể) để giải. Vì vậy, chúng ta phải tìm một giải pháp gần đúng của nó để phát triển một trạng thái lượng tử đối với một Hamilton phụ thuộc thời gian.

Sự tiến hóa gần đúng thông qua sự tiết chế theo thời gian

Vì vậy, làm thế nào để chúng tôi tìm thấy một giải pháp gần đúng như vậy? Chúng ta biết rằng sự phát triển của trạng thái lượng tử theo thời gian tcó thể được mô tả bằng một ma trận đơn nhất. Hãy để chúng tôi biểu thị ma trận đơn nhất này như được hiển thị bên dưới, nơi mà sự tiến hóa xảy ra theo thời t0gian t.

Thông thường, bước đầu tiên để ước lượng một thứ liên tục trong thời gian (chẳng hạn như ma trận đơn nhất được hiển thị ở trên) là chia nó thành các bước thời gian rời rạc có thể được kết hợp với nhau. Điều này được hiển thị bên dưới (lưu ý rằng tích của hai ma trận đơn nhất luôn là đơn nhất).

Việc tùy biến ma trận đơn nhất của chúng ta thành nhiều bước thời gian nhỏ hơn tương tự như việc tính gần đúng một hàm liên tục với nhiều thành phần từng mảnh. Cụ thể, khi số lượng bước thời gian rời rạc tăng lên, thì phép tính gần đúng sẽ trở nên chính xác hơn. Đi xa hơn, các ma trận đơn nhất cho mỗi bước thời gian rời rạc có thể được biểu diễn đối với một Hamilton phụ thuộc thời gian, như được hiển thị bên dưới.

Như có thể thấy ở trên, bằng cách thực hiện các bước rời rạc trong thời gian, chúng ta có thể ước tính sự tiến hóa theo thời gian liên tục đối với một Hamilton phụ thuộc thời gian bằng cách lặp đi lặp lại những việc sau: (1) lấy Hamilton vào một thời điểm cố định nào đó, (2) giả sử là Hamilton được cố định trong một khoảng thời gian ngắn, và (3) thực hiện quá trình tiến hóa đối với Hamilton cố định này trong một thời gian ngắn. Bằng cách thực hiện quá trình tiến hóa rời rạc như vậy trong khoảng thời gian rất ngắn, chúng tôi tạo ra một dãy các ma trận đơn nhất, khi kết hợp với nhau, xấp xỉ sự tiến hóa theo thời gian mong muốn đối với một Hamilton phụ thuộc thời gian.

Trotterization (Suzuki-Trotter Decomposition)

Sự tiết chế về thời gian đôi khi có thể không phải là thành phần bắt buộc duy nhất để tiến hóa gần đúng đối với một Hamilton phụ thuộc thời gian. Điều này là do Hamiltonians thường được biểu thị dưới dạng tổng của nhiều Hamiltonians không đi lại, tạo ra một biểu thức giống như biểu thức bên dưới.

Trong biểu thức trên, ma trận mũ không thể được phân tích thành tích của một số ma trận đơn nhất bởi vì mỗi thành phần của Hamilton không đi lại (tức là, nhớ lại tính chất cuối cùng từ phần giải thích trước về ma trận cấp số nhân). Kết quả là, chúng tôi gặp phải vấn đề sau.

Bởi vì việc triển khai một cổng lượng tử dựa trên tổng nhiều thành phần Hamilton không đi lại là điều khó khăn, các học viên thường dựa vào sự phân rã Suzuki-Trotter (tức là, thường được gọi là "Trotterization") để phân rã một biểu thức như vậy dưới dạng tích của nhiều ma trận đơn nhất. Sự phân hủy này có dạng như sau.

Sử dụng phép phân rã Suzuki-Trotter, đơn nguyên được giới thiệu ở đầu phần này có thể được tính gần đúng bằng một dãy lặp lại các cấp số nhân ma trận riêng biệt cho mỗi thành phần không đi lại của Hamilton. Sự phân rã như vậy giúp đơn giản hóa đáng kể việc triển khai ma trận đơn nhất này như một cổng lượng tử, điều này cực kỳ phù hợp với các thuật toán lượng tử thân thiện với NISQ như QAOA. Kết quả là, Trotterization phát sinh rất thường xuyên trong điện toán lượng tử.

Thuật toán đoạn nhiệt lượng tử

Bước cuối cùng để đạt được và hiểu sâu về QAOA là hiểu thuật toán mà từ đó nó được hình thành: thuật toán đoạn nhiệt lượng tử (QAA). QAA là một thuật toán ban đầu được đề xuất để tìm kiếm các giải pháp chính xác cho các vấn đề tối ưu hóa tổ hợp với việc sử dụng tiến hóa đoạn nhiệt. Ở cấp độ cao, QAA tương tự như QAOA, vì nó bắt đầu ở một số trạng thái ban đầu và phát triển trạng thái này để tạo ra trạng thái năng lượng thấp của một con hamiltonian giá rẻ. Tuy nhiên, QAA không phải là một thuật toán có thể được triển khai trên các thiết bị NISQ, vì nó đòi hỏi quá trình tiến hóa phải được thực hiện trong một thời gian (có thể) rất dài, vượt quá khả năng của phần cứng hiện tại.

Định lý đoạn nhiệt

QAA dựa trên định lý đoạn nhiệt của cơ học lượng tử. Cho một Hamilton phụ thuộc thời gian và một vật liệu điện tử năng lượng thấp của Hamilton đó tại thời điểm đó t0, định lý đoạn nhiệt phát biểu rằng, nếu trạng thái lượng tử được phát triển đủ chậm theo thời gian t, nó sẽ vẫn là trạng thái năng lượng thấp của Hamilton theo thời gian ( tức là, trạng thái kết quả sau khi tiến hóa là trạng thái năng lượng thấp của Hamilton của chúng ta tại thời điểmt0 + t). Định lý này dựa trên giả thiết rằng tồn tại một khoảng cách giữa hai giá trị riêng thấp nhất của Hamilton tại bất kỳ thời điểm nào. Ngoài ra, lượng thời gian cần thiết cho quá trình tiến hóa phụ thuộc vào khoảng cách này và có thể trở nên lớn tùy ý nếu khoảng cách nhỏ. Hơn nữa, giá trị của khoảng cách này nói chung không thể được ước tính, nên rất khó xác định tổng thời gian cần thiết để thực hiện một quá trình tiến hóa như vậy.

Giải quyết các vấn đề về tối ưu hóa với Định lý đoạn nhiệt

Dựa trên định lý đoạn nhiệt, QAA đưa ra đề xuất sau. Giả sử rằng chúng tôi có một số trường hợp vấn đề tối ưu hóa tổ hợp mà chúng tôi muốn giải quyết. Hãy nhớ từ mô tả trước của QAOA rằng chúng ta có thể mã hóa trường hợp vấn đề này trong một Hamilton chi phí, sao cho giải pháp cho vấn đề được đưa ra bởi trạng thái năng lượng thấp của Hamilton. Ngoài ra, hãy nhớ lại rằng bộ trộn Hamilton được xác định trước đó có trạng thái năng lượng thấp dễ xây dựng (tức là trạng thái ban đầu trong QAOA). Sau đó, giả sử chúng ta xác định Hamilton phụ thuộc thời gian sau đây, dựa trên chi phí và bộ trộn Hamilton được xác định trong mô tả của QAOA.

Với Hamilton phụ thuộc thời gian ở trên, chúng ta có thể dễ dàng xây dựng trạng thái năng lượng thấp tại thời điểm 0 (tức là nó chỉ là trạng thái năng lượng thấp của bộ trộn Hamilton). Ngoài ra, Hamilton phụ thuộc thời gian tại thời điểm T bằng giá trị Hamilton. Do đó, nếu chúng ta phát triển trạng thái nội nguyên này đủ lâu, cuối cùng chúng ta sẽ tạo ra trạng thái năng lượng thấp của giá trị Hamilton theo định lý đoạn nhiệt (nghĩa là chúng ta được đảm bảo một eigengap khác 0 theo định lý Perron-Frobenius ). Kết quả là, một sự tiến hóa như vậy tạo ra một giải pháp chính xác cho vấn đề chúng ta quan tâm!

Quay lại QAOA

Bây giờ chúng ta đã bao gồm thông tin cơ bản có liên quan, đã đến lúc quay lại QAOA và hiểu toàn diện hơn về động lực của nó. Đặc biệt, QAOA có thể được hiểu là một ước tính của QAA, có thể được rút ra bằng cách tận dụng các công cụ mà chúng ta đã thảo luận cho đến nay.

Từ QAA đến QAOA

Cả QAOA và QAA đều bắt đầu với cùng một trạng thái ban đầu (tức là trạng thái chồng chất bằng nhau) và cố gắng phát triển trạng thái ban đầu này để tạo ra trạng thái năng lượng thấp của Hamilton. Hãy xem xét Hamilton phụ thuộc thời gian sau đây, là phép nội suy giữa bộ trộn và giá trị Hamilton.

Như đã trình bày trước đây, việc thể hiện sự tiến hóa đối với một Hamilton phụ thuộc thời gian ở dạng đóng là rất khó. Vì vậy, chúng ta phải ước tính sự tiến hóa này bằng cách sử dụng các bước thời gian rời rạc, như được hiển thị bên dưới. Chúng tôi biểu thị đơn thể thể hiện chính xác sự tiến hóa của trạng thái lượng tử của chúng ta đối với Hamilton phụ thuộc thời gian cho thời gian tlà U.

trong đó Deltađại diện cho độ dài của mỗi khoảng thời gian rời rạc giữa thời gian 0 và t. Hơn nữa, mỗi thuật ngữ Hamilton phụ thuộc thời gian trong biểu thức trên có thể được biểu thị theo chi phí và bộ trộn Hamilton (từ thời điểm này trở đi, chỉ số hạng đầu tiên trong dãy được liệt kê để dễ đọc - các thuật ngữ khác theo cùng một mẫu).

Từ đây, chúng ta có thể thực hiện phép phân rã Suzuki-Trotter để đi đến biểu thức sau, trong đó chúng ta nhận pđược một số nguyên dương lớn. Nhớ lại rằng chi phí và máy trộn Hamiltonians không đi làm. Vì vậy, chúng ta bắt buộc phải thực hiện Trotterization để phân rã ma trận theo cấp số nhân theo cách này.

Điều này bắt đầu trông hơi quen thuộc… Bằng cách biểu thị các hằng số ở phía trước của mỗi Hamilton (không bao gồm các thành phần tưởng tượng) như betavà gamma, chúng ta đi đến biểu thức sau.

Vì vậy, sau khi phân tách quá trình tiến hóa của chúng ta thành các bước thời gian rời rạc và áp dụng Trotterization, chúng ta đi đến một biểu thức (gần như) chính xác giống với ansatz của chúng ta từ QAOA! Do đó, QAOA có thể được thúc đẩy như một sự xấp xỉ của QAA trong đó các tham số betavà gammakhông cố định và độ sâu pcó thể được đặt tùy ý! Về mặt trực quan, chất lượng của phép gần đúng này phải được cải thiện khi độ sâu của QAOA được tăng lên, vì sự phân hủy Suzuki-Trotter chỉ đúng trong giới hạn của vô hạn p. Điều thú vị là một số kết quả lý thuyết cho QAOA được suy ra bằng cách giả sử một ansatz có độ sâu vô hạn và vẽ các kết nối với QAA và định lý đoạn nhiệt.

Các điểm khác biệt quan trọng

Mặc dù QAOA có thể được hiểu là sự xấp xỉ của QAA, nhưng có một số điểm khác biệt quan trọng giữa các thuật toán này. Đầu tiên, QAOA là một thuật toán lượng tử biến thiên, chứa các mạch lượng tử tham số được tối ưu hóa theo kiểu cổ điển để đáp ứng một số mục tiêu. Ngược lại, các “tham số” tương ứng trong QAA được cố định dựa trên khoảng thời gian được sử dụng trong khoảng thời gian gần đúng của ma trận đơn nhất mã hóa sự tiến hóa phụ thuộc vào thời gian của trạng thái lượng tử. Do đó, QAOA không nhất thiết phải gần đúng với QAA, vì các tham số của nó có thể được đặt tùy ý và có thể không phản ánh các hằng số khoảng thời gian rời rạc phát sinh trong QAA. Ngoài ra, độ sâu của QAA có thể lớn tùy ý, trong khi độ sâu của ansatz QAOA thường nhỏ hơn nhiều để đáp ứng các hạn chế phần cứng lượng tử (tức làQAOA ansatz sâu nhất đã được triển khai thực tế chỉ có độ sâu là ba) - hãy nhớ rằng, QAOA là một thuật toán thực tế cho máy tính lượng tử thời NISQ. Do đó, mối liên hệ giữa các thuật toán QAOA thực tế và QAA trên thực tế khá hạn chế. Cuối cùng, QAOA tìm thấy một giải pháp gần đúng cho vấn đề quan tâm, trong khi QAA tìm ra giải pháp tối ưu toàn cầu cho đủ thời gian, khiến mục tiêu của hai thuật toán hơi khác nhau.

Phần kết luận

Trong bài đăng này, tôi đã cố gắng cung cấp sự hiểu biết tương đối toàn diện về QAOA từ đầu. Bằng cách cung cấp thông tin cơ bản có liên quan, tôi đã vẽ ra mối liên hệ giữa QAA và QAOA, tiết lộ rằng QAOA có thể được hiểu là một sự gần đúng của QAOA (mặc dù có sự khác biệt thực tế giữa hai thuật toán). Điều này làm sáng tỏ động lực cho các khía cạnh khác nhau của QAOA, chẳng hạn như sự lựa chọn bộ trộn Hamilton (tức là, bắt nguồn từ QAA) và cấu trúc đơn nhất xen kẽ (nghĩa là, có thể được hiểu là sự xấp xỉ rời rạc, được điều chỉnh của QAA).

Cảm ơn bạn đã đọc, và tôi hy vọng bạn thích bài viết. Nếu bạn tìm thấy bất kỳ lỗi hoặc có đề xuất, vui lòng liên hệ với tôi . Hơn nữa, nếu bạn quan tâm đến chủ đề này, tôi khuyên bạn nên xem phòng nghiên cứu của tôi tại Đại học Rice, nơi thực hiện các nghiên cứu liên quan đến nhiều chủ đề trong điện toán lượng tử.