A Limit on the Speed of Quantum Computation for Insertion into an Ordered List

Simple item page
dc.creatorFarhi, E.
dc.creatorGoldstone, J.
dc.creatorGutmann, S.
dc.creatorSipser, M.
dc.date1998-12-18
dc.date.accessioned2026-07-07T06:15:56Z
dc.date.available2026-07-07T06:15:56Z
dc.descriptionWe consider the problem of inserting a new item into an ordered list of N-1 items. The length of an algorithm is measured by the number of comparisons it makes between the new item and items already on the list. Classically, determining the insertion point requires log N comparisons. We show that, for N large, no quantum algorithm can reduce the number of comparisons below log N/(2 loglog N).
dc.description5 pages
dc.identifierhttps://arxiv.org/abs/quant-ph/9812057
dc.identifierhttp://arxiv.org/abs/quant-ph/9812057
dc.identifier.urihttp://salesiana.dossiersoluciones.com/handle/123456789/93914
dc.subjectQuantum Physics
dc.titleA Limit on the Speed of Quantum Computation for Insertion into an Ordered List
dc.typetext

Files

Collections

arXiv