April 2020
Intermediate to advanced
244 pages
7h 20m
English
Just as we introduced the Turing machine concept for traditional computers, in the same way, we can define a theoretical model of the Turing machine for quantum computing, the Quantum Turing machine (QTM).
Likewise, we can introduce analogous definitions regarding the computability and complexity of QTMs.
Let's start with the Church-Turing thesis for quantum computing, which states that a QTM can be simulated by a Turing machine by executing a number of steps that are polynomial in the resources used by the QTM. This means that a quantum computing machine does not provide greater computational capacity than a traditional Turing machine, but greater efficiency in terms of resources used.
It is precisely ...
Read now
Unlock full access