image: 二重和三重Forrelation值的实验结果 view more
Credit: ©《中国科学》杂志社
关联函数经常用来量化不同变量或数据组之间的关联程度。几年前，Aaronson和Ambainis提出了一个叫傅换关联（Forrelation）的性能测试问题，它可以用于研究量子设备的询问复杂度。如今，科学家们在一个三比特核磁共振信息处理器上进行了对傅换关联问题的实验研究。
相关研究论文题目为 “Experimental study of Forrelation in nuclear spins”。文章近期在Science Bulletin 2017年第7期上出版，清华大学龙桂鲁教授和南方科技大学翁文康教授为共同通讯作者。文章在核自旋体系中解决了二重和三重傅换关联问题，并借助优化控制脉冲序列将自旋波动控制在一个很小的阈值内。
正如物理和计算机科学领域内的大量专家所证明的，量子计算机比经典计算机具有指数加速的优势。在黑盒子模型中，大部分量子算法都可以证明量子计算机可以实现指数甚至更大的加速，于是就产生一个问题：在黑盒子模型中，量子加速的极限是什么？特别地，在询问复杂度理论中，我们能否将量子与经典询问复杂度进行最大分离？
两年前，Aaronson和Ambainis引入傅换关联性能测试问题，即人们需要判断一个布尔函数与经过傅立叶变换后的另一个布尔函数之间的关联程度。他们证明了这种算法是目前最大的量子黑盒子加速算法。
龙桂鲁教授和他的合作者设计了一个量子线路并实验实现了多重傅换关联算法。具体地，通过判断Forrelation值是否满足大于等于3/5或者其绝对值小于1/100，他们在一个核磁共振谱仪上实现了二重和三重傅换关联算法。这是实验上首次实现傅换关联算法，他们的实验结果如图1所示。
龙桂鲁教授将Forrelation的中文名词翻译为傅换关联，他指导了实验实现，他说：“由于傅换关联值对实验结果非常敏感，实验实现的一个巨大困难在于保证实验最终态的高保真度。为了将误差控制在一个合理的阈值内，实验上使用了优化梯度控制脉冲技术来代替由硬脉冲和系统自由演化组成的符合脉冲序列” 。
翁文康教授指出他们工作可进一步发展之处：“我们所有的量子算法都是在一个三比特量子信息处理器上实现的，由于现有实验技术条件的限制，并没有直接证明量子计算比经典计算的强大之处，但这个实验可以作为一个实验蓝本证明我们可以在不久的将来实现量子计算的量子霸权地位”
这一研究结果证明了傅换关联算法可以最大限度地区分量子询问复杂度和经典询问复杂度，具有十分重要的科学意义和参考价值。
该项研究得到了国家自然科学基金项目（No. 11175094, 91221205 and 11405093）和国家基础科研项目（No. 2015CB921002）的资助。
更多详情请阅原文：
Hang Li, Xun Gao, Tao Xin, Man-Hong Yung and Guilu Long, Experimental Study of Forrelation in Nuclear Spins, Science Bulletin, 2017, Vol.62, No. 7:497-502 http://www.sciencedirect.com/science/article/pii/S2095927317301299
###
Journal
Science Bulletin