Extended learning graphs for triangle finding

DOI10.1007/S00453-019-00627-ZMaRDI QIDQ2300731zbMATH OpenOpenAlexFDO

Authors Titouan Carette, Mathieu Laurière, Frédéric Magniez

Publication date 28 February 2020

Published in Algorithmica (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1609.07786

zbMATH Keywords

learning graphquantum query complexityquantum walktriangle finding

Mathematics Subject Classification ID

Density (toughness, etc.) (05C42) Graph algorithms (graph-theoretic aspects) (05C85) Quantum algorithms and complexity in the theory of computing (68Q12) Graph theory (including graph drawing) in computer science (68R10)

Abstract: We present new quantum algorithms for Triangle Finding improving its best previously known quantum query complexities for both dense and spare instances.For dense graphs on $n$ vertices, we get a query complexity of $O(n^{5/4})$ without any of the extra logarithmic factors present in the previous algorithm of Le Gall [FOCS'14]. For sparse graphs with $mgeq{n}^{5/4}$ edges, we get a query complexity of $O(n^{11/12}{m}^{1/6}sqrtlogn)$, which is better than the one obtained by Le Gall and Nakajima [ISAAC'15] when $mgeq{n}^{3/2}$. We also obtain an algorithm with query complexity $O(n^{5/6}(mlogn{)}^{1/6}+d_{2}sqrtn)$ where $d_2$ is the variance of the degree distribution. Our algorithms are designed and analyzed in a new model of learning graphs that we call extended learning graphs. In addition, we present a framework in order to easily combine and analyze them. As a consequence we get much simpler algorithms and analyses than previous algorithms of Le Gall {it et al} based on the MNRS quantum walk framework [SICOMP'11].

Recommendations

• Extended Learning Graphs for Triangle Finding
• Improved quantum query algorithms for triangle finding and associativity testing
• Quantum Algorithms for the Triangle Problem

Cites work

• CREW PRAM<scp>s</scp> and Decision Trees
• scientific article; zbMATH DE number 5605071 (Why is no real title available?)
• scientific article; zbMATH DE number 5485488 (Why is no real title available?)
• scientific article; zbMATH DE number 1256737 (Why is no real title available?)
• scientific article; zbMATH DE number 2038718 (Why is no real title available?)
• scientific article; zbMATH DE number 1776257 (Why is no real title available?)
• scientific article; zbMATH DE number 2103524 (Why is no real title available?)
• Improved quantum query algorithms for triangle detection and associativity testing
• On the power of non-adaptive learning graphs
• Polynomial-Time Algorithms for Prime Factorization and Discrete Logarithms on a Quantum Computer
• Quantum Algorithms for Element Distinctness
• Quantum Algorithms for the Triangle Problem
• Quantum algorithms revisited
• Quantum lower bounds by polynomials
• Quantum Query Complexity of State Conversion
• Quantum search with variable times
• Reflections for quantum query algorithms
• Search via Quantum Walk
• Separations in query complexity using cheat sheets
• Span programs for functions with constant-sized 1-certificates (extended abstract)
• Time-efficient quantum walks for 3-distinctness
• Understanding quantum algorithms via query complexity

Cited in

(6)

• Models in quantum computing: a systematic review
• Extended Learning Graphs for Triangle Finding
• On the power of non-adaptive learning graphs
• Improved quantum query algorithms for triangle detection and associativity testing
• Improved quantum query algorithms for triangle finding and associativity testing
• Parameterized quantum query algorithms for graph problems

This page was built for publication: Extended learning graphs for triangle finding

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2300731)