arXiv:1210.1014

Improved Quantum Query Algorithms for Triangle Finding and Associativity Testing

Troy Lee, Frédéric Magniez, Miklós Sántha

Published Oct 3, 2012• 0 citations

Abstract

We show that the quantum query complexity of detecting if an $n$-vertex graph contains a triangle is $O(n^{9/7})$. This improves the previous best algorithm of Belovs making $O(n^{35/27})$ queries. For the problem of determining if an operation $\circ : S \times S \rightarrow S$ is associative, we give an algorithm making $O(|S|^{10/7})$ queries, the first improvement to the trivial $O(|S|^{3/2})$ application of Grover search. Our algorithms are designed using the learning graph framework of Belovs. We give a family of algorithms for detecting constant-sized subgraphs, which can possibly be directed and colored. These algorithms are designed in a simple high-level language; our main theorem shows how this high-level language can be compiled as a learning graph and gives the resulting complexity. The key idea to our improvements is to allow more freedom in the parameters of the database kept by the algorithm. As in our previous work, the edge slots maintained in the database are specified by a graph whose edges are the union of regular bipartite graphs, the overall structure of which mimics that of the graph of the certificate. By allowing these bipartite graphs to be unbalanced and of variable degree we obtain better algorithms.

DOI: 10.48550/arxiv.1210.1014

Related papers

Improved Quantum Query Algorithms for Triangle Finding and Associativity Testing

Troy Lee, Frédéric Magniez, Miklós Sántha

ACM-SIAM Symposium on Discrete Algorithms (SODA)Jan 6, 201333 citations

Superlinear Quantum Query Lower Bounds for Subgraph Detection

Amin Shiraz Gilani, Xingyu Zhou

quant-pharXiv:2609.40263Oct 1, 20260 citations

Improved Quantum Algorithm for Triangle Finding via Combinatorial Arguments

François Le Gall

arXiv:1407.0085Annual Symposium on Foundations of Computer ScienceOct 1, 201456 citations

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

Troy Lee, Frédéric Magniez, Miklós Sántha

arXiv:1109.5135Sep 23, 201121 citations

QUANTUM QUERY COMPLEXITY OF CONSTANT-SIZED SUBGRAPH CONTAINMENT

Elton Yechao Zhu

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 [Formula: see text], with g(H) a strictly positive function of H. This is better than Õ(n 2-2/k ) by Magniez et al. This result is obtained in the learning graph model of Belovs.

arXiv:1109.4165International Journal of Quantum InformationApr 1, 201224 citations

Extended Learning Graphs for Triangle Finding

Titouan Carette, Mathieu Laurière, Frédéric Magniez

arXiv:1609.07786Sep 25, 20161 citation

arXiv:1210.1014

Improved Quantum Query Algorithms for Triangle Finding and Associativity Testing

Troy Lee, Frédéric Magniez, Miklós Sántha

Published Oct 3, 2012• 0 citations

arXiv HTML PDF

Abstract

We show that the quantum query complexity of detecting if an

n

-vertex graph contains a triangle is

O(n^{9/7})

. This improves the previous best algorithm of Belovs making

O(n^{35/27})

queries. For the problem of determining if an operation

\circ : S \times S \rightarrow S

is associative, we give an algorithm making

O(|S|^{10/7})

queries, the first improvement to the trivial

O(|S|^{3/2})

application of Grover search. Our algorithms are designed using the learning graph framework of Belovs. We give a family of algorithms for detecting constant-sized subgraphs, which can possibly be directed and colored. These algorithms are designed in a simple high-level language; our main theorem shows how this high-level language can be compiled as a learning graph and gives the resulting complexity. The key idea to our improvements is to allow more freedom in the parameters of the database kept by the algorithm. As in our previous work, the edge slots maintained in the database are specified by a graph whose edges are the union of regular bipartite graphs, the overall structure of which mimics that of the graph of the certificate. By allowing these bipartite graphs to be unbalanced and of variable degree we obtain better algorithms.

DOI: 10.48550/arxiv.1210.1014

Related papers

Improved Quantum Query Algorithms for Triangle Finding and Associativity Testing

Troy Lee, Frédéric Magniez, Miklós Sántha

We show that the quantum query complexity of detecting if an n-vertex graph contains a triangle is O(n9/7). This improves the previous best algorithm of Belovs [2] making O(n35/27) queries. For the problem of determining if an operation o : S × S → S is associative, we give an algorithm making O(|S|10/7) queries, the first improvement to the trivial O(|S|3/2) application of Grover search. Our algorithms are designed using the learning graph framework of Belovs. We give a family of algorithms for detecting constant-sized subgraphs, which can possibly be directed and colored. These algorithms are designed in a simple high-level language; our main theorem shows how this high-level language can be compiled as a learning graph and gives the resulting complexity. The key idea to our improvements is to allow more freedom in the parameters of the database kept by the algorithm. As in our previous work [9], the edge slots maintained in the database are specified by a graph whose edges are the union of regular bipartite graphs, the overall structure of which mimics that of the graph of the certificate. By allowing these bipartite graphs to be unbalanced and of variable degree we obtain better algorithms.We show that the quantum query complexity of detecting if an n-vertex graph contains a triangle is O(n9/7). This improves the previous best algorithm of Belovs [2] making O(n35/27) queries. For the problem of determining if an operation o : S × S → S is associative, we give an algorithm making O(|S|10/7) queries, the first improvement to the trivial O(|S|3/2) application of Grover search. Our algorithms are designed using the learning graph framework of Belovs. We give a family of algorithms for detecting constant-sized subgraphs, which can possibly be directed and colored. These algorithms are designed in a simple high-level language; our main theorem shows how this high-level language can be compiled as a learning graph and gives the resulting complexity. The key idea to our improvements is to allow more freedom in the parameters of the database kept by the algorithm. As in our previous work [9], the edge slots maintained in the database are specified by a graph whose edges are the union of regular bipartite graphs, the overall structure of which mimics that of the graph of the certificate. By allowing these bipartite graphs to be unbalanced and of variable degree we obtain better algorithms.

ACM-SIAM Symposium on Discrete Algorithms (SODA)Jan 6, 201333 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

Improved Quantum Algorithm for Triangle Finding via Combinatorial Arguments

François Le Gall

In this paper we present a quantum algorithm solving the triangle finding problem in unweighted graphs with query complexity Õ(n5/4), where n denotes the number of vertices in the graph. This improves the previous upper bound O(n9/7) = O(n1.285) recently obtained by Lee, Magniez and Santha. Our result shows, for the first time, that in the quantum query complexity setting unweighted triangle finding is easier than its edge-weighted version, since for finding an edge-weighted triangle Belovs and Rosmanis proved that any quantum algorithm requires O(n9/7/ √log n) queries. Our result also illustrates some limitations of the non-adaptive learning graph approach used to obtain the previous O(n9/7) upper bound since, even over unweighted graphs, any quantum algorithm for triangle finding obtained using this approach requires v(n9/7/ √log n) queries as well. To bypass the obstacles characterized by these lower bounds, our quantum algorithm uses combinatorial ideas exploiting the graph-theoretic properties of triangle finding, which cannot be used when considering edge-weighted graphs or the non-adaptive learning graph approach.In this paper we present a quantum algorithm solving the triangle finding problem in unweighted graphs with query complexity Õ(n5/4), where n denotes the number of vertices in the graph. This improves the previous upper bound O(n9/7) = O(n1.285) recently obtained by Lee, Magniez and Santha. Our result shows, for the first time, that in the quantum query complexity setting unweighted triangle finding is easier than its edge-weighted version, since for finding an edge-weighted triangle Belovs and Rosmanis proved that any quantum algorithm requires O(n9/7/ √log n) queries. Our result also illustrates some limitations of the non-adaptive learning graph approach used to obtain the previous O(n9/7) upper bound since, even over unweighted graphs, any quantum algorithm for triangle finding obtained using this approach requires v(n9/7/ √log n) queries as well. To bypass the obstacles characterized by these lower bounds, our quantum algorithm uses combinatorial ideas exploiting the graph-theoretic properties of triangle finding, which cannot be used when considering edge-weighted graphs or the non-adaptive learning graph approach.

arXiv:1407.0085Annual Symposium on Foundations of Computer ScienceOct 1, 201456 citations

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

Troy Lee, Frédéric Magniez, Miklós Sántha

Let $H$ be a fixed $k$ -vertex graph with $m$ edges and minimum degree $d >0$ . We use the learning graph framework of Belovs to show that the bounded-error quantum query complexity of determining if an $n$ -vertex graph contains $H$ as a subgraph is $O(n^{2-2/k-t})$ , where $ t = \max{\frac{k^2- 2(m+1)}{k(k+1)(m+1)}, \frac{2k - d - 3}{k(d+1)(m-d+2)}}$. The previous best algorithm of Magniez et al. had complexity $\widetilde O(n^{2-2/k})$ .Let $H$ be a fixed $k$-vertex graph with $m$ edges and minimum degree $d >0$. We use the learning graph framework of Belovs to show that the bounded-error quantum query complexity of determining if an $n$-vertex graph contains $H$ as a subgraph is $O(n^{2-2/k-t})$, where $ t = \max{\frac{k^2- 2(m+1)}{k(k+1)(m+1)}, \frac{2k - d - 3}{k(d+1)(m-d+2)}}$. The previous best algorithm of Magniez et al. had complexity $\widetilde O(n^{2-2/k})$.

arXiv:1109.5135Sep 23, 201121 citations

QUANTUM QUERY COMPLEXITY OF CONSTANT-SIZED SUBGRAPH CONTAINMENT

Elton Yechao Zhu

arXiv:1109.4165International Journal of Quantum InformationApr 1, 201224 citations

Extended Learning Graphs for Triangle Finding

Titouan Carette, Mathieu Laurière, Frédéric Magniez

We present new quantum algorithms for Triangle Finding improving its best previously known quantum query complexities for both dense and spare instances.For dense graphs on $n$ vertices, we get a query complexity of $O(n^{5/4})$ without any of the extra logarithmic factors present in the previous algorithm of Le Gall [FOCS'14]. For sparse graphs with $m\geq n^{5/4}$ edges, we get a query complexity of $O(n^{11/12}m^{1/6}\sqrt{\log n})$ , which is better than the one obtained by Le Gall and Nakajima [ISAAC'15] when $m \geq n^{3/2}$ . We also obtain an algorithm with query complexity ${O}(n^{5/6}(m\log n)^{1/6}+d_2\sqrt{n})$ where $d_2$ is the variance of the degree distribution. Our algorithms are designed and analyzed in a new model of learning graphs that we call extended learning graphs. In addition, we present a framework in order to easily combine and analyze them. As a consequence we get much simpler algorithms and analyses than previous algorithms of Le Gall {\it et al} based on the MNRS quantum walk framework [SICOMP'11].We present new quantum algorithms for Triangle Finding improving its best previously known quantum query complexities for both dense and spare instances.For dense graphs on $n$ vertices, we get a query complexity of $O(n^{5/4})$ without any of the extra logarithmic factors present in the previous algorithm of Le Gall [FOCS'14]. For sparse graphs with $m\geq n^{5/4}$ edges, we get a query complexity of $O(n^{11/12}m^{1/6}\sqrt{\log n})$, which is better than the one obtained by Le Gall and Nakajima [ISAAC'15] when $m \geq n^{3/2}$. We also obtain an algorithm with query complexity ${O}(n^{5/6}(m\log n)^{1/6}+d_2\sqrt{n})$ where $d_2$ is the variance of the degree distribution. Our algorithms are designed and analyzed in a new model of learning graphs that we call extended learning graphs. In addition, we present a framework in order to easily combine and analyze them. As a consequence we get much simpler algorithms and analyses than previous algorithms of Le Gall {\it et al} based on the MNRS quantum walk framework [SICOMP'11].

arXiv:1609.07786Sep 25, 20161 citation

We show that the quantum query complexity of detecting if an

n

-vertex graph contains a triangle is

O(n^{9/7})

. This improves the previous best algorithm of Belovs making

O(n^{35/27})

queries. For the problem of determining if an operation

\circ : S \times S \rightarrow S

is associative, we give an algorithm making

O(|S|^{10/7})

queries, the first improvement to the trivial

O(|S|^{3/2})

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.

Let

H

be a fixed

k

-vertex graph with

m

edges and minimum degree

d >0

. We use the learning graph framework of Belovs to show that the bounded-error quantum query complexity of determining if an

n

-vertex graph contains

H

as a subgraph is

O(n^{2-2/k-t})

, where $ t = \max{\frac{k^2- 2(m+1)}{k(k+1)(m+1)}, \frac{2k - d - 3}{k(d+1)(m-d+2)}}$. The previous best algorithm of Magniez et al. had complexity

\widetilde O(n^{2-2/k})

We present new quantum algorithms for Triangle Finding improving its best previously known quantum query complexities for both dense and spare instances.For dense graphs on

n

vertices, we get a query complexity of

O(n^{5/4})

without any of the extra logarithmic factors present in the previous algorithm of Le Gall [FOCS'14]. For sparse graphs with

m\geq n^{5/4}

edges, we get a query complexity of

O(n^{11/12}m^{1/6}\sqrt{\log n})

, which is better than the one obtained by Le Gall and Nakajima [ISAAC'15] when

m \geq n^{3/2}

. We also obtain an algorithm with query complexity

{O}(n^{5/6}(m\log n)^{1/6}+d_2\sqrt{n})

where

d_2

is the variance of the degree distribution. Our algorithms are designed and analyzed in a new model of learning graphs that we call extended learning graphs. In addition, we present a framework in order to easily combine and analyze them. As a consequence we get much simpler algorithms and analyses than previous algorithms of Le Gall {\it et al} based on the MNRS quantum walk framework [SICOMP'11].