Time-Space Complexity Advantages for Quantum Computing

DOI10.1007/978-3-319-71069-3_24zbMATH Open1505.68017OpenAlexW2770686326MaRDI QIDQ5055992FDOQ5055992

Authors: Shenggen Zheng, Jozef Gruska, Daowen 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

Recommendations

• Unbounded-error quantum computation with small space bounds
• Space-bounded quantum complexity
• scientific article; zbMATH DE number 1335895
• State succinctness of two-way finite automata with quantum and classical states
• Exponential separation of quantum and classical online space complexity

zbMATH Keywords

quantum computingtime-space complexity

Mathematics Subject Classification ID

Quantum algorithms and complexity in the theory of computing (68Q12) Quantum computation (81P68) Other nonclassical models of computation (68Q09)

Cites Work

• Two-way finite automata with quantum and classical states.
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Succinctness of two-way probabilistic and quantum finite automata
• On hybrid models of quantum finite automata
• Quantum search of spatial regions
• One-way finite automata with quantum and classical states
• On the state complexity of semi-quantum finite automata
• Communication Complexity
• Multiparty protocols, pseudorandom generators for Logspace, and time- space trade-offs
• Complexity measures and decision tree complexity: a survey.
• On the distributional complexity of disjointness
• On quantum and probabilistic communication: Las Vegas and one-way protocols
• Quantum and Classical Strong Direct Product Theorems and Optimal Time‐Space Tradeoffs
• Dense quantum coding and quantum finite automata
• Quantum finite automata
• From Quantum Query Complexity to State Complexity
• Generalizations of the distributed Deutsch–Jozsa promise problem
• A Time-Space Tradeoff for Sorting on a General Sequential Model of Computation
• Design and analysis of randomized algorithms. Introduction to design paradigms.
• Separations in Query Complexity Based on Pointer Functions
• Title not available (Why is that?)
• Superlinear advantage for exact quantum algorithms
• Separations in query complexity using cheat sheets
• Deterministic Communication vs. Partition Number
• Quantum time-space tradeoffs for sorting
• Title not available (Why is that?)

This page was built for publication: Time-Space Complexity Advantages for Quantum Computing

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