dorsal/arxiv
View SchemaQuantum algorithm to distinguish Boolean functions of different weights
| Authors | Samuel L. Braunstein, Byung-Soo Choi, Subhamoy Maitra, Dibyendu Chakrabarti, Subhroshekhar Ghosh, Partha Mukhopadhyay |
|---|---|
| Categories | |
| ArXiv ID | quant-ph/0410043 |
| URL | https://arxiv.org/abs/quant-ph/0410043 |
| DOI | 10.1088/1751-8113/40/29/017 |
| Journal | J. Phys. A: Math. Theor. 40 8441 2007 |
Abstract
We exploit Grover operator of database search algorithm for weight decision algorithm. In this research, weight decision problem is to find an exact weight w from given two weights as w1 and w2 where w1+w2=1 and 0<w1<w2<1. Firstly, if a Boolean function is given and when weights are {1/4,3/4}, we can find w with only one application of Grover operator. Secondly, if we apply k many times of Grover operator, we can decide w from the set of weights {sin^2(\frac{k}{2k+1}\frac{\pi}{2}) cos^2(\frac{k}{2k+1}\frac{\pi}{2})}. Finally, by changing the last two Grover operators with two phase conditions, we can decide w from given any set of two weights. To decide w with a sure success, if the quantum algorithm requires O(k) Grover steps, then the best known classical algorithm requires \Omega(k^s) steps where s>2. Hence the quantum algorithm achieves at least quadratic speedup.
{
"annotation_id": "c5136c7c-a2eb-4416-b26d-561c526f7f23",
"date_created": "2026-03-02T18:02:10.383000Z",
"date_modified": "2026-03-02T18:02:10.383000Z",
"file_hash": "07fc2371165d7cb30a3af689b2efca41879d3588b63eec257e0efce67de48290",
"private": false,
"record": {
"abstract": "We exploit Grover operator of database search algorithm for weight decision\nalgorithm. In this research, weight decision problem is to find an exact weight\nw from given two weights as w1 and w2 where w1+w2=1 and 0\u003cw1\u003cw2\u003c1. Firstly, if\na Boolean function is given and when weights are {1/4,3/4}, we can find w with\nonly one application of Grover operator. Secondly, if we apply k many times of\nGrover operator, we can decide w from the set of weights\n{sin^2(\\frac{k}{2k+1}\\frac{\\pi}{2}) cos^2(\\frac{k}{2k+1}\\frac{\\pi}{2})}.\nFinally, by changing the last two Grover operators with two phase conditions,\nwe can decide w from given any set of two weights. To decide w with a sure\nsuccess, if the quantum algorithm requires O(k) Grover steps, then the best\nknown classical algorithm requires \\Omega(k^s) steps where s\u003e2. Hence the\nquantum algorithm achieves at least quadratic speedup.",
"arxiv_id": "quant-ph/0410043",
"authors": [
"Samuel L. Braunstein",
"Byung-Soo Choi",
"Subhamoy Maitra",
"Dibyendu Chakrabarti",
"Subhroshekhar Ghosh",
"Partha Mukhopadhyay"
],
"categories": [
"quant-ph"
],
"doi": "10.1088/1751-8113/40/29/017",
"journal_ref": "J. Phys. A: Math. Theor. 40 8441 2007",
"title": "Quantum algorithm to distinguish Boolean functions of different weights",
"url": "https://arxiv.org/abs/quant-ph/0410043"
},
"schema_id": "dorsal/arxiv",
"source": {
"execution_id": "09fae699-b13a-4417-ad45-57e4ce938d8d",
"id": "arXiv Dataset IDs",
"type": "Model",
"variant": "snapshot-2026-03-01",
"version": "0.1.0"
},
"user_id": 1000002
}