Quantum Query Complexity of Subgraph Containment with Constant-sized Certificates

Details Quantum Query Complexity of Subgraph Containment with Constant-sized Certificates Quantum Query Complexity of Subgraph Containment with Constant-sized Certificates

2011-09-19

arxiv.org/abs/1109.4165v1

Physics

Quantum Physics

13 pages, 1 figure

Scientific paper

We study the quantum query complexity of subgraph containment with constant-sized certificates. 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-\frac{2}{k}-g(H)}) $, with $ g(H) $ a strictly positive function of $ H $. This is better than $ \tilde{O}\s{n^{2-2/k}} $ by Magniez et al. These results are obtained in the learning graph model of Belovs.

Affiliated with

Also associated with

No associations

Rating

Quantum Query Complexity of Subgraph Containment with Constant-sized Certificates does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Quantum Query Complexity of Subgraph Containment with Constant-sized Certificates, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Quantum Query Complexity of Subgraph Containment with Constant-sized Certificates will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-145722