0000000000341280

AUTHOR

Farid Ablayev

0000-0002-5592-3211

showing 4 related works from this author

Very Narrow Quantum OBDDs and Width Hierarchies for Classical OBDDs

2014

In the paper we investigate a model for computing of Boolean functions – Ordered Binary Decision Diagrams (OBDDs), which is a restricted version of Branching Programs. We present several results on the comparative complexity for several variants of OBDD models. We present some results on the comparative complexity of classical and quantum OBDDs. We consider a partial function depending on a parameter k such that for any k > 0 this function is computed by an exact quantum OBDD of width 2, but any classical OBDD (deterministic or stable bounded-error probabilistic) needs width 2 k + 1. We consider quantum and classical nondeterminism. We show that quantum nondeterminism can be more efficient …

Discrete mathematicsImplicit functionBinary decision diagram010102 general mathematics02 engineering and technologyFunction (mathematics)Computer Science::Artificial IntelligenceComputer Science::Computational Complexity01 natural sciencesCombinatoricsNondeterministic algorithmComputer Science::Logic in Computer SciencePartial function0202 electrical engineering electronic engineering information engineering020201 artificial intelligence & image processing0101 mathematicsBoolean functionQuantumQuantum computerMathematics
researchProduct

Classical and Quantum Computations with Restricted Memory

2018

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.

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

Lower Bounds and Hierarchies for Quantum Memoryless Communication Protocols and Quantum Ordered Binary Decision Diagrams with Repeated Test

2017

We explore multi-round quantum memoryless communication protocols. These are restricted version of multi-round quantum communication protocols. The “memoryless” term means that players forget history from previous rounds, and their behavior is obtained only by input and message from the opposite player. The model is interesting because this allows us to get lower bounds for models like automata, Ordered Binary Decision Diagrams and streaming algorithms. At the same time, we can prove stronger results with this restriction. We present a lower bound for quantum memoryless protocols. Additionally, we show a lower bound for Disjointness function for this model. As an application of communicatio…

Discrete mathematicsSublinear functionComputational complexity theory010102 general mathematics0102 computer and information sciencesFunction (mathematics)01 natural sciencesUpper and lower boundsCombinatorics010201 computation theory & mathematicsQuantum algorithm0101 mathematicsQuantum information scienceCommunication complexityQuantum computerMathematics
researchProduct

Lower Bounds and Hierarchies for Quantum Memoryless Communication Protocols and Quantum Ordered Binary Decision Diagrams with Repeated Test

2017

We explore multi-round quantum memoryless communication protocols. These are restricted version of multi-round quantum communication protocols. The "memoryless" term means that players forget history from previous rounds, and their behavior is obtained only by input and message from the opposite player. The model is interesting because this allows us to get lower bounds for models like automata, Ordered Binary Decision Diagrams and streaming algorithms. At the same time, we can prove stronger results with this restriction. We present a lower bound for quantum memoryless protocols. Additionally, we show a lower bound for Disjointness function for this model. % As an application of communicat…

FOS: Computer and information sciencesComputer Science - Computational ComplexityQuantum PhysicsFOS: Physical sciencesComputational Complexity (cs.CC)Quantum Physics (quant-ph)
researchProduct