Reversible prime-field modular inversion
Follow the latest progress by email.
Given nonzero w modulo a prime p, how efficiently can a reversible circuit compute w⁻¹ mod p? The task includes retaining enough information to reverse Euclidean or divstep updates.
Why it matters and what counts as progress
Why it matters: Modular inversion exposes a trade-off between arithmetic gates and the qubits needed to make classical updates reversible.
What counts as progress: A reversible architecture with improved Toffoli–qubit trade-offs, with the prime size, allowed failures and uncomputation costs fixed.
How the problem developed
- 15 Oct 2026 · Architecture [1]
Andi Gu, Alek H. Kemeny, Susanne F. Yelin and Mikhail D. Lukin Introduced a reversible prime-field modular-inversion architecture in a study of circuit costs for eight quantum-computing tasks.
AI contribution
Discovering state-of-the-art quantum circuits with large language models
Gu, Kemeny, Yelin and Lukin report lower Toffoli and peak-qubit counts in seven specified circuit benchmarks, plus a new prime-field modular-inversion architecture. For fixed-point Gaussian evaluation, their stated benchmark falls from about 24,000 Toffolis and 362 qubits to 1,583 Toffolis and 139 qubits; the reported worst-case error is 9.99×10⁻⁸.
Sources
Website timeline
Publication dates and editorial changes.
LLM-discovered quantum circuits reduce Toffoli and qubit costs