Expressing power of elementary quantum recursion schemes for quantum logarithmic-time computability

DOI10.1007/978-3-031-15298-6_6MaRDI QIDQ6102995zbMATH OpenOpenAlexFDO

Authors Tomoyuki Yamakami

Publication date 2 June 2023

Published in Logic, Language, Information, and Computation (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/978-3-031-15298-6_6

zbMATH Keywords

quantum Turing machineschematic definitionfast quantum recursionquantum logarithmic-time computability

Mathematics Subject Classification ID

Logic in computer science (03B70)

Recommendations

• Computing power of Turing machines in the framework of unsharp quantum logic
• Quantum computation of discrete logarithms in semigroups
• Quantum proof systems for iterated exponential time, and beyond
• scientific article; zbMATH DE number 1839432
• Quantum algorithms for computing general discrete logarithms and orders with tradeoffs
• scientific article; zbMATH DE number 799789
• On exact quantum query complexity
• A SCHEMATIC DEFINITION OF QUANTUM POLYNOMIAL TIME COMPUTABILITY
• Polynomial-Time Algorithms for Prime Factorization and Discrete Logarithms on a Quantum Computer
• Polynomial-Time Algorithms for Prime Factorization and Discrete Logarithms on a Quantum Computer

Cites work

• scientific article; zbMATH DE number 1776257 (Why is no real title available?)
• scientific article; zbMATH DE number 1418357 (Why is no real title available?)
• A SCHEMATIC DEFINITION OF QUANTUM POLYNOMIAL TIME COMPUTABILITY
• ANALYSIS OF QUANTUM FUNCTIONS
• Computability and Recursion
• General recursive functions of natural numbers
• On uniformity within \(NC^ 1\)
• Quantum computational networks
• Quantum lower bounds by polynomials
• Quantum theory, the Church–Turing principle and the universal quantum computer
• Recursive Predicates and Quantifiers
• The computer as a physical system: a microscopic quantum mechanical Hamiltonian model of computers as represented by Turing machines
• Theory of one-tape linear-time Turing machines

Cited in

(3)

• Quantum first-order logics that capture logarithmic-time/space quantum computability
• ON THE POWER QUANTUM COMPUTATION OVER REAL HILBERT SPACES
• Elementary quantum recursion schemes that capture quantum polylogarithmic-time computability of quantum functions

This page was built for publication: Expressing power of elementary quantum recursion schemes for quantum logarithmic-time computability

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6102995)