Cover Image

Elementary Quantum Recursion Schemes That Capture Quantum Polylogarithmic Time Computability of Quantum Functions

Fuente: arXiv

Saved in:

Bibliographic Details
Main Author:	Yamakami, Tomoyuki
Format:	Preprint
Published:	2023
Subjects:	Computational Complexity Quantum Physics
Online Access:	Acceder al recurso
Tags:	Add Tag No Tags, Be the first to tag this record!

Similar Items

Quantum First-Order Logics That Capture Logarithmic-Time/Space Quantum Computability
by: Yamakami, Tomoyuki
Published: (2025)

A Schematic Definition of Quantum Polynomial Time Computability
by: Yamakami, Tomoyuki
Published: (2018)

How Does Adiabatic Quantum Computation Fit into Quantum Automata Theory?
by: Yamakami, Tomoyuki
Published: (2020)

Nonuniform Families of Polynomial-Size Quantum Finite Automata and Quantum Logarithmic-Space Computation with Polynomial-Size Advice
by: Yamakami, Tomoyuki
Published: (2019)

Quantum Advantage from One-Way Functions
by: Morimae, Tomoyuki, et al.
Published: (2023)

Hardness of Quantum Distribution Learning and Quantum Cryptography
by: Hiroka, Taiga, et al.
Published: (2025)

The Space-Time Cost of Purifying Quantum Computations
by: Zhandry, Mark
Published: (2024)

New Quantum Algorithms for Computing Quantum Entropies and Distances
by: Wang, Qisheng, et al.
Published: (2022)

From Worst-Case Hardness of $\mathsf{NP}$ to Quantum Cryptography via Quantum Indistinguishability Obfuscation
by: Morimae, Tomoyuki, et al.
Published: (2025)

Logical Expressibility of Syntactic NL for Complementarity, Monotonicity, and Maximization
by: Yamakami, Tomoyuki
Published: (2024)

The 2CNF Boolean Formula Satisfiability Problem and the Linear Space Hypothesis
by: Yamakami, Tomoyuki
Published: (2017)

The Power of Lorentz Quantum Computer
by: Zhang, Qi, et al.
Published: (2024)

Bosonic Quantum Computational Complexity
by: Chabaud, Ulysse, et al.
Published: (2024)

Quantum Cryptography and Hardness of Non-Collapsing Measurements
by: Morimae, Tomoyuki, et al.
Published: (2025)

Unambiguous and Co-Nondeterministic Computations of Finite Automata and Pushdown Automata Families and the Effects of Multiple Counters
by: Yamakami, Tomoyuki
Published: (2024)

Quantum Public-Key Encryption with Tamper-Resilient Public Keys from One-Way Functions
by: Kitagawa, Fuyuki, et al.
Published: (2023)

Modifications of Quantum Computation and Adaptive Queries to PP
by: Miloschewsky, David, et al.
Published: (2025)

Random Unitaries in Constant (Quantum) Time
by: Foxman, Ben, et al.
Published: (2025)

Machine Learning by Adiabatic Evolutionary Quantum System
by: Yamakami, Tomoyuki
Published: (2025)

Quantum-Computable One-Way Functions without One-Way Functions
by: Kretschmer, William, et al.
Published: (2024)

Computational Complexity and Simulability of Non-Hermitian Quantum Dynamics
by: Barch, Brian, et al.
Published: (2025)

Quantum and Classical Communication Complexity of Permutation-Invariant Functions
by: Guan, Ziyi, et al.
Published: (2023)

Rewindable Quantum Computation and Its Equivalence to Cloning and Adaptive Postselection
by: Hiromasa, Ryo, et al.
Published: (2022)

New Lower-bounds for Quantum Computation with Non-Collapsing Measurements
by: Miloschewsky, David, et al.
Published: (2024)

Multimarked Spatial Search by Continuous-Time Quantum Walk
by: Lugão, Pedro H. G., et al.
Published: (2022)

Dequantizing the Quantum Singular Value Transformation: Hardness and Applications to Quantum Chemistry and the Quantum PCP Conjecture
by: Gharibian, Sevag, et al.
Published: (2021)

Following Forrelation -- Quantum Algorithms in Exploring Boolean Functions' Spectra
by: Dutta, Suman, et al.
Published: (2021)

Cryptographic Conditions for Efficient Testing of Distributions and Quantum States
by: Cavalar, Bruno, et al.
Published: (2025)

Power of Counting by Nonuniform Families of Polynomial-Size Finite Automata
by: Yamakami, Tomoyuki
Published: (2023)

Coherent-State Propagation: A Computational Framework for Simulating Bosonic Quantum Systems
by: Guseynov, Nikita, et al.
Published: (2026)

Between SC and LOGDCFL: Families of Languages Accepted by Logarithmic-Space Deterministic Auxiliary Depth-k Storage Automata
by: Yamakami, Tomoyuki
Published: (2022)

Intersection and Union Hierarchies of Deterministic Context-Free Languages and Pumping Lemmas
by: Yamakami, Tomoyuki
Published: (2021)

The No Endmarker Theorem for One-Way Probabilistic Pushdown Automata
by: Yamakami, Tomoyuki
Published: (2021)

Nondeterministic Auxiliary Depth-Bounded Storage Automata and Semi-Unbounded Fan-in Cascading Circuits
by: Yamakami, Tomoyuki
Published: (2024)

Sampling Frequency Thresholds for Quantum Advantage of Quantum Approximate Optimization Algorithm
by: Lykov, Danylo, et al.
Published: (2022)

Oracle Separation between Noisy Quantum Polynomial Time and the Polynomial Hierarchy
by: Chia, Nai-Hui, et al.
Published: (2024)

On the Computational Hardness of Quantum One-Wayness
by: Cavalar, Bruno, et al.
Published: (2023)

Uncloneable Quantum Advice
by: Broadbent, Anne, et al.
Published: (2023)

Basic Quantum Algorithms
by: Portugal, Renato
Published: (2022)

Quantum Threshold is Powerful
by: Grier, Daniel, et al.
Published: (2024)