Hostname: page-component-cd9895bd7-q99xh Total loading time: 0 Render date: 2024-12-27T07:46:09.515Z Has data issue: false hasContentIssue false
  • English
  • Français

A SCHEMATIC DEFINITION OF QUANTUM POLYNOMIAL TIME COMPUTABILITY

Part of: Theory of computing Computability and recursion theory

Published online by Cambridge University Press:  08 September 2020

TOMOYUKI YAMAKAMI
TOMOYUKI YAMAKAMI*
Affiliation:
FACULTY OF ENGINEERING UNIVERSITY OF FUKUI 3-9-1 BUNKYO, FUKUI910-8507, JAPANE-mail: [email protected]
Get access Rights & Permissions [Opens in a new window]

Abstract

In the past four decades, the notion of quantum polynomial-time computability has been mathematically modeled by quantum Turing machines as well as quantum circuits. This paper seeks the third model, which is a quantum analogue of the schematic (inductive or constructive) definition of (primitive) recursive functions. For quantum functions mapping finite-dimensional Hilbert spaces to themselves, we present such a schematic definition, composed of a small set of initial quantum functions and a few construction rules that dictate how to build a new quantum function from the existing ones. We prove that our schematic definition precisely characterizes all functions that can be computable with high success probabilities on well-formed quantum Turing machines in polynomial time, or equivalently uniform families of polynomial-size quantum circuits. Our new, schematic definition is quite simple and intuitive and, more importantly, it avoids the cumbersome introduction of the well-formedness condition imposed on a quantum Turing machine model as well as of the uniformity condition necessary for a quantum circuit model. Our new approach can further open a door to the descriptional complexity of quantum functions, to the theory of higher-type quantum functionals, to the development of new first-order theories for quantum computing, and to the designing of programming languages for real-life quantum computer

Keywords

quantum computingquantum functionquantum Turing machinequantum circuitschematic definitiondescriptional complexitypolynomial-time computabilitynormal form theorem

MSC classification

Primary: 81P68: Quantum computation
Secondary: 68Q12: Quantum algorithms and complexity 68Q10: Modes of computation (nondeterministic, parallel, interactive, probabilistic, etc.) 03D75: Abstract and axiomatic computability and recursion theory
Type
Articles
Information
The Journal of Symbolic Logic , Volume 85 , Issue 4 , December 2020 , pp. 1546 - 1587
Check for updates
Copyright
© The Association for Symbolic Logic 2020

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

References

REFERENCES

Adleman, L. M., DeMarrais, J., and Huang, M. A., Quantum computability. SIAM Journal on Computing, vol. 26 (1997), pp. 1524–1540.CrossRefGoogle Scholar
Barenco, A., et al., Elementary gates for quantum computation. Physical Review A, vol. 52 (1995), pp. 3457–3467.CrossRefGoogle ScholarPubMed
Benioff, P., The computer as a physical system: A microscopic quantum mechanical Hamiltonian model of computers represented by turing machines. Journal of Statistical Physics, vol. 22 (1980), pp. 563–591.CrossRefGoogle Scholar
Bernstein, E. and Vazirani, U., Quantum complexity theory. SIAM Journal on Computing, vol. 26 (1997) pp. 1411–1473.CrossRefGoogle Scholar
Boykin, P. O., et al., On universal and fault-tolerant quantum computing, preprint, 1999. arXiv:quant-ph/9906054.Google Scholar
Cobham, A., The intrinsic computational difficulty of functions, Proceedings of the 1964 Congress for Logic, Mathematics, and Philosophy of Science, North-Holland, 1964, pp. 24–30.Google Scholar
Constable, R. L., Type two computational complexity, Proceedings of the 5th ACM Symposium on Theory of Computing (STOC’73), Association for Computing Machinery, New York, 1973, pp. 108–121.Google Scholar
Cook, S. and Kapron, B. M., Characterizations of the basic feasible functionals of finite type, Proceedings of the 30th IEEE Conference on Foundations of Computer Science (STOC’89), IEEE, 1989, pp. 154–159.Google Scholar
Davis, M., The Unidecidable. Basic Papers on Undecidable Propositions, Unsolvable Problems, and Computable Functions, Raven Press, Hewlett-Packard, New York, 1965.Google Scholar
Deutsch, D., Quantum theory, the Church-Turing principle, and the universal quantum computer. Proceedings Royal Society London, Series A, vol. 400 (1985), pp. 97–117.Google Scholar
Deutsch, D., Quantum computational networks. Proceedings of the Royal Society of London Series, vol. 425 (1989), pp. 73–90.Google Scholar
Gay, S. J., Quantum programming languages: Survey and bibliography. Mathematical Structures in Computer Science, vol. 16 (2006) pp. 581–600.CrossRefGoogle Scholar
Grover, L. K., A fast quantum mechanical algorithm for database search, Proceedings of the 28th Annual ACM Symposium on the Theory of Computing (STOC’96), Association for Computing Machinery, New York, 1996, pp. 212–219.CrossRefGoogle Scholar
Grover, L., Quantum mechanics in searching for a needle in a haystack. Physical Review Letters, vol. 79 (1997), p. 325.CrossRefGoogle Scholar
Hopcroft, J. and Ullman, J., An Introduction to Automata Theory Languages and Computation, Addison-Wesley, Reading, MA, 1979.Google Scholar
Kitaev, A., Quantum computations: Algorithms and error correction. Russian Mathematical Surveys, vol. 52 (1997), pp. 1191–1249.CrossRefGoogle Scholar
Kitaev, A. Y., Shen, A. H., and Vyalyi, M. N., Classical and Quantum Computation, American Mathematical Society, Providence, RI, 2002.CrossRefGoogle Scholar
Kleene, S. C., General recursive functions of natural numbers. Mathematische Annalen, vol. 112 (1936), pp. 727–742.CrossRefGoogle Scholar
Kleene, S. C., Recursive predicates and quantifiers. Transactions of the American Mathematical Society, vol. 53 (1943), pp. 41–73.CrossRefGoogle Scholar
Kleene, S. C., Recursive functionals and quantifiers of finite types I. Transactions of the American Mathematical Society, vol. 91 (1959), pp. 1–52.Google Scholar
Kleene, S. C., Recursive functionals and quantifiers of finite types II. Transactions of the American Mathematical Society, vol. 108 (1963), pp. 106–142.Google Scholar
Ko, K. and Friedman, H., Computational complexity of real functions. Theoretical Computer Science, vol. 20 (1982), pp. 323–352.Google Scholar
Mehlhorn, K., Polynomial and abstract subrecursive classes. Journal of Computer and System Sciences, vol. 12 (1976), pp. 147–178.CrossRefGoogle Scholar
Nielsen, M. A. and Chuang, I. L., Quantum Computation and Quantum Information, Cambridge University Press, Cambridge, 2000.Google Scholar
Nishimura, H. and Ozawa, M., Computational complexity of uniform quantum circuit families and quantum turing machines. Theoretical Computer Science, vol. 276 (2002), pp. 147–181.CrossRefGoogle Scholar
Ozawa, M. and Nishimura, H., Local transition functions of quantum turing machines. RAIRO—Theoretical Informatics and Applications, vol. 276 (2000), pp. 379–402.CrossRefGoogle Scholar
Peano, G., Sul concetto di numero. Rivista di Matematica, vol. 1 (1891), pp. 87–102, 256–267.Google Scholar
Soare, R. I., Computability and recursion. The Bulletin of Symbolic Logic, vol. 2 (1996), no. 3, pp.284–321.CrossRefGoogle Scholar
Shor, P. W., Polynomial-time algorithms for prime factorization and discrete logarithms on a quantum computer. SIAM Journal on Computing, vol. 26 (1997), pp. 1484–1509.CrossRefGoogle Scholar
Townsend, M., Complexity for type-2 relations. Notre Dame Journal of Formal Logic, vol. 31 (1990), 241–262.CrossRefGoogle Scholar
Turing, A. M., On computable numbers with an application to the Entscheidungsproblem. Proceedings of the London Mathematical Society, vol. 42 (1936), no. 2, pp. 230–265; Errutum ibid 43 (1937) 544–546.Google Scholar
Villagra, M. and Yamakami, T., Quantum state complexity of formal languages, Proceedings of the 17th International Workshop on Descriptional Complexity of Formal Systems (DFCS 2015), Lecture Notes in Computer Science, vol. 9118, Springer, New York, 2015, pp. 280–291.CrossRefGoogle Scholar
Yamakami, T., Structural properties for feasiblely computable classes of type two. Mathematical Systems Theory, vol. 25 (1992), pp. 177–201.CrossRefGoogle Scholar
Yamakami, T., Feasible computability and resource bounded topology. Information and Computation, vol. 116 (1995), pp. 214–230.CrossRefGoogle Scholar
Yamakami, T., A foundation of programming a multi-tape quantum Turing machine, Proceedings of the 24th Mathematical Foundations of Computer Science (MFCS’99), Lecture Notes in Computer Science, vol. 1672, 1999, pp. 430–441. arXiv:quant-ph/9906084.Google Scholar
Yamakami, T., Quantum NP and a quantum hierarchy, Proceedings of the 2nd IFIP International Conference on Theoretical Computer Science (TCS 2002), Kluwer Academic Press (under the name “Foundations of Information Technology in the Era of Network and Mobile Computing”), the series IFIP—The International Federation for Information Processing, vol. 96, 2002, (Track 1), pp. 323–336.CrossRefGoogle Scholar
Yamakami, T., Analysis of quantum functions. International Journal of Foundations of Computer Science, vol. 14 (2003), pp. 815–852. A preliminary version appeared in the Proceedings of the 19th International Conference on Foundations of Software Technology and Theoretical Computer Science, Lecture Notes in Computer Science, vol. 1738, 1999, pp. 407–419.CrossRefGoogle Scholar
Yamakami, T., A recursive definition of quantum polynomial time computability (extended abstract), Proceedings of the 9th Workshop on Non-Classical Models of Automata and Applications (NCMA 2017), Österreichische Computer Gesellschaft 2017, The Austrian Computer Society, 2017, pp. 243–258.Google Scholar
Yao, A. C., Quantum circuit complexity, Proceedings of the 34th Annual IEEE Symposium on Foundations of Computer Science (FOCS’93), 1993, pp. 80–91.Google Scholar