dorsal/arxiv
View SchemaSystematic Analysis of Majorization in Quantum Algorithms
| Authors | Roman Orus, Jose I. Latorre, Miguel A. Martin-Delgado |
|---|---|
| Categories | |
| ArXiv ID | quant-ph/0212094 |
| URL | https://arxiv.org/abs/quant-ph/0212094 |
| DOI | 10.1140/epjd/e2004-00009-3 |
| Journal | European Physical Journal D 29, 119-132 (2004) |
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.
{
"annotation_id": "da46ed44-2416-4bc6-b1c2-30f5a06f574d",
"date_created": "2026-03-02T18:01:56.632000Z",
"date_modified": "2026-03-02T18:01:56.632000Z",
"file_hash": "967ab946d96ed2ccae3a00c518d65e6da5731587db48456b4fe1e7aa017c0466",
"private": false,
"record": {
"abstract": "Motivated by the need to uncover some underlying mathematical structure of\noptimal quantum computation, we carry out a systematic analysis of a wide\nvariety of quantum algorithms from the majorization theory point of view. We\nconclude that step-by-step majorization is found in the known instances of fast\nand efficient algorithms, namely in the quantum Fourier transform, in Grover\u0027s\nalgorithm, in the hidden affine function problem, in searching by quantum\nadiabatic evolution and in deterministic quantum walks in continuous time\nsolving a classically hard problem. On the other hand, the optimal quantum\nalgorithm for parity determination, which does not provide any computational\nspeed-up, does not show step-by-step majorization. Lack of both speed-up and\nstep-by-step majorization is also a feature of the adiabatic quantum algorithm\nsolving the 2-SAT ``ring of agrees\u0027\u0027 problem. Furthermore, the quantum\nalgorithm for the hidden affine function problem does not make use of any\nentanglement while it does obey majorization. All the above results give\nsupport to a step-by-step Majorization Principle necessary for optimal quantum\ncomputation.",
"arxiv_id": "quant-ph/0212094",
"authors": [
"Roman Orus",
"Jose I. Latorre",
"Miguel A. Martin-Delgado"
],
"categories": [
"quant-ph"
],
"doi": "10.1140/epjd/e2004-00009-3",
"journal_ref": "European Physical Journal D 29, 119-132 (2004)",
"title": "Systematic Analysis of Majorization in Quantum Algorithms",
"url": "https://arxiv.org/abs/quant-ph/0212094"
},
"schema_id": "dorsal/arxiv",
"source": {
"execution_id": "9b955231-7089-445d-aa4e-e6d2a42432b6",
"id": "arXiv Dataset IDs",
"type": "Model",
"variant": "snapshot-2026-03-01",
"version": "0.1.0"
},
"user_id": 1000002
}