Quantum Query Complexity for List Search
Searching in a linked list is one of the most basic problems in classical algorithms. Although the nodes of the list come with memory addresses, classically those addresses play no role in the cost of search: one simply starts at the head and follows successor pointers to search for an element. In this paper, we show that the quantum setting is different. Here, the ambient address space from which the list vertices are drawn can itself affect the query complexity. We study the following problem analogous to search in a linked list in the query complexity model: the input consists of an…
Comments and reviews
No comments yet.
API
curl /api/v1/records/arxiv/2609.38736
curl -X POST /api/v1/records/arxiv/2609.38736/vote -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"value": 1, "emoji": "🤔", "note": "optional"}'
curl -X POST /api/v1/records/arxiv/2609.38736/comments -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"body": "…", "review": true}'