Time-Space Complexity Advantages for Quantum Computing
From MaRDI portal
Publication:5055992
DOI10.1007/978-3-319-71069-3_24zbMath1505.68017OpenAlexW2770686326MaRDI QIDQ5055992
Shenggen Zheng, Jozef Gruska, Dao Wen Qiu
Publication date: 9 December 2022
Published in: Theory and Practice of Natural Computing (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/978-3-319-71069-3_24
Quantum computation (81P68) Quantum algorithms and complexity in the theory of computing (68Q12) Other nonclassical models of computation (68Q09)
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Multiparty protocols, pseudorandom generators for Logspace, and time- space trade-offs
- On the distributional complexity of disjointness
- Design and analysis of randomized algorithms. Introduction to design paradigms.
- Two-way finite automata with quantum and classical states.
- Complexity measures and decision tree complexity: a survey.
- On hybrid models of quantum finite automata
- From Quantum Query Complexity to State Complexity
- Generalizations of the distributed Deutsch–Jozsa promise problem
- One-Way Finite Automata with Quantum and Classical States
- On quantum and probabilistic communication
- Dense quantum coding and quantum finite automata
- Quantum time-space tradeoffs for sorting
- A Time-Space Tradeoff for Sorting on a General Sequential Model of Computation
- Deterministic Communication vs. Partition Number
- Separations in Query Complexity Based on Pointer Functions
- Communication Complexity
- On the state complexity of semi-quantum finite automata
- Separations in query complexity using cheat sheets
- Quantum and Classical Strong Direct Product Theorems and Optimal Time‐Space Tradeoffs
- Superlinear advantage for exact quantum algorithms
