Monday, April 6, 2020

Quantum Computer on a Turing Machine


Quantum computer is discussed in papers both as a mathematical model and as its technical realization. Only the mathematical model is meant here and in comparison with that of a standard computer, namely a Turing machine. The quantum Turing machine is an abstract model equivalent to the quantum circuit and can represent all features of quantum computer without entanglement.
Another way to generalize the Turing machine to the quantum computer is by replacing all bits or cells of a Turing tape with “quantum bits” or “qubits”. A qubit is equivalently representable by a unit sphere and a point chosen on its surface. Then if any bit is an elementary binary choice between two disjunctive options usually designated by “0” and “1”, any qubit is a choice between a continuum of disjunctive options as many as the points of the surface of the unit ball. That visualization allows of highlighting the fundamental difference between the Turing machine and the quantum computer: the choice of an element of an uncountable set necessarily requiring the axiom of choice.
The term of “quantum invariance” can be coined to outline the important role assigned to the axiom of choice in the theory of quantum computer and inherited from quantum mechanics: The theorems about the absence of hidden variables in quantum mechanics exclude any well-ordering before measurement, but the results of the measurements are always well-ordered and thus any quantum model implies the well-ordering theorem equivalent to the axiom of choice. However quantum reality according to the cited theorems is not well-orderable in principle. Thus the relation between quantum model and quantum reality requires correspondingly the axiom of choice and its absence or the coined quantum invariance to designate that extraordinary relation between model and reality specific to quantum mechanics and trough it, to the theory of quantum computer. That quantum invariance is well known in mathematics in the form of Skolem’s paradox, who has introduced the notion of “relativity” as to set theory discussing infinity.
Quantum invariance as to quantum computer can be exhaustedly described by the mapping of quantum computer on a Turing machine. The offered above visualization of quantum computer as a tape of qubits is about to be used: Any qubit of it being a choice of one between a continuum of disjunctive options can be replaced by a Turing machine (possibly with a tape consisting of infinitely many cells) utilizing the axiom of choice for replacing. Furthermore quantum invariance states the equivalence after that replacement.
Given all that, any quantum computational process can by defined in terms of a standard one on a Turing machine as infinite but convergent. The limit, to which it converges, is the result of this quantum computation. It involves the notion of actual infinity since the computational series is both infinite and considered as a completed whole by dint of its limit.
As the model of a Turing machine unifies the utilized algorithm with the result obtained by it, quantum computer can be interpreted both as a convergently advanced algorithm and a convergently improved result for the former. If its objectivity is to model a concrete reality by the computed ultimate result, it coincides with reality unlike any standard Turing machine which has to be finite and thus there is always a finite difference between the computed reality and any completed result of a Turing computation. One can state that quantum computer calculates reality or that quantum model and reality coincide.
The offered model of quantum computer on a Turing machine as a convergent and infinite process comprises the more general case where that infinite process does not converge and even has infinitely many limit points. One can use the granted above axiom of choice to order the limit points even being infinitely many as a monotonic series, which necessarily converges if it is a subset of any finite interval, and to accept this last limit as the ultimate result of the quantum computer.
The axiom of choice can be used in another way to give the same result thus elucidating the physical and even philosophical meaning of Hilbert space, the basic mathematical structure of quantum mechanics:
Any qubit represents equivalently a limit point of the “tape” of the Turing machine, on which the quantum computer is modeled. If those limit points are even infinitely many, they can be represented equivalently by a point in Hilbert space where any “axis” of it corresponds one-to-one to a qubit ant thus to a limit point of the quantum computational process. Then obviously any state of any quantum system being a wave function and a point in Hilbert space can be interpreted as a quantum calculative process, and the physical world as a whole as an immense quantum computer.
Using the axiom of choice, one can always reorder monotonically a bounded set of limit points to converge or represent a point in Hilbert space as a single qubit by the Banach-Tarski paradox: Both are only different images of one and the same quantum computation.
The model of quantum computer on a Turing machine allows of clarifying the sense and meaning of a quantum computation in terms of a usual computer equivalent to some finite Turing machine: While the standard computer gives a result, the quantum computer offers a tendency comprising a potentially infinite sequence of converging algorithms and results as well as the limit of this tendency both as an ultimate algorithm-result coinciding with reality and as an image (“Gestalt”) of the tendency as a completed whole.
The transition from the result of a usual computer to the ultimate result of quantum computer is a leap comparable with human understanding and interpretation to restore the true reality on the base of a finite set of sensual or experimental data.


The paper
The presentation (PDF) (PowerPoint) (Video) or as slides @ EsyChair