Dec, 2016

量子霸权实验的复杂性理论基础

PDF
TL;DR本文针对量子计算机的性能和量子电路等问题，探讨了量子优越性、采样、复杂度等方面的理论基础及相关算法，并展示了量子优越性相对于多项式层次、BPP、BQP 等的可行性及其假设。
quantum computingquantum supremacyquantum circuitssamplingcomplexity theory
发现论文，激发创造
  • 近期量子设备中量子至高性的特征化

    研究量子计算中的量子优越性，探讨基于（伪）随机量子电路输出分布的采样任务，指出在经典计算机上模拟需指数级时间，并在超级计算机模拟的基础上，得出了实现量子优越性所需的近 50 个超导量子位。引入交叉熵作为量子电路的评估标准，并提出基于交叉熵的量子优越性实验方案。

    Jul, 2016

  • 量子计算霸权

    量子算法是通过使用量子计算机加速计算问题的解决而发展的领域。量子霸权是一种超越任何经典计算机能力的计算任务，在该领域的关键里程碑是实现了通用量子计算。本文介绍了实现量子霸权的主要方案，并讨论了如何可靠地比较经典计算机和量子计算机的性能。

    Sep, 2018

  • 设备独立认证 “量子霸权” 的采样复杂度

    证明实现正确性是量子设备展示卓越计算能力的关键挑战之一，本文表明，所有足够平坦的分布样本都需要指数级的设备使用才能进行验证。

    Dec, 2018

  • 量子计算机的争议

    本研究针对量子计算机的可行性进行了计算复杂度的论证，并且鉴定了一种由噪声中等规模量子计算机描述的非常低复杂度概率分布，解释了为什么它既不允许高质量的量子纠错，也不允许展示量子霸权。同时，我们还推导了一些关于噪声量子系统行为的一般性原理。这项工作支持 Pitowsky（1990）研究的 “物理教堂论文”，并遵循他利用有关计算的抽象思想来研究实际物理计算机的性能的愿景。

    Aug, 2019

  • 量子速度提升的最大割问题需要数百个量子比特的量子近似优化算法

    通过模拟 Quantum Approximate Optimization Algorithm，我们得出结论，除非可用几百个量子位，否则不可能实现量子加速度。

    Dec, 2018

  • 关于线性光学量子复杂性的实验验证

    利用线性光学电路采样算法和观察 “波色云” 现象成功验证量子技术，为所有架构的量子技术提供了可行的验证方法。

    Nov, 2013

  • 量子机器学习的优势演示

    使用超导体五比特处理器，对基于 oracle 的问题进行求解，经过实验验证，在现有的嘈杂系统中，量子计算机的查询次数明显比经典计算机少，这种差距会随着误差率和问题大小的增加而不断扩大，这证明了量子优势确实在现有的嘈杂系统中出现了。

    Dec, 2015

  • 量子近似优化算法实现量子霸权

    该文研究了基于门模型的量子计算机上的量子近似优化算法（QAOA）及其可能表现出的量子霸权，发现即使低深度 QAOA 的输出也无法在任何经典设备上进行高效模拟，并提出了量子绝热算法（QADI）仍存在一个 oracle 使采样成为可能的限制。这表明 QAOA 不仅可能在优化方面有用，而且在实现量子霸权方面也具有潜力。

    Feb, 2016

  • 利用稀疏嘈杂的交错量子计算实现量子霸权

    该文主要研究 IQP 电路的量子计算和经典模拟问题，探究在有误差和噪声存在时的处理方法和纠错技术。

    Oct, 2016

  • 量子算法测量

    我们从计算复杂性的角度对实验量子物理学进行了系统研究，定义了量子算法测量 (QUALMs) 框架，用于研究量子多体物理学中的两个重要实验问题，并显示在使用实验样品的相干性 (空间和时间) 时，相较于分别访问每个实验样本的标准情况，可以实现可证明的指数加速。因此，我们的研究表明，量子计算机可以提供一种新的指数优势：量子实验的资源消耗获得指数级的节省。

    Jan, 2021