Quantum algorithms for finding constant-sized sub-hypergraphs

DOI10.1016/J.TCS.2015.10.006zbMATH Open1333.68115arXiv1310.4127OpenAlexW1814302338MaRDI QIDQ896154FDOQ896154

François Le Gall, Seiichiro Tani, Harumichi Nishimura

Publication date: 11 December 2015

Published in: Theoretical Computer Science (Search for Journal in Brave)

Abstract: We develop a general framework to construct quantum algorithms that detect if a $3$-uniform hypergraph given as input contains a sub-hypergraph isomorphic to a prespecified constant-sized hypergraph. This framework is based on the concept of nested quantum walks recently proposed by Jeffery, Kothari and Magniez [SODA'13], and extends the methodology designed by Lee, Magniez and Santha [SODA'13] for similar problems over graphs. As applications, we obtain a quantum algorithm for finding a $4$-clique in a $3$-uniform hypergraph on $n$ vertices with query complexity $O(n^{1.883})$, and a quantum algorithm for determining if a ternary operator over a set of size $n$ is associative with query complexity $O(n^{2.113})$.

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

Recommendations

• Quantum Algorithms for Finding Constant-Sized Sub-hypergraphs
• Improved quantum query algorithms for triangle finding and associativity testing
• Improved quantum query algorithms for triangle detection and associativity testing
• Learning graph based quantum query algorithms for finding constant-size subgraphs
• Quantum algorithms for the triangle problem

zbMATH Keywords

hypergraphsquantum algorithmsquantum walk

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Quantum algorithms and complexity in the theory of computing (68Q12) Hypergraphs (05C65)

Cites Work

• Title not available (Why is that?)
• Title not available (Why is that?)
• Search via Quantum Walk
• Title not available (Why is that?)
• Polynomial-Time Algorithms for Prime Factorization and Discrete Logarithms on a Quantum Computer
• On the Power of Quantum Computation
• Title not available (Why is that?)
• Quantum Algorithms for the Triangle Problem
• Quantum Walk Algorithm for Element Distinctness
• A new algorithm for optimal 2-constraint satisfaction and its implications
• Rapid solution of problems by quantum computation
• Span Programs and Quantum Query Complexity: The General Adversary Bound Is Nearly Tight for Every Boolean Function
• Title not available (Why is that?)
• Span programs for functions with constant-sized 1-certificates
• Quantum lower bounds by polynomials
• Title not available (Why is that?)
• Title not available (Why is that?)
• Quantum query complexity of constant-sized subgraph containment
• On the power of non-adaptive learning graphs
• Title not available (Why is that?)
• Nested Quantum Walks with Quantum Data Structures
• Quantum Algorithms for Element Distinctness
• Finding, minimizing, and counting weighted subgraphs
• Time-Efficient Quantum Walks for 3-Distinctness
• Improved Quantum Query Algorithms for Triangle Finding and Associativity Testing

Cited In (3)

• Title not available (Why is that?)
• Quantum algorithm for triangle finding in sparse graphs
• Quantum Algorithms for Finding Constant-Sized Sub-hypergraphs

This page was built for publication: Quantum algorithms for finding constant-sized sub-hypergraphs

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