arXiv:2308.16827

Linear-depth quantum oracles for clique problems from edge colorings and graph states, with linear non-Clifford cost and a provably bounded-error k-clique search

Payman Kazemikhah, Ali Hadizadeh Moghadam, Hossein Aghababa

Published Aug 31, 2023• 0 citations

Abstract

Quantum algorithms for clique problems are usually analyzed in the query model, where the graph is accessed through an oracle of unit cost. When the oracle must itself be compiled into gates, published $k$-clique circuits have depth quadratic in the number $n$ of vertices, and every oracle that counts edges spends at least one non-Clifford gate per edge. We first show that scheduling the commuting edge gates by a proper edge coloring yields adjacency-type oracles, including an exact $k$-clique oracle, whose depth and width are linear in $n$, within a logarithmic factor of a depth--width lower bound. Our central result is a $k$-clique oracle in which the graph enters only through the Clifford gate that prepares a graph state, so that its non-Clifford cost is linear in $n$ for every graph. We analyze this oracle exactly: on a candidate vertex set it acts as a reflection whose overlap is $-1$ for cliques and, as we prove, at most $5/8$ in modulus otherwise, a tight bound that tends to $1/2$ as the candidate set grows. A two-qubit phase-estimation filter turns the reflection into a one-sided bounded-error phase oracle, and amplitude amplification then finds a $k$-clique with $O(\sqrt{\binom nk})$ oracle calls, each of depth $O(Δ+\log n)$ for maximum degree $Δ$. The guarantee holds for two or more estimation registers; exact simulations on $312$ induced subgraphs of two brain networks confirm it and show that the cheaper single-register variant performs nearly as well.

DOI: 10.48550/arxiv.2308.16827

Related papers

Quantum Query Algorithms for the Constructive Diagonal Ramsey Theorem

Cheng Xin

quant-pharXiv:2609.05812Sep 8, 20260 citations

Quantum Circuit Design for Finding k-Cliques via Quantum Amplitude Amplification Strategies

Simone Perriello

ACM International Conference on Computing Frontiers (CF)May 28, 20252 citations

Superlinear Quantum Query Lower Bounds for Subgraph Detection

Amin Shiraz Gilani, Xingyu Zhou

quant-pharXiv:2609.40263Oct 1, 20260 citations

A quantum algorithm for learning a graph of bounded degree

Asaf Ferber, Liam Hardiman

arXiv:2402.18714Feb 28, 20240 citations

Complexity of graph-state preparation by Clifford circuits

Soh Kumabe, Ryuhei Mori, Yusei Yoshimura

arXiv:2402.05874QuantumJul 18, 20261 citation

Tight bounds for hybrid quantum-classical query algorithms

Andris Ambainis, András Gilyén, Martins Kokainis

quant-pharXiv:2610.06803Oct 6, 20260 citations

arXiv:2308.16827

Linear-depth quantum oracles for clique problems from edge colorings and graph states, with linear non-Clifford cost and a provably bounded-error k-clique search

Payman Kazemikhah, Ali Hadizadeh Moghadam, Hossein Aghababa

Published Aug 31, 2023• 0 citations

arXiv HTML PDF

Abstract

k

-clique circuits have depth quadratic in the number

n

of vertices, and every oracle that counts edges spends at least one non-Clifford gate per edge. We first show that scheduling the commuting edge gates by a proper edge coloring yields adjacency-type oracles, including an exact

k

-clique oracle, whose depth and width are linear in

n

, within a logarithmic factor of a depth--width lower bound. Our central result is a

k

-clique oracle in which the graph enters only through the Clifford gate that prepares a graph state, so that its non-Clifford cost is linear in

n

for every graph. We analyze this oracle exactly: on a candidate vertex set it acts as a reflection whose overlap is

-1

for cliques and, as we prove, at most

5/8

in modulus otherwise, a tight bound that tends to

1/2

as the candidate set grows. A two-qubit phase-estimation filter turns the reflection into a one-sided bounded-error phase oracle, and amplitude amplification then finds a

k

-clique with

O(\sqrt{\binom nk})

oracle calls, each of depth

O(Δ+\log n)

for maximum degree

Δ

. The guarantee holds for two or more estimation registers; exact simulations on

312

induced subgraphs of two brain networks confirm it and show that the cheaper single-register variant performs nearly as well.

DOI: 10.48550/arxiv.2308.16827

Related papers

Quantum Query Algorithms for the Constructive Diagonal Ramsey Theorem

Cheng Xin

The constructive diagonal Ramsey problem asks, given adjacency-oracle access to an $N$ -vertex graph, for a clique or independent set of the order guaranteed by Ramsey's theorem. We give a bounded-error quantum algorithm that, for every $K\ge2$ and $N\ge4^{K-1}$ , finds and verifies a homogeneous $K$ -set using $O\!\left(2^K K\log\frac Kη\right)$ edge queries with failure probability at most $η$ . At the Ramsey scale $N=2^n$ , this yields a homogeneous set of order $\lfloor n/2\rfloor+1$ using $O(\sqrt N\log N\log(\log N/η))$ queries, improving on the $O(N)$ queries of the explicit classical recursion and giving, to our knowledge, the first sublinear worst-case algorithm for the Ramsey relation. We also derive an $Ω(N^{1/12})$ quantum lower bound by a reduction from collision finding. The algorithm runs the constructive recursion over implicit candidate sets. Each set is represented by a short conjunction of adjacency constraints and sampled using capped unknown-solution quantum search, and a scale-aware concentration schedule balances estimation accuracy against the increasing cost of sampling deeper sets. We complement the upper bound with an $Ω(N^{1-1/\sqrt2})$ randomized lower bound, transported from the random-Painter analysis of online Ramsey numbers, which holds on the uniform distribution $G(N,1/2)$ . On that distribution a greedy quantum search uses only $\widetilde O(N^{1/4})$ queries, giving a provable polynomial quantum speedup for Ramsey search on random graphs. We also give an estimation-free size-biased recursion and extend it to every fixed number of edge colours.The constructive diagonal Ramsey problem asks, given adjacency-oracle access to an $N$-vertex graph, for a clique or independent set of the order guaranteed by Ramsey's theorem. We give a bounded-error quantum algorithm that, for every $K\ge2$ and $N\ge4^{K-1}$, finds and verifies a homogeneous $K$-set using $O\!\left(2^K K\log\frac Kη\right)$ edge queries with failure probability at most $η$. At the Ramsey scale $N=2^n$, this yields a homogeneous set of order $\lfloor n/2\rfloor+1$ using $O(\sqrt N\log N\log(\log N/η))$ queries, improving on the $O(N)$ queries of the explicit classical recursion and giving, to our knowledge, the first sublinear worst-case algorithm for the Ramsey relation. We also derive an $Ω(N^{1/12})$ quantum lower bound by a reduction from collision finding. The algorithm runs the constructive recursion over implicit candidate sets. Each set is represented by a short conjunction of adjacency constraints and sampled using capped unknown-solution quantum search, and a scale-aware concentration schedule balances estimation accuracy against the increasing cost of sampling deeper sets. We complement the upper bound with an $Ω(N^{1-1/\sqrt2})$ randomized lower bound, transported from the random-Painter analysis of online Ramsey numbers, which holds on the uniform distribution $G(N,1/2)$. On that distribution a greedy quantum search uses only $\widetilde O(N^{1/4})$ queries, giving a provable polynomial quantum speedup for Ramsey search on random graphs. We also give an estimation-free size-biased recursion and extend it to every fixed number of edge colours.

quant-pharXiv:2609.05812Sep 8, 20260 citations

Quantum Circuit Design for Finding k-Cliques via Quantum Amplitude Amplification Strategies

Simone Perriello

The 𝑘-clique problem, which involves identifying complete subgraphs of size 𝑘 within a graph, is a fundamental challenge in combinatorial optimization with applications in network analysis, bioinformatics, and cryptography.As the number of nodes 𝑛 grows, classical algorithms become computationally intractable, motivating the exploration of quantum computing to address these limitations.This work introduces two quantum algorithms for solving the 𝑘-clique problem: one based on Quantum Amplitude Amplification (QAA) and another leveraging Quantum Walks (QW) over the Johnson graph 𝐽 (𝑛, 𝑘).By exploiting the regular structure of the Johnson graph, the QW approach achieves the same quadratic speedup of the QAA approach over classical algorithms, while remaining applicable to arbitrary undirected, unweighted graphs.We provide detailed quantum circuit designs for both approaches, analyzing their performance in terms of qubit count, gate count, and circuit depth under the NOT-CNOT-Toffoli + arbitrary rotations and Clifford + T gate sets.Compared to state-of-the-art quantum algorithms, our methods achieve significant improvements in scaling, particularly for dense graphs, with speedups ranging from 2 5 to 2 20 .The 𝑘-clique problem, which involves identifying complete subgraphs of size 𝑘 within a graph, is a fundamental challenge in combinatorial optimization with applications in network analysis, bioinformatics, and cryptography.As the number of nodes 𝑛 grows, classical algorithms become computationally intractable, motivating the exploration of quantum computing to address these limitations.This work introduces two quantum algorithms for solving the 𝑘-clique problem: one based on Quantum Amplitude Amplification (QAA) and another leveraging Quantum Walks (QW) over the Johnson graph 𝐽 (𝑛, 𝑘).By exploiting the regular structure of the Johnson graph, the QW approach achieves the same quadratic speedup of the QAA approach over classical algorithms, while remaining applicable to arbitrary undirected, unweighted graphs.We provide detailed quantum circuit designs for both approaches, analyzing their performance in terms of qubit count, gate count, and circuit depth under the NOT-CNOT-Toffoli + arbitrary rotations and Clifford + T gate sets.Compared to state-of-the-art quantum algorithms, our methods achieve significant improvements in scaling, particularly for dense graphs, with speedups ranging from 2 5 to 2 20 .

ACM International Conference on Computing Frontiers (CF)May 28, 20252 citations

Superlinear Quantum Query Lower Bounds for Subgraph Detection

Amin Shiraz Gilani, Xingyu Zhou

Subgraph detection asks whether an $n$ -vertex graph, accessed through queries to its adjacency matrix, contains a copy of a fixed graph $H$ . We prove the first unconditional superlinear lower bounds on the bounded-error quantum query complexity of this problem, answering a longstanding open question. A copy of $H$ is a certificate of constant size, so the adversary method with nonnegative weights cannot prove superlinear lower bounds. For every fixed $r\ge 4$ , detecting the clique $K_r$ requires $n^{λ_r-o(1)}$ queries, where $λ_4=19/18$ , the exponents $λ_r$ increase strictly with $r$ , and $λ_r\ge 2-4\sqrt{2/r}+O(1/r)$ . More generally, we prove superlinear lower bounds for detecting every fixed connected graph $H$ with chromatic number $c\ge 4$ . These bounds approach quadratic as $c$ grows: for sufficiently large $c$ , detection requires $n^{2-O(\sqrt{\log\log c/c})-o(1)}$ queries. Chromatic number alone does not characterize the quantum query complexity of subgraph detection: we show that detecting the complete bipartite graph $K_{r,r}$ requires $n^{β_r-o(1)}$ queries, where $β_{10}=181/180$ and $β_r\ge 2-O(1/\sqrt{r})$ . Our main technical result is a lower bound for finding an all-ones certificate from a known family when the input bits are sampled independently. Its proof combines Zhandry's compressed oracle [CRYPTO 2019] with conditioning on a randomly planted certificate, adapting an argument of Belovs [FOCS 2026]. Our hard instances are built from graphs containing many copies of the desired subgraph with limited overlap. For cliques, we use a construction of Gowers and Janzer [CPC 2021]; for complete bipartite graphs, we use a random construction.Subgraph detection asks whether an $n$-vertex graph, accessed through queries to its adjacency matrix, contains a copy of a fixed graph $H$. We prove the first unconditional superlinear lower bounds on the bounded-error quantum query complexity of this problem, answering a longstanding open question. A copy of $H$ is a certificate of constant size, so the adversary method with nonnegative weights cannot prove superlinear lower bounds. For every fixed $r\ge 4$, detecting the clique $K_r$ requires $n^{λ_r-o(1)}$ queries, where $λ_4=19/18$, the exponents $λ_r$ increase strictly with $r$, and $λ_r\ge 2-4\sqrt{2/r}+O(1/r)$. More generally, we prove superlinear lower bounds for detecting every fixed connected graph $H$ with chromatic number $c\ge 4$. These bounds approach quadratic as $c$ grows: for sufficiently large $c$, detection requires $n^{2-O(\sqrt{\log\log c/c})-o(1)}$ queries. Chromatic number alone does not characterize the quantum query complexity of subgraph detection: we show that detecting the complete bipartite graph $K_{r,r}$ requires $n^{β_r-o(1)}$ queries, where $β_{10}=181/180$ and $β_r\ge 2-O(1/\sqrt{r})$. Our main technical result is a lower bound for finding an all-ones certificate from a known family when the input bits are sampled independently. Its proof combines Zhandry's compressed oracle [CRYPTO 2019] with conditioning on a randomly planted certificate, adapting an argument of Belovs [FOCS 2026]. Our hard instances are built from graphs containing many copies of the desired subgraph with limited overlap. For cliques, we use a construction of Gowers and Janzer [CPC 2021]; for complete bipartite graphs, we use a random construction.

quant-pharXiv:2609.40263Oct 1, 20260 citations

A quantum algorithm for learning a graph of bounded degree

Asaf Ferber, Liam Hardiman

We are presented with a graph, $G$ , on $n$ vertices with $m$ edges whose edge set is unknown. Our goal is to learn the edges of $G$ with as few queries to an oracle as possible. When we submit a set $S$ of vertices to the oracle, it tells us whether or not $S$ induces at least one edge in $G$ . This so-called OR-query model has been well studied, with Angluin and Chen giving an upper bound on the number of queries needed of $O(m \log n)$ for a general graph $G$ with $m$ edges. When we allow ourselves to make *quantum* queries (we may query subsets in superposition), then we can achieve speedups over the best possible classical algorithms. In the case where $G$ has maximum degree $d$ and is $O(1)$ -colorable, Montanaro and Shao presented an algorithm that learns the edges of $G$ in at most $\tilde{O}(d^2m^{3/4})$ quantum queries. This gives an upper bound of $\tilde{O}(m^{3/4})$ quantum queries when $G$ is a matching or a Hamiltonian cycle, which is far away from the lower bound of $Ω(\sqrt{m})$ queries given by Ambainis and Montanaro. We improve on the work of Montanaro and Shao in the case where $G$ has bounded degree. In particular, we present a randomized algorithm that, with high probability, learns cycles and matchings in $\tilde{O}(\sqrt{m})$ quantum queries, matching the theoretical lower bound up to logarithmic factors.We are presented with a graph, $G$, on $n$ vertices with $m$ edges whose edge set is unknown. Our goal is to learn the edges of $G$ with as few queries to an oracle as possible. When we submit a set $S$ of vertices to the oracle, it tells us whether or not $S$ induces at least one edge in $G$. This so-called OR-query model has been well studied, with Angluin and Chen giving an upper bound on the number of queries needed of $O(m \log n)$ for a general graph $G$ with $m$ edges. When we allow ourselves to make *quantum* queries (we may query subsets in superposition), then we can achieve speedups over the best possible classical algorithms. In the case where $G$ has maximum degree $d$ and is $O(1)$-colorable, Montanaro and Shao presented an algorithm that learns the edges of $G$ in at most $\tilde{O}(d^2m^{3/4})$ quantum queries. This gives an upper bound of $\tilde{O}(m^{3/4})$ quantum queries when $G$ is a matching or a Hamiltonian cycle, which is far away from the lower bound of $Ω(\sqrt{m})$ queries given by Ambainis and Montanaro. We improve on the work of Montanaro and Shao in the case where $G$ has bounded degree. In particular, we present a randomized algorithm that, with high probability, learns cycles and matchings in $\tilde{O}(\sqrt{m})$ quantum queries, matching the theoretical lower bound up to logarithmic factors.

arXiv:2402.18714Feb 28, 20240 citations

Complexity of graph-state preparation by Clifford circuits

Soh Kumabe, Ryuhei Mori, Yusei Yoshimura

In this work, we study the complexity of graph-state preparation in a general model of quantum algorithms that allows measurements in the computational basis, single-qubit Clifford operations, and two-qubit Clifford operations. We define the CZ-complexity of a graph state | G ⟩ as the minimum number of two-qubit Clifford operations required to generate | G ⟩ from | 0 ⟩ ⊗ ( n + s ) for some s ≥ 0 . Equivalently, every optimal algorithm can be taken to use only controlled-Z (CZ) gates as its two-qubit Clifford operations. We then give a combinatorial characterization of graph-state transformations. Specifically, | G ⟩ can be generated from another graph state | H ⟩ by an algorithm of CZ-complexity at most t if and only if G can be obtained from H by vertex deletions, local complementations and at most t elementary edge-complementations. Here, an elementary edge-complementation toggles either a single edge, all edges between one vertex and the neighborhood of another, or all edges between the neighborhoods of two non-adjacent vertices. Using this characterization, we relate CZ-complexity to rank-width. For any graph G with n vertices and rank-width r , the CZ-complexity is O ( r n ) , and if G is connected then it is at least n + r − 2 . We also show that these bounds are close to optimal. Finally, for interval graphs and circle graphs, whose rank-width is unbounded, we present preparation algorithms with CZ-complexity O ( n ) and O ( n log ⁡ n ) , respectively.In this work, we study the complexity of graph-state preparation in a general model of quantum algorithms that allows measurements in the computational basis, single-qubit Clifford operations, and two-qubit Clifford operations. We define the CZ-complexity of a graph state | G ⟩ as the minimum number of two-qubit Clifford operations required to generate | G ⟩ from | 0 ⟩ ⊗ ( n + s ) for some s ≥ 0 . Equivalently, every optimal algorithm can be taken to use only controlled-Z (CZ) gates as its two-qubit Clifford operations. We then give a combinatorial characterization of graph-state transformations. Specifically, | G ⟩ can be generated from another graph state | H ⟩ by an algorithm of CZ-complexity at most t if and only if G can be obtained from H by vertex deletions, local complementations and at most t elementary edge-complementations. Here, an elementary edge-complementation toggles either a single edge, all edges between one vertex and the neighborhood of another, or all edges between the neighborhoods of two non-adjacent vertices. Using this characterization, we relate CZ-complexity to rank-width. For any graph G with n vertices and rank-width r , the CZ-complexity is O ( r n ) , and if G is connected then it is at least n + r − 2 . We also show that these bounds are close to optimal. Finally, for interval graphs and circle graphs, whose rank-width is unbounded, we present preparation algorithms with CZ-complexity O ( n ) and O ( n log ⁡ n ) , respectively.

arXiv:2402.05874QuantumJul 18, 20261 citation

Tight bounds for hybrid quantum-classical query algorithms

Andris Ambainis, András Gilyén, Martins Kokainis

We study hybrid quantum-classical algorithms in the query model. The computation consists of quantum subroutines that make at most $q$ oracle queries; between subroutines, all qubits are measured and discarded. We prove matching upper and lower bounds for several problems in this model: (i) (Unbiased) Phase estimation up to a precision $ε$ requires $Θ(\frac{1}{q ε^2})$ queries; (ii) (Unbiased) Amplitude estimation up to a precision $ε$ requires $Θ(\frac{p(1-p)}{q ε^2})$ queries; (iii) Search among $N$ items requires $Θ(\frac{N}{q})$ queries; (iv) Two level AND-OR tree (AND of $m$ ORs, with $n$ inputs to each OR) requires $Θ(\frac{nm}{q})$ queries. All of these bounds are optimal up to a constant factor, for all $q$ from 1, corresponding to the classical complexity, to $Q(f)$ , the unrestricted quantum query complexity of the respective problem. We also derive a hybrid lower bound for distinguishing two distributions specified by a state-preparation unitary; this bound is tight up to a logarithmic factor. Besides specific lower bounds, an important contribution is developing methods for proving lower bounds on hybrid quantum algorithms (which have been very ad-hoc up to now). The first two bounds follow from a common framework: we analyze probability distributions over measurement transcripts and bound a progress measure that captures their distinguishability. The AND-OR bound requires a more delicate argument, combining two progress measures that track the information available to the algorithm classically and in quantum form, respectively.We study hybrid quantum-classical algorithms in the query model. The computation consists of quantum subroutines that make at most $q$ oracle queries; between subroutines, all qubits are measured and discarded. We prove matching upper and lower bounds for several problems in this model: (i) (Unbiased) Phase estimation up to a precision $ε$ requires $Θ(\frac{1}{q ε^2})$ queries; (ii) (Unbiased) Amplitude estimation up to a precision $ε$ requires $Θ(\frac{p(1-p)}{q ε^2})$ queries; (iii) Search among $N$ items requires $Θ(\frac{N}{q})$ queries; (iv) Two level AND-OR tree (AND of $m$ ORs, with $n$ inputs to each OR) requires $Θ(\frac{nm}{q})$ queries. All of these bounds are optimal up to a constant factor, for all $q$ from 1, corresponding to the classical complexity, to $Q(f)$, the unrestricted quantum query complexity of the respective problem. We also derive a hybrid lower bound for distinguishing two distributions specified by a state-preparation unitary; this bound is tight up to a logarithmic factor. Besides specific lower bounds, an important contribution is developing methods for proving lower bounds on hybrid quantum algorithms (which have been very ad-hoc up to now). The first two bounds follow from a common framework: we analyze probability distributions over measurement transcripts and bound a progress measure that captures their distinguishability. The AND-OR bound requires a more delicate argument, combining two progress measures that track the information available to the algorithm classically and in quantum form, respectively.

quant-pharXiv:2610.06803Oct 6, 20260 citations

k

-clique circuits have depth quadratic in the number

n

k

-clique oracle, whose depth and width are linear in

n

, within a logarithmic factor of a depth--width lower bound. Our central result is a

k

-clique oracle in which the graph enters only through the Clifford gate that prepares a graph state, so that its non-Clifford cost is linear in

n

for every graph. We analyze this oracle exactly: on a candidate vertex set it acts as a reflection whose overlap is

-1

for cliques and, as we prove, at most

5/8

in modulus otherwise, a tight bound that tends to

1/2

as the candidate set grows. A two-qubit phase-estimation filter turns the reflection into a one-sided bounded-error phase oracle, and amplitude amplification then finds a

k

-clique with

O(\sqrt{\binom nk})

oracle calls, each of depth

O(Δ+\log n)

for maximum degree

Δ

. The guarantee holds for two or more estimation registers; exact simulations on

312

induced subgraphs of two brain networks confirm it and show that the cheaper single-register variant performs nearly as well.

The constructive diagonal Ramsey problem asks, given adjacency-oracle access to an

N

-vertex graph, for a clique or independent set of the order guaranteed by Ramsey's theorem. We give a bounded-error quantum algorithm that, for every

K\ge2

and

N\ge4^{K-1}

, finds and verifies a homogeneous

K

-set using

O\!\left(2^K K\log\frac Kη\right)

edge queries with failure probability at most

η

. At the Ramsey scale

N=2^n

, this yields a homogeneous set of order

\lfloor n/2\rfloor+1

using

O(\sqrt N\log N\log(\log N/η))

queries, improving on the

O(N)

queries of the explicit classical recursion and giving, to our knowledge, the first sublinear worst-case algorithm for the Ramsey relation. We also derive an

Ω(N^{1/12})

quantum lower bound by a reduction from collision finding. The algorithm runs the constructive recursion over implicit candidate sets. Each set is represented by a short conjunction of adjacency constraints and sampled using capped unknown-solution quantum search, and a scale-aware concentration schedule balances estimation accuracy against the increasing cost of sampling deeper sets. We complement the upper bound with an

Ω(N^{1-1/\sqrt2})

randomized lower bound, transported from the random-Painter analysis of online Ramsey numbers, which holds on the uniform distribution

G(N,1/2)

. On that distribution a greedy quantum search uses only

\widetilde O(N^{1/4})

queries, giving a provable polynomial quantum speedup for Ramsey search on random graphs. We also give an estimation-free size-biased recursion and extend it to every fixed number of edge colours.

Subgraph detection asks whether an

n

-vertex graph, accessed through queries to its adjacency matrix, contains a copy of a fixed graph

H

. We prove the first unconditional superlinear lower bounds on the bounded-error quantum query complexity of this problem, answering a longstanding open question. A copy of

H

is a certificate of constant size, so the adversary method with nonnegative weights cannot prove superlinear lower bounds. For every fixed

r\ge 4

, detecting the clique

K_r

requires

n^{λ_r-o(1)}

queries, where

λ_4=19/18

, the exponents

λ_r

increase strictly with

r

, and

λ_r\ge 2-4\sqrt{2/r}+O(1/r)

. More generally, we prove superlinear lower bounds for detecting every fixed connected graph

H

with chromatic number

c\ge 4

. These bounds approach quadratic as

c

grows: for sufficiently large

c

, detection requires

n^{2-O(\sqrt{\log\log c/c})-o(1)}

queries. Chromatic number alone does not characterize the quantum query complexity of subgraph detection: we show that detecting the complete bipartite graph

K_{r,r}

requires

n^{β_r-o(1)}

queries, where

β_{10}=181/180

and

β_r\ge 2-O(1/\sqrt{r})

. Our main technical result is a lower bound for finding an all-ones certificate from a known family when the input bits are sampled independently. Its proof combines Zhandry's compressed oracle [CRYPTO 2019] with conditioning on a randomly planted certificate, adapting an argument of Belovs [FOCS 2026]. Our hard instances are built from graphs containing many copies of the desired subgraph with limited overlap. For cliques, we use a construction of Gowers and Janzer [CPC 2021]; for complete bipartite graphs, we use a random construction.

We are presented with a graph,

G

, on

n

vertices with

m

edges whose edge set is unknown. Our goal is to learn the edges of

G

with as few queries to an oracle as possible. When we submit a set

S

of vertices to the oracle, it tells us whether or not

S

induces at least one edge in

G

. This so-called OR-query model has been well studied, with Angluin and Chen giving an upper bound on the number of queries needed of

O(m \log n)

for a general graph

G

with

m

edges. When we allow ourselves to make *quantum* queries (we may query subsets in superposition), then we can achieve speedups over the best possible classical algorithms. In the case where

G

has maximum degree

d

and is

O(1)

-colorable, Montanaro and Shao presented an algorithm that learns the edges of

G

in at most

\tilde{O}(d^2m^{3/4})

quantum queries. This gives an upper bound of

\tilde{O}(m^{3/4})

quantum queries when

G

is a matching or a Hamiltonian cycle, which is far away from the lower bound of

Ω(\sqrt{m})

queries given by Ambainis and Montanaro. We improve on the work of Montanaro and Shao in the case where

G

has bounded degree. In particular, we present a randomized algorithm that, with high probability, learns cycles and matchings in

\tilde{O}(\sqrt{m})

quantum queries, matching the theoretical lower bound up to logarithmic factors.

We study hybrid quantum-classical algorithms in the query model. The computation consists of quantum subroutines that make at most

q

oracle queries; between subroutines, all qubits are measured and discarded. We prove matching upper and lower bounds for several problems in this model: (i) (Unbiased) Phase estimation up to a precision

ε

requires

Θ(\frac{1}{q ε^2})

queries; (ii) (Unbiased) Amplitude estimation up to a precision

ε

requires

Θ(\frac{p(1-p)}{q ε^2})

queries; (iii) Search among

N

items requires

Θ(\frac{N}{q})

queries; (iv) Two level AND-OR tree (AND of

m

ORs, with

n

inputs to each OR) requires

Θ(\frac{nm}{q})

queries. All of these bounds are optimal up to a constant factor, for all

q

from 1, corresponding to the classical complexity, to

Q(f)

, the unrestricted quantum query complexity of the respective problem. We also derive a hybrid lower bound for distinguishing two distributions specified by a state-preparation unitary; this bound is tight up to a logarithmic factor. Besides specific lower bounds, an important contribution is developing methods for proving lower bounds on hybrid quantum algorithms (which have been very ad-hoc up to now). The first two bounds follow from a common framework: we analyze probability distributions over measurement transcripts and bound a progress measure that captures their distinguishability. The AND-OR bound requires a more delicate argument, combining two progress measures that track the information available to the algorithm classically and in quantum form, respectively.