横滨国立大学
该图显示，索引选择问题的搜索空间大小导致组合爆炸，其中从M个元素中选择任何K个元素，并分配log2(Q)位信息
即使对于像(M，K，Q) = (16，8，64)这样的简单情况，也有大约6个
94 * 10173考生，这很难解决
学分:横滨国立大学 不幸的是，所提出的深刻提高无线网络能量效率的方法也受到计算复杂问题的困扰
但是，一位计算机科学家首次证明，量子搜索算法可以比经典计算机更快地解决这个问题
一种新颖的无线通信技术可以打开或关闭电信介质本身的某些部分，如天线和副载波，这种技术可以带来超高的能效增益，但它的优化却是一个难以解决的计算难题
然而，横滨国立大学的一名计算机科学家首次证明，就查询复杂性而言，量子搜索算法可以比经典计算机更快地解决这个问题
描述他的发现的论文发表在8月9日的《电气和电子工程师协会接入》杂志上
5G无线网络的到来极大地提升了带宽和更高的数据速率，并有可能实现自动驾驶汽车和物联网(IoT)等一系列新的移动数据应用
与此同时，这种通信量的激增需要增强技术，以提高所有这些信息的无线电频谱载波的使用效率和为系统供电所需的能量
一种用于提高能量效率的创新方法是所谓的指数调制，这种方法近年来在无线通信领域引起了极大的关注
这项技术的名字呼应了调频或调幅这两个术语，这两个术语用来描述在20世纪的大部分时间里，声音或音乐等信息是如何通过无线电波在太空中传输的
在发送端，“载波”无线电波的频率或振幅被发射机瞬间改变(“调制”)，以便在该波上留下信息，类似于19世纪电报员如何在通过电报线的电流上以莫尔斯电码的形式留下信息
在接收端，对该载波的解码或“解调”提取出嵌入其形式的信息，产生人类耳朵可以听到的声音
除了改变无线电波的频率或振幅之外，调制载波的第三种方法是改变其相位
指数调制(IM)提供了第四种方式，或者可以说是第四维度，来传递信息，但这一次是通过利用指数的开或关状态
在这种情况下，单词index只是通信系统的基础设施和操作构造块的总称，例如传输天线、子载波、时隙、射频反射镜、发光二极管，甚至中继和扩展码
通过打开或关闭这些不同的元件，这可能会给传输增加另一层信息，这次是以二进制数字或比特的形式
通过关闭系统的某些部分，即使它们正在传递信息，传输的符号序列的稀疏性简化了计算的复杂性
这也大大减少了传输给定量数据所需的能量
该论文的作者、副教授石川直树说:“这是一个非常优雅的概念，它利用通信系统本身构件的激活模式来传递信息，从而降低了硬件的复杂性。”
但是这种彻底的改进带来了一个额外的——而且是实质性的——挑战
IM需要优化来确定应该使用哪些索引以及何时使用，以便传达这种二进制信息，而这种特定类型的优化恰好在计算上非常困难
“这个优化问题就是计算复杂性理论家所称的‘NP-hard’，这是一类非常难的问题
这导致了我们所说的组合爆炸，”他补充道
“所以我把这个数学挑战的怪物命名为‘指数选择问题’
" 为了解决索引选择问题，石川使用了一种称为格罗弗自适应搜索(GAS)的量子计算算法，也称为量子搜索算法
有一天，量子计算可能会提供比经典计算机更快地执行多种计算的能力
在这篇论文中，Ishikawa首次证明了原则上GAS在查询复杂度方面比经典计算机更快地解决索引选择问题
他说:“这表明指数调制与量子计算机兼容，因为它代表了信息的开和关，从而产生了通常用于量子计算的二进制变量。”
使用GAS解决指数调制问题仍然是一个概念证明，因为容错的大规模量子计算机距离实现还有数年的时间
现有量子计算机的工业应用仍然面临许多挑战，因为它们不可忽略的噪声淹没了许多信号
此外，GAS可以提供二次加速，但指数复杂度的问题仍未解决，需要长期研究
当量子计算机通过N个查询解决一个问题时，就会出现二次加速，而经典计算机需要进行N * N = N2查询
指数加速发生在量子计算机通过N个查询解决一个问题的地方，而经典计算机需要2N个查询
因此，如果N是一个很大的值，那么在查询复杂度方面的差异也会变大
尽管如此，由GAS实现的量子加速演示有可能解决社会中的许多其他问题，而不仅仅是指数选择问题
来源：由phyica.com整理转载自PH，转载请保留出处和链接！
