dorsal/arxiv
View SchemaMaximum Speedup in Quantum Search : O(1) Running Time
| Authors | Joonwoo Bae, Younghun Kwon |
|---|---|
| Categories | |
| ArXiv ID | quant-ph/0204087 |
| URL | https://arxiv.org/abs/quant-ph/0204087 |
| Journal | Int. J. Theor. Phys. Vol. 42, Issue 9, 2069-2074 (2003) |
Abstract
Recently the continuous time algorithm based on the generalized quantum search Hamiltonian was presented. In this letter, we consider the running time of the generalized quantum search Hamiltonian. We provide the surprising result that the maximum speedup of quantum search in the generalized Hamiltonian is the O(1) running time regardless of the number of total states. It seems to violate the proof of Zalka that the quadratic speedup is optimal in quantum search. However the argurment of Giovannetti et al. that a quantum speedup comes from the interaction between subsystems(or, equivalently entanglement) (and is concerned with the Margolus and Levitin theorem) supports our result.
{
"annotation_id": "fbda8c82-df40-4edd-8194-b7ba5044ae95",
"date_created": "2026-03-02T18:01:49.441000Z",
"date_modified": "2026-03-02T18:01:49.441000Z",
"file_hash": "f9d88d9ef01cb109892b5d6a13380845cc0a2e1565aad5b32e5bac066135eb7c",
"private": false,
"record": {
"abstract": "Recently the continuous time algorithm based on the generalized quantum\nsearch Hamiltonian was presented. In this letter, we consider the running time\nof the generalized quantum search Hamiltonian. We provide the surprising result\nthat the maximum speedup of quantum search in the generalized Hamiltonian is\nthe O(1) running time regardless of the number of total states. It seems to\nviolate the proof of Zalka that the quadratic speedup is optimal in quantum\nsearch. However the argurment of Giovannetti et al. that a quantum speedup\ncomes from the interaction between subsystems(or, equivalently entanglement)\n(and is concerned with the Margolus and Levitin theorem) supports our result.",
"arxiv_id": "quant-ph/0204087",
"authors": [
"Joonwoo Bae",
"Younghun Kwon"
],
"categories": [
"quant-ph"
],
"journal_ref": "Int. J. Theor. Phys. Vol. 42, Issue 9, 2069-2074 (2003)",
"title": "Maximum Speedup in Quantum Search : O(1) Running Time",
"url": "https://arxiv.org/abs/quant-ph/0204087"
},
"schema_id": "dorsal/arxiv",
"source": {
"execution_id": "9e9095dc-c3d1-4c0e-973d-500569bf9f6a",
"id": "arXiv Dataset IDs",
"type": "Model",
"variant": "snapshot-2026-03-01",
"version": "0.1.0"
},
"user_id": 1000002
}