10 citations · 13 across the 4 of their papers we have counts for
5 papers · 1 filter
On Randomized and Quantum Query Complexities
Gatis Midrijanis
We study randomized and quantum query (a.k.a. decision tree) complexity for all total Boolean functions, with emphasis to derandomization and dequantization (removing quantumness f…
Exact quantum query complexity for total Boolean functions
Gatis Midrijanis
We will show that if there exists a quantum query algorithm that exactly computes some total Boolean function f by making T queries, then there is a classical deterministic algorit…
A polynomial quantum query lower bound for the set equality problem
Gatis Midrijanis
The set equality problem is to tell whether two sets and are equal or disjoint under the promise that one of these is the case. This problem is related to the Graph Isomorp…
The Complexity of Probabilistic versus Quantum Finite Automata
Gatis Midrijanis
We present a language which is recognizable by a probabilistic finite automaton (PFA) with probability for all with states, with a deterministic fi…
Quantum lower bounds for the set equality problems
Gatis Midrijanis
The set equality problem is to decide whether two sets and are equal or disjoint, under the promise that one of these is the case. Some other problems, like the Graph Isomo…