Efficient Simulation of Random States and Random Unitaries
Efficient Simulation of Random States and Random Unitaries
复制标题
随机状态和随机酉的有效模拟
DOI：
10.1007/978-3-030-45727-3_26
复制
发表时间：
2020
期刊：
影响因子：
--
通讯作者：
Gorjan Alagic, Christian Majenz
中科院分区：
文献类型：
--
作者：
Gorjan Alagic, Christian Majenz
我们考虑的问题，有效地模拟随机量子态和随机幺正算子，在某种程度上，这是令人信服的与黑盒预言访问无界advertisers。这个问题以前只被认为是受限制的advertisers。针对对手的一个先验约束的数量查询，这是众所周知的，att-designs就足够了。针对多项式时间的对手，可以使用伪随机状态（PRS）和伪随机酉（PRU），正如Ji，Liu和Song最近的工作中定义的那样;不幸的是，没有可证明安全的PRU结构。尽管如此，我们能够给出有状态的量子算法，在两种感兴趣的设置中模拟理想对象。在Haar随机状态的情况下，我们的模拟器是多项式时间的，具有可忽略的误差，并且还可以通过模拟的状态来模拟验证和反射。这产生了一个直接应用到量子货币：一个货币计划，这是信息理论上不可伪造和不可追踪的。在Haar随机幺正的情况下，我们的模拟器采用多项式空间，但模拟正向和反向访问都是零误差的。这些结果可以被视为发展随机量子对象的惰性采样理论的第一个重要步骤。
We consider the problem of efficiently simulating random quantum states and random unitary operators, in a manner which is convincing to unbounded adversaries with black-box oracle access.This problem has previously only been considered for restricted adversaries. Against adversaries with an a priori bound on the number of queries, it is well-known thatt-designs suffice. Against polynomial-time adversaries, one can use pseudorandom states (PRS) and pseudorandom unitaries (PRU), as defined in a recent work of Ji, Liu, and Song; unfortunately, no provably secure construction is known for PRUs.In our setting, we are concerned with unbounded adversaries. Nonetheless, we are able to give stateful quantum algorithms which simulate the ideal object in both settings of interest. In the case of Haar-random states, our simulator is polynomial-time, has negligible error, and can also simulate verification and reflection through the simulated state. This yields an immediate application to quantum money: a money scheme which is information-theoretically unforgeable and untraceable. In the case of Haar-random unitaries, our simulator takes polynomial space, but simulates both forward and inverse access with zero error.These results can be seen as the first significant steps in developing a theory of lazy sampling for random quantum objects.