English (United Kingdom)

https://curated-unify.zendy.io/wp-json/zendy-region/v1/featured_content/oa?rat=en

https://curated-unify.zendy.io/wp-json/zendy-region/v1/highlighted_journal/

Global: Zendy Plus annual

Presents the access of premium content as premium feature

Premium Content

Presents the keyphrase highlighting as premium feature

Keyphrase Highlighting

Presents the summarisation as premium feature

Summarisation

Insights

Presents the pdf analysis as premium feature

PDF Analysis

Presents the zaia usage as premium feature

ZAIA

Global: Zendy Plus monthly

Global: Zendy Tools annual

Global: Zendy Tools monthly

Global: Zendy Free Plan

We show that an improvement to the best known quantum lower bound forGRAPH-COLLISION problem implies an improvement to the best known lower boundfor TRIANGLE problem in the quantum query complexity model. In GRAPH-COLLISIONwe 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 thereexist $(u,v) \in E$, such that $f(u)=f(v)=1$. In TRIANGLE we have a black boxaccess to an adjacency matrix of a graph and we have to determine if the graphcontains a triangle. For both of these problems the known lower bounds aretrivial ($\Omega(\sqrt{n})$ and $\Omega(n)$, respectively) and there is noknown matching upper bound.

Quantum Lower Bound for Graph Collision Implies Lower Bound for Triangle Detection