QUANTUM QUERY COMPLEXITY OF CONSTANT-SIZED SUBGRAPH CONTAINMENT
From MaRDI portal
Publication:2909539
DOI10.1142/S0219749912500190zbMath1281.68113arXiv1109.4165OpenAlexW3103161513MaRDI QIDQ2909539
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
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
