25、量子计算中的复杂度与简单算法解读

量子计算中的复杂度与简单算法解读

1. 复杂度概念

在解决问题时，复杂度是一个关键的考量因素。复杂度主要分为查询复杂度和通信复杂度。

1.1 查询复杂度

黑盒技术在确定问题的查询复杂度方面十分有用。通过对量子预言机和经典预言机的调用次数对比，能发现解决某些问题时，量子预言机所需的调用次数严格少于经典预言机。例如，Grover发现对于在N个事物中进行无约束搜索的查询复杂度问题，仅需对量子黑盒进行O(√N)次调用就能找到目标，而其在现实世界应用中的贡献程度值得进一步探讨。

一些优化算法可用于解决黑盒问题，如Deutsch–Jozsa问题、Bernstein–Vazirani问题和Simon问题等。

1.2 通信复杂度

通信复杂度通常以完成任务所需传输的最少比特或量子比特数量来衡量网络拓扑结构。此外，交换的不同部分数量、量子EPR对的传输速率等资源也可能与具体应用相关。

根据传输的是实验知识还是经典知识、传输的是量子比特还是比特以及可使用的相关组件，存在多种通信复杂度的概念。
-密集编码：传统协议传输n比特信息需要n比特数据，而量子协议仅需n/2个量子比特。对于EPR对（在通信协议环境中也称为ebit），所需的对数为n/2。
-量子隐形传态：借助量子纠缠，仅需2n比特就能传输n个量子比特的状态。每次进行n量子比特的隐形传态，涉及n个ebit。
-分布式计算协议：该协议虽不涉及比特或量子比特，但完成长度为N = 2ⁿ的巨大比特串计算工作需要n个eb