Image de couverture de livre

Time hierarchies for sublogarithmic-space quantum computation

Fuente: arXiv

Enregistré dans:

Détails bibliographiques
Auteur principal:	Say, A. C. Cem
Format:	Preprint
Publié:	2025
Sujets:	Computational Complexity
Accès en ligne:	Acceder al recurso
Tags:	Ajouter un tag Pas de tags, Soyez le premier à ajouter un tag!

Documents similaires

Short and useful quantum proofs for sublogarithmic-space verifiers
par: Say, A. C. Cem
Publié: (2025)

Fine-grained quantum advantage beyond double-logarithmic space
par: Say, A. C. Cem
Publié: (2026)

Unconditional proofs of quantumness between small-space machines
par: Say, A. C. Cem, et autres
Publié: (2024)

Constant-Space, Constant-Randomness Verifiers with Arbitrarily Small Error
par: Gezer, M. Utkan, et autres
Publié: (2020)

$\rm P$ has polynomial-time finite-state verifiers
par: Gezer, M. Utkan, et autres
Publié: (2023)

Collapses in quantum-classical probabilistically checkable proofs and the quantum polynomial hierarchy
par: Anand, Kartik, et autres
Publié: (2025)

The complexity of computing in continuous time: space complexity is precision
par: Blanc, Manon, et autres
Publié: (2024)

Fast polynomial computations with space constraints
par: Grenet, Bruno
Publié: (2025)

Symmetric quantum computation
par: Castro-Silva, Davi, et autres
Publié: (2025)

Man, these New York Times games are hard! A computational perspective
par: Alberti, Alessandro Giovanni, et autres
Publié: (2025)

Improved separation between quantum and classical computers for sampling and functional tasks
par: Marshall, Simon C., et autres
Publié: (2024)

Quantum circuit lower bounds in the magic hierarchy
par: Parham, Natalie
Publié: (2025)

Physical complexity and black hole quantum computers
par: Reilly, Michele, et autres
Publié: (2025)

Arity hierarchies for quantifiers closed under partial polymorphisms
par: Dawar, Anuj, et autres
Publié: (2025)

Capturing the polynomial hierarchy by second-order revised Krom logic
par: Wang, Kexu, et autres
Publié: (2022)

A universal bound on the space complexity of Directed Acyclic Graph computations
par: Bilardi, Gianfranco, et autres
Publié: (2024)

The NPA hierarchy does not always attain the commuting operator value
par: Fanizza, Marco, et autres
Publié: (2025)

A full dichotomy for Holant$^c$, inspired by quantum computation
par: Backens, Miriam
Publié: (2022)

Whether a quantum computation employs nonlocal resources is operationally undecidable
par: Fields, Chris, et autres
Publié: (2025)

Downward self-reducibility in the total function polynomial hierarchy
par: Gajulapalli, Karthik, et autres
Publié: (2025)

On the computational power of $C$-random strings
par: Milovanov, Alexey
Publié: (2024)

Positivity of the symmetric group characters is as hard as the polynomial time hierarchy
par: Ikenmeyer, Christian, et autres
Publié: (2022)

On the quantum computational complexity of classical linear dynamics with geometrically local interactions: Dequantization and universality
par: Sakamoto, Kazuki, et autres
Publié: (2025)

Space-bounded quantum state testing via space-efficient quantum singular value transformation
par: Gall, François Le, et autres
Publié: (2023)

Unconventional complexity classes in unconventional computing (extended abstract)
par: Porreca, Antonio E.
Publié: (2024)

Limit on the computational power of $\mathrm{C}$-random strings
par: Milovanov, Alexey
Publié: (2026)

On the power of counting the total number of computation paths of NPTMs
par: Bakali, Eleni, et autres
Publié: (2023)

The computational power of discrete chemical reaction networks with bounded executions
par: Doty, David, et autres
Publié: (2024)

A computing machinery using a continuous memory tape
par: Oktar, Yigit
Publié: (2023)

Monitoring graph edges via shortest paths: computational complexity and approximation algorithms
par: Colli, Giordano
Publié: (2025)

The computational two-way quantum capacity
par: Meyer, Johannes Jakob, et autres
Publié: (2026)

Stochastic thermodynamics of computation
par: Wolpert, David H.
Publié: (2019)

Bounding the computational power of bosonic systems
par: Upreti, Varun, et autres
Publié: (2025)

Geometric and computational hardness of bilevel programming
par: Bolte, Jérôme, et autres
Publié: (2024)

Quantum computational complexity of matrix functions
par: Cifuentes, Santiago, et autres
Publié: (2024)

Quantum computation with indefinite causal structures
par: Araújo, Mateus, et autres
Publié: (2017)

On hardness of computing analytic Brouwer degree
par: Chakraborty, Somnath
Publié: (2023)

Robust and optimal loading of general classical data into quantum computers
par: Zhang, Xiao-Ming
Publié: (2024)

A new metric for evaluating the performance and complexity of computer programs: A new approach to the traditional ways of measuring the complexity of algorithms and estimating running times
par: Folea, Rares, et autres
Publié: (2025)

Simulating Time With Square-Root Space
par: Williams, R. Ryan
Publié: (2025)