Presentation
Optimizing windowed arithmetic for quantum attacks against RSA2048
DescriptionWindowed arithmetic [Gid19] uses precomputed lookup tables (LUTs) to reduce quantum-classical multiplication costs, achieving state-of-the-art resource estimates for integer factoring [GE21]. We introduce four optimizations to enhance this approach, focusing on efficient uncomputation-of-lookups (unlookups), minimizing lookups, and reducing table entries. These improvements reduce unlookup costs by ~50% for factoring, yielding a 16% runtime reduction with only a 12% qubit increase for RSA-2048. Our techniques provide broad utility in improving depth, runtime, and gate costs of quantum LUTs and windowed arithmetic, enabling significant performance gains across diverse quantum algorithms.
Event Type
Research Manuscript
TimeTuesday, June 242:30pm - 2:45pm PDT
Location3003, Level 3