虽然这意味着量子计算机在可计算性方面没有比传统计算机多提供额外的优势，但在理论上，但量子算法对于某些问题的时间复杂度明显低于相应的已知经典算法。
任何可以由经典计算机解决的计算问题，原则上也可以由量子计算机解决。[13]反过来，任何可以由量子计算机解决的计算问题也可以由经典计算机解决，至少在给予足够时间的情况下，换句话说，量子计算机遵循 Church-Turing 理论。虽然这意味着量子计算机在可计算性方面没有比传统计算机多提供额外的优势，但在理论上，但量子算法对于某些问题的时间复杂度明显低于相应的已知经典算法。值得注意的是，人们相信量子计算机能够快速解决某些问题，而这些问题是任何传统计算机都无法在可行的时间内解决的——这一壮举被称为“量子至上 quantum supremacy”。关于量子计算机问题的计算复杂性的研究被称为量子复杂性理论 Quantum complexity theory。