量子复杂性类

量子复杂性类（quantum complexity class），理学-计算机科学技术-计算机科学理论-计算复杂性-复杂性类-量子复杂性类，量子复杂性类（quantum complexity class）就是量子图灵机或量子电路等量子计算模型在资源约束条件下能够求解的问题类。量子图灵机与经典图灵机一样，包括状态集合、输入输出字母表、带字母表、转移函数、初始状态、接受状态集合、拒绝状态集合等，不同之处在于，量子图灵机的状态集合和带字母表都是希尔伯特空间（Hilbert Space）（这两个空间可以不同），接受状态集合和拒绝状态集合都是状态集希尔伯特空间的子空间，转移函数是希尔伯特空间上的酉变换（unitary transform），输入和输出字母表可以是经典的离散有穷集。量子电路由一些量子寄存器和一些量子门组成，每个量子寄存器都关联一个希尔伯特空间，每个量子门都作用在一些量子寄存器上，对相关寄存器的希尔伯特空间做酉变换。量子寄存器中的量子态是希尔伯特空间中的向量，可以对寄存器量子态进行测量以得到经典输出，测量的结果是随机的，因此量子电路或量子图灵机很容易模拟概率图灵机。