dorsal/arxiv
View SchemaQuantum lower bounds for the set equality problems
| Authors | Gatis Midrijanis |
|---|---|
| Categories | |
| ArXiv ID | quant-ph/0309068 |
| URL | https://arxiv.org/abs/quant-ph/0309068 |
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 $\Omega(\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$.
{
"annotation_id": "0243f110-5024-4d55-a119-88069589d028",
"date_created": "2026-03-02T18:02:03.318000Z",
"date_modified": "2026-03-02T18:02:03.318000Z",
"file_hash": "991c478e583876e86e8e36e9c4b56bff03b58c51f0f37055a17b89c3a516f56a",
"private": false,
"record": {
"abstract": "The set equality problem is to decide whether two sets $A$ and $B$ are equal\nor disjoint, under the promise that one of these is the case. Some other\nproblems, like the Graph Isomorphism problem, is solvable by reduction to the\nset quality problem. It was an open problem to find any $w(1)$ query lower\nbound when sets $A$ and $B$ are given by quantum oracles with functions $a$ and\n$b$.\n We will prove $\\Omega(\\frac{n^{1/3}}{\\log^{1/3} n})$ lower bound for the set\nequality problem when the set of the preimages are very small for every element\nin $A$ and $B$.",
"arxiv_id": "quant-ph/0309068",
"authors": [
"Gatis Midrijanis"
],
"categories": [
"quant-ph"
],
"title": "Quantum lower bounds for the set equality problems",
"url": "https://arxiv.org/abs/quant-ph/0309068"
},
"schema_id": "dorsal/arxiv",
"source": {
"execution_id": "8341c1fb-e8bb-464e-b6fe-ae8e02f110fa",
"id": "arXiv Dataset IDs",
"type": "Model",
"variant": "snapshot-2026-03-01",
"version": "0.1.0"
},
"user_id": 1000002
}