Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

arXiv:quant-ph/0309068

Quantum lower bounds for the set equality problems

Gatis Midrijānis

Published Sep 8, 2003• 1 citation
arXivHTMLPDF

Abstract

The set equality problem is to decide whether two sets $A$ and $B$ are equal or disjoint, under the promise that one of these is the case. Some other problems, like the Graph Isomorphism problem, is solvable by reduction to the set quality problem. It was an open problem to find any $w(1)$ query lower bound when sets $A$ and $B$ are given by quantum oracles with functions $a$ and $b$. We will prove $Ω(\frac{n^{1/3}}{\log^{1/3} n})$ lower bound for the set equality problem when the set of the preimages are very small for every element in $A$ and $B$.

DOI
10.48550/arxiv.quant-ph/0309068

Related papers

Quantum Lower Bounds for Tripartite Versions of the Hidden Shift and the Set Equality Problems

Aleksandrs Belovs, Ansis Rosmanis

In this paper, we study quantum query complexity of the following rather natural tripartite generalisations (in the spirit of the 3-sum problem) of the hidden shift and the set equality problems, which we call the 3-shift-sum and the 3-matching-sum problems. The 3-shift-sum problem is as follows: given a table of $3\times n$ elements, is it possible to circularly shift its rows so that the sum of the elements in each column becomes zero? It is promised that, if this is not the case, then no 3 elements in the table sum up to zero. The 3-matching-sum problem is defined similarly, but it is allowed to arbitrarily permute elements within each row. For these problems, we prove lower bounds of $Ω(n^{1/3})$ and $Ω(\sqrt n)$, respectively. The second lower bound is tight. The lower bounds are proven by a novel application of the dual learning graph framework and by using representation-theoretic tools.

arXiv:1712.10194•Leibniz international proceedings in informatics•Dec 29, 2017•2 citations

Quantum Algorithms and Lower Bounds for Independent Set and Subgraph Isomorphism Problem

Sebastian Doern

The study of the quantum query complexity for some graph problems is an interesting area in quantum computing. Only for a few graph problems there are quantum algorithms and lower bounds known. We present some new quantum query and quantum time algorithms and quantum query complexity bounds for the maximal and maximum independent set problem and the graph and subgraph isomorphism problem.

•Oct 12, 2005•1 citation

A note on the quantum collision and set equality problems

Mark Zhandry

A collision for a function $f$ is two distinct inputs $x_1\neq x_2$ such that $f$ outputs the same value on both inputs: $f(x_1)=f(x_2)$. The quantum query complexity of finding collisions has been shown~\cite{BHT1997,AS2004, Ambainis05, Kutin05} in some settings to be $\Theta(N^{1/3})$; however, these results do not apply to random functions. The issues are two-fold. First, the $\Omega(N^{1/3})$ lower bound only applies when the domain is no larger than the co-domain, which precludes many of the cryptographically interesting applications. Second, most of the results in the literature only apply to $r$-to-1 functions, which are quite different from random functions. Understanding the collision problem for random functions is of great importance to cryptography, and we seek to fill the gaps of knowledge for this problem. To that end, we prove that, as expected, a quantum query complexity of $\Theta(N^{1/3})$ holds for all interesting domain and co-domain sizes. Our proofs are simple, and combine existing techniques with several novel tricks to obtain the desired results. Using our techniques, we also give an optimal $\Omega(M^{1/3})$ lower bound for the set equality problem. This lower bound can be used to improve the relationship between classical randomized query complexity and quantum query complexity for so-called permutation-symmetric functions.

arXiv:1312.1027•Quantum Information and Computation•May 1, 2015•138 citations

Adversary lower bounds for the collision and the set equality problems

Aleksandrs Belovs, Ansis Rosmanis

We prove tight \Omega(n^{1/3}) lower bounds on the quantum query complexity of the Collision and the Set Equality problems, provided that the size of the alphabet is large enough. We do this using the negative-weight adversary method. Thus, we reprove the result by Aaronson and Shi, as well as a more recent development by Zhandry.

arXiv:1310.5185•Quantum Information and Computation•Mar 1, 2018•20 citations

A Block-Sensitivity Lower Bound for Quantum Testing Hamming Distance

Marcos Villagra

The Gap-Hamming distance problem is the promise problem of deciding if the Hamming distance $h$ between two strings of length $n$ is greater than $a$ or less than $b$, where the gap $g=|a-b|\geq 1$ and $a$ and $b$ could depend on $n$. In this short note, we give a lower bound of $Ω( \sqrt{n/g})$ on the quantum query complexity of computing the Gap-Hamming distance between two given strings of lenght $n$. The proof is a combinatorial argument based on block sensitivity and a reduction from a threshold function.

arXiv:1705.09710•May 26, 2017•0 citations

Elementary proofs of quantum lower bounds for element distinctness and k-sum

Andris Ambainis, Martins Kokainis

We give elementary proofs of the $Ω(n^{2/3})$ quantum query lower bound for element distinctness and the $Ω(n^{k/(k+1)})$ lower bound for the $k$-sum problem, for fixed $k$ and sufficiently large groups. The proofs use only basic properties of quantum states and linear algebra, analyzing the differences of algorithm states on different inputs.

quant-pharXiv:2610.32693•Oct 26, 2026•0 citations
The set equality problem is to decide whether two sets AAA and BBB are equal or disjoint, under the promise that one of these is the case. Some other problems, like the Graph Isomorphism problem, is solvable by reduction to the set quality problem. It was an open problem to find any w(1)w(1)w(1) query lower bound when sets AAA and BBB are given by quantum oracles with functions aaa and bbb. We will prove Ω(n1/3log⁡1/3n)Ω(\frac{n^{1/3}}{\log^{1/3} n})Ω(log1/3nn1/3​) lower bound for the set equality problem when the set of the preimages are very small for every element in AAA and BBB.
In this paper, we study quantum query complexity of the following rather natural tripartite generalisations (in the spirit of the 3-sum problem) of the hidden shift and the set equality problems, which we call the 3-shift-sum and the 3-matching-sum problems. The 3-shift-sum problem is as follows: given a table of 3×n3\times n3×n elements, is it possible to circularly shift its rows so that the sum of the elements in each column becomes zero? It is promised that, if this is not the case, then no 3 elements in the table sum up to zero. The 3-matching-sum problem is defined similarly, but it is allowed to arbitrarily permute elements within each row. For these problems, we prove lower bounds of Ω(n1/3)Ω(n^{1/3})Ω(n1/3) and Ω(n)Ω(\sqrt n)Ω(n​), respectively. The second lower bound is tight. The lower bounds are proven by a novel application of the dual learning graph framework and by using representation-theoretic tools.
A collision for a function fff is two distinct inputs x1≠x2x_1\neq x_2x1​=x2​ such that fff outputs the same value on both inputs: f(x1)=f(x2)f(x_1)=f(x_2)f(x1​)=f(x2​). The quantum query complexity of finding collisions has been shown~\cite{BHT1997,AS2004, Ambainis05, Kutin05} in some settings to be Θ(N1/3)\Theta(N^{1/3})Θ(N1/3); however, these results do not apply to random functions. The issues are two-fold. First, the Ω(N1/3)\Omega(N^{1/3})Ω(N1/3) lower bound only applies when the domain is no larger than the co-domain, which precludes many of the cryptographically interesting applications. Second, most of the results in the literature only apply to rrr-to-1 functions, which are quite different from random functions. Understanding the collision problem for random functions is of great importance to cryptography, and we seek to fill the gaps of knowledge for this problem. To that end, we prove that, as expected, a quantum query complexity of Θ(N1/3)\Theta(N^{1/3})Θ(N1/3) holds for all interesting domain and co-domain sizes. Our proofs are simple, and combine existing techniques with several novel tricks to obtain the desired results. Using our techniques, we also give an optimal Ω(M1/3)\Omega(M^{1/3})Ω(M1/3) lower bound for the set equality problem. This lower bound can be used to improve the relationship between classical randomized query complexity and quantum query complexity for so-called permutation-symmetric functions.
The Gap-Hamming distance problem is the promise problem of deciding if the Hamming distance hhh between two strings of length nnn is greater than aaa or less than bbb, where the gap g=∣a−b∣≥1g=|a-b|\geq 1g=∣a−b∣≥1 and aaa and bbb could depend on nnn. In this short note, we give a lower bound of Ω(n/g)Ω( \sqrt{n/g})Ω(n/g​) on the quantum query complexity of computing the Gap-Hamming distance between two given strings of lenght nnn. The proof is a combinatorial argument based on block sensitivity and a reduction from a threshold function.
We give elementary proofs of the Ω(n2/3)Ω(n^{2/3})Ω(n2/3) quantum query lower bound for element distinctness and the Ω(nk/(k+1))Ω(n^{k/(k+1)})Ω(nk/(k+1)) lower bound for the kkk-sum problem, for fixed kkk and sufficiently large groups. The proofs use only basic properties of quantum states and linear algebra, analyzing the differences of algorithm states on different inputs.