Source author record

Dmitry Kravchenko

Explore this author’s publications, collaborators and research topics. This catalog record has not been claimed by its author.

ResearcherUnclaimed source record

quant-ph Computational Complexity Computer Science and Game Theory Information Theory math.IT

Catalog footprint

Research overview

3works

5topics

4close collaborators

Actions

Is this your work?

Open graph Browse papers

preprint2020arXiv

Quantum-over-classical Advantage in Solving Multiplayer Games

We study the applicability of quantum algorithms in computational game theory and generalize some results related to Subtraction games, which are sometimes referred to as one-heap Nim games. In quantum game theory, a subset of Subtraction games became the first explicitly defined class of zero-sum combinatorial games with provable separation between quantum and classical complexity of solving them. For a narrower subset of Subtraction games, an exact quantum sublinear algorithm is known that surpasses all deterministic algorithms for finding solutions with probability $1$ . Typically, both Nim and Subtraction games are defined for only two players. We extend some known results to games for three or more players, while maintaining the same classical and quantum complexities: $Θ\left(n^2\right)$ and $\tilde{O}\left(n^{1.5}\right)$ respectively.

preprint2016arXiv

Parity Oblivious d-Level Random Access Codes and Class of Noncontextuality Inequalities

One of the fundamental results in quantum foundations is the Kochen-Specker no-go theorem. For the quantum theory, the no-go theorem excludes the possibility of a class of hidden variable models where value attribution is context independent. Recently, the notion of contextuality has been generalized for different operational procedures and it has been shown that preparation contextuality of mixed quantum states can be a useful resource in an information-processing task called parity-oblivious multiplexing. Here, we introduce a new class of information processing tasks, namely d-level parity oblivious random access codes and obtain bounds on the success probabilities of performing such tasks in any preparation noncontextual theory. These bounds constitute noncontextuality inequalities for any value of d. For d=3, using a set of mutually asymmetric biased bases we show that the corresponding noncontextual bound is violated by quantum theory. We also show quantum violation of the inequalities for some other higher values of d. This reveals operational usefulness of preparation contextuality of higher level quantum systems.

preprint2015arXiv

Grover's search with faults on some marked elements

Grover's algorithm is a quantum query algorithm solving the unstructured search problem of size $N$ using $O(\sqrt{N})$ queries. It provides a significant speed-up over any classical algorithm \cite{Gro96}. The running time of the algorithm, however, is very sensitive to errors in queries. It is known that if query may fail (report all marked elements as unmarked) the algorithm needs $Ω(N)$ queries to find a marked element \cite{RS08}. \cite{AB+13} have proved the same result for the model where each marked element has its own probability to be reported as unmarked. We study the behavior of Grover's algorithm in the model where the search space contains both faulty and non-faulty marked elements. We show that in this setting it is indeed possible to find one of non-faulty marked items in $O(\sqrt{N})$ queries. We also analyze the limiting behavior of the algorithm for a large number of steps and show the existence and the structure of limiting state $ρ_{lim}$ .

Inspect adjacent papers, topics, institutions and collaborators without losing the researcher page.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.