量子查询复杂性

量子查询复杂性（quantum query complexity），理学-计算机科学技术-计算机科学理论-计算复杂性-代数复杂性，计算复杂性和量子算法的一个研究方向，与之对应的是经典的判定树复杂性。量子查询复杂性是量子查询算法调用查询门访问输入的次数。量子查询算法（quantum query algorithm）把输入作为谕示（oracle），利用查询门（query gate）来访问输入。如果输入是一个函数，则查询门把量子寄存器映射到来获得的值。如果输入是一个二进制串x，则查询门把量子寄存器映射到来获得第位输入的值。这样做是为了使得查询门与其他量子门一样成为酉变换（unitary transform）。一个量子查询算法在一个输入上的量子查询复杂度就是此算法在此输入上调用查询门的次数。一个量子查询算法的量子查询复杂度就是此算法在所有长度为的输入上调用查询门的最大次数，通常表示成的函数。一个给定问题的量子查询复杂度就是解决该问题的最优量子查询算法（最优指查询次数最少）的量子查询复杂度。量子查询算法是最早证明了量子计算可以比经典计算更强的计算模型。