Reflections on quantum computing

In this rather speculative note three problems pertaining to the power and limits of quantum computing are posed and partially answered: (a) when are quantum speedups possible? (b) is fixed-point computing a better model for quantum computing? (c) can quantum computing trespass the Turing barrier? WHEN ARE QUANTUM SPEEDUPS POSSIBLE? This section discusses the possibility that speedups in quantum computing can be achieved only for problems that have a few or even unique solutions [1]. For instance, this includes the computational complexity class UP [2]. Typical examples are Shor’s quantum algorithm for prime factoring [3] and Grover’s database search algorithm [4] for a single item satisfying a given condition in an unsorted database (see also Gruska [5]). In quantum complexity, one popular class of problems is BQP, which is the set of decision problems that can be solved in polynomial time (on a quantum computer) so that the correct answer is obtained with probability at least 1

# Quantum Computing Algorithms and Architecture # Computer Science # Computability, Logic, AI Algorithms # Quantum Information and Cryptography

Cristian S. Calude, Michael J. Dinneen, Karl Svozil (2000). "Reflections on quantum computing". Complexity. https://doi.org/10.1002/1099-0526(200009/10)6:1<35::aid-cplx1005>3.0.co;2-t