Buzz
Năm 1935, Albert Einstein, cùng với Boris Podolsky và Nathan Rosen, đối mặt với một khả năng được tiết lộ bởi các định luật vật lý lượng tử mới: rằng hai hạt có thể bị liên kết, hoặc tương quan, ngay cả qua những khoảng cách rất lớn.
Ngay trong năm tiếp theo, Alan Turing đề xuất lý thuyết tổng quát đầu tiên về máy tính và chứng minh rằng tồn tại một vấn đề mà máy tính sẽ không bao giờ có thể giải quyết được.
Hai ý tưởng này đã làm cách mạng hóa lĩnh vực chuyên ngành của chúng. Họ cũng dường như không có liên quan gì đến nhau. Nhưng bây giờ, một bằng chứng quan trọng đã kết hợp chúng trong khi giải quyết một loạt các vấn đề mở trong tin học, vật lý và toán học.
Bằng chứng mới này xác định rằng máy tính lượng tử tính toán với các bit hoặc qubit lượng tử liên kết, thay vì các bit cổ điển 1 và 0, có thể được sử dụng lý thuyết để xác minh câu trả lời cho một bộ vấn đề vô cùng lớn. Sự tương ứng giữa sự liên kết và việc tính toán đã khiến nhiều nghiên cứu viên bất ngờ.
“Đó là một điều hoàn toàn bất ngờ,” nói Miguel Navascués, người nghiên cứu vật lý lượng tử tại Viện Quang học và Thông tin Lượng tử ở Vienna.
Các tác giả của bằng chứng đã quyết định xác định giới hạn của một phương pháp để xác minh câu trả lời cho vấn đề tính toán. Phương pháp đó liên quan đến sự liên kết. Bằng cách tìm ra giới hạn đó, các nhà nghiên cứu đã giải quyết hai vấn đề khác gần như như một sản phẩm phụ: vấn đề Tsirelson trong vật lý, về cách mô phỏng toán học sự liên kết, và một vấn đề liên quan trong toán học thuần túy gọi là giả thiết nhúng của Connes.
Cuối cùng, kết quả lan tỏa như những chiếc domino.
“Các ý tưởng đều đến từ cùng một thời điểm. Thật tuyệt vời khi chúng quay lại với nhau một cách ấn tượng như vậy,” nói Henry Yuen của Đại học Toronto, một trong những tác giả của bằng chứng, cùng với Zhengfeng Ji của Đại học Công nghệ Sydney, Anand Natarajan và Thomas Vidick của Viện Công nghệ California, và John Wright của Đại học Texas, Austin. Cả năm nghiên cứu viên đều là những nhà khoa học máy tính.
Vấn Đề Không Thể Giải
Turing định nghĩa một khung cơ bản để suy nghĩ về tính toán trước khi máy tính thực sự tồn tại. Gần như cùng một lúc, ông chứng minh rằng có một vấn đề cụ thể mà máy tính không thể giải quyết được theo cách có thể chứng minh được. Nó liên quan đến việc liệu một chương trình có bao giờ dừng lại không.
Thường, các chương trình máy tính nhận đầu vào và tạo ra đầu ra. Nhưng đôi khi chúng bị mắc kẹt trong vòng lặp vô hạn và quay mãi không ngừng. Khi điều đó xảy ra ở nhà, chỉ còn một điều duy nhất còn lại để làm.
“Bạn phải chấm dứt chương trình bằng tay. Đơn giản là ngắt nó đi,” Yuen nói.
Turing chứng minh rằng không có thuật toán đa năng nào có thể xác định được liệu một chương trình máy tính sẽ dừng lại hay chạy mãi mãi. Bạn phải chạy chương trình để biết.
“Bạn đã đợi một triệu năm và một chương trình vẫn chưa dừng lại. Liệu bạn chỉ cần đợi thêm 2 triệu năm nữa không? Không cách nào biết được,” nói William Slofstra, một nhà toán học tại Đại học Waterloo.
Trong thuật ngữ kỹ thuật, Turing đã chứng minh rằng vấn đề dừng này không thể giải quyết được — thậm chí máy tính mạnh mẽ nhất có thể tưởng tượng cũng không thể giải quyết được nó.
Sau Turing, những nhà khoa học máy tính bắt đầu phân loại các vấn đề khác nhau theo độ khó của chúng. Những vấn đề khó đòi hỏi nhiều tài nguyên tính toán hơn để giải quyết — thêm thời gian chạy, thêm bộ nhớ. Điều này là nghiên cứu về độ phức tạp tính toán.
Cuối cùng, mỗi vấn đề đều đặt ra hai câu hỏi lớn: “Nó khó giải quyết đến mức nào?” và “Nó khó xác minh rằng một câu trả lời là đúng không?”
Thẩm vấn để Xác minh
Khi vấn đề đơn giản, bạn có thể tự kiểm tra câu trả lời. Nhưng khi chúng trở nên phức tạp hơn, thậm chí việc kiểm tra một câu trả lời cũng có thể là một nhiệm vụ overwhelming. Tuy nhiên, vào năm 1985, các nhà khoa học máy tính nhận ra có thể phát triển niềm tin vào việc một câu trả lời là đúng ngay cả khi bạn không thể xác nhận nó bằng chính mình.
Phương pháp này tuân theo logic của một cuộc thẩm vấn của cảnh sát.
Nếu một nghi phạm kể một câu chuyện phức tạp, có thể bạn không thể ra khỏi thế giới để xác nhận từng chi tiết. Nhưng bằng cách đặt câu hỏi đúng, bạn có thể bắt gặp nghi phạm nói dối hoặc phát triển niềm tin rằng câu chuyện là chính xác.
Trong thuật ngữ máy tính, hai bên trong một cuộc thẩm vấn là một máy tính mạnh mẽ đề xuất một giải pháp cho một vấn đề — được biết đến là người chứng minh — và một máy tính ít mạnh mẽ muốn đặt câu hỏi cho người chứng minh để xác định xem câu trả lời có đúng không. Máy tính thứ hai này được gọi là người xác minh.
Để lấy một ví dụ đơn giản, hãy tưởng tượng bạn là một người mù màu và người khác — người chứng minh — tuyên bố hai viên bi là màu khác nhau. Bạn không thể kiểm tra tuyên bố này một mình, nhưng thông qua cuộc thẩm vấn khéo léo, bạn vẫn có thể xác định xem nó có đúng không.
Đặt hai viên bi sau lưng và trộn chúng lên. Sau đó, hỏi người chứng minh cho bạn biết viên nào là viên nào. Nếu chúng thực sự có màu khác nhau, người chứng minh nên trả lời đúng câu hỏi mỗi lần. Nếu các viên bi thực sự có màu giống nhau — có nghĩa là chúng trông giống nhau — người chứng minh sẽ đoán sai một nửa thời gian.
“Nếu tôi thấy bạn thành công nhiều hơn nửa thời gian, tôi khá chắc chắn rằng chúng không” có cùng màu, Vidick nói.
Bằng cách đặt câu hỏi cho người chứng minh, bạn có thể xác minh các giải pháp cho một loại vấn đề rộng lớn hơn so với việc bạn làm tự mình.
Năm 1988, các nhà khoa học máy tính xem xét xảy ra gì khi hai người chứng minh đề xuất giải pháp cho cùng một vấn đề. Sau tất cả, nếu bạn có hai nghi phạm để thẩm vấn, việc giải quyết một tội ác, hoặc xác minh một giải pháp, càng dễ dàng, vì bạn có thể chơi họ lẫn nhau.
“Nó mang lại nhiều đòn bẩy hơn cho người xác minh. Bạn thẩm vấn, đặt câu hỏi liên quan, kiểm tra câu trả lời,” Vidick nói. Nếu những nghi phạm nói đúng sự thật, phản ứng của họ nên phù hợp hầu hết thời gian. Nếu họ nói dối, các câu trả lời sẽ xung đột nhiều hơn.
Tương tự, các nghiên cứu đã chỉ ra rằng bằng cách thẩm vấn hai người chứng minh riêng biệt về câu trả lời của họ, bạn có thể nhanh chóng xác minh giải pháp cho một lớp vấn đề ngay cả lớn hơn so với khi bạn chỉ có một người chứng minh để thẩm vấn.
Độ phức tạp tính toán có vẻ hoàn toàn lý thuyết, nhưng nó cũng liên quan chặt chẽ đến thế giới thực. Những nguồn lực mà máy tính cần để giải quyết và xác minh vấn đề — thời gian và bộ nhớ — là vật lý cơ bản. Vì lý do này, những khám phá mới trong vật lý có thể thay đổi độ phức tạp tính toán.
“Nếu bạn chọn một bộ vật lý khác nhau, chẳng hạn như lượng tử thay vì cổ điển, bạn sẽ có một lý thuyết phức tạp khác,” Natarajan nói.
Bằng chứng mới là kết quả cuối cùng của những nhà khoa học máy tính thế kỷ 21 đối mặt với một trong những ý tưởng kỳ lạ nhất của vật lý thế kỷ 20: sự liên kết.
Giả thiết Nhúng Connes
Khi hai hạt bị liên kết, chúng thực sự không ảnh hưởng đến nhau — chúng không có mối quan hệ nhân quả. Einstein và các đồng tác giả của ông đã phát triển ý tưởng này trong bài báo năm 1935 của họ. Sau đó, các nhà vật lý học và toán học cố gắng tìm ra một cách toán học để mô tả ý nghĩa thực sự của sự liên kết.
Tuy nhiên, sự cố gắng này hơi lẫn lộn. Các nhà khoa học đã đưa ra hai mô hình toán học khác nhau cho sự liên kết — và không rõ liệu chúng có tương đương với nhau hay không.
Một cách vòng vo, sự không nhất quán này cuối cùng đã tạo ra một vấn đề quan trọng trong toán học thuần túy được gọi là giả thiết nhúng Connes. Cuối cùng, nó cũng là một khe nứt mà năm nhà khoa học máy tính đã tận dụng trong bằng chứng mới của họ.
Cách đầu tiên để mô phỏng sự liên kết là nghĩ về các hạt như là cách ly không gian từ nhau. Một cái ở Trái Đất, ví dụ, và cái kia ở Sao Hỏa; khoảng cách giữa chúng là điều ngăn chặn nhân quả. Điều này được gọi là mô hình tích tensor.
Nhưng trong một số tình huống, không hoàn toàn rõ ràng khi nào hai thứ là độc lập nhân quả với nhau. Vì vậy, các nhà toán học đã đưa ra một cách thứ hai, tổng quát hơn, để mô tả sự độc lập nhân quả.
Khi thứ tự thực hiện hai thao tác không ảnh hưởng đến kết quả, các thao tác “commute”: 3 x 2 giống như 2 x 3. Trong mô hình thứ hai này, các hạt được liên kết khi các tính chất của chúng tương quan nhưng thứ tự thực hiện các đo lường không quan trọng: Đo lường hạt A để dự đoán động lượng của hạt B hoặc ngược lại. Bằng cách nào, bạn cũng nhận được cùng một câu trả lời. Điều này được gọi là mô hình toán tử commuting của sự liên kết.
Cả hai mô tả về sự liên kết đều sử dụng các mảng số được tổ chức thành các hàng và cột được gọi là ma trận. Mô hình tích tensor sử dụng ma trận với số hàng và cột hữu hạn. Mô hình toán tử commuting sử dụng một đối tượng tổng quát hơn, hoạt động giống như một ma trận với số hàng và cột vô hạn.
Theo thời gian, các nhà toán học bắt đầu nghiên cứu những ma trận này như là các đối tượng đặc biệt, hoàn toàn riêng biệt từ bất kỳ liên kết nào với thế giới vật lý. Trong quá trình này, một nhà toán học tên là Alain Connes đặt ra giả thiết vào năm 1976 rằng có thể xấp xỉ nhiều ma trận vô hạn chiều bằng các ma trận có số hàng và cột hữu hạn. Điều này là một hậu quả của giả thiết nhúng Connes.
Thập kỷ tiếp theo, một nhà vật lý tên là Boris Tsirelson đưa ra một phiên bản của vấn đề đưa nó trở lại với vật lý. Tsirelson giả thiết rằng mô hình tích tensor và mô hình toán tử commuting của sự liên kết có độ tương đương khoảng. Điều này có ý nghĩa, vì lý thuyết là hai cách khác nhau để mô tả cùng một hiện tượng vật lý. Công việc tiếp theo đã chỉ ra rằng do mối liên kết giữa ma trận và các mô hình vật lý sử dụng chúng, giả thiết nhúng Connes và vấn đề của Tsirelson gợi ý lẫn nhau: Giải một, bạn sẽ giải quyết cả hai.
Tuy nhiên, giải pháp cho cả hai vấn đề cuối cùng lại đến từ một nơi thứ ba hoàn toàn.
Vật Lý Trò Chơi Truyền Hình
Trong những năm 1960, một nhà vật lý tên là John Bell đưa ra một kiểm tra để xác định liệu sự liên kết có phải là một hiện tượng vật lý thực sự, chứ không chỉ là một khái niệm lý thuyết. Kiểm tra này liên quan đến một loại trò chơi, kết quả của nó cho thấy liệu có điều gì đó hơn ngoại trừ vật lý thông thường, không phải lượng tử, đang hoạt động.
Những nhà khoa học máy tính sau này nhận ra rằng kiểm tra này về sự liên kết cũng có thể được sử dụng như một công cụ để xác minh câu trả lời cho những vấn đề rất phức tạp.
Nhưng trước hết, để hiểu cách trò chơi hoạt động, hãy tưởng tượng hai người chơi, Alice và Bob, và một lưới 3x3. Một trọng tài giao cho Alice một hàng và bảo cô nhập 0 hoặc 1 vào mỗi ô sao cho tổng các chữ số là số lẻ. Bob nhận được một cột và phải điền vào sao cho tổng là số chẵn. Họ thắng nếu họ đặt cùng một số ở vị trí nơi hàng của cô và cột của anh chồng lấp. Họ không được phép giao tiếp.
Dưới điều kiện bình thường, điều tốt nhất mà họ có thể làm là thắng 89% trong số các lần. Nhưng dưới điều kiện lượng tử, họ có thể làm tốt hơn.
Tưởng tượng Alice và Bob chia một cặp hạt bị liên kết. Họ thực hiện các đo lường trên các hạt của họ và sử dụng kết quả để quyết định việc viết số 1 hoặc 0 vào mỗi ô. Bởi vì các hạt được liên kết, kết quả của các đo lường của họ sẽ tương quan, điều này có nghĩa là câu trả lời của họ cũng sẽ tương quan — có nghĩa là họ có thể thắng trò chơi 100% trong số các lần.
Vì vậy, nếu bạn thấy hai người chơi chiến thắng trò chơi với tỷ lệ cao không ngờ, bạn có thể kết luận rằng họ đang sử dụng cái gì đó khác với vật lý cổ điển để có lợi thế. Những thí nghiệm kiểu Bell này hiện được gọi là trò chơi 'nonlocal', để tham chiếu đến sự tách biệt giữa các người chơi. Các nhà vật lý thực sự thực hiện chúng trong phòng thí nghiệm.
“Mọi người đã thực hiện các thí nghiệm qua các năm thực sự chỉ ra điều kỳ quái này là thực sự,” nói Yuen.
Như khi phân tích bất kỳ trò chơi nào, bạn có thể muốn biết người chơi có thể chiến thắng trò chơi 'nonlocal' bao nhiêu lần, miễn là họ chơi tốt nhất có thể. Ví dụ, với solitaire, bạn có thể tính toán xem người chơi chơi hoàn hảo có khả năng thắng bao nhiêu lần.
Nhưng vào năm 2016, William Slofstra chứng minh rằng không có thuật toán chung nào để tính toán xác định xác suất chiến thắng tối đa chính xác cho tất cả các trò chơi 'nonlocal'. Vì vậy, các nhà nghiên cứu tự hỏi: Ít nhất bạn có thể ước lượng được tỷ lệ chiến thắng tối đa không?
Các nhà khoa học máy tính đã tập trung vào một câu trả lời bằng cách sử dụng hai mô hình mô tả sự liên kết. Một thuật toán sử dụng mô hình tích tensor thiết lập một sàn, hoặc giá trị tối thiểu, về xác suất chiến thắng tối đa xấp xỉ cho tất cả các trò chơi 'nonlocal'. Một thuật toán khác, sử dụng mô hình toán tử commuting, thiết lập một trần.
Những thuật toán này tạo ra những câu trả lời chính xác hơn mỗi khi chúng chạy lâu hơn. Nếu dự đoán của Tsirelson đúng và hai mô hình thực sự tương đương, sàn và trần nên tiếp tục chật lại gần nhau, hẹp về một giá trị duy nhất cho tỷ lệ chiến thắng tối đa xấp xỉ.
Nhưng nếu dự đoán của Tsirelson là sai và hai mô hình không tương đương, “trần và sàn sẽ mãi mãi được giữ cách xa nhau,” Yuen nói. Sẽ không cách nào tính toán được thậm chí một tỷ lệ chiến thắng xấp xỉ cho các trò chơi 'nonlocal'.
Trong công việc mới của họ, năm nhà nghiên cứu đã sử dụng câu hỏi này — về việc liệu trần và sàn có hội tụ và vấn đề của Tsirelson có đúng hay sai — để giải quyết một câu hỏi khác về khi nào có thể xác minh câu trả lời cho một vấn đề tính toán.
Hỗ Trợ Liên Kết
Vào đầu những năm 2000, các nhà khoa học máy tính bắt đầu tự hỏi: Làm thế nào nó thay đổi phạm vi các vấn đề bạn có thể xác minh nếu bạn thẩm vấn hai người chứng minh chia sẻ các hạt bị liên kết?
Hầu hết mọi người cho rằng liên kết làm việc ngược lại với việc xác minh. Sau tất cả, hai nghi can sẽ dễ dàng hơn để kể một câu nói dối nhất quán nếu họ có một phương tiện để phối hợp câu trả lời của họ.
Nhưng trong những năm gần đây, các nhà khoa học máy tính đã nhận ra rằng ngược lại là đúng: Bằng cách thẩm vấn những người chứng minh chia sẻ các hạt bị liên kết, bạn có thể xác minh một loạt lớn vấn đề hơn so với việc không có liên kết.
“Liên kết là một cách để tạo ra sự tương quan mà bạn nghĩ có thể giúp họ nói dối hoặc gian lận,” Vidick nói. “Nhưng thực sự bạn có thể sử dụng điều đó vào lợi ích của mình.”
Để hiểu cách đó, trước hết bạn cần nắm vững quy mô hầu như siêu nhiên của những vấn đề mà bạn có thể xác minh thông qua quy trình tương tác này.
Hãy tưởng tượng một đồ thị—một tập hợp các điểm (đỉnh) được kết nối bởi các đoạn đường (cạnh). Bạn có thể muốn biết liệu có thể tô màu các đỉnh bằng ba màu, sao cho không có đỉnh nào được kết nối bởi một cạnh có màu giống nhau. Nếu có thể, đồ thị đó là 'ba-màu'.
Nếu bạn đưa một cặp người chứng minh bị liên kết một đồ thị rất lớn, và họ báo cáo rằng nó có thể được tô màu bằng ba màu, bạn sẽ tự hỏi: Liệu có cách nào để xác minh câu trả lời của họ không?
Đối với các đồ thị rất lớn, sẽ không thể kiểm tra công việc trực tiếp. Thay vào đó, bạn có thể yêu cầu mỗi người chứng minh cho bạn biết màu của một trong hai đỉnh kết nối. Nếu họ mỗi lần bạn hỏi đều báo cáo một màu khác nhau, và họ tiếp tục làm như vậy, bạn sẽ có niềm tin rằng tô màu ba màu thực sự hoạt động.
Nhưng thậm chí chiến lược thẩm vấn này cũng thất bại khi đồ thị trở nên rất lớn—với nhiều cạnh và đỉnh hơn cả số nguyên tử trong vũ trụ. Ngay cả việc đặt một câu hỏi cụ thể (“Hãy nói cho tôi biết màu của đỉnh XYZ”) cũng là điều quá khả năng của bạn, người xác minh: Lượng dữ liệu cần thiết để đặt tên một đỉnh cụ thể nhiều hơn bạn có thể giữ trong bộ nhớ làm việc của mình.
Nhưng sự liên kết làm cho việc người chứng minh đưa ra câu hỏi tự nảy sinh.
“Người xác minh không cần tính toán câu hỏi. Người xác minh buộc người chứng minh tính toán câu hỏi cho họ,” Wright nói.
Người xác minh muốn người chứng minh báo cáo màu của các đỉnh được kết nối. Nếu các đỉnh không kết nối, thì câu trả lời cho các câu hỏi sẽ không nói lên điều gì về việc đồ thị có thể tô màu ba màu hay không. Nói cách khác, người xác minh muốn người chứng minh đặt ra các câu hỏi tương quan: Một người chứng minh hỏi về đỉnh ABC và người kia hỏi về đỉnh XYZ. Hi vọng là hai đỉnh được kết nối với nhau, ngay cả khi không có người chứng minh nào biết đỉnh nào người kia đang nghĩ đến. (Giống như Alice và Bob hy vọng điền cùng một số vào cùng một ô ngay cả khi họ không biết hàng hoặc cột nào mà người khác đã được hỏi.)
Nếu hai người chứng minh đang tự đặt ra những câu hỏi này hoàn toàn tự do, không có cách nào để buộc họ chọn các đỉnh kết nối, hoặc tương quan, một cách cho phép người xác minh xác minh câu trả lời của họ. Nhưng sự tương quan chính là điều mà sự liên kết cho phép.
“Chúng ta sẽ sử dụng sự liên kết để chuyển gần như tất cả mọi thứ cho người chứng minh. Chúng ta buộc họ chọn câu hỏi theo cách của họ,” Vidick nói.
Cuối cùng của thủ tục này, người chứng minh mỗi người báo cáo một màu. Người xác minh kiểm tra xem chúng có giống nhau hay không. Nếu đồ thị thực sự có thể tô màu ba màu, người chứng minh không bao giờ nên báo cáo cùng một màu.
“Nếu có một cách tô màu ba màu, người chứng minh sẽ thuyết phục bạn rằng có,” Yuen nói.
Như nói về, thủ tục xác minh này là một ví dụ khác về một trò chơi phi địa phương. Người chứng minh “thắng” nếu họ thuyết phục bạn rằng giải pháp của họ là chính xác.
Năm 2012, Vidick và Tsuyoshi Ito chứng minh rằng có thể chơi một loạt các trò chơi phi địa phương với người chứng minh bị liên kết để xác minh câu trả lời ít nhất là cùng một số vấn đề bạn có thể xác minh bằng cách thẩm vấn hai máy tính cổ điển. Đó là, việc sử dụng người chứng minh bị liên kết không làm tăng đối diện xác minh. Và năm ngoái, Natarajan và Wright chứng minh rằng tương tác với người chứng minh bị liên kết thực sự mở rộng loại vấn đề có thể được xác minh.
Nhưng các nhà khoa học máy tính không biết đến phạm vi đầy đủ của các vấn đề có thể được xác minh bằng cách này. Cho đến bây giờ.
Một Loạt Các Hậu Quả
Trong bài báo mới của họ, năm nhà khoa học máy tính chứng minh rằng thẩm vấn người chứng minh bị liên kết làm cho việc xác minh câu trả lời cho các vấn đề không thể giải quyết, bao gồm cả vấn đề dừng lại.
“Khả năng xác minh của loại mô hình này thực sự là điều đầy kinh ngạc,” Yuen nói.
Nhưng vấn đề dừng lại không thể giải quyết. Và sự thật đó là tia lửa làm cho bằng chứng cuối cùng bắt đầu.
Hãy tưởng tượng bạn đưa một chương trình cho một cặp người chứng minh bị liên kết. Bạn hỏi họ xem nó có dừng lại hay không. Bạn đã sẵn sàng xác minh câu trả lời của họ thông qua một loại trò chơi phi địa phương: Người chứng minh tạo ra câu hỏi và “thắng” dựa trên sự phối hợp giữa câu trả lời của họ.
Nếu chương trình thực sự dừng lại, người chứng minh nên có thể thắng trò chơi này 100 phần trăm thời gian—tương tự như việc nếu đồ thị thực sự có thể được tô ba màu, người chứng minh bị liên kết không bao giờ báo cáo cùng một màu cho hai đỉnh kết nối. Nếu nó không dừng lại, người chứng minh chỉ nên thắng bằng cơ hội—50 phần trăm thời gian.
Điều đó có nghĩa là nếu ai đó yêu cầu bạn xác định xem xác suất thắng lớn nhất xấp xỉ cho một trường hợp cụ thể của trò chơi phi địa phương này, bạn sẽ cần giải quyết vấn đề dừng lại trước tiên. Và giải quyết vấn đề dừng lại là không thể. Điều này có nghĩa là việc tính toán xác suất thắng lớn nhất xấp xỉ cho trò chơi phi địa phương là không thể quyết định được, giống như vấn đề dừng lại.
Điều này lại có nghĩa là câu trả lời cho vấn đề của Tsirelson là không—hai mô hình của sự liên kết không tương đương. Vì nếu chúng có, bạn có thể chen giữa sàn và trần để tính toán xác suất thắng lớn nhất xấp xỉ.
“Không thể có một thuật toán như vậy, vì vậy hai [mô hình] phải khác nhau,” David Pérez-García của Đại học Complutense Madrid nói.
Bài báo mới chứng minh rằng lớp các vấn đề có thể được xác minh thông qua tương tác với người chứng minh lượng tử bị liên kết, một lớp được gọi là MIP*, chính xác bằng với lớp các vấn đề không khó hơn vấn đề dừng lại, một lớp được gọi là RE. Tiêu đề của bài báo diễn đạt điều này một cách ngắn gọn: “MIP* = RE.”
Trong quá trình chứng minh rằng hai lớp phức tạp này bằng nhau, các nhà khoa học máy tính đã chứng minh rằng vấn đề của Tsirelson là sai, điều này, do công việc trước đó, có nghĩa là giả thuyết nhúng Connes cũng là sai.
Đối với những người nghiên cứu trong những lĩnh vực này, đó là một điều đáng kinh ngạc khi câu trả lời cho những vấn đề lớn như vậy xuất hiện từ một bằng chứng trong lĩnh vực máy tính học có vẻ không liên quan.
“Nếu tôi đọc một bài báo nói rằng MIP* = RE, tôi không nghĩ nó có liên quan gì đến công việc của tôi,” Navascués, người đã đồng sáng tác công việc trước đó liên quan đến vấn đề của Tsirelson và giả thuyết nhúng Connes. “Với tôi, đó là một bất ngờ hoàn toàn.”
Những nhà vật lý lượng tử và toán học đang bắt đầu tiêu thụ bằng chứng. Trước khi có công việc mới, các nhà toán học đã tự hỏi liệu họ có thể chấp nhận việc xấp xỉ ma trận vô hạn chiều bằng cách sử dụng những ma trận hữu hạn lớn thay vì. Bây giờ, vì giả thuyết nhúng Connes là sai, họ biết họ không thể.
“Kết quả của họ ngụ ý điều đó là không thể,” nói Slofstra.
Các nhà khoa học máy tính chính họ không nhằm mục đích giải đáp giả thuyết nhúng Connes, và do đó, họ không ở trong tình thế tốt nhất để giải thích ý nghĩa của một trong những vấn đề mà họ kết thúc bằng cách giải quyết.
“Cá nhân tôi, tôi không phải là một nhà toán học. Tôi không hiểu rõ về hình thức ban đầu của giả thuyết nhúng Connes,” nói Natarajan.
Ông và các tác giả khác dự đoán rằng những nhà toán học sẽ dịch kết quả mới này sang ngôn ngữ của lĩnh vực riêng của họ. Trong một bài đăng trên blog thông báo về bằng chứng, Vidick viết, “Tôi không nghi ngờ rằng cuối cùng lý thuyết phức tạp sẽ không còn cần thiết để đạt được những hậu quả toán học thuần túy.”
Tuy nhiên, khi các nghiên cứu khác chạy theo bằng chứng, dòng điều tra đã thúc đẩy nó đang dần chấm dứt. Trong hơn ba thập kỷ, các nhà khoa học máy tính đã cố gắng tìm hiểu xem thủ tục xác minh tương tác sẽ đưa họ đến đâu. Bây giờ, họ đối mặt với câu trả lời, dưới dạng một bài báo dài với một tiêu đề đơn giản và vang vọng của Turing.
“Có một chuỗi dài các tác phẩm chỉ tự hỏi về sức mạnh của” một thủ tục xác minh với hai nhà cung cấp lượng tử buộc, Natarajan nói. “Bây giờ chúng ta biết nó mạnh mẽ đến đâu. Câu chuyện đó đã kết thúc.”
Câu chuyện gốc được tái in với sự cho phép từ Quanta Magazine, một tờ báo độc lập biên tập của Quỹ Simons với nhiệm vụ tăng cường sự hiểu biết của công chúng về khoa học thông qua việc đưa tin về phát triển nghiên cứu và xu hướng trong toán học và các ngành khoa học tự nhiên và sinh học.
Những điều tuyệt vời khác trên Mytour
- Bí mật để thưởng thức thiên nhiên là ... chiếc điện thoại của bạn
- Wikipedia là nơi tốt nhất cuối cùng trên internet
- Vậy, loài lưỡng cư sáng lên. Con người chỉ không thể nhìn thấy nó—cho đến bây giờ
- Liệu đây có phải là sự kết thúc của việc chia sẻ quá mức?
- Những nhà phát triển ô tô bay nhận được sự hỗ trợ từ Không quân
- 👁 Nhà vô địch cờ vua thất bại làm hòa với AI. Ngoài ra, tin tức AI mới nhất
- 📱 Rơi vào sự phân vân giữa những chiếc điện thoại mới nhất? Đừng lo lắng—kiểm tra hướng dẫn mua iPhone của chúng tôi và những chiếc điện thoại Android yêu thích
