5 papers
On the quantum communication complexity of total functions
Dmytro Gavinsky
We present a total function with a polylogarithmic two-message quantum protocol, whereas every randomised protocol, even with arbitrarily many rounds, requires polynomial communica…
Asymptotic yet practical optimization of quantum circuits implementing GF() multiplication and division operations
Noureldin Yosri, Dmytro Gavinsky, Dmitri Maslov
We present optimized quantum circuits for GF multiplication and division operations, which are essential computing primitives in various quantum algorithms. Our ancilla-free…
Anonymous Quantum Tokens with Classical Verification
Dmytro Gavinsky, Dar Gilboa, Siddhartha Jain +2
The no-cloning theorem can be used as a basis for quantum money constructions which guarantee unconditionally unforgeable currency. Existing schemes, however, either (i) require lo…
Unambiguous parity-query complexity
Dmytro Gavinsky
We give a lower bound of on the unambiguous randomised parity-query complexity of the approximate majority problem -- that is, on the lowest randomised parity-query co…
Patterned non-determinism in communication complexity
Dmytro Gavinsky
We define and study the model of patterned non-determinism in bipartite communication complexity, denoted by . It generalises the known models $UP^{X\left…