Name
Abstract | ||
|---|---|---|
We present three new quantum algorithms in the quantum query model for \textsc{graph-collision} problem: \begin{itemize} \item an algorithm based on tree decomposition that uses $O\left(\sqrt{n}t^{\sfrac{1}{6}}\right)$ queries where $t$ is the treewidth of the graph; \item an algorithm constructed on a span program that improves a result by Gavinsky and Ito. The algorithm uses $O(\sqrt{n}+\sqrt{\alpha^{**}})$ queries, where $\alpha^{**}(G)$ is a graph parameter defined by \[\alpha^{**}(G):=\min_{VC\text{-- vertex cover of}G}{\max_{\substack{I\subseteq VC\\I\text{-- independent set}}}{\sum_{v\in I}{\deg{v}}}};\] \item an algorithm for a subclass of circulant graphs that uses $O(\sqrt{n})$ queries. \end{itemize} We also present an example of a possibly difficult graph $G$ for which all the known graphs fail to solve graph collision in $O(\sqrt{n} \log^c n)$ queries. |
Year | Venue | Field |
|---|---|---|
2013 | CoRR | Quantum,Discrete mathematics,Combinatorics,Parameterized complexity,Tree decomposition,Quantum algorithm,Circulant matrix,Independent set,Vertex cover,Treewidth,Mathematics |
DocType | Volume | Citations |
Journal | abs/1305.1021 | 2 |
PageRank | References | Authors |
0.51 | 6 | 5 |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Andris Ambainis | 1 | 2000 | 183.24 |
| Kaspars Balodis | 2 | 17 | 6.03 |
| Janis Iraids | 3 | 18 | 6.14 |
| Raitis Ozols | 4 | 10 | 2.89 |
| Juris Smotrovs | 5 | 51 | 7.35 |