儀器獨立隨機放大協定的負面結果

Abstract

Randomness amplification 協定的目的是要藉由weak source 產生接近完美的亂數位元。在這篇論文中，我們證明了使用兩個儀器的 randomness amplification 協定有一些不能達到的結果。具體的結果是，給定任意使用兩個儀器的Randomness amplification 協定，當協定要求輸入的weak source 之min-entropy 的大小在log n 的量級時，存在一種策略可以以最高機率通過協定每一輪的測試，並且當協定接受時，產生的亂數位元在給定每一輪的輸入值以及額外資訊時是固定的。

Randomness amplification is a protocol that outputs nearly uniform bits using inputs generated from weak source. In this work, we present some negative results for two-device randomness amplification protocol with weak source. Specifically, given a two-device randomness amplification protocol with inputs generated from a weak source that has log n min-entropy, then there exists a strategy which has the highest probability of passing every round of the protocol, such that if the protocol accepts, then the output of the protocol is deterministic given inputs for all round and side information.