6533b827fe1ef96bd128642e

RESEARCH PRODUCT

Classical and Quantum Computations with Restricted Memory

Farid AblayevMarat AblayevAlexander VasilievKamil KhadievKamil Khadiev

subject

Theoretical computer scienceComputer scienceComputationModel of computation010102 general mathematicsHash function0102 computer and information sciences01 natural sciencesAutomatonBranching (version control)010201 computation theory & mathematics0101 mathematicsStreaming algorithmQuantumQuantum computer

description

Automata and branching programs are known models of computation with restricted memory. These models of computation were in focus of a large number of researchers during the last decades. Streaming algorithms are a modern model of computation with restricted memory. In this paper, we present recent results on the comparative computational power of quantum and classical models of branching programs and streaming algorithms.

yearjournalcountryeditionlanguage
2018-01-01
https://doi.org/10.1007/978-3-319-98355-4_9