Zobrazeno 1 - 10
of 42
pro vyhledávání: '"Mande, Nikhil S."'
Given a Boolean function $f:\{0,1\}^n\to\{0,1\}$, the goal in the usual query model is to compute $f$ on an unknown input $x \in \{0,1\}^n$ while minimizing the number of queries to $x$. One can also consider a "distinguishing" problem denoted by $f_
Externí odkaz:
http://arxiv.org/abs/2408.12595
Autor:
Mande, Nikhil S., Shao, Changpeng
Quantum-inspired classical algorithms provide us with a new way to understand the computational power of quantum computers for practically-relevant problems, especially in machine learning. In the past several years, numerous efficient algorithms for
Externí odkaz:
http://arxiv.org/abs/2402.15686
A tournament is a complete directed graph. A king in a tournament is a vertex v such that every other vertex is reachable from v via a path of length at most 2. It is well known that every tournament has at least one king, one of which is a maximum o
Externí odkaz:
http://arxiv.org/abs/2402.14751
In the area of query complexity of Boolean functions, the most widely studied cost measure of an algorithm is the worst-case number of queries made by it on an input. Motivated by the most natural cost measure studied in online algorithms, the compet
Externí odkaz:
http://arxiv.org/abs/2309.15026
A tournament is a complete directed graph. It is well known that every tournament contains at least one vertex v such that every other vertex is reachable from v by a path of length at most 2. All such vertices v are called *kings* of the underlying
Externí odkaz:
http://arxiv.org/abs/2308.02472
Autor:
Mande, Nikhil S., de Wolf, Ronald
Phase estimation, due to Kitaev [arXiv'95], is one of the most fundamental subroutines in quantum computing. In the basic scenario, one is given black-box access to a unitary $U$, and an eigenstate $\lvert \psi \rangle$ of $U$ with unknown eigenvalue
Externí odkaz:
http://arxiv.org/abs/2305.04908
We show that the deterministic decision tree complexity of a (partial) function or relation $f$ lifts to the deterministic parity decision tree (PDT) size complexity of the composed function/relation $f \circ g$ as long as the gadget $g$ satisfies a
Externí odkaz:
http://arxiv.org/abs/2211.17214
Given a classical query algorithm as a decision tree, when does there exist a quantum query algorithm with a speed-up over the classical one? We provide a general construction based on the structure of the underlying decision tree, and prove that thi
Externí odkaz:
http://arxiv.org/abs/2203.02968
We study the problem of computing the Hamming weight of an $n$-bit string modulo $m$, for any positive integer $m \leq n$ whose only prime factors are 2 and 3. We show that the exact quantum query complexity of this problem is $\left\lceil n(1 - 1/m)
Externí odkaz:
http://arxiv.org/abs/2112.14682
We investigate the randomized and quantum communication complexities of the well-studied Equality function with small error probability $\epsilon$, getting optimal constant factors in the leading terms in a number of different models. In the randomiz
Externí odkaz:
http://arxiv.org/abs/2107.11806