{
  "annotation_id": "e36d7ded-89d5-4134-9929-fed398f46802",
  "date_created": "2026-03-02T18:02:45.233000Z",
  "date_modified": "2026-03-02T18:02:45.233000Z",
  "file_hash": "0dca90b16ac9927771e0a2f2c0c8f9ed377d33e482e855cee5a7188410a48eb4",
  "private": false,
  "record": {
    "abstract": "We consider the problem of inserting one item into a list of N-1 ordered\nitems. We previously showed that no quantum algorithm could solve this problem\nin fewer than log N/(2 log log N) queries, for N large. We transform the\nproblem into a \"translationally invariant\" problem and restrict attention to\ninvariant algorithms. We construct the \"greedy\" invariant algorithm and show\nnumerically that it outperforms the best classical algorithm for various N. We\nalso find invariant algorithms that succeed exactly in fewer queries than is\nclassically possible, and iterating one of them shows that the insertion\nproblem can be solved in fewer than 0.53 log N quantum queries for large N\n(where log N is the classical lower bound). We don\u0027t know whether a o(log N)\nalgorithm exists.",
    "arxiv_id": "quant-ph/9901059",
    "authors": [
      "Edward Farhi",
      "Jeffrey Goldstone",
      "Sam Gutmann",
      "Michael Sipser"
    ],
    "categories": [
      "quant-ph"
    ],
    "title": "Invariant Quantum Algorithms for Insertion into an Ordered List",
    "url": "https://arxiv.org/abs/quant-ph/9901059"
  },
  "schema_id": "dorsal/arxiv",
  "source": {
    "execution_id": "e84a1118-a875-41dc-b3ad-a52dab487e68",
    "id": "arXiv Dataset IDs",
    "type": "Model",
    "variant": "snapshot-2026-03-01",
    "version": "0.1.0"
  },
  "user_id": 1000002
}