dorsal/arxiv
View SchemaThe Quantum Query Complexity of 0-1 Knapsack and Associated Claw Problems
| Authors | V. Arvind, Rainer Schuler |
|---|---|
| Categories | |
| ArXiv ID | quant-ph/0212048 |
| URL | https://arxiv.org/abs/quant-ph/0212048 |
Abstract
We first give an $\O(2^{n/3})$ quantum algorithm for the 0-1 Knapsack problem with $n$ variables. More generally, for 0-1 Integer Linear Programs with $n$ variables and $d$ inequalities we give an $\O(2^{n/3}n^d)$ quantum algorithm. For $d =o(n/\log n)$ this running time is bounded by $\O(2^{n(1/3+\epsilon)})$ for every $\epsilon>0$ and in particular it is better than the $\O(2^{n/2})$ upper bound for general quantum search. To investigate whether better algorithms for these NP-hard problems are possible, we formulate a \emph{symmetric} claw problem corresponding to 0-1 Knapsack and study its quantum query complexity. For the symmetric claw problem we establish a lower bound of $\O(2^{n/4})$ for its quantum query complexity. We have an $\O(2^{n/3})$ upper bound given by essentially the same quantum algorithm that works for Knapsack. Additionally, we consider CNF satisfiability of CNF formulas $F$ with no restrictions on clause size, but with the number of clauses in $F$ bounded by $cn$ for a constant $c$, where $n$ is the number of variables. We give a $2^{(1-\alpha)n/2}$ quantum algorithm for satisfiability in this case, where $\alpha$ is a constant depending on $c$.
{
"annotation_id": "0c4e39e5-b457-4dbb-a170-1804e7bbb1d0",
"date_created": "2026-03-02T18:01:56.678000Z",
"date_modified": "2026-03-02T18:01:56.678000Z",
"file_hash": "0c89f2ec749c3b6c3e1f3f2519065cb2ab48674dfaf5703123e05b56bb7573d9",
"private": false,
"record": {
"abstract": "We first give an $\\O(2^{n/3})$ quantum algorithm for the 0-1 Knapsack problem\nwith $n$ variables. More generally, for 0-1 Integer Linear Programs with $n$\nvariables and $d$ inequalities we give an $\\O(2^{n/3}n^d)$ quantum algorithm.\nFor $d =o(n/\\log n)$ this running time is bounded by $\\O(2^{n(1/3+\\epsilon)})$\nfor every $\\epsilon\u003e0$ and in particular it is better than the $\\O(2^{n/2})$\nupper bound for general quantum search. To investigate whether better\nalgorithms for these NP-hard problems are possible, we formulate a\n\\emph{symmetric} claw problem corresponding to 0-1 Knapsack and study its\nquantum query complexity. For the symmetric claw problem we establish a lower\nbound of $\\O(2^{n/4})$ for its quantum query complexity. We have an\n$\\O(2^{n/3})$ upper bound given by essentially the same quantum algorithm that\nworks for Knapsack. Additionally, we consider CNF satisfiability of CNF\nformulas $F$ with no restrictions on clause size, but with the number of\nclauses in $F$ bounded by $cn$ for a constant $c$, where $n$ is the number of\nvariables. We give a $2^{(1-\\alpha)n/2}$ quantum algorithm for satisfiability\nin this case, where $\\alpha$ is a constant depending on $c$.",
"arxiv_id": "quant-ph/0212048",
"authors": [
"V. Arvind",
"Rainer Schuler"
],
"categories": [
"quant-ph"
],
"title": "The Quantum Query Complexity of 0-1 Knapsack and Associated Claw Problems",
"url": "https://arxiv.org/abs/quant-ph/0212048"
},
"schema_id": "dorsal/arxiv",
"source": {
"execution_id": "215bdcae-8c13-4cc5-93fc-bc45c88cb056",
"id": "arXiv Dataset IDs",
"type": "Model",
"variant": "snapshot-2026-03-01",
"version": "0.1.0"
},
"user_id": 1000002
}