|
| related topics |
| {algorithm, log, probability} |
| {let, theorem, proof} |
| {key, protocol, security} |
| {phase, path, phys} |
| {qubit, qubits, gate} |
|
Quantum Algorithms for Weighing Matrices and Quadratic Residues
Wim van Dam
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.
- oai_identifier:
- oai:arXiv.org:quant-ph/0008059
- categories:
- quant-ph cs.CC math.CO
- comments:
- 18 pages, no figures, LaTeX2e, uses packages {amssymb,amsmath};
classical upper bounds added, presentation improved
- doi:
- 10.1007/s00453-002-0975-4
- arxiv_id:
- quant-ph/0008059
- journal_ref:
- Algorithmica, Volume 34, No. 4, pages 413-428 (2002)
- created:
- 2000-08-11
- updated:
- 2001-03-19
Full article ▸
|
|
| related documents |
| 9802040v2 |
| 0607148v3 |
| 0408150v2 |
| 9907020v2 |
| 0410042v1 |
| 0510185v1 |
| 0403140v2 |
| 0304131v1 |
| 0504083v2 |
| 0010034v1 |
| 0207131v1 |
| 0612089v3 |
| 0210077v1 |
| 0302022v1 |
| 0511272v1 |
| 0505007v3 |
| 0201152v1 |
| 0504067v3 |
| 0212096v1 |
| 0206089v2 |
| 0610235v2 |
| 0703231v2 |
| 0011052v2 |
| 0303175v1 |
| 0010021v1 |
|