On the (Im)Possibility of Quantum String Commitment
On the (Im)Possibility of Quantum String Commitment
复制标题
关于量子弦承诺的（我）可能性
DOI：
--
复制
发表时间：
2005
期刊：
影响因子：
--
通讯作者：
M. Christandl
中科院分区：
文献类型：
--
作者：
H. Buhrman;P. Hayden;H. Lo;S. Wehner;M. Christandl
无条件安全的非相对论比特承诺在经典世界和量子世界都是不可能的。然而，当一次提交一个n比特的字符串时，我们能把量子极限延伸多远？我们考虑的量子方案中，爱丽丝提交了一个字符串的n位鲍勃，在这样一种方式，她只能作弊的一个位和鲍勃可以学习最多B位的“信息”之前透露阶段。我们显示一个否定和一个肯定的结果，这取决于我们如何衡量鲍勃的信息。如果我们使用Holevo量，就不存在好的方案：a+B至少是n。然而，如果我们使用可访问信息，则存在a=4 log n+O（1）且B=4的方案。这在经典上是不可能的。我们的协议是不是有效的，但是，我们也表现出一个有效的方案时，鲍勃的测量电路被限制到多项式的大小。我们的计划还意味着一个协议，n同时硬币翻转，实现更高的熵所产生的字符串比任何以前已知的协议。
Unconditionally secure non-relativistic bit commitment is known to be impossible in both the classical and quantum worlds. However, when committing to a string of n bits at once, how far can we stretch the quantum limits? We consider quantum schemes where Alice commits a string of n bits to Bob, in such a way that she can only cheat on a bits and Bob can learn at most b bits of ''information'' before the reveal phase. We show a negative and a positive result, depending on how we measure Bob's information. If we use the Holevo quantity, no good schemes exist: a+b is at least n. If, however, we use accessible information, there exists a scheme where a=4 log n+O(1) and b=4. This is classically impossible. Our protocol is not efficient, however, we also exhibit an efficient scheme when Bob's measurement circuit is restricted to polynomial size. Our scheme also implies a protocol for n simultaneous coin flips which achieves higher entropy of the resulting string than any previously known protocol.