Quantum algorithms for finding constant-sized sub-hypergraphs

DOI10.1016/J.TCS.2015.10.006MaRDI QIDQ896154zbMATH OpenOpenAlexFDO

Authors François Le Gall, Harumichi Nishimura, Seiichiro Tani

Publication date 11 December 2015

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

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

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)

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})$.

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

Cites work

• scientific article; zbMATH DE number 1579275 (Why is no real title available?)
• scientific article; zbMATH DE number 5076264 (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 1540669 (Why is no real title available?)
• scientific article; zbMATH DE number 1776257 (Why is no real title available?)
• A new algorithm for optimal 2-constraint satisfaction and its implications
• Finding, minimizing, and counting weighted subgraphs
• Improved output-sensitive quantum algorithms for Boolean matrix multiplication
• Improved quantum query algorithms for triangle finding and associativity testing
• Learning graph based quantum query algorithms for finding constant-size subgraphs
• Nested Quantum Walks with Quantum Data Structures
• On the Power of Quantum Computation
• 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 Walk Algorithm for Element Distinctness
• Quantum lower bounds by polynomials
• Quantum query complexity of constant-sized subgraph containment
• Rapid solution of problems by quantum computation
• Search via Quantum Walk
• Span Programs and Quantum Query Complexity: The General Adversary Bound Is Nearly Tight for Every Boolean Function
• Span programs for functions with constant-sized 1-certificates (extended abstract)
• Time-efficient quantum walks for 3-distinctness

Cited in

(3)

• Quantum Algorithms for Finding Constant-Sized Sub-hypergraphs
• Computing hypergraph Ramsey numbers by using quantum circuit
• scientific article; zbMATH DE number 5320343 (Why is no real title available?)

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)