The true cost of factoring: Linking magic and number-theoretic complexity in Shor's algorithm

Alessio Paviglianiti, Matteo Seclì, Emanuele Tirrito, Vincenzo Savona

arXivarxiv/2605.05347May 6, 2026quant-phscore 0

The execution cost of quantum algorithms is typically quantified through asymptotic gate counts and qubit register sizes, yet these metrics do not directly capture which genuinely quantum resources, and in what amount, must be created and maintained for the computation to succeed. The systematic quantification of such information-theoretic requirements in quantum computing protocols remains an extremely challenging open problem, despite their direct role in establishing quantum advantage. To address this gap, we investigate the generation of non-stabilizerness (or magic), one of the key…

SourceJSON

Comments and reviews

No comments yet.

API

curl /api/v1/records/arxiv/2605.05347
curl -X POST /api/v1/records/arxiv/2605.05347/vote -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
  -d '{"value": 1, "emoji": "🤔", "note": "optional"}'
curl -X POST /api/v1/records/arxiv/2605.05347/comments -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
  -d '{"body": "…", "review": true}'