Windowed quantum arithmetic

2019/05/19 by Craig Gidney, Gidney, Craig · 6 citations
Computer Science · Physics and Astronomy · #FOS: Physical sciences #Quantum Computing Algorithms and Architecture #Quantum Information and Cryptography #Quantum Physics (quant-ph) #Quantum-Dot Cellular Automata #quant-ph

paper · pdf · doi:10.48550/arxiv.1905.07682

11 pages, 7 figures

arxiv created 2019/05/19 · openalex publication_date 2019/05/19 · arxiv updated 2019/05/21 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

We demonstrate a technique for optimizing quantum circuits that is analogous to classical windowing. Specifically, we show that small table lookups can allow control qubits to be iterated in groups instead of individually. We present various windowed quantum arithmetic circuits, including a windowed modular exponentiation with nested windowed modular multiplications, which have lower Toffoli counts than previous work at register sizes ranging from tens of qubits to thousands of qubits.

Citations

• Shor's algorithm with fewer (pure) qubits

Cited by

• Logarithmic-depth quantum state preparation of polynomials
• Parallel Spooky Pebbling Makes Regev Factoring More Practical
• Flexible layout of surface code computations using AutoCCZ states
• A distillation-teleportation protocol for fault-tolerant QRAM
• Resource Analysis of Low-Overhead Transversal Architectures for Reconfigurable Atom Arrays
• Network Requirements for Distributed Quantum Computation

Related

• Optimized circuits for windowed modular arithmetic with applications to quantum attacks against RSA
• Quantum schoolbook multiplication with fewer Toffoli gates
• Faster Quantum Number Factoring via Circuit Synthesis
• Efficient Quantum Modular Arithmetics for the ISQ Era
• An efficient quantum circuits optimizing scheme compared with QISKit