-sum problem derived recently in arXiv:1206.6528. Finally, we use these results to show that the learning graph for the triangle problem from arXiv:1210.1014 is almost optimal in these settings. This also gives a quantum query lower bound for the triangle-sum problem.

DOI: 10.48550/arxiv.1210.3279

Related papers

On the Power of Non-adaptive Learning Graphs

Aleksandrs Belovs, Ansis Rosmanis

We introduce a notion of the quantum query complexity of a certificate structure. This is a formalisation of a well-known observation that many quantum query algorithms only require the knowledge of the disposition of possible certificates in the input string, not the precise values therein. Next, we derive a dual formulation of the complexity of a non-adaptive learning graph, and use it to show that non-adaptive learning graphs are tight for all certificate structures. By this, we mean that there exists a function possessing the certificate structure and such that a learning graph gives an optimal quantum query algorithm for it. For a special case of certificate structures generated by certificates of bounded size, we construct a relatively general class of functions having this property. The construction is based on orthogonal arrays, and generalizes the quantum query lower bound for the k-sum problem derived recently. Finally, we use these results to show that the best known learning graph for the triangle problem is almost optimal in these settings. This also gives a quantum query lower bound for the triangle-sum problem.We introduce a notion of the quantum query complexity of a certificate structure. This is a formalisation of a well-known observation that many quantum query algorithms only require the knowledge of the disposition of possible certificates in the input string, not the precise values therein. Next, we derive a dual formulation of the complexity of a non-adaptive learning graph, and use it to show that non-adaptive learning graphs are tight for all certificate structures. By this, we mean that there exists a function possessing the certificate structure and such that a learning graph gives an optimal quantum query algorithm for it. For a special case of certificate structures generated by certificates of bounded size, we construct a relatively general class of functions having this property. The construction is based on orthogonal arrays, and generalizes the quantum query lower bound for the k-sum problem derived recently. Finally, we use these results to show that the best known learning graph for the triangle problem is almost optimal in these settings. This also gives a quantum query lower bound for the triangle-sum problem.

IEEE Conference on Computational Complexity (CCC)Jun 1, 201319 citations

Lower Bounds on Quantum Query and Learning Graph Complexities

Ansis Rosmanis

I hereby declare that I am the sole author of this thesis. This is a true copy of the thesis, including any required final revisions, as accepted by my examiners. I understand that my thesis may be made electronically available to the public. ii In this thesis we study the power of quantum query algorithms and learning graphs; the latter essentially being very specialized quantum query algorithms themselves. We almost exclusively focus on proving lower bounds for these computational models. First, we study lower bounds on learning graph complexity. We consider two types of learning graphs: adaptive and, more restricted, non-adaptive learning graphs. We express both adaptive and non-adaptive learning graph complexities of Boolean-valued functions (i.e., decision problems) as semidefinite minimization problems, and derive their dual problems. For various functions, we construct feasible solutions to these dual problems, thereby obtaining lower bounds on the learn-ing graph complexity of the functions. Most notably, we prove an almost optimal Ω(n9/7/ log n)I hereby declare that I am the sole author of this thesis. This is a true copy of the thesis, including any required final revisions, as accepted by my examiners. I understand that my thesis may be made electronically available to the public. ii In this thesis we study the power of quantum query algorithms and learning graphs; the latter essentially being very specialized quantum query algorithms themselves. We almost exclusively focus on proving lower bounds for these computational models. First, we study lower bounds on learning graph complexity. We consider two types of learning graphs: adaptive and, more restricted, non-adaptive learning graphs. We express both adaptive and non-adaptive learning graph complexities of Boolean-valued functions (i.e., decision problems) as semidefinite minimization problems, and derive their dual problems. For various functions, we construct feasible solutions to these dual problems, thereby obtaining lower bounds on the learn-ing graph complexity of the functions. Most notably, we prove an almost optimal Ω(n9/7/ log n)

Jul 22, 20142 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

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

Applications of the Adversary Method in Quantum Query Algorithms

Aleksandrs Belovs

In the thesis, we use a recently developed tight characterisation of quantum query complexity, the adversary bound, to develop new quantum algorithms and lower bounds. Our results are as follows: * We develop a new technique for the construction of quantum algorithms: learning graphs. * We use learning graphs to improve quantum query complexity of the triangle detection and the $k$ -distinctness problems. * We prove tight lower bounds for the $k$ -sum and the triangle sum problems. * We construct quantum algorithms for some subgraph-finding problems that are optimal in terms of query, time and space complexities. * We develop a generalisation of quantum walks that connects electrical properties of a graph and its quantum hitting time. We use it to construct a time-efficient quantum algorithm for 3-distinctness.In the thesis, we use a recently developed tight characterisation of quantum query complexity, the adversary bound, to develop new quantum algorithms and lower bounds. Our results are as follows: * We develop a new technique for the construction of quantum algorithms: learning graphs. * We use learning graphs to improve quantum query complexity of the triangle detection and the $k$-distinctness problems. * We prove tight lower bounds for the $k$-sum and the triangle sum problems. * We construct quantum algorithms for some subgraph-finding problems that are optimal in terms of query, time and space complexities. * We develop a generalisation of quantum walks that connects electrical properties of a graph and its quantum hitting time. We use it to construct a time-efficient quantum algorithm for 3-distinctness.

arXiv:1402.3858Feb 16, 201410 citations

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

Aleksandrs Belovs, Troy Lee

It is known that the dual of the general adversary bound can be used to build quantum query algorithms with optimal complexity. Despite this result, not many quantum algorithms have been designed this way. This paper shows another example of such algorithm. We use the learning graph technique from arXiv:1105.4024 to give a quantum algorithm for $k$ -distinctness problem that runs in $o(n^{3/4})$ queries, for a fixed $k$ , given some prior knowledge on the structure of the input. The best known quantum algorithm for the unconditional problem uses $O(n^{k/(k+1)})$ queries.It is known that the dual of the general adversary bound can be used to build quantum query algorithms with optimal complexity. Despite this result, not many quantum algorithms have been designed this way. This paper shows another example of such algorithm. We use the learning graph technique from arXiv:1105.4024 to give a quantum algorithm for $k$-distinctness problem that runs in $o(n^{3/4})$ queries, for a fixed $k$, given some prior knowledge on the structure of the input. The best known quantum algorithm for the unconditional problem uses $O(n^{k/(k+1)})$ queries.

arXiv:1108.3022Aug 15, 201125 citations

k

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.

k

-distinctness problems. * We prove tight lower bounds for the

k

-sum and the triangle sum problems. * We construct quantum algorithms for some subgraph-finding problems that are optimal in terms of query, time and space complexities. * We develop a generalisation of quantum walks that connects electrical properties of a graph and its quantum hitting time. We use it to construct a time-efficient quantum algorithm for 3-distinctness.

k

-distinctness problem that runs in

o(n^{3/4})

queries, for a fixed

k

, given some prior knowledge on the structure of the input. The best known quantum algorithm for the unconditional problem uses

O(n^{k/(k+1)})

queries.