Quick Navigation

Overview Topics Abstract Importance Paper Tools References Reactions Discussion Publication Related

Topics

Quantum Optimization Quantum Simulation

Quantum Algorithms for Finding Constant-sized Sub-hypergraphs

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

Year

2013

Paper ID

32225

Status

Preprint

Abstract Read

~2 min

Abstract Words

108

Citations

N/A

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\(n1.883\), and a quantum algorithm for determining if a ternary operator over a set of size n is associative with query complexity O\(n2.113\).

Why This Paper Matters

  • This paper contributes to the Quantum Simulation research area in the Quantum Articles archive.
  • It adds a 2013 reference point for readers tracking recent quantum research.
  • 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...

Paper Tools

Become a member to use research tools

Sign in to open papers, visit source links, share, cite, compare, copy DOI links, request category corrections, and build your reading list.

Become a member Sign in
Show Paper arXiv Publisher Share Cite This Paper Copy URL Compare Copy DOI Add to Reading List Category Correction Request

References & Citation Signals

[1] DOI https://doi.org/arXiv:1310.4127 [2] arXiv https://arxiv.org/abs/1310.4127 [3] Publisher https://arxiv.org/abs/1310.4127

Local Citation Graph (Related-Paper Links)

Current Paper #32225 #69978 Distribution Complexity of Elec... #69974 Hierarchical separation of rela... #69964 Bounded-depth spacetime lattice... #69945 Phase Stable Integrated Delay L...

External citation index: OpenAlex citation signal

Community Reactions

Quick sentiment from readers on this paper.

Score: 0
Likes: 0 Dislikes: 0

Sign in to react to this paper.

Discussion & Reviews (Moderated)

Average Rating: 0.0 / 5 (0 ratings)

No written reviews yet.