Điểm:4

Bạn thực sự có thể bỏ qua số bước xử lý lượng tử cần thiết cho thuật toán của Shor không?

lá cờ gs

Câu trả lời cho câu hỏi Độ dài khóa RSA so với thuật toán của Shor đề nghị rằng ví dụ Mã hóa RSA 2048 bit sẽ bị phá vỡ một cách tầm thường với máy tính lượng tử 4099 qubit sử dụng thuật toán của Shor (việc triển khai thuật toán được biết đến nhiều nhất yêu cầu 2n+3 qubit).

Điều này có thực sự đúng không? Nếu tôi hiểu chính xác, số cổng (hoạt động lượng tử logic) cần thiết sẽ vào khoảng log(2^2048)^2Ãlog(log(2^2048))Ãlog(log(log(2^2048) )) là khoảng 2,9Ã10â·. Xem xét rằng ngay cả máy tính cổ điển cũng không thể thực hiện bất kỳ hoạt động nào với 2,9-10-cổng bằng cách sử dụng một phần dữ liệu đầu vào duy nhất, thực sự không hợp lý khi cho rằng một số lượng lớn cổng như vậy có thể được vận hành bởi máy tính lượng tử trong điều kiện không tầm thường. thời gian.

Tôi cho rằng để máy tính lượng tử thực hiện một bước thực thi thuật toán của Shor sẽ cần chuyển (về mặt logic) một đầu vào qua tất cả các cổng đó, tương tự như máy tính cổ điển thực thi đủ mã máy tính để chuyển một đầu vào 2048 bit qua 2.9Ã10â · cổng.Bởi vì thông tin không thể truyền đi nhanh hơn tốc độ ánh sáng và các cánh cổng có các chiều khác không, điều này không thể xảy ra trong thời gian tầm thường. Và nếu bạn sử dụng photon cho qubit trong máy tính lượng tử, bước sóng có thể đặt kích thước tối thiểu cho một cổng bất kể khả năng sản xuất.

Và nếu bạn cần bất kỳ sửa lỗi nào giữa các cổng, điều đó sẽ cần thêm dung lượng và do đó cũng làm tăng độ trễ.

Ngoài ra, nếu tôi hiểu đúng, để thực sự tính các số lớn bằng thuật toán của Shor, bạn cần sử dụng máy tính cổ điển để tạo dự đoán ngẫu nhiên và thuật toán của Shor sau đó sẽ sử dụng dự đoán đó để có thể tạo ra dữ liệu cần tính toán các thừa số. Bạn thực sự cần bao nhiêu lần đoán trung bình cho các số bao thanh toán được sử dụng trong RSA 2048 bit?

Đã có nghiên cứu về thời gian chạy thực tế tiềm năng của một máy tính lượng tử vật lý lớn đang cố gắng thực hiện thuật toán Shor để phân tích số lượng lớn chưa? Điều đó có thực sự hỗ trợ cho việc giải thích rằng bạn có thể bỏ qua thời gian xử lý bất kể kích thước của các con số không?

lá cờ us
Theo hiểu biết của tôi, chúng tôi có thể giải quyết vấn đề với khoảng 50 q-bit, thậm chí không phải là câu hỏi về thời gian chạy. Nếu bạn tra cứu "vấn đề đo lường" trong trao đổi vật lý, bạn có thể kết luận rằng ngay cả định nghĩa vấn đề cũng thuộc về con mèo của schrödinger.
lá cờ jp
"ngay cả máy tính cổ điển cũng không thể thực hiện bất kỳ thao tác nào với cổng 2,9Ã10â· bằng cách sử dụng một phần dữ liệu đầu vào"? Gì? Vâng, họ có thể! Trong một vài phần nghìn giây!
lá cờ jp
Có lẽ máy tính lượng tử đầu tiên làm được điều đó sẽ không nhanh lắm, nên có thể sẽ mất một tuần, một tháng hoặc một năm thay vì vài mili giây. Điều đó vẫn nhanh hơn rất nhiều so với "mãi mãi"
lá cờ gs
@ user253751 Tôi đồng ý rằng các máy tính hiện đại có thể thực hiện các hoạt động làm việc với các cổng 2.9Ã10â· trong thời gian rất ngắn bằng cách thực hiện đủ lệnh theo chuỗi. Điều này xảy ra ngay sau đó vì các CPU hiện đại có thể chạy tối đa 5Ã10â¹ lệnh mỗi giây trên mỗi lõi. Ý tôi là không có hướng dẫn SIMD nào có thể chạy với cổng (bóng bán dẫn) cao như vậy được tính là một hoạt động đơn lẻ, điều đó có nghĩa là việc thực hiện nối tiếp các hoạt động riêng lẻ sẽ là một yếu tố hạn chế quan trọng.
Điểm:3
lá cờ my

Tôi cho rằng để máy tính lượng tử thực hiện một bước, thực thi thuật toán của Shor sẽ cần chuyển (về mặt logic) một đầu vào qua tất cả các cổng đó

Bạn hiểu sai những gì đang được đo bằng 'hoạt động cổng'. Máy tính lượng tử sẽ không có $2,9 \times 10^7$ cổng (và tất cả dữ liệu được đặt lặp đi lặp lại thông qua bộ cổng đó).

Thay vào đó, Máy tính lượng tử sẽ cần thực hiện tổng cộng $2,9 \times 10^7$ hoạt động cổng; rõ ràng, không cần phải thực hiện tất cả chúng đồng thời (và trên thực tế, với Shor's, chúng ta không thể, cả hai vì định lý không nhân bản cấm tạo các bản sao của Qubit để gửi đến các cổng độc lập và vì lý do thực dụng hơn mà đầu vào của một số thao tác cổng phụ thuộc vào các thao tác cổng trước đó).

Đối với làm thế nào những $2,9 \times 10^7$ các hoạt động của cổng được ánh xạ tới các cổng phần cứng, rất khó có khả năng chúng ta sẽ có $2,9 \times 10^7$ cổng vật lý; một số cổng phần cứng có khả năng được sử dụng lại nhiều lần trong quá trình tính toán (giống như khi một máy tính cổ điển thực hiện thao tác RSA, các cổng giống nhau được sử dụng lại để thực hiện các thao tác nhân mô-đun khác nhau).

Và nếu bạn cần bất kỳ sửa lỗi nào giữa các cổng, điều đó sẽ cần thêm dung lượng và do đó cũng làm tăng độ trễ.

Vâng chúng tôi biết; các $2,9 \times 10^7$ hình trên phản ánh các qubit logic; điều đó sẽ chuyển thành một số lượng qubit vật lý lớn hơn - quy mô của mức tăng sẽ phụ thuộc vào mã sửa lỗi lượng tử được sử dụng (điều này sẽ phụ thuộc vào, trong số những thứ khác, tỷ lệ lỗi thực tế của các hoạt động của qubit vật lý).

Bạn thực sự cần bao nhiêu lần đoán trung bình cho các số bao thanh toán được sử dụng trong RSA 2048 bit?

Với xác suất cực cao, một. Máy tính lượng tử tìm thấy thứ tự của $g$ modulo $n$, tức là giá trị $x$ ở đâu $g^x \equiv 1 \bmod n$. Trừ khi lệnh của $g$ đối với cả hai $p$$q$ (các thừa số nguyên tố) nhỏ bất thường (có thể chỉ xảy ra với xác suất rất nhỏ nếu $g$ được chọn ngẫu nhiên), giá trị đó của $x$ có thể được sử dụng để nhanh chóng yếu tố.

lá cờ gs
Thông tin tuyệt vời! Tất cả những điều này có thể được tóm tắt như sau? Với một máy tính lượng tử có 4099 qubit, khóa RSA 2048 bit có thể bị phá vỡ với 2,9 đô la \times 10^7$ hoạt động tại cổng và thiết lập tổng thời gian tính toán cần thiết. Thời gian tường thực tế cần thiết được xác định bởi tốc độ đồng hồ hướng dẫn trung bình hiệu quả của máy tính này để thực hiện các thao tác đó.
lá cờ gs
Theo https://quantumcomputing.stackexchange.com/a/2404/18991, có vẻ như máy tính lượng tử có thể chạy khoảng 5 triệu phép tính mỗi giây nên tổng thời gian tính toán cần thiết sẽ chỉ khoảng 6 giây! Vì vậy, nếu số lượng qubit thực sự có thể tăng lên hàng nghìn mà không làm chậm các hoạt động riêng lẻ, thì tốc độ thực thi phải đủ tốt để không phải là yếu tố hạn chế trong thực tế.

Đăng câu trả lời

Hầu hết mọi người không hiểu rằng việc đặt nhiều câu hỏi sẽ mở ra cơ hội học hỏi và cải thiện mối quan hệ giữa các cá nhân. Ví dụ, trong các nghiên cứu của Alison, mặc dù mọi người có thể nhớ chính xác có bao nhiêu câu hỏi đã được đặt ra trong các cuộc trò chuyện của họ, nhưng họ không trực giác nhận ra mối liên hệ giữa câu hỏi và sự yêu thích. Qua bốn nghiên cứu, trong đó những người tham gia tự tham gia vào các cuộc trò chuyện hoặc đọc bản ghi lại các cuộc trò chuyện của người khác, mọi người có xu hướng không nhận ra rằng việc đặt câu hỏi sẽ ảnh hưởng—hoặc đã ảnh hưởng—mức độ thân thiện giữa những người đối thoại.