Bộ giải đại số tuyến tính cổ điển có thể thực hiện các thuật toán lượng tử với tốc độ tương tự không?
Một thuật toán lượng tử bắt đầu với một đăng ký các qubit ở trạng thái ban đầu, một toán tử đơn nhất (thuật toán) thao tác trạng thái của các qubit đó, và sau đó trạng thái của các qubit được đọc ra (hoặc ít nhất một số thông tin về trạng thái trên một đơn vị chạy của thuật toán).
Đối với tôi, dường như một máy tính lượng tử trả lời câu hỏi về các hành động đơn nhất trên trạng thái lượng tử. Đây "chỉ là" một vấn đề của đại số tuyến tính. Do đó, tôi thấy ngạc nhiên rằng máy tính lượng tử có thể được coi là máy tính đại số tuyến tính.
Tại sao chúng ta cần cơ học lượng tử? Chúng ta không thể tìm thấy một hệ thống cổ điển thực hiện các phép toán đại số tuyến tính và sử dụng hệ thống này để thực hiện các thuật toán đã được thiết kế cho máy tính lượng tử? Tất nhiên máy tính kỹ thuật số cổ điển sẽ không đủ, những máy này dựa trên xử lý nhị phân của thông tin chứ không phải là thao tác với các vectơ trong không gian chiều cao.
Câu hỏi: Có ứng cử viên nào cho bộ giải đại số tuyến tính cổ điển (máy tính tương tự cổ điển) có thể thực hiện các thuật toán "máy tính lượng tử" giúp tăng tốc độ tương tự so với máy tính cổ điển kỹ thuật số không?
Câu hỏi 2: Có lẽ tôi đã quá đơn giản hóa bằng cách giảm một máy tính lượng tử thành một máy giải đại số tuyến tính. Đây có phải là trường hợp? Tôi đang đề cập đến sự phức tạp nào?
Trả lời
Sự phức tạp mà bạn đang đề cập là trong trường hợp chung, bạn cần lưu trữ $2^n$ biên độ phức tạp để thậm chí đại diện cho một $n$hệ thống qubit cổ điển. Do đó, đối với một máy tính lượng tử, giả sử bạn cần lưu trữ 1000 qubit$2^{1000}$biên độ phức tạp. Ngay cả khi bạn sử dụng một nguyên tử trên mỗi biên độ để làm điều này, bạn vẫn sử dụng hết nguyên tử trong vũ trụ quan sát được.
Theo tôi được biết, trên đây là lý luận chung. Tuy nhiên, vẫn có thể có những cách để biểu diễn các thuật toán lượng tử nhất định theo cách cổ điển có thể kiểm soát được bằng cách sử dụng một số thông tin chi tiết thông minh để tiết kiệm nhu cầu biểu diễn của thuật toán, do đó đi xuống dưới$2^n$yêu cầu. Nhưng điều này có thể là vấn đề cụ thể và không có khả năng hoạt động trong trường hợp chung.
Theo tuyên bố của câu hỏi về tính toán kỹ thuật số so với tương tự, có những chủ đề khác trên trang web này đã hỏi về các đề xuất tương tự. Xem, ví dụ, ở đây , và ở đây . Trong số những thứ khác, các hệ thống tương tự cổ điển không thể vướng vào; do đó việc ghi lại một máy tính lượng tử như một máy tính tương tự sẽ không dẫn đến tốc độ tăng nhanh như quan sát được.
Tuy nhiên, đối với câu trả lời của @Attila Kun, có những vấn đề cụ thể trong đại số tuyến tính / máy học có các thuật toán lượng tử nhanh nhưng đã được đúc lại thành các thuật toán cổ điển có tốc độ tương tự.
Ví dụ: vấn đề đề xuất được Netflix / Amazon / v.v. sử dụng. có một thuật toán nhanh trên máy tính lượng tử. Thuật toán này cho thấy sự cải thiện theo cấp số nhân so với thuật toán cổ điển nổi tiếng nhất (khi đó).
Tuy nhiên, trong nỗ lực chứng minh rằng thuật toán lượng tử thực sự vượt trội, E. Tang đã chỉ ra rằng thực sự có một "hệ thống cổ điển thực hiện các phép toán đại số tuyến tính và sử dụng [các] này để thực hiện các thuật toán được thiết kế cho máy tính lượng tử".
Công việc của Tang đã khởi động chương trình dequantization - tức là thiết kế lại các thuật toán lượng tử nhanh trong đại số tuyến tính / máy học như các thuật toán cổ điển nhanh. Một bài báo trên Tạp chí Quanta mô tả vấn đề và cách tiếp cận của Tang.
Những vấn đề nào có thể giải quyết được đối với việc dequantization này là một lĩnh vực nghiên cứu tích cực, như chủ đề này thảo luận. Điều này có thể phụ thuộc vào thứ hạng của ma trận được xem xét.