Abstract quantum computing machines and quantum computational logics

Research paper by Maria Luisa Dalla Chiara, Roberto Giuntini, Giuseppe Sergioli, Roberto Leporini

Indexed on: 23 Jun '16Published on: 08 Jun '16Published in: International Journal of Quantum Information


International Journal of Quantum Information, Ahead of Print. Classical and quantum parallelism are deeply different, although it is sometimes claimed that quantum Turing machines are nothing but special examples of classical probabilistic machines. We introduce the concepts of deterministic state machine, classical probabilistic state machine and quantum state machine. On this basis, we discuss the question: To what extent can quantum state machines be simulated by classical probabilistic state machines? Each state machine is devoted to a single task determined by its program. Real computers, however, behave differently, being able to solve different kinds of problems. This capacity can be modeled, in the quantum case, by the mathematical notion of abstract quantum computing machine, whose different programs determine different quantum state machines. The computations of abstract quantum computing machines can be linguistically described by the formulas of a particular form of quantum logic, termed quantum computational logic.