3

Thinking about the theoretical capabilities of quantum computers has led to important insights on the theory of classical computers. One example is the proof that the (classical) complexity class PP is closed under intersection. While there was already a purely classical proof due to Beigel, Reingold, and Spielman, there exists a simpler proof that uses ...


2

Executing a NISQ-device in a manner that asymptotically outperforms a classical computer invalidates the Extended Church-Turing Thesis (ECT). Voluminous tomes written about the (non-extended) Church-Turing Thesis, with implications for branches of philosophy such as the philosophy of mind. The fact that the ECT was not only falsifiable but also is likely ...


Only top voted, non community-wiki answers of a minimum length are eligible