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

Classically, for many computational problems one can conclude time lowerbounds conditioned on the hardness of one or more of key problems: k-SAT, 3SUMand APSP. More recently, similar results have been derived in the quantumsetting conditioned on the hardness of k-SAT and 3SUM. This is done usingfine-grained reductions, where the approach is to (1) select a key problem $X$that, for some function $T$, is conjectured to not be solvable by any$O(T(n)^{1-\epsilon})$ time algorithm for any constant $\epsilon > 0$ (in afixed model of computation), and (2) reduce $X$ in a fine-grained way to thesecomputational problems, thus giving (mostly) tight conditional time lowerbounds for them.  Interestingly, for Delta-Matching Triangles and Triangle Collection,classical hardness results have been derived conditioned on hardness of allthree mentioned key problems. More precisely, it is proven that an$n^{3-\epsilon}$ time classical algorithm for either of these two graphproblems would imply faster classical algorithms for k-SAT, 3SUM and APSP,which makes Delta-Matching Triangles and Triangle Collection worthwhile tostudy.  In this paper, we show that an $n^{1.5-\epsilon}$ time quantum algorithm foreither of these two graph problems would imply faster quantum algorithms fork-SAT, 3SUM, and APSP. We first formulate a quantum hardness conjecture forAPSP and then present quantum reductions from k-SAT, 3SUM, and APSP toDelta-Matching Triangles and Triangle Collection. Additionally, based on thequantum APSP conjecture, we are also able to prove quantum lower bounds for amatrix problem and many graph problems. The matching upper bounds followtrivially for most of them, except for Delta-Matching Triangles and TriangleCollection for which we present quantum algorithms that require careful use ofdata structures and Ambainis' variable time search.

Matching Triangles and Triangle Collection: Hardness based on a Weak Quantum Conjecture