A SCHEMATIC DEFINITION OF QUANTUM POLYNOMIAL TIME COMPUTABILITY

DOI10.1017/jsl.2020.45zbMath1461.81020arXiv1802.02336OpenAlexW2785371369MaRDI QIDQ5858921

Tomoyuki Yamakami

Publication date: 15 April 2021

Published in: The Journal of Symbolic Logic (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1802.02336

zbMATH Keywords

quantum computingdescriptional complexityquantum circuitnormal form theoremquantum Turing machinepolynomial-time computabilityquantum functionschematic definition

Mathematics Subject Classification ID

Modes of computation (nondeterministic, parallel, interactive, probabilistic, etc.) (68Q10) Quantum computation (81P68) Quantum algorithms and complexity in the theory of computing (68Q12) Abstract and axiomatic computability and recursion theory (03D75)

Related Items (3)

Quantum logical depth and shallowness of streaming data by one-way quantum finite-state transducers (preliminary report) ⋮ A programming language characterizing quantum polynomial time ⋮ Expressing power of elementary quantum recursion schemes for quantum logarithmic-time computability

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Complexity for type-2 relations
• Computational complexity of real functions
• Polynomial and abstract subrecursive classes
• Computational complexity of uniform quantum circuit families and quantum Turing machines
• The computer as a physical system: a microscopic quantum mechanical Hamiltonian model of computers as represented by Turing machines
• Feasible computability and resource bounded topology
• General recursive functions of natural numbers
• Local Transition Functions of Quantum Turing Machines
• Quantum computational networks
• Recursive Functionals and Quantifiers of Finite Types I
• Structural properties for feasibly computable classes of type two
• Quantum theory, the Church–Turing principle and the universal quantum computer
• Quantum computations: algorithms and error correction
• Polynomial-Time Algorithms for Prime Factorization and Discrete Logarithms on a Quantum Computer
• Quantum Computability
• Quantum Complexity Theory
• Quantum programming languages: survey and bibliography
• Quantum State Complexity of Formal Languages
• Computability and Recursion
• Recursive Functionals and Quantifiers of Finite Types II
• Recursive Predicates and Quantifiers

This page was built for publication: A SCHEMATIC DEFINITION OF QUANTUM POLYNOMIAL TIME COMPUTABILITY