dorsal/arxiv
View SchemaQuantum Algorithms for Weighing Matrices and Quadratic Residues
| Authors | Wim van Dam |
|---|---|
| Categories | |
| ArXiv ID | quant-ph/0008059 |
| URL | https://arxiv.org/abs/quant-ph/0008059 |
| DOI | 10.1007/s00453-002-0975-4 |
| Journal | Algorithmica, Volume 34, No. 4, pages 413-428 (2002) |
Abstract
In this article we investigate how we can employ the structure of combinatorial objects like Hadamard matrices and weighing matrices to device new quantum algorithms. We show how the properties of a weighing matrix can be used to construct a problem for which the quantum query complexity is ignificantly lower than the classical one. It is pointed out that this scheme captures both Bernstein & Vazirani's inner-product protocol, as well as Grover's search algorithm. In the second part of the article we consider Paley's construction of Hadamard matrices, which relies on the properties of quadratic characters over finite fields. We design a query problem that uses the Legendre symbol chi (which indicates if an element of a finite field F_q is a quadratic residue or not). It is shown how for a shifted Legendre function f_s(i)=chi(i+s), the unknown s in F_q can be obtained exactly with only two quantum calls to f_s. This is in sharp contrast with the observation that any classical, probabilistic procedure requires more than log(q) + log((1-e)/2) queries to solve the same problem.
{
"annotation_id": "a0a159a1-9b9d-4776-bae8-b3431f770767",
"date_created": "2026-03-02T18:01:38.621000Z",
"date_modified": "2026-03-02T18:01:38.621000Z",
"file_hash": "f5bec7f96ba4d5953305964397b21edde126cc783424d916b374877f3a1a3d8d",
"private": false,
"record": {
"abstract": "In this article we investigate how we can employ the structure of\ncombinatorial objects like Hadamard matrices and weighing matrices to device\nnew quantum algorithms. We show how the properties of a weighing matrix can be\nused to construct a problem for which the quantum query complexity is\nignificantly lower than the classical one. It is pointed out that this scheme\ncaptures both Bernstein \u0026 Vazirani\u0027s inner-product protocol, as well as\nGrover\u0027s search algorithm.\n In the second part of the article we consider Paley\u0027s construction of\nHadamard matrices, which relies on the properties of quadratic characters over\nfinite fields. We design a query problem that uses the Legendre symbol chi\n(which indicates if an element of a finite field F_q is a quadratic residue or\nnot). It is shown how for a shifted Legendre function f_s(i)=chi(i+s), the\nunknown s in F_q can be obtained exactly with only two quantum calls to f_s.\nThis is in sharp contrast with the observation that any classical,\nprobabilistic procedure requires more than log(q) + log((1-e)/2) queries to\nsolve the same problem.",
"arxiv_id": "quant-ph/0008059",
"authors": [
"Wim van Dam"
],
"categories": [
"quant-ph",
"cs.CC",
"math.CO"
],
"doi": "10.1007/s00453-002-0975-4",
"journal_ref": "Algorithmica, Volume 34, No. 4, pages 413-428 (2002)",
"title": "Quantum Algorithms for Weighing Matrices and Quadratic Residues",
"url": "https://arxiv.org/abs/quant-ph/0008059"
},
"schema_id": "dorsal/arxiv",
"source": {
"execution_id": "4ffb6509-d294-45cf-8ffc-03d959d0653b",
"id": "arXiv Dataset IDs",
"type": "Model",
"variant": "snapshot-2026-03-01",
"version": "0.1.0"
},
"user_id": 1000002
}