要理解這類基於概率的算法與普通算法的不同， 我們可以考慮一個特定的例子：譬如找出14的因 數。除去1和14本身，要分解14，最笨的算法就 是從2開始到13，一個一個試著去整除14，如果 能整除餘0，那這個數就是14的其中一個因數。 計算機很擅長一個一個去試，由此我們可以很快 算出2和7兩個因數，而這種依靠蠻力的算法程式 也很容易編寫。不過我們可以馬上想像到使用蠻 力的代價是這方法只對100,000或1,000,000以內 的整數有用，對再大的數字譬如14位的整數，似 乎就有點無力了，因為要試做整除的數字太多， 計算速度一下就降低了。 平行計算在這時變成了拯救者。假如我們用兩台計 算機去分解14，一個從2試到4，一個從5試到7， 那計算時間就馬上縮短為原有的一半。換句話說， 如果計算機的處理器能集成N個計算核心，計算 複雜度會簡化為原來的N分之一，但是這種簡化 還是不足以對付太大的整數，效率不高。但是， 我們若能隨機抽選因數去嘗試整除，那麼從概率 上來說找到真正因數的效率會大大提高。譬如2 到7之間有2，3，4，5，6，7六個數，如果不按 順序試整除14，而是隨機抽樣，有可能我們第一 個抽到就是7、第二個抽到的就是2，那麼我們根 本不需要嘗試3，4，5，6就已經找到了所有14的 因數，這就是所謂的“概率算法”。 In order to appreciate the difference of probabilistic algorithms from regular algorithms we can consider a specific example: for example, to find the factors of 14. Besides the trivial factors 1 and 14, the stupidest way to solve the problem is to try dividing 14 by the numbers 2 up to 7 one-by-one. If it is divisible with a remainder of 0, then we can determine the relevant number is a factor. Computers are good at trying one-by-one. Hence, it’s easy to figure out that 2 and 7 are the only two factors for 14 and these brute-force methods are also easy to program. However, we would soon realise that the brute-force methods are useful to deal with integers within 100,000 or 1,000,000 given a powerful computer. If we are to deal with an integer with, say, 14 digits, we are going to hit a brick wall since the number of integers we need try dividing is simply too many. Parallel computing is our saviour. Suppose we use two computers to try factoring 14, one trying the factors from 2 to 4 and the other 5 to 7; then the computing time is instantaneously reduced to half the original. In other words, if the processing unit of a computer can integrate N computing cores, the computing time complexity would be reduced to 1/N. Nonetheless, this type of simplification is still not efficient enough for factoring a very large integer. Yet, if we are allowed to try factoring randomly, the efficiency of successfully finding a factor would be greatly improved, probabilistically speaking. For instance, we have six numbers 2, 3, 4, 5, 6, 7 between 2 and 7. If we do the division of 14 not sequentially but by picking randomly the candidate factors from these six numbers, it’s likely that the first one we pick is 7 and the second one 2. In that case, we don’t even need to try 3, 4, 5, and 6 before we have found all factors of 14. This is the motivation behind the so-called ‘probabilistic algorithms.’ 作者殷灝是澳門大學應用物理及材料工程研究所的副教授。他在澳大建立 了低溫量子計算實驗室，來進行超導電路上量子光學與量子信息處理的研 究。中科院理論物理研究所的科研經歷讓他對天文物理亦產生興趣，並在 澳大任教一門關於宇宙奧秘的通識課。 The author is an associate professor of the Institute of Applied Physics and Materials Engineering, University of Macau. He has established the cryogenic quantum computation laboratory and conducted research studies on quantum optics and quantum information processing using superconducting circuits. Through his research experience at the Institute of Theoretical Physics of the Chinese Academy of Sciences, he has developed an interest in astrophysics, and currently teaches a general education course on the mysteries of the universe. umagazine issue 19 59
RkJQdWJsaXNoZXIy MTQ1NDU2Ng==