Quantum computers can sometimes exponentially outperform classical ones, but only for problems with sufficient structure. While it is well known that query problems with full permutation symmetry can have at most polynomial quantum speedup -- even for partial functions -- it is unclear how far this condition must be relaxed to enable exponential speedup. In particular, it is natural to ask whether exponential speedup is possible for (partial) graph properties, in which the input describes a graph and the output can only depend on its isomorphism class. We show that the answer to this question depends strongly on the input model. In the adjacency matrix model, we prove that the bounded-error randomized query complexity $R$ of any graph property $\mathcal{P}$ has $R(\mathcal{P}) = O(Q(\mathcal{P})^{6})$, where $Q$ is the bounded-error quantum query complexity. This negatively resolves an open question of Montanaro and de Wolf in the adjacency matrix model. More generally, we prove $R(\mathcal{P}) = O(Q(\mathcal{P})^{3l})$ for any $l$-uniform hypergraph property $\mathcal{P}$ in the adjacency matrix model. In direct contrast, in the adjacency list model for bounded-degree graphs, we exhibit a promise problem that shows an exponential separation between the randomized and quantum query complexities.
Quantum computers can sometimes exponentially outperform classical ones, but only for problems with sufficient structure. While it is well known that query problems with full permutation symmetry can have at most polynomial quantum speedup -- even for partial functions -- it is unclear how far this condition must be relaxed to enable exponential speedup. In particular, it is natural to ask whether exponential speedup is possible for (partial) graph properties, in which the input describes a graph and the output can only depend on its isomorphism class. We show that the answer to this question depends strongly on the input model. In the adjacency matrix model, we prove that the bounded-error randomized query complexity R of any graph property P has R(P)=O(Q(P)6), where Q is the bounded-error quantum query complexity. This negatively resolves an open question of Montanaro and de Wolf in the adjacency matrix model. More generally, we prove R(P)=O(Q(P)3l) for any l-uniform hypergraph property P in the adjacency matrix model. In direct contrast, in the adjacency list model for bounded-degree graphs, we exhibit a promise problem that shows an exponential separation between the randomized and quantum query complexities.
Aaronson and Ambainis (2009) and Chailloux (2018) showed that fully symmetric (partial) functions do not admit exponential quantum query speedups. This raises a natural question: how symmetric must a function be before it cannot exhibit a large quantum speedup? In this work, we prove that hypergraph symmetries in the adjacency matrix model allow at most a polynomial separation between randomized and quantum query complexities. We also show that, remarkably, permutation groups constructed out of these symmetries are essentially the only permutation groups that prevent super-polynomial quantum speedups. We prove this by fully characterizing the primitive permutation groups that allow super-polynomial quantum speedups. In contrast, in the adjacency list model for bounded-degree graphs-where graph symmetry is manifested differently-we exhibit a property testing problem that shows an exponential quantum speedup. These results resolve open questions posed by Ambainis, Childs, and Liu (2010) and Montanaro and de Wolf (2013).
Abstract. Aaronson and Ambainis [ Theory Comput., 10 (2014), pp. 133–166] and Chailloux [ Proceedings of the 10 th Innovations in Theoretical Computer Science Conference, 2018, pp. 19:1–19:7] showed that fully symmetric (partial) functions do not admit exponential quantum query speedups. This raises a natural question: how symmetric must a function be before it cannot exhibit a large quantum speedup? In this work, we prove that hypergraph symmetries in the adjacency matrix model allow at most a polynomial separation between randomized and quantum query complexities. We also show that, remarkably, permutation groups constructed out of these symmetries are essentially the only permutation groups that prevent superpolynomial quantum speedups. We prove this by fully characterizing the primitive permutation groups that allow superpolynomial quantum speedups. In contrast, in the adjacency list model for bounded-degree graphs—where graph symmetry is manifested differently—we exhibit a property testing problem that shows an exponential quantum speedup. These results resolve open questions posed by Ambainis, Childs, and Liu [ Lecture Notes in Comput. Sci. 6845, Springer, 2011, pp. 365–376] and Montanaro and de Wolf [ Theory Comput., 7 (2016)].
The graph isomorphism problem asks whether two graphs are identical up to vertex relabeling. While the exact problem admits quasi-polynomial-time classical algorithms, many applications in molecular comparison, noisy network analysis, and pattern recognition require a flexible notion of structural similarity. We study the quantum query complexity of approximate graph isomorphism testing, where two graphs on n vertices drawn from the Erdős--Rényi distribution G(n,1/2) are considered approximately isomorphic if they can be made isomorphic by at most k edge edits.
We present a quantum algorithm based on MNRS quantum walk search over the product graph Γ(G,H) of the two input graphs. When the graphs are approximately isomorphic, the quantum walk search detects vertex pairs belonging to a dense near isomorphic matching set; candidate pairings are then reconstructed via local consistency propagation and verified via a Grover-accelerated consistency check. We prove that this approach achieves query complexity O(n3/2logn/ε), where ε parameterizes the approximation threshold. We complement this with an Ω(n2) classical lower bound for constant approximation, establishing a genuine polynomial quantum speedup in the query model.
We extend the framework to spectral similarity measures based on graph Laplacian eigenvalues, as well as weighted and attributed graphs. Small-scale simulation results on quantum simulators for graphs with up to twenty vertices demonstrate compatibility with near-term quantum devices.
In this work, we study bipartiteness and expansion testing, two canonical problems in graph property testing in the bounded-degree model through the lens of quantum query complexity. In the classical setting, it is known that Θ(N) queries are necessary and sufficient for both these testing problems (Goldreich and Ron, 1999, 2000 & 2002), where N denotes the number of vertices of the input graph. Due to their significance, (Ambainis, Childs, and Liu, 2011) initiated the study of these problems in the quantum setting and designed quantum algorithms for bipartiteness and expansion testing that perform O(N1/3) queries, showing a polynomial speedup. They also proved that Ω(N1/4) queries are necessary for expansion testing, but the possibility of an exponential quantum advantage for bipartiteness testing remained open. Despite significant effort, there has been no improvement in these results in the last decade and a half. In this work, we prove essentially tight Ω(N1/3) quantum query lower bounds for both bipartiteness and expansion testing, thereby completely characterizing the quantum query complexity of these problems up to polylogarithmic factors. While our proofs use the polynomial method similarly to Ambainis, Childs, and Liu, we use intermediate problems that we relate to the main problems via reductions, and perform a more precise analysis of the resulting polynomials, leading to the near-optimal lower bounds.
Suppose a Boolean function f is symmetric under a group action G acting on the n bits of the input. For which G does this mean f does not have an exponential quantum speedup? Is there a characterization of how rich G must be before the function f cannot have enough structure for quantum algorithms to exploit? In this work, we make several steps towards understanding the group actions G which are "quantum intolerant" in this way. We show that sufficiently transitive group actions do not allow a quantum speedup, and that a "well-shuffling" property of group actions -- which happens to be preserved by several natural transformations -- implies a lack of super-polynomial speedups for functions symmetric under the group action. Our techniques are motivated by a recent paper by Chailloux (2018), which deals with the case where G=Sn. Our main application is for graph symmetries: we show that any Boolean function f defined on the adjacency matrix of a graph (and symmetric under relabeling the vertices of the graph) has a power 6 relationship between its randomized and quantum query complexities, even if f is a partial function. In particular, this means no graph property testing problems can have super-polynomial quantum speedups, settling an open problem of Ambainis, Childs, and Liu (2011).
One of the most basic conjectures in quantum complexity theory states that every t-query quantum algorithm can be simulated on most inputs by a poly(t)-query classical algorithm. If true, this would provide broad justification for the need for structure in quantum speedups.
We settle this conjecture for parallel quantum algorithms, showing that every t-query d-round quantum algorithm can be simulated on most inputs with tO(d2) classical queries. This suggests that for unstructured problems, superpolynomial speedups would require quantum circuits of superconstant depth, and exponential speedups would further require polynomial depth. In contrast, most known speedups for structured problems are achieved by highly parallel, low-depth algorithms.
Our techniques also carry new implications for the status of BPP vs. BQP relative to a random oracle, a similarly longstanding problem.