Search results for "Quantum query"
showing 3 items of 13 documents
Ultrametric Vs. Quantum Query Algorithms
2014
Ultrametric algorithms are similar to probabilistic algorithms but they describe the degree of indeterminism by p-adic numbers instead of real numbers. This paper introduces the notion of ultrametric query algorithms and shows an example of advantages of ultrametric query algorithms over deterministic, probabilistic and quantum query algorithms.
Quantum Lower Bound for Graph Collision Implies Lower Bound for Triangle Detection
2015
We show that an improvement to the best known quantum lower bound for GRAPH-COLLISION problem implies an improvement to the best known lower bound for TRIANGLE problem in the quantum query complexity model. In GRAPH-COLLISION we are given free access to a graph $(V,E)$ and access to a function $f:V\rightarrow \{0,1\}$ as a black box. We are asked to determine if there exist $(u,v) \in E$, such that $f(u)=f(v)=1$. In TRIANGLE we have a black box access to an adjacency matrix of a graph and we have to determine if the graph contains a triangle. For both of these problems the known lower bounds are trivial ($\Omega(\sqrt{n})$ and $\Omega(n)$, respectively) and there is no known matching upper …
Grover’s Search with Faults on Some Marked Elements
2016
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 [2]. The running time of the algorithm, however, is very sensitive to errors in queries. Multiple authors have analysed the algorithm using different models of query errors and showed the loss of quantum speed-up [1, 4]. 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 marked elements in $$O\sqrt{N}$$ queries.