QUANTUM QUERY COMPLEXITY OF CONSTANT-SIZED SUBGRAPH CONTAINMENT

DOI10.1142/S0219749912500190zbMath1281.68113arXiv1109.4165OpenAlexW3103161513MaRDI QIDQ2909539

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

quantum query complexitylearning graph

Mathematics Subject Classification ID

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

Related Items (3)

Quantum algorithms for finding constant-sized sub-hypergraphs ⋮ On the power of non-adaptive learning graphs ⋮ Improved quantum query algorithms for triangle detection and associativity testing

Cites Work

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

This page was built for publication: QUANTUM QUERY COMPLEXITY OF CONSTANT-SIZED SUBGRAPH CONTAINMENT