Quantum Computability
Abstract
In this paper some theoretical and (potentially) practical aspects of quantum computing are considered. Using the tools of transcendental number theory it is demonstrated that quantum Turing machines (QTM) with rational amplitudes are sufficient to define the class of bounded error quantum polynomial time (BQP) introduced by Bernstein and Vazirani [Proc. 25th ACM Symposium on Theory of Computation, 1993, pp. 11--20, SIAM J. Comput., 26 (1997), pp. 1277--1339]. On the other hand, if quantum Turing machines are allowed unrestricted amplitudes (i.e., arbitrary complex amplitudes), then the corresponding BQP class has uncountable cardinality and contains sets of all Turing degrees. In contrast, allowing unrestricted amplitudes does not increase the power of computation for error-free quantum polynomial time (EQP). Moreover, with unrestricted amplitudes, BQP is not equal to EQP. The relationship between quantum complexity classes and classical complexity classes is also investigated. It is shown that when quantum Turing machines are restricted to have transition amplitudes which are algebraic numbers, BQP, EQP, and nondeterministic quantum polynomial time (NQP) are all contained in PP, hence in ${\rm P}^{#{\rm P}}$ and PSPACE. A potentially practical issue of designing "machine independent" quantum programs is also addressed. A single ("almost universal") quantum algorithm based on Shor's method for factoring integers is developed which would run correctly on almost all quantum…
Read the paper
Related studies
- In silico toxicology protocols
- QM7-X, a comprehensive dataset of quantum-mechanical properties spanning the chemical space of small organic molecules
- Quantum Informed Machine-Learning Potentials for Molecular Dynamics Simulations of CO2's Chemisorption and Diffusion in Mg-MOF-74
- In-silico strategies in nano-drug design: Bridging nanomaterials and pharmacological applications
- mRNA codon optimization with quantum computers
- The computational power of the human brain
Go deeper in Evidence Hub
Evidence Hub adds a study data sheet (design, sample size, evidence level, key numbers), an AI summary and a chat grounded in the paper's text.