Quantum query complexity of constant-sized subgraph containment

DOI10.1142/S0219749912500190MaRDI QIDQ2909539zbMATH OpenOpenAlexFDO

Authors Yechao Zhu

Publication date 30 August 2012

Published in International Journal of Quantum Information (Search for Journal in Brave)

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

zbMATH Keywords

learning graphquantum query complexity

Mathematics Subject Classification ID

Isomorphism problems in graph theory (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.) (05C60) Quantum algorithms and complexity in the theory of computing (68Q12) Analysis of algorithms and problem complexity (68Q25)

Abstract: We study the quantum query complexity of constant-sized subgraph containment. Such problems include determining whether an $n$-vertex graph contains a triangle, clique or star of some size. For a general subgraph $H$ with $k$ vertices, we show that $H$ containment can be solved with quantum query complexity $O(n^{2-frac2k-g(H)})$, with $g(H)$ a strictly positive function of $H$. This is better than $ildeOs{n}^{2-2/k}$ by Magniez et al. These results are obtained in the learning graph model of Belovs.

Recommendations

• Learning graph based quantum query algorithms for finding constant-size subgraphs
• Quantum query complexity of subgraph isomorphism and homomorphism
• Improved quantum query algorithms for triangle detection and associativity testing
• Improved quantum query algorithms for triangle finding and associativity testing
• Quantum query complexity of minor-closed graph properties

Cites work

• Complexity measures and decision tree complexity: a survey.
• From quantum cellular automata to quantum lattice gases
• On the absence of homogeneous scalar unitary cellular automata.
• On the power of Ambainis lower bounds
• 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 lower bounds by polynomials
• Quantum lower bounds by quantum arguments
• Quantum lower bounds for the collision and the element distinctness problems
• Quantum simulations of classical random walks and undirected graph connectivity
• Quantum Walk Algorithm for Element Distinctness
• Rapid solution of problems by quantum computation

Cited in

(10)

• Quantum Algorithms for Finding Constant-Sized Sub-hypergraphs
• Quantum query complexity of minor-closed graph properties
• Quantum query complexity of subgraph isomorphism and homomorphism
• On the power of non-adaptive learning graphs
• Quantum query complexity of minor-closed graph properties
• Improved quantum query algorithms for triangle detection and associativity testing
• Learning graph based quantum query algorithms for finding constant-size subgraphs
• SOFSEM 2004: Theory and Practice of Computer Science
• Parameterized quantum query algorithms for graph problems
• Quantum algorithms for finding constant-sized sub-hypergraphs

This page was built for publication: Quantum query complexity of constant-sized subgraph containment

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