×
Zhu, Yechao

Quantum query complexity of constant-sized subgraph containment. (English) Zbl 1281.68113

Int. J. Quantum Inf. 10, No. 3, 1250019, 13 p. (2012).
Summary: We study the quantum query complexity of constant-sized subgraph containment. Such problems include determining whether a \(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 \(\widetilde O(n^{2-2/k})\) by Magniez et al. This result is obtained in the learning graph model of Belovs.

Cited in 3 Documents

MSC:

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

Keywords:

quantum query complexity; learning graph
Cite Review PDF
Full Text: DOI arXiv

References:

[1] DOI: 10.1098/rspa.1992.0167 · Zbl 0792.68058 · doi:10.1098/rspa.1992.0167
[2] DOI: 10.1137/S0097539795293172 · Zbl 1005.11065 · doi:10.1137/S0097539795293172
[3] DOI: 10.1145/502090.502097 · Zbl 1127.68404 · doi:10.1145/502090.502097
[4] DOI: 10.1006/jcss.2002.1826 · Zbl 1015.68075 · doi:10.1006/jcss.2002.1826
[5] DOI: 10.1007/BF02199356 · Zbl 0952.37501 · doi:10.1007/BF02199356
[6] DOI: 10.1016/S0375-9601(96)00745-1 · Zbl 1037.82529 · doi:10.1016/S0375-9601(96)00745-1
[7] DOI: 10.1006/jcss.2000.1732 · Zbl 0990.68519 · doi:10.1006/jcss.2000.1732
[8] DOI: 10.1103/PhysRevA.67.052307 · doi:10.1103/PhysRevA.67.052307
[9] DOI: 10.1137/S0097539705447311 · Zbl 1134.81010 · doi:10.1137/S0097539705447311
[10] DOI: 10.1145/1008731.1008735 · Zbl 1169.68406 · doi:10.1145/1008731.1008735
[11] DOI: 10.1137/S0097539702402780 · Zbl 1081.68029 · doi:10.1137/S0097539702402780
[12] DOI: 10.1137/050643684 · Zbl 1166.68032 · doi:10.1137/050643684
[13] DOI: 10.1016/j.tcs.2005.01.019 · Zbl 1142.68367 · doi:10.1016/j.tcs.2005.01.019
[14] DOI: 10.1016/S0304-3975(01)00144-X · Zbl 1061.68058 · doi:10.1016/S0304-3975(01)00144-X
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.