Loss of the quadratic speedup in Grover search under local and coherent noise
Source: arxiv.org/abs/2611.16398
Grover's algorithm searches an unstructured database with a number of oracle queries that grows only as the square root of its size. Noise erodes this advantage, and we ask, analytically, how quickly. When a depolarizing channel acts on the whole register after every gate layer, it commutes with the gates, and the noisy state is the noiseless one with a coherent weight that decays geometrically with depth. The Grover rotation is not slowed. Its weight decays, the best stopping point moves earlier, and the expected query cost keeps its square-root scaling only while the accumulated noise over…
Comments and reviews
No comments yet.
API
curl /api/v1/records/arxiv/2611.16398
curl -X POST /api/v1/records/arxiv/2611.16398/vote -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"value": 1, "emoji": "🤔", "note": "optional"}'
curl -X POST /api/v1/records/arxiv/2611.16398/comments -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"body": "…", "review": true}'