dorsal/arxiv
View SchemaHigher order perturbation theory for decoherence in Grover's algorithm
| Authors | Hiroo Azuma |
|---|---|
| Categories | |
| ArXiv ID | quant-ph/0504033 |
| URL | https://arxiv.org/abs/quant-ph/0504033 |
| DOI | 10.1103/PhysRevA.72.042305 10.1103/PhysRevA.72.049902 |
| Journal | Phys. Rev. A 72, 042305 (2005); Phys. Rev. A 72, 049902(E) (2005) |
Abstract
In this paper, we study decoherence in Grover's quantum search algorithm using a perturbative method. We assume that each two-state system (qubit) that belongs to a register suffers a phase flip error (\sigma_{z} error) with probability p independently at every step in the algorithm, where $0\leq p\leq 1$. Considering an n-qubit density operator to which Grover's iterative operation is applied M times, we expand it in powers of 2Mnp and derive its matrix element order by order under the large-n limit. [In this large-n limit, we assume p is small enough, so that 2Mnp can take any real positive value or zero. We regard $x\equiv 2Mnp(\geq 0)$ as a perturbative parameter.] We obtain recurrence relations between terms in the perturbative expansion. By these relations, we compute higher orders of the perturbation efficiently, so that we extend the range of the perturbative parameter that provides a reliable analysis. Calculating the matrix element numerically by this method, we derive the maximum value of the perturbative parameter x at which the algorithm finds a correct item with a given threshold of probability P_{th} or more. (We refer to this maximum value of x as x_{c}, a critical point of x.) We obtain a curve of x_{c} as a function of P_{th} by repeating this numerical calculation for many points of P_{th} and find the following facts: a tangent of the obtained curve at P_{th}=1 is given by x=(8/5)(1-P_{th}), and we have x_{c}>-(8/5)\log_{e}P_{th} near P_{th}=0.
{
"annotation_id": "6ad6de5f-ef44-4f4e-90dd-338fd0b1dc15",
"date_created": "2026-03-02T18:02:16.605000Z",
"date_modified": "2026-03-02T18:02:16.605000Z",
"file_hash": "9c34e4ecb3ab8769edd268b9f42d4eee1ff6cfaed16e5e18a37649ab839f4dc6",
"private": false,
"record": {
"abstract": "In this paper, we study decoherence in Grover\u0027s quantum search algorithm\nusing a perturbative method. We assume that each two-state system (qubit) that\nbelongs to a register suffers a phase flip error (\\sigma_{z} error) with\nprobability p independently at every step in the algorithm, where $0\\leq p\\leq\n1$. Considering an n-qubit density operator to which Grover\u0027s iterative\noperation is applied M times, we expand it in powers of 2Mnp and derive its\nmatrix element order by order under the large-n limit. [In this large-n limit,\nwe assume p is small enough, so that 2Mnp can take any real positive value or\nzero. We regard $x\\equiv 2Mnp(\\geq 0)$ as a perturbative parameter.] We obtain\nrecurrence relations between terms in the perturbative expansion. By these\nrelations, we compute higher orders of the perturbation efficiently, so that we\nextend the range of the perturbative parameter that provides a reliable\nanalysis. Calculating the matrix element numerically by this method, we derive\nthe maximum value of the perturbative parameter x at which the algorithm finds\na correct item with a given threshold of probability P_{th} or more. (We refer\nto this maximum value of x as x_{c}, a critical point of x.) We obtain a curve\nof x_{c} as a function of P_{th} by repeating this numerical calculation for\nmany points of P_{th} and find the following facts: a tangent of the obtained\ncurve at P_{th}=1 is given by x=(8/5)(1-P_{th}), and we have\nx_{c}\u003e-(8/5)\\log_{e}P_{th} near P_{th}=0.",
"arxiv_id": "quant-ph/0504033",
"authors": [
"Hiroo Azuma"
],
"categories": [
"quant-ph"
],
"doi": "10.1103/PhysRevA.72.042305 10.1103/PhysRevA.72.049902",
"journal_ref": "Phys. Rev. A 72, 042305 (2005); Phys. Rev. A 72, 049902(E) (2005)",
"title": "Higher order perturbation theory for decoherence in Grover\u0027s algorithm",
"url": "https://arxiv.org/abs/quant-ph/0504033"
},
"schema_id": "dorsal/arxiv",
"source": {
"execution_id": "1caaa41a-48fe-4c71-8837-fc9b5b7427e2",
"id": "arXiv Dataset IDs",
"type": "Model",
"variant": "snapshot-2026-03-01",
"version": "0.1.0"
},
"user_id": 1000002
}