Cover Image

A Schematic Definition of Quantum Polynomial Time Computability

Fuente: arXiv

Saved in:

Bibliographic Details
Main Author:	Yamakami, Tomoyuki
Format:	Preprint
Published:	2018
Subjects:	Computational Complexity Logic 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)

Elementary Quantum Recursion Schemes That Capture Quantum Polylogarithmic Time Computability of Quantum Functions
by: Yamakami, Tomoyuki
Published: (2023)

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

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

SAT, Gadgets, Max2XOR, and Quantum Annealers
by: Ansótegui, Carlos, et al.
Published: (2024)

Search-Driven Clause Learning for Product-State Quantum $k$-SAT (PRODSAT-QSAT)
by: González-Castillo, Samuel, et al.
Published: (2026)

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

Satisfiability of commutative vs. non-commutative CSPs
by: Bulatov, Andrei A., et al.
Published: (2024)

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)

Flexible Type-Based Resource Estimation in Quantum Circuit Description Languages
by: Colledan, Andrea, et al.
Published: (2024)

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

Undecidability and incompleteness in quantum information theory and operator algebras
by: Goldbring, Isaac
Published: (2024)

Functional variant of Polynomial Analogue of Gandy's Fixed Point Theorem
by: Nechesov, Andrey
Published: (2024)

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

Polynomial Calculus sizes over the Boolean and Fourier bases are incomparable
by: Mouli, Sasank
Published: (2024)

Relating the Computational and Logical Difficulty of Solving ODEs: From Polynomial to Discontinuous Right-Hand Sides
by: Bournez, Olivier, et al.
Published: (2026)

Meta-Mathematics of Computational Complexity Theory
by: Oliveira, Igor C.
Published: (2025)

Undecidability of Polynomial Inequalities in Subset Densities and Additive Energies
by: Li, Yaqiao
Published: (2025)

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)

Complexity Classification of Complex-Weighted Counting Acyclic Constraint Satisfaction Problems
by: Yamakami, Tomoyuki
Published: (2024)

Polynomial-Time Classical Simulation of Noisy Quantum Circuits with Naturally Fault-Tolerant Gates
by: Nelson, Jon, et al.
Published: (2024)

The Entangled Quantum Polynomial Hierarchy Collapses
by: Grewal, Sabee, et al.
Published: (2024)

Potential for Polynomial Solution for NP-Complete Problems using Quantum Computation
by: Badihian, Neema Rustin
Published: (2025)

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

A Theory for Probabilistic Polynomial-Time Reasoning
by: Chen, Lijie, et al.
Published: (2026)

Oracle Separations for the Quantum-Classical Polynomial Hierarchy
by: Agarwal, Avantika, et al.
Published: (2024)

On the Pure Quantum Polynomial Hierarchy and Quantified Hamiltonian Complexity
by: Grewal, Sabee, et al.
Published: (2025)

Quantum Polymorphisms and the Complexity of Quantum Constraint Satisfaction
by: Ciardo, Lorenzo, et al.
Published: (2025)

On the Quantum Chromatic Gap
by: Ciardo, Lorenzo
Published: (2025)

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

Quantum Polynomial Hierarchies: Karp-Lipton, error reduction, and lower bounds
by: Agarwal, Avantika, et al.
Published: (2024)

Polynomial-Time Classical Simulation of Noisy IQP Circuits with Constant Depth
by: Rajakumar, Joel, et al.
Published: (2024)

Classical Simulation of Quantum CSP Strategies
by: Banakh, Demian, et al.
Published: (2025)

Specification and Automatic Verification of Computational Reductions
by: Grange, Julien, et al.
Published: (2024)

Logic and Computation through the Lens of Semirings
by: Barlag, Timon, et al.
Published: (2025)

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