Edward H. “Ned” Allen and Cristian S. Calude
We present a class of hybrid classical systems using quantum coprocessors and point out that unlike purely quantum computers, such hybrids can be both universal and Turing complete; we introduce such quantum-classical hybrids as “quassical.” We discuss the benefits of quassical architectures from a theoretical point of view: for some classes of problems they achieve computational supremacy. From a practical point of view, quassical architectures can also reduce the overhead burden imposed by most error correction schemes and minimize the challenges of interconnecting qubits in a usefully large connection graph. All quantum computing systems are cyber-physical machines and thus quassical to at least a trivial degree but only the more profoundly quassical hybrids can exhibit an optimum problem-solving capability for the amount of quantum resources deployed. Most significantly, quassical architectures advance our thinking past that of seeing quantum machines as simply quantum embodiments of classical ones and can enliven whole new fields of analytical thinking that takes us beyond quantum information science per se into a deeper understanding of the duality between quantum information and fundamental thermodynamics, possibly suggesting unexpectedly useful new technologies.
Keywords: Universality, Turing completeness, quassical computing, Jozsa Conjecture