通訊複雜性，英文是communication complexity，這是一個理論計算機的子領域，在過去30年衍生了很多東西。
基本介紹
- 中文名：通訊複雜性
- 外文名：communication complexity
- 領域：理論計算機的子領域
- 複雜性：問題不能以多快的速度解決
通訊協定,複雜性,複雜性理論,更複雜的例子,
通訊協定
我們說一個通訊問題，是有兩台機器Alice和Bob，它們需要計算某個函式 f(x, y)。但是Alice只知道輸入x，Bob只知道y。它們之間離得很遠，需要通過光纜互相傳遞信息，把f(x, y)計算出來。它們之間傳遞信息的過程稱為通訊，一個有效的通訊過程稱為一個協定。
舉一個例子，比如兩個數據中心，它們想知道它們的數據是否已經同步(指數據完全一樣)，如果不一樣的話就需要重新同步。它們之間該怎么通訊來確定這一點呢？這個問題就是通訊問題 EQ。在這個問題里，Alice和Bob分別擁有一個字元串x和y，它們想計算x==y。
對於所有通訊問題，Alice可以通過傳送它的所有輸入x到Bob，然後Bob擁有全部輸入，從而計算f(x, y)。注意在通訊問題裡面，我們只考慮通訊消耗，而不考慮本地的計算時間和空間消耗。我們能設計更好的通訊協定嗎？
對於一個通訊問題，如果要求對於任何輸入，輸出結果完全精確，這種符合條件的協定稱為確定型通訊協定。但在實際套用中，我們可以容忍一個足夠小的出錯機率。在某些時候這是有很大好處的。比如上面那個EQ通訊問題，在要求結果完全精確的情況下，Alice傳送自己的x已經是一個最優方案了。但在實際套用中，我們有一個更簡單的方法，那就是傳送hash函式（比如MD5碼），然後雙方檢驗MD5碼即可。當然某種意義上這個協定不夠嚴格，更嚴格的應該是Alice隨機選擇一個合適長度的質數，然後傳送。
Communication Complexity 通訊複雜性
複雜性
量子通訊和上面的經典通訊基本上是一樣的，除了Alice和Bob是兩台量子計算機，可以操縱量子比特，以及它們之間共享量子通道可以傳送量子比特。我們希望能夠儘可能少的傳送量子比特就能解決問題。
就像在計算理論里，人們非常關係量子系統的引入能否大幅度提高計算的速度，人們也關心量子系統對於通訊的幫助。目前，人們發現對於partial函式(對於某些輸入對(x, y)，f(x, y)可以沒有定義的f稱為partial函式)，量子系統可以指數級的縮減傳送的比特數，但對於完全函式(對對所有(x, y)，f(x, y)都有定義)，人們猜測量子系統是沒有幫助的。
複雜性理論
通訊複雜性理論和資訊理論是兩個不同的領域。通訊複雜性通常研究如何傳送儘可能少的比特得到計算結果，而資訊理論是研究通訊的過程(?)，比如如何糾錯，如何利用量子糾纏等。現在的量子資訊理論發展非常火熱，但和量子通訊複雜性是兩個完全不同的概念。
更複雜的例子
現在Alice和Bob分別擁有兩個字元串s和y，它們該如何確定誰的字元串更大(按字典序)呢？同樣這裡很低的錯誤機率是可以忍受的。
思路：每次Alice和Bob先檢查前一半輸入是否相等（調用EQ的通訊協定），如果是，拋棄之；否則後一半可以拋棄；重複這個步驟即可。
