Quantum Query Complexity of Subgraph Containment with Constant-sized Certificates

Yechao Zhu

RECORD

Quantum Query Complexity of Subgraph Containment with Constant-sized Certificates

Yechao Zhu

Quantum Physics · Submitted 19 Sep 2011

abstract compiled · 2026-09-23 · no language-model review

The authors' main claim 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 $.

how it is stated · asserted 1.00 read the record →

Comment (0) Read on arXiv ↗

Cite ▾

Claim paper

The compiled record

The paper's own sentences, arranged. Each label is drawn from a closed vocabulary; the number beside it is the probability the classifier gave that label. Numbers in the tables are the authors', checked by code. No sentence in this record was written by a model.

Open the compiled record

Compiled by classifier-1.13-20260917 via OpenRouter, question bank abstract-p1-20260923, 2026-09-23: 1 request, 3,638 input tokens, $0.0002 reported.

What the abstract itself states, as probabilities: claims first 0.06 · states limitation 0.23 · human participants 0.01 · controlled comparison 0.15 · randomized assignment 0.01 · states quantitative result 0.98 · compares with prior results 0.98 · mentions code or data availability 0.02.

The abstract, sentence by sentence

arXiv listing abstract v2. Results and the main claim are underlined; show every role.

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-\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.

background contribution method result interpretation main claim

What the classifier reports for each sentence. The number is the probability it gave the label.
#	sentence	role	the authors' own work	states the main conclusion	strength
s0	We study the quantum query complexity of constant-sized subgraph containment.	contribution 0.80	0.71	0.07	unclear 0.52
s1	Such problems include determining whether an $ n $-vertex graph contains a triangle, clique or star of some size.	background 1.00	0.08	0.03	asserted 0.95
s2	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 $.	result 0.99	0.95	0.88	asserted 1.00
s3	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.	result 0.31	0.71	0.30	asserted 1.00

What kind of paper the classifier reports this is: theoretical result 1.00 · evidence from proof or derivation 1.00.

What was examined, and what was not

sources read

arXiv listing abstract v2

not examined

full text
figures and tables
references and citing sentences
relations to other papers

levels run

P abstract

not run

S sections
T body sentences
C citations
R cross-paper relations

Every quoted sentence on this record is the authors'. Every label is from Pith's closed vocabulary, with the probability shown beside it. Every number in the measurements table is the authors', checked by code. Record as JSON

The paper

Original 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-\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.

Human review

How Pith checks papers → · Full audit of this paper →

References

How the literature uses it

10 arXiv papers cite this in 18 sentences

Each citing sentence is taken from the citing paper's LaTeX source and typed by Pith's classifier. A label appears at probability 0.8 or more (0.95 for support), a contest at 0.7 or more; the quoted words are the citing authors'. How each label was checked · JSON

Papers citing it · 7 sentences without a confident label

Builds on it 2 papers

It is simple to extend our quantum walk algorithms for triangle finding to obtain the more general learning graph upper bounds for subgraph containment [ref] .

Nested Quantum Walks with Quantum Data Structures · Application to subgraph containment · 0.95
The algorithms for finding $k$-vertex subgraphs given in [ref] have complexity $O(n^1.48)$ for finding a $4$-path, but it was not realized there that these algorithms apply to a much broader class of functions like associativity.

Improved Quantum Query Algorithms for Triangle Finding and Associativity Testing · Associativity testing · 0.89

Uses its method or tool 1 paper

The corresponding upper bound can be derived by similar methods as used for the $k$-sum problem in Ref. [ref] .

On the Power of Non-Adaptive Learning Graphs · Examples of Application · 0.92

Compares with it 2 papers

Our very simple idea seems for now as powerful as most learning graph based algorithms [ref] , except the recent one for $k$-element distinctness [ref] , which deviates significantly from the original learning graph framework.

Nested Quantum Walks with Quantum Data Structures · Our contribution · 1.00
Independently of our work, Zhu [ref] also obtained t:main2.

A learning graph based quantum query algorithm for finding constant-size subgraphs · Introduction · 0.97

Cites it as background 5 papers

Span programs have been used to design quantum query algorithms for formula evaluation [ref] , the matrix rank problem [ref] , subgraph detection [ref] , s-t connectivity [ref] , and strong connectivity [ref] .

Time and Space Efficient Quantum Algorithms for Detecting Cycles and Testing Bipartiteness · Span Programs · 0.93
Finally, there were also upper bounds on the quantum query complexity of detecting arbitrary patterns [ref] .

Span-program-based quantum algorithm for tree detection · Introduction · 0.91
Although more general concepts of learning graphs were introduced [ref] , the non-adaptive version was used extensively [ref] , mostly because of its simplicity.

On the Power of Non-Adaptive Learning Graphs · Learning Graph Complexity · 0.93

What it cites · 6 sentences without a confident label

Builds on 1 paper

This is a natural extension of the first learning graph for the triangle problem in [ref] .

Span Programs for Functions with Constant-Sized 1-certificates · Subgraph containment problem · 1.00

Uses the method or tool of 1 paper

Then we use another type of learning graph in [ref] and derive our main theorem.

Span Programs for Functions with Constant-Sized 1-certificates · Introduction · 0.92

Compares with 1 paper

This result was obtained independently by Belovs and Lee [ref] .

Quantum Algorithm for k-distinctness with Prior Knowledge on the Input · Introduction · 0.89

Cites as background 2 papers

Following the completion of this work, I became aware of recent independent work by Lee, Magniez and Santha [ref] .

A learning graph based quantum query algorithm for finding constant-size subgraphs · Conclusion and open problems · 0.87
Recently, a modified learning graph model was proposed by Belovs and Lee [ref] .

Quantum Algorithm for k-distinctness with Prior Knowledge on the Input · Conclusion and open problems · 0.99

Discussion

Know something about this paper? Leave a comment, or highlight any passage above to comment on it.