|
| related topics |
| {state, algorithm, problem} |
| {algorithm, log, probability} |
| {measurement, state, measurements} |
| {classical, space, random} |
| {let, theorem, proof} |
| {time, wave, function} |
| {operator, operators, space} |
| {entanglement, phys, rev} |
| {state, states, entangled} |
| {wave, scattering, interference} |
| {bell, inequality, local} |
| {qubit, qubits, gate} |
| {information, entropy, channel} |
|
Systematic Analysis of Majorization in Quantum Algorithms
Roman Orus, Jose I. Latorre, Miguel A. Martin-Delgado
abstract: Motivated by the need to uncover some underlying mathematical structure of
optimal quantum computation, we carry out a systematic analysis of a wide
variety of quantum algorithms from the majorization theory point of view. We
conclude that step-by-step majorization is found in the known instances of fast
and efficient algorithms, namely in the quantum Fourier transform, in Grover's
algorithm, in the hidden affine function problem, in searching by quantum
adiabatic evolution and in deterministic quantum walks in continuous time
solving a classically hard problem. On the other hand, the optimal quantum
algorithm for parity determination, which does not provide any computational
speed-up, does not show step-by-step majorization. Lack of both speed-up and
step-by-step majorization is also a feature of the adiabatic quantum algorithm
solving the 2-SAT ``ring of agrees'' problem. Furthermore, the quantum
algorithm for the hidden affine function problem does not make use of any
entanglement while it does obey majorization. All the above results give
support to a step-by-step Majorization Principle necessary for optimal quantum
computation.
- oai_identifier:
- oai:arXiv.org:quant-ph/0212094
- categories:
- quant-ph
- comments:
- 15 pages, 14 figures, final version
- doi:
- 10.1140/epjd/e2004-00009-3
- arxiv_id:
- quant-ph/0212094
- journal_ref:
- European Physical Journal D 29, 119-132 (2004)
- created:
- 2002-12-16
- updated:
- 2003-12-18
Full article ▸
|
|
| related documents |
| 0301023v2 |
| 0504101v1 |
| 0601116v1 |
| 9802043v1 |
| 0001106v1 |
| 0405168v2 |
| 0308060v1 |
| 0605244v3 |
| 0611140v3 |
| 0506270v2 |
| 0702007v2 |
| 0411194v2 |
| 0312083v1 |
| 0609125v1 |
| 0303070v1 |
| 0502014v2 |
| 0405157v2 |
| 0510179v1 |
| 0506244v2 |
| 0408081v5 |
| 0304054v2 |
| 0406092v1 |
| 0308016v1 |
| 0401053v1 |
| 0701096v2 |
|