图灵奖获得者姚期智教授主题演讲:量子计算

Sina WeiboBaiduLinkedInQQGoogle+RedditEvernote分享




(1个打分, 平均:3.00 / 5)

雁过留声

“图灵奖获得者姚期智教授主题演讲:量子计算”有1个回复

  1. laotuinbay 于 2013-05-28 10:38 下午

    Yao大牛In computational complexity theory, Yao’s principle or Yao’s minimax principle states that the expected cost of any randomized algorithm for solving a given problem, on the worst case input for that algorithm, can be no better than the expected cost, for a worst-case random probability distribution on the inputs, of the deterministic algorithm that performs best against that distribution. Thus, to establish a lower bound on the performance of randomized algorithms, it suffices to find an appropriate distribution of difficult inputs, and to prove that no deterministic algorithm can perform well against that distribution. This principle is named after Andrew Yao, who first proposed it. –Wikipedia.
    有点难懂。佩服。