2005/07/21 by Tereza Tusarova, Tusarova, Tereza
Computer Science · #Computational Complexity (cs.CC) #FOS: Computer and information sciences #cs.CC
paper · pdf · doi:10.48550/arxiv.cs/0507057
extended abstract, submitted to UC'05
arxiv created 2005/07/21 · arxiv updated 2009/12/01
We present a new quantum complexity class, called MQ2, which is contained in AWPP. This class has a compact and simple mathematical definition, involving only polynomial-time computable functions and a unitarity condition. It contains both Deutsch-Jozsa's and Shor's algorithm, while its relation to BQP is unknown. This shows that in the complexity class hierarchy, BQP is not an extraordinary isolated island, but has ''siblings'' which as well can solve prime-factorization.