{
  "annotation_id": "01648f50-447d-48c5-9ce6-6447ea00b3bb",
  "date_created": "2026-03-02T18:02:16.981000Z",
  "date_modified": "2026-03-02T18:02:16.981000Z",
  "file_hash": "0a6a2da0aef09d278897ce3c939ebe77bc7d980321467c74b42fb34e19d75c85",
  "private": false,
  "record": {
    "abstract": "The rigidity of a matrix measures how many of its entries need to be changed\nin order to reduce its rank to some value. Good lower bounds on the rigidity of\nan explicit matrix would imply good lower bounds for arithmetic circuits as\nwell as for communication complexity. Here we reprove the best known bounds on\nthe rigidity of Hadamard matrices, due to Kashin and Razborov, using tools from\nquantum computing. Our proofs are somewhat simpler than earlier ones (at least\nfor those familiar with quantum) and give slightly better constants. More\nimportantly, they give a new approach to attack this longstanding open problem.",
    "arxiv_id": "quant-ph/0505188",
    "authors": [
      "Ronald de Wolf"
    ],
    "categories": [
      "quant-ph",
      "cs.CC"
    ],
    "title": "Lower Bounds on Matrix Rigidity via a Quantum Argument",
    "url": "https://arxiv.org/abs/quant-ph/0505188"
  },
  "schema_id": "dorsal/arxiv",
  "source": {
    "execution_id": "01da0f61-0f20-4c96-89d9-8ee8933195d5",
    "id": "arXiv Dataset IDs",
    "type": "Model",
    "variant": "snapshot-2026-03-01",
    "version": "0.1.0"
  },
  "user_id": 1000002
}